akhauriyash/Code-Regression huggingface dataset:
"""

https://atcoder.jp/contests/agc026/tasks/agc026_d

10101100011
01010011100

→1列目を決めたとする
→2列目の置き方は、左端を決めればすべて決まる
偶数列目を反転してみる？

10 → 11
01    00

10 → 11
10    11

すなわち、偶数列目が反転して表示されるとすると

全て01を入れ替える or 全てそのまま　しか許されない
→すべてそのままが可能なのは全て0 or 1のときのみ

dp[i][0][X] = i列目の下からX個まですべて0の時の通り数
dp[i][1][X] = i列目の下からX個まですべて1の時の通り数
→答えは dp[i][0][0]

if h[i-1] >= h[i]:
    dp[i][0][X] = dp[i-1][1][X] + dp[i-1][0][h[i]]
    dp[i][1][X] = dp[i-1][0][X] + dp[i-1][1][h[i]]
else:
    if X <= h[i-1]:
        dp[i][0][X] = (dp[i-1][1][X] + dp[i-1][0][h[i-1]]) * pow(2,h[i]-h[i-1],mod)
        dp[i][1][X] = (dp[i-1][0][X] + dp[i-1][1][h[i-1]]) * pow(2,h[i]-h[i-1],mod)
    else:
        dp[i][0][X] = (dp[i-1][1][h[i-1]] + dp[i-1][0][h[i-1]]) * pow(2,h[i]-X,mod)
        dp[i][1][X] = (dp[i-1][0][h[i-1]] + dp[i-1][1][h[i-1]]) * pow(2,h[i]-X,mod)

"""

from sys import stdin

N = int(stdin.readline())
h = list(map(int,stdin.readline().split()))
mod = 10**9+7

dp = [ [{},{}] for i in range(N) ]
numlis = set()
numlis.add(1)
for i in h:
    numlis.add(i)
for i in numlis:
    if i <= h[0]:
        dp[0][0][i] = pow(2,h[0]-i,mod)
        dp[0][1][i] = pow(2,h[0]-i,mod)

for i in range(1,N):

    for X in numlis:
        if X > h[i]:
            continue

        if h[i-1] >= h[i]:
            dp[i][0][X] = (dp[i-1][1][X] + dp[i-1][0][h[i]]) % mod
            dp[i][1][X] = (dp[i-1][0][X] + dp[i-1][1][h[i]]) % mod
        else:
            if X <= h[i-1]:
                dp[i][0][X] = (dp[i-1][1][X] + dp[i-1][0][h[i-1]]) * pow(2,h[i]-h[i-1],mod) % mod
                dp[i][1][X] = (dp[i-1][0][X] + dp[i-1][1][h[i-1]]) * pow(2,h[i]-h[i-1],mod) % mod
            else:
                dp[i][0][X] = (dp[i-1][1][h[i-1]] + dp[i-1][0][h[i-1]]) * pow(2,h[i]-X,mod) % mod
                dp[i][1][X] = (dp[i-1][0][h[i-1]] + dp[i-1][1][h[i-1]]) * pow(2,h[i]-X,mod) % mod

print ((dp[N-1][0][1] + dp[N-1][1][1]) % mod)


Measured memory_bytes: 91040
#include <algorithm>
#include <cstdio>
#include <vector>

const int N = 100000;

int n, m, a[N], result;
std::vector<int> children[N];

int dfs(int u)
{
    int dep = 0;
    for (auto v : children[u]) {
        auto ret = dfs(v);
        if (u && ret == m - 1) {
            result ++;
        } else {
            dep = std::max(dep, ret + 1);
        }
    }
    return dep;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++ i) {
        scanf("%d", a + i);
        if (i) {
            children[-- a[i]].push_back(i);
        }
    }
    result = a[0] != 1;
    dfs(0);
    printf("%d\n", result);
}


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

typedef long long ll;

int max(int a, int b){
  if(a > b) return a;
  else return b;
}
int min(int a, int b){
  if(a < b) return a;
  else return b;
}

int sort(const void *a ,const void *b){
  return *(int*)a - *(int*)b;
}

int main(){

  int N,T;
  scanf("%d%d",&N,&T);

  int c,t;
  int c_min = 99999999;
  for(int i = 0; i < N; ++i){
    scanf("%d %d",&c,&t);
    if(c < c_min && t <= T){
      c_min = c;
    }
  }

  if(c_min == 99999999){
    printf("TLE");
  }else{
    printf("%d",c_min);
  }

  return 0;
}


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


using LL = long long int;
using uLL = unsigned long long int;
using uint = unsigned int;
using ld = long double;

const int N = 100107;
const int INF = 10000007;

int dp[N], h[N];

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> h[i];
    }
    for(int i = n+1; i <= n+k; i++){
        dp[i] = INF;
    }
    for(int i = n-1; i > 0; i--){
        int res = abs(h[i+1]-h[i])+dp[i+1];
        for(int j = 2; j <= k; j++){
            res = min(res, abs(h[i+j]-h[i])+dp[i+j]);
        }
        dp[i] = res;
    }
    cout << dp[1] << '\n';
    
    
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	ll n,m;
	cin>>n>>m;
	ll r=1,st=1;
	if(n%2==1){
		ll en=n;
		rep(i,m){
			cout<<st<<' '<<en<<endl;
			st++;
			en--;
		}
		return 0;
	}
	vector<bool> used(n,false);
	ll en=n;
	used[n/2]=true;
	rep(i,m){
		while(used[en-st] || used[n-(en-st)]){
			en--;
		}
		cout<<st<<' '<<en<<endl;
		used[en-st]=used[n-(en-st)]=true;
		st++;
		en--;
	}
}

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

int main() {
  int n; cin >> n;
  int F[50];
  F[0] = F[1] = 1;
  for ( int i = 2; i <= n; i++ ) F[i] = F[i - 1] + F[i - 2];

  cout << F[n] << endl;

  return 0;
}


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

int main(){
    int n, i, a, mx = -1, mn = 2000000000;
    cin >> n;
    for(i=0; i<n; i++){
        cin >> a;
        mx = max(mx, a);
        mn = min(mn, a);
    }
    cout << mx - mn;
    return 0;
}

Measured memory_bytes: 256
A = int(input())
B = int(input())
C = int(input())
X = int(input())
cnt = 0

workX = X

for i in range(A + 1):
    if workX > 500 * i:
        workX -= 500 * i
    elif workX == 500 * i:
        cnt += 1
        continue
    else:
        break

    for j in range(B + 1):
        if workX > 100 * j:
            workX -= 100 * j
        elif workX == 100 * j:
            cnt += 1
            break
        else:
            break

        if workX % 50 == 0 and workX <= 50 * C:
            cnt += 1
            workX += 100 * j
            continue
        else:
            workX += 100 * j

    workX = X


print(cnt)

Measured memory_bytes: 3064
def calc(N, Y):
    for x in reversed(range(N + 1)):
        if x* 10000 > Y: continue 
        for y in reversed(range(N + 1 - x)):
            z= N -  x- y
            s = z* 1000 + y* 5000 + x* 10000
            if  s == Y:
                return x, y, z
    return -1, -1, -1

_N, _Y = tuple(map(int, input().split()))
print(*calc(_N, _Y))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, K;
  int point = 1;
  
  cin >> N >> K;
  
  for (int i = 0; i < N; i++) {
    if (point*2 <= point + K) point *= 2;
    else point += K;
  }
  
  cout << point << endl;
}

Measured memory_bytes: 256
import math
atan2 = math.atan2
pi = math.pi

A, B, X = map(float, input().split())

# border
halfAB = A * A * B / 2

if X >= halfAB:
    X = A*A*B - X
    t = X*2 / A / A
    # print(t)
    resRad = atan2(t, A)
else:
    t = X*2 / A / B
    # print(t)
    resRad = atan2(B, t)

print(resRad * 180.0 / pi)


Measured memory_bytes: 3060
let (n, d) = Scanf.scanf " %d %d" (fun x y -> (x, y))
let arr = List.init n (fun _ -> Scanf.scanf " %d %d" (fun x y -> (x, y)))

let () =
  let d = float (d * d) in
  arr
  |> List.filter (fun (x, y) ->
         (float x) ** 2. +. (float y) ** 2. <= d
       )
  |> List.length
  |> Printf.printf "%d\n"


Measured memory_bytes: 28156
if __name__ == '__main__':
    X = int(input())

    if X == 1:
        print(1)
    else:
        res = 0
        for i in range(2, X):
            p = 2
            while True:
                temp = i ** p
                if temp <= X:
                    if res < temp:
                        res = temp
                    else:
                        p += 1
                else:
                    break
        print(res)

Measured memory_bytes: 3060
#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
    ll a,b;
    char c;
    cin>>a>>c>>b;
    if(c=='-') printf("%lld",a-b);
    if(c=='+') printf("%lld",a+b);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
void minusone(int K, int N, vector<int>& x)
{
    if (x.size() == N) {
        if (x.back() == 1) x.pop_back();
        else x.back()--;
    } else {
        if (x.back() == 1) x.pop_back();
        else {
            x.back()--;
            for (int i = 0, cnt = N-x.size(); i < cnt; i++) x.push_back(K);
        }
    }
}
int main()
{
    int K, N; cin >> K >> N;
    vector<int> ans;
    if (K % 2 == 0) {
        ans.push_back(K/2);
        for (int i = 0; i < N-1; i++) ans.push_back(K);
    } else {
        for (int i = 0; i < N; i++) ans.push_back(K/2+1);
        for (int i = 0; i < N/2; i++) minusone(K, N, ans);
    }
    for (auto a : ans) cout << a << ' ';
    cout << '\n';
    return 0;
}


Measured memory_bytes: 3568
import sys
s = input()
k = int(input())
w = s * 2

s = list(s)
w = list(w)

same = 0
for i in s:
    if i == s[0]:
        same += 1
if same == len(s):
    ans_s = (len(s)*k) // 2
    print(ans_s)
    sys.exit()

ans_s = 0
ans_w = 0
ans_t = 0
for i in range(0, len(s)-1):
    if s[i] == s[i+1]:
        ans_s += 1
        s[i+1] = "0"

for i in range(0, len(w)-1):
    if w[i] == w[i+1]:
        ans_w += 1
        w[i+1] = "0"

if len(s) == 1:
    ans_s = k // 2
elif (ans_s*2) == ans_w:
    ans_s *= k
else:
    ans_s = ans_s*k + k - 1

print(ans_s)

Measured memory_bytes: 3064
#[allow(unused_macros)]
macro_rules! scan {
    () => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().to_string()
        }
    };
    (;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().split_whitespace().map(|s| s.to_string()).collect::<Vec<String>>()
        }
    };
    (;;$n:expr) => {
        {
            (0..$n).map(|_| scan!()).collect::<Vec<_>>()
        }
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty;;$n:expr) => {
        (0..$n).map(|_| scan!($t;;)).collect::<Vec<_>>()
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    scan!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    scan!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn main() {
    let (n, m) = scan!(usize, usize);
    let mut ws = vec![];
    for _ in 0..m {
        let vs = scan!(usize;;);
        ws.push(vs[1..].to_vec());
    }

    let ps = scan!(usize;;);
    let mut ans = 0;
    for i in 0..1 << n {
        let mut on = true;
        for (k, w) in ws.iter().enumerate() {
            let mut num = 0;
            for j in 0..n {
                if i & (1 << j) != 0 {
                    if w.iter().any(|&x| x == j + 1) {
                        num += 1;
                    }
                }
            }
            if ps[k] != num % 2 {
                on = false
            }
        }
        if on {
            ans += 1;
        }
    }

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


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

// #undef DEBUG
// #define DEBUG
/// {{{ DEBUG --- ///
#ifdef DEBUG
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << "{"; for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? ", " : ""); o << "}"; return o; }
#ifdef USE_COUT
#define dump(...) (cout<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<make_tuple(__VA_ARGS__)<<"\n")
#else
#define dump(...) (cerr<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<make_tuple(__VA_ARGS__)<<"\n")
#endif
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream &o, tuple<T...> const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; }
template<class T, class U> ostream & operator<<(ostream &o, pair<T, U> const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; }
#else
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? " " : ""); return o; }
#define dump(...) (0)
#endif
/// }}}--- ///


int h, w, n;
const int N = 1e5;
vector<ll> x(N), y(N);
ll a[N];
ll r[N], c[N];
vector<pair<int, ll>> xg[N], yg[N];
int sol() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> h >> w >> n;
  for(int i = 0; i < n; i++) {
    cin >> r[i] >> c[i] >> a[i];
    r[i]--; c[i]--;
    yg[r[i]].emplace_back(c[i], a[i]);
    xg[c[i]].emplace_back(r[i], a[i]);
  }
  vector<vector<int>> used(2, vector<int>(N));
  for(int i = 0; i < w; i++) if(!used[1][i]) {
    queue<pair<int, int>> q;
    q.emplace(i, 1);
    used[1][i] = 1;
    ll mi[2] = {(ll) 1e18, (ll) 1e18};
    while(q.size()) {
      int i, xx; tie(i, xx) = q.front(); q.pop();
      vector<ll> &v = xx ? x : y;
      vector<ll> &ov = !xx ? x : y;
      auto* g = xx ? xg : yg;
      mi[xx] = min(mi[xx], v[i]);
      for(auto to : g[i]) if(!used[!xx][to.first]) {
        q.emplace(to.first, !xx);
        ov[to.first] = - v[i] + to.second;
        used[!xx][to.first] = 1;
      }
    }
    if(mi[0] + mi[1] < 0) return 0;
  }
  for(int i = 0; i < n; i++) {
    if(y[r[i]] + x[c[i]] != a[i]) return 0;
  }
  return 1;
}

int main() {
  cout << (sol() ? "Yes" : "No") << endl;
}



Measured memory_bytes: 16256
import Foundation

#if swift(>=4.0)
extension String {
    func split(by separator: String) -> [String] {
        return self.components(separatedBy: separator)
    }
    func toArray() -> [String] {
        return self.map{String($0)}
    }
}
#else
extension String {
    func split(by separator: String) -> [String] {
        return self.componentsSeparatedByString(separator)
    }
    var count: Int {
        return self.characters.count
    }
    func toArray() -> [String] {
        return self.characters.map{String($0)}
    }
    func uppercased() -> String {
        return self.uppercaseString
    }
    func lowercased() -> String {
        return self.lowercaseString
    }
}
extension Array where Element: Comparable {
    func max() -> Element {
        return self.maxElement()!
    }
    func min() -> Element {
        return self.minElement()!
    }
    func sorted() -> Array {
        return self.sort()
    }
    func reversed() -> Array {
        return self.reverse()
    }
    mutating func sort() {
        self.sortInPlace()
    }
}
extension Array {
    init(repeating: Element, count: Int) {
        self.init(count: count, repeatedValue: repeating)
    }
}
func stride<T: Strideable>(from start: T, to end: T, by stride: T.Stride) -> StrideTo<T> {
    return start.stride(to: end, by: stride)
}
#endif
func readInt() -> Int? {
    return Int(readLine()!)
}
func readStringSplit(by separator: String) -> [String] {
    return readLine()!.split(by: separator)
}
func readIntSplit(by separator: String) -> [Int] {
    return readLine()!.split(by: separator).map{Int($0)!}
}

/*************** テストスペース ***************/



/*************** メインプログラム ***************/

let _ = readLine()!
let arr = readIntSplit(by: " ")
print(arr.max()-arr.min())


Measured memory_bytes: 7908
#include<bits/stdc++.h>
using namespace std;
int main(){long long n;
cin>>n;
long long a[n+1]={0},b[n+1],i,j,s=0,p,r,t,m;
for(i=1;i<=n;i++){
    cin>>b[i];
    a[b[i]]++;
}
for(i=1;i<=n;i++){p=a[i];
if(p>1)
s=s+((p*(p-1))/2);
}for(i=1;i<=n;i++){r=a[b[i]];t=a[b[i]]-1;m=s;
if(r>1)
m=m-((r*(r-1))/2);
if(t>1)
m=m+((t*(t-1))/2);
cout<<m<<endl;
}
    return 0;
  
}


Measured memory_bytes: 5760
#include <stdio.h>

int main(void)
{
	int a, b, c, i, n = 0;

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

	for (i = a; i <= b; i++) {
		if (c % i == 0) {
			n++;
		}
	}

	printf("%d\n", n);

	return 0;
}


Measured memory_bytes: 2756
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(x)    (x).begin(),(x).end()
typedef long long ll;
const int MOD = (int)1e9 + 7;

int main(){
  int n,m,c;
  cin>>n>>m>>c;
  int ans = 0;
  vector<int> b(m);
  rep(i,m) cin >> b[i];

  rep(i,n){
    int product=0;
    rep(j,m){
      int buf;
      cin>>buf;
      product += b[j] * buf;
    }
    if (product+c>0) ans ++;
  }
  cout<<ans<<endl;
}



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

#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

using namespace std;
using ll  = long long;
using pll = pair<ll, ll>;

const ll MOD  = 1e9+7;
const ll LINF = 1LL << 60;
const int INF = 1e9 + 7;

ll n;
vector<vector<ll>> tree(100010);
vector<vector<ll>> path_dist(100010);
vector<ll> dist_from_k(100010);

void dfs(ll pos, ll parent, ll dist){
    dist_from_k[pos] = dist;

    rep(i, tree[pos].size()){
        if(tree[pos][i] == parent)continue;
        dfs(tree[pos][i], pos, dist+path_dist[pos][i]);
    }
}

int main(){
    cin >> n;
    
    rep(i, n-1){
        ll a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        tree[a].push_back(b);
        tree[b].push_back(a);
        path_dist[a].push_back(c);
        path_dist[b].push_back(c);
    }

    ll q, k;
    cin >> q >> k;

    dfs(k-1, k-1, 0);

    vector<ll> ans(q);
    rep(i, q){
        ll x, y;
        cin >> x >> y;
        x--, y--;
        ans[i] = dist_from_k[x] + dist_from_k[y];
    }

    rep(i, q)cout << ans[i] << endl;
}


Measured memory_bytes: 18944
#include <iostream>
using namespace std;
int A[100000]={},n;
int solve(int i,int m){
    if(m==0){
        return true;
    }
    if(i>=n){
        return false;
    }
    return solve(i+1,m) || solve(i+1,m-A[i]);
}
int main(){
    int m,l;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    cin>>l;
    for(int j=0;j<l;j++){
        cin>>m;
        if(solve(0,m)){
            cout<<"yes"<<endl;
        }
        else{
            cout<<"no"<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3092
import Control.Monad
main = do 
  [r,d,x] <- map read . words <$> getLine :: IO [Int]
  forM_ (take 10 $ alg x r d) print

alg :: Int -> Int -> Int -> [Int]
alg n r d = 
  let v = r*n-d in v : (alg v r d)

Measured memory_bytes: 508
#include <iostream>

using namespace std;

int main()
{
	int a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	int k;
	cin>>k;
	cout<<a[k-1]<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	char map[10];
	while(~scanf("%s",map)){
		if(map[0] == map[1] && map[1] == map[2] && map[0] - 's') printf("%c\n",map[0]);
		else if(map[3] == map[4] && map[4] == map[5] && map[3] - 's') printf("%c\n",map[3]);
		else if(map[6] == map[7] && map[7] == map[8] && map[6] - 's') printf("%c\n",map[6]);
		else if(map[0] == map[3] && map[3] == map[6] && map[0] - 's') printf("%c\n",map[0]);
		else if(map[1] == map[4] && map[4] == map[7] && map[1] - 's') printf("%c\n",map[1]);
		else if(map[2] == map[5] && map[5] == map[8] && map[2] - 's') printf("%c\n",map[2]);
		else if(map[0] == map[4] && map[4] == map[8] && map[0] - 's') printf("%c\n",map[0]);
		else if(map[2] == map[4] && map[4] == map[6] && map[2] - 's') printf("%c\n",map[2]);
		else printf("d\n");
	}
	return 0;
}

Measured memory_bytes: 548
#include <bits/stdc++.h>
using namespace std;
typedef pair < int , int > Pi;
int main()
{
    set < Pi > st; //y order
    Pi data[100005]; // x order
    int W, H, N;
    cin >> W >> H >> N;
    st.insert(Pi(0, -1));
    for(int i = 0; i < N; i++) {
        cin >> data[i].first >> data[i].second;
        st.insert(Pi(data[i].second, data[i].first));
    }
    sort(data, data + N);
    
    int minv = (--st.end()) -> first;
    int i;
    while(i < N) {
        int val = data[i].first;
        while(data[i].first == val) {
            st.erase(Pi(data[i].second, data[i].first));
            i++;
        }
        minv = min(minv, val + (--st.end()) -> first);
    }
    cout << minv << endl;
    return (0);
}
        

Measured memory_bytes: 8568
#include <iostream>

using namespace std;

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

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

	int count = 0;

	while(1){
		int check = 0;
		for(int i=0;i<n;i++){
			if(a[i]%2 == 0){
				check++;
			}
		}

		if(check == n){
			for(int i=0;i<n;i++){
				a[i] /= 2;
			}
			count++;
		}else{
			break;
		}
	}

	cout << count << endl;	
	
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))
#define iter(v,ite) for(auto ite=(v).begin();ite!=(v).end();ite++)
#define mimunum(v,x) distance((v).begin(),lower_bound((v).begin(),(v).end(),x))


struct unifo{
	int n;
	int uni[200005];
	void init(int in){
		n=in;
		rep(i,n)uni[i]=i;
	}
	int find(int p){
		if(uni[p]==p)return p;
		else return (uni[p]=find(uni[p]));
	}
	void mer(int p,int q){
		if(!same(p,q))uni[find(p)]=find(q);
	}
	bool same(int p,int q){
		return find(p)==find(q);
	}
	void out(){
		vector<mp> ps;
		//printf("%d %d\n",i,find(i));
		rep(i,n)ps.push_back(mp(find(i),i));
		sort(ps.begin(),ps.end());
		printf("uni .. %d elem\n{ ",n);
		rep(i,n){
			if(i!=0 && ps[i-1].fir!=ps[i].fir)printf("}\n{ ");
			printf("%d ",ps[i].sec);
		}
		printf("}\n\n");
	}
} uni[2];


int n;
mp dat[200005];
int main(void){
	int ns[2];
	scanf("%d%d%d",&n,&ns[0],&ns[1]);
	rep(t,2){
		uni[t].init(n+5);
		rep(i,ns[t]){
			int a,b;
			scanf("%d%d",&a,&b); a--; b--;
			uni[t].mer(a,b);
		}
	}
	rep(i,n)dat[i]=mp(uni[0].find(i),uni[1].find(i));
	
	map<mp,int> mas;
	rep(i,n){
		mas[dat[i]]++;
	}
	rep(i,n){
		printf("%d\n",mas[dat[i]]);
	}
	
	return 0;
}






Measured memory_bytes: 15104
#include <bits/stdc++.h>
using namespace std; 
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define INIT(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define INIT2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define LINY "YES\n"
#define Liny "Yes\n"
#define LINN "NO\n"
#define Linn "No\n"
#define unordered_map umap
typedef long long ll;
typedef long double ld;
ll min(ll x,ll y){return (x<y ? x:y);}
ll max(ll x,ll y){return (x>y ? x:y);}
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){if(a<b){swap(a,b);} return a*b /gcd(a,b);}
bool isPrime(int n){if(n<2){return false;}for(int i=2;i<sqrt(n)+1;i++){if(n%i==0) return false;}return true;}

int func(ll N){
  int count = 0;
  while(N%2==0){ N/=2; count++;}
  return count;
}

int main(){
  int N; cin>>N;
  ll a;
  int num = 0;
  REP(i,N){
    cin >> a;
    num += func(a);
  }
  printf("%d\n",num);  
}


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

int main()
{
	long long N;
	scanf("%lld", &N);

	int i, digit[64] = {};
	long long n, l, u;
	while (N != 0) {
		for (i = 0, n = 1, l = 0, u = 1; N < l || u < N; i++) {
			n *= -2;
			if (i % 2 == 0) l += n;
			else u += n;
		}
		N -= n;
		digit[i] = 1;
	}

	for (i = 63; i > 0 && digit[i] == 0; i--);
	for (; i >= 0; i--) printf("%d", digit[i]);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>

int main(void){
  using namespace std;
  long long d, t, s;

  cin >> d >> t >> s;
  
  //cout << (double)(d)/(double)(s) << endl;
  //cout << (double)t << endl;
  
  //if ((double)t < (double)(d/s)) cout << "No" << endl;
  if ((double)t < (double)(d)/(double)(s)) cout << "No" << endl;
  else cout << "Yes" << endl;

}
  

Measured memory_bytes: 3632
#include <bits/stdc++.h>
template<int mod>
class Combination {
    std::vector<long long> fact, finv, inv;
public:
    Combination(int sz) {
        fact.resize(sz);
        finv.resize(sz);
        inv.resize(sz);
        fact[0] = 1;
        for(int i=1;i<sz;++i) {
            fact[i] = fact[i-1] * i % mod;
        }
        inv[0] = 0;
        inv[1] = 1;
        for(int i=2;i<sz;++i) {
            inv[i] = mod - inv[mod%i] * (mod/i) % mod;
        }
        finv[0] = 1;
        for(int i=1;i<sz;++i) {
            finv[i] = finv[i-1] * inv[i] % mod;
        }
    }
    long long C(long long n, long long k) {
        if(n < k) return 0;
        if(n < 0 || k < 0) return 0;
        return (fact[n] * finv[k] % mod) * finv[n-k] % mod;
    }
    long long P(long long n, long long k) {
        if(n < k) return 0;
        if(n < 0 || k < 0) return 0;
        return fact[n] * finv[n-k] % mod;
    }
    long long H(long long n, long long k) {
        return this->C(n + k - 1, k);
    }
    long long getfact(int i) {
        return fact[i];
    }
    long long getinv(int i) {
        return inv[i];
    }
    long long getfinv(int i) {
        return finv[i];
    }
};
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using vi = vector<ll>;
using vvi = vector<vector<ll>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const ll MOD = 1000000007;
const ll INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(ll i=0;i<(ll)(s.size());++i) {
    cout << s[i];
    if(i == (ll)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  ll x, y; cin >> x >> y;
  ll n = x + y;
  if(n % 3) {
    cout << 0 << endl;
    return 0;
  }
  ll m = n / 3;
  if(x < m || y < m) {
    cout << 0 << endl;
    return 0;
  }
  Combination<MOD> comb(1000010);
  ll mi = min(x, y);
  ll l = mi - m;
  cout << comb.C(m, l) << endl;
}


Measured memory_bytes: 23680
use std::collections::HashMap;
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
fn main(){
    let (n,m) ={
        let t = read_vec::<usize>();
        (t[0],t[1])
    };
    let v = read_vec2::<usize>(n as u32);
    let mut map = HashMap::new();
    for j in 0..n {
        for k in 1..v[j].len(){
            let y = map.get(&v[j][k]).map(|i| i + 1).unwrap_or(1);
            map.insert(v[j][k],y);
        }
    }
    let ans = map.into_iter().filter(|&(k,value)|{
        value == n
    }).count();
    
    println!("{}",ans);
}

Measured memory_bytes: 4352
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
#include<limits.h>
#include<deque>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1000000;
const int mod = 998244353;
const ll INF = 1LL << 60;
#define rep(i,n) for(ll i=(ll)0;i<(ll)n;++i)
#define ALL(x) x.begin(),x.end()
#define pp pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define fix(n) fixed<<setprecision(n)
#define itr vector<ll>::iterator
#define print(s) cout<<s<<endl
#define input(s) cin>>s
ll n, m,ans;
int main() {
	input(n >> m);
	ans += min(n,m/2);
	m -= n * 2;
	if (m > 0) {
		ans += m / 4;
	}
	print(ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>/*{{{*/
#include <bits/stdc++.h>
#define REP(i, x) for(int i = 0; i < (int)(x); i++)
#define REPS(i,x) for(int i = 1; i <= (int)(x); i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define RFOR(i, m, n) for(int i = m;i >= n;i--)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define FILL(x,y) memset(x,y,sizeof(x))
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define PB(a) push_back(a)
#define debug(x) cerr << __LINE__ << ": " << #x << " -> " << x << '\n'
#define INF 999999999
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};/*}}}*/

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  if(a*b <= c*d){
    cout << c*d << endl;
  }
  else{
    cout << a*b << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <sstream>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

#define MP make_pair
#define PB push_back
#define FF first
#define SS second

#define FORN(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD(i, n) for (int i = (int)(n) - 1; i >= 0; i--)

#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define PR0(A,n) { cout << #A << " = "; FORN(_,n) cout << A[_] << ' '; cout << endl; }

#define MOD 1000000007
#define INF 2000000000

int GLL(LL& x) {
    return scanf("%lld", &x);
}

int GI(int& x) {
    return scanf("%d", &x);
}

string s;

int main() {
    cin >> s;

    int n = s.size();

    int res = n;

    for (int i = 0; i < n-1; i++)
    {
        if (s[i] != s[i+1])
        {
            res = min(res, max(i+1, n-1-i));
        }
    }

    cout << res << "\n";
    return 0;
}

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

int main(){
  int A,B,C;
  cin >> A;
  cin >> B;
  cin >> C;
  int s=0;
  if( A == B ) s++; 
  if( A == C ) s++;
  if( B == C ) s++;
  if( s == 1 ){
  cout << "Yes" << endl;
  }
  else cout << "No" << endl;
}


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

#define mod 1000000007

using namespace std;
 
int main(void){
	
	int N, odd = 0;
	bool ans = false;
	
	cin >> N;
	
	long long int A[N];
	
	for(int i=0; i<N; i++){
		cin >> A[i];
		if(A[i]%2 == 1)
			odd++;
	}
	
	if(odd%2 == 0)
		ans = true;
	
	if(ans)
		cout << "YES";
	else
		cout << "NO";
	
	return 0;
}

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

const int mod=1e9+7;

string s;
int dp[2][4];

int main()
{
    cin>>s;
    int n=s.size();
    dp[n&1][3]=1;
    for(int i=n-1; ~i; i--)
        for(int j=3; ~j; j--)
        {
            dp[i&1][j]=dp[(i+1)&1][j]*(s[i]=='?'? 3LL:1)%mod;
            if(j<3&&(s[i]=='?'||s[i]=="ABC"[j]))
                dp[i&1][j]=(dp[i&1][j]+dp[(i+1)&1][j+1])%mod;
        }
    cout<<dp[0][0];
    return 0;
}


Measured memory_bytes: 512
import java.util.*;

import java.lang.*;

import java.math.*;



public class Main {

	Scanner sc = new Scanner(System.in);



	int[] ope(int[] s) {

		int[] ret = new int[s.length];

		for (int i = 0; i < s.length; i++) {

			for (int j = 0; j < s.length; j++) {

				if (s[i] == s[j]) {

					ret[i]++;

				}

			}

		}

		return ret;

	}



	boolean equ(int[] a, int[] b) {

		int i = a.length;

		for (int j = 0; j < i; j++) {

			if (a[j] != b[j])

				return false;

		}

		return true;

	}

	String p(int[]a){

		String r = "";

		for(int i:a){

			r += " "+i;

		}

		return r.trim();

	}

	void run() {

		for (;;) {

			int n = sc.nextInt();

			if (n == 0) {

				break;

			}

			int[] s = new int[n];

			for (int i = 0; i < n; i++) {

				s[i] = sc.nextInt();

			}

			int[] pre = s.clone();

			int[] now = ope(s);

			int t = 0;

			for (; !equ(pre, now);) {

				t++;

				pre = now.clone();

				now = ope(pre);

			}

			System.out.println(t);

			System.out.println(p(now));

		}



	}



	public static void main(String[] args) {

		Main m = new Main();

		m.run();

	}

}

Measured memory_bytes: 12000
#include <iostream>

using namespace std;

long long gcd(long long x, long long y) {return (y ? gcd(y, x % y) : x);}

long long cntDiv(long long rg, long long p, long long q)
{
    return rg / p + rg / q - rg / (p / gcd(p, q) * q);
}

int main()
{
    long long a, b, c, d; cin >> a >> b >> c >> d;
    cout << (b - a + 1) - cntDiv(b, c, d) + cntDiv(a - 1, c, d);
    return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {


    public static void main(String[] args) {


        Scanner scan = new Scanner(System.in);
int p=scan.nextInt();
p=p+(int)Math.pow(p,2)+(int)Math.pow(p,3);

System.out.println(p);
    }
    }






Measured memory_bytes: 27072
using System;

public class Test
{
	public static void Main()
	{
		// your code goes here
		
		string s = Console.ReadLine();
		string s1 = s.Substring(0,1);
		string s2 = s.Substring(1,1);
		string s3 = s.Substring(2,1);
		string s4 = s.Substring(3,1);
		
		if(s1==s2){
			if(s3==s4){
				if(s1==s3){Console.WriteLine("No");}else{Console.WriteLine("Yes");}
			}else{Console.WriteLine("No");}
		}else if(s1==s3){
			if(s2==s4){Console.WriteLine("Yes");
			}else{Console.WriteLine("No");}
		}else if(s1==s4){
			if(s2==s3){Console.WriteLine("Yes");
			}else{Console.WriteLine("No");}
		}else{Console.WriteLine("No");}
		
	}
}

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

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

long long INF=LLONG_MAX;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int a[3][3];
	int v[3][3];
	memset(v,0,sizeof(v));
	int row[3],col[3],dig1=0,dig2=0;
	for(int i = 0; i < 3; i++){
		row[i]=0; col[i]=0;
		cin >> a[i][0] >> a[i][1] >> a[i][2];
	}
	int n; cin >> n;
	map < int, int> vis;
	int x;
	for(int i = 0; i < n; i++){
		cin >> x;
		vis[x] = 1;
	}
	bool bingo = 0;
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			if(vis[a[i][j]]){
				v[i][j] = 1;
			}
			row[i] += v[i][j];
			col[j] += v[i][j];
			if(i==j)dig1 += v[i][j];
			if(i+j==2)dig2 += v[i][j];
			if(row[i]==3||col[j]==3||dig1==3||dig2==3)bingo = 1;
		}
	}
	if(bingo)cout << "Yes" << endl;
	else cout << "No" << endl;
}	


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FR first
#define SE second
#define inf 0x3f3f3f3f3f3f3f3fLL

using namespace std;

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

struct Frac {
  ll x,y;
  Frac() {}
  Frac(ll a,ll b):x(a),y(b) {}
  bool operator < (const Frac & b) {return x*b.y<y*b.x;}
};

pr a[100005],b[100005];
int sz1,sz2;

bool check(int n,int d) {
  int l=max(0,sz1-d),r=min(sz1,n-d);
  ll s=0;
  for(int i=sz1-r+1;i<=sz1;i++) s+=a[i].SE-a[i].FR;
  for(int i=1;i<=sz1-r;i++) s-=a[i].FR;
  for(int i=1;i<=d-(sz1-r);i++) s-=b[i].FR;
  int r1=sz1-r+1,r2=d-(sz1-r);
  for(int i=r;i>=l;i--) {
  	if (s>=0) return 1;
  	s-=a[r1++].SE;
  	s+=b[r2--].FR;
  }  
  return 0;
}

ll max1[100005],max2[100005],max3[100005];

Frac solve(int n,int d) {
  for(int i=0;i<=n+1;i++) max1[i]=max2[i]=max3[i]=-inf;
  int l=max(0,sz1-d-1),r=min(sz1-1,n-d-1);
  ll s=0;
  for(int i=sz1-r+1;i<=sz1;i++) s+=a[i].SE-a[i].FR;
  for(int i=1;i<=sz1-r;i++) s-=a[i].FR;
  for(int i=1;i<=d-(sz1-r-1);i++) s-=b[i].FR;
  int r1=sz1-r+1,r2=d-(sz1-r-1);
  for(int i=r;i>=l;i--) {
  	max1[r1-1]=max(max1[r1-1],s);
  	max2[r2]=max(max2[r2],s);
  	if (r2) max3[r2+1]=max(max3[r2+1],s+b[r2].FR);
  	s-=a[r1++].SE;
  	s+=b[r2--].FR;
  }
  Frac ans(0,1);
  if (n-d-1>=sz1) {
  	ll s=0;
  	for(int i=1;i<=sz1;i++) s+=a[i].SE-a[i].FR;
  	for(int i=1;i<=d+1;i++) s-=b[i].FR;
  	for(int i=1;i<=d+1;i++)
  	  if (s+b[i].SE>=0) {
  	  	  Frac t(s+b[i].SE,b[i].SE);
  	  	  if (ans<t) ans=t;
		}
	for(int i=d+2;i<=sz2;i++)
	  if (s+b[d+1].FR-b[i].FR+b[i].SE>=0) {
	  	  Frac t(s+b[d+1].FR-b[i].FR+b[i].SE,b[i].SE);
	  	  if (ans<t) ans=t;
	  }
  }
  for(int i=sz1;i>0;i--) {
  	max1[i]=max(max1[i],max1[i+1]);
  	if (max1[i]+a[i].SE>=0) {
  		Frac t(max1[i]+a[i].SE,a[i].SE);
  		if (ans<t) ans=t;
	  }
  }
  for(int i=sz2;i>0;i--) {
  	max2[i]=max(max2[i],max2[i+1]);
  	if (max2[i]+b[i].SE>=0) {
  		Frac t(max2[i]+b[i].SE,b[i].SE);
  		if (ans<t) ans=t;
	  }
  }
  for(int i=1;i<=sz2;i++) {
  	max3[i]=max(max3[i],max3[i-1]);
  	if (max3[i]-b[i].FR+b[i].SE>=0) {
  		Frac t(max3[i]-b[i].FR+b[i].SE,b[i].SE);
  		if (ans<t) ans=t;
	  }
  }
  ans.x+=d*ans.y;
  ans.y*=n;
  return ans;
}

bool cmp1(pr x,pr y) {
  return x.FR<y.FR;
}

bool cmp2(pr x,pr y) {
  return x.SE<y.SE;
}

int main() {
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++) {
  	int x,y;
  	scanf("%d%d",&x,&y);
  	if (x<=y) a[++sz1]=pr(x,y);
  	else b[++sz2]=pr(x,y);
  }
  sort(a+1,a+sz1+1,cmp2);
  sort(b+1,b+sz2+1,cmp1);
  int l=0,r=n;
  while (l<r) {
  	int m=((l+r)>>1)+1;
  	if (check(n,m)) l=m; else r=m-1;
  }
  Frac ans=solve(n,l);
  ll d=__gcd(ans.x,ans.y);
  ans.x/=d;ans.y/=d;
  printf("%lld %lld\n",ans.x,ans.y);
  return 0;
} 

Measured memory_bytes: 3328
object Main extends App {
  val in = new java.util.Scanner(System.in)
  val N = in.nextInt
  val Xs = Array.fill(N)(in.nextInt)
  val sumX = Xs.sum
  val sumSqX = Xs.map(x => x * x).sum
  val min = (1 to 100).map(p => -2 * p * sumX + p * p * N).min
  println(sumSqX + min)
}

Measured memory_bytes: 25516
#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;
int main(){
  int n;cin >> n;
  double x1,x2,x3,y1,y2,y3,x12,x13,y12,y13,xx12,yy12,xx13,yy13,x,y,r;
  for(int i=0;i<n;i++){
    cin>>x1>>y1>>x2>>y2>>x3>>y3;
    x12 = x1 -x2;
    x13 = x1 -x3;
    y12 = y1-y2;
    y13 = y1 -y3;
    xx12 = x1*x1-x2*x2;
    xx13 = x1*x1-x3*x3;
    yy12 = y1*y1-y2*y2;
    yy13 = y1*y1-y3*y3;

    x=-0.5*(y12*(xx13+yy13)-y13*(xx12+yy12))/(x12*y13-x13*y12);
    y=-0.5*(x12*(xx13+yy13)-x13*(xx12+yy12))/(y12*x13-y13*x12);
    r=sqrt(x*x+y*y+x1*x1+y1*y1-2*x*x1-2*y*y1);
    printf("%.3lf %.3lf %.3lf\n",x,y,r);
   }
   return 0;
}



Measured memory_bytes: 3164
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0 for i in range(n)]
        self.size = [1 for i in range(n)]

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

    def getSize(self, x):
        return self.size[self.find(x)]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

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

N = int(input())
A = [0] + list(map(int, input().split())) + [N+1]
B = [None] * (N+2)
for i, x in enumerate(A):
    B[x] = i
A[0] = N+1
uf = UnionFind(N+1)
ans = 0
for x in range(1, N):
    i = B[x]
    if A[i-1] < A[i]:
        uf.unite(i-1, i)
    if A[i] > A[i+1]:
        uf.unite(i, i+1)
    if x < A[i-1]:
        k2 = i-1
    else:
        l, r = 0, i-1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(m, i-1):
                r = m
            else:
                l = m
        k2 = l
    if k2 == 0 or A[max(0, k2-1)] > x:
        k1 = max(0, k2-1)
    else:
        l, r = 0, k2-1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(m, k2-1):
                r = m
            else:
                l = m
        k1 = l
    if x < A[i+1]:
        k3 = i+1
    else:
        l, r = i+1, N+1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(i+1, m):
                l = m
            else:
                r = m
        k3 = r
    if k3 == N+1 or x < A[min(N+1, k3+1)]:
        k4 = min(N+1, k3+1)
    else:
        l, r = k3+1, N+1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(k3+1, m):
                l = m
            else:
                r = m
        k4 = r
    ans += x * ((k2-k1)*(k3-i) + (k4-k3)*(i-k2))
print(ans)


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

int main(){
    string s;
    cin >> s;
    string m, y;
    rep(i, 0, 2){
        m += s[i];
        y += s[i+2];
    }
    bool my_format = 0, ym_format = 0;
    int mm = stoi(m);
    int yy = stoi(y);
    if (1 <= mm && mm <=12) my_format = 1;
    if (1 <= yy && yy <=12) ym_format = 1;

    string judge;
    if (my_format && ym_format) judge = "AMBIGUOUS";
    else if (my_format) judge = "MMYY";
    else if (ym_format) judge = "YYMM";
    else judge = "NA";
    cout << judge << endl;
    return 0;
}   

Measured memory_bytes: 256
import bisect
from collections import defaultdict
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

ans = 0
bb = []
for b in B:
  idx = bisect.bisect_right(C, b)
  bb += [[b, len(C)-idx]]

for i in range(len(bb)-1, 0, -1):
  bb[i-1][1] += bb[i][1]

for a in A:
  idx = bisect.bisect_right(B, a)
  if idx > len(B)-1:
    continue
  ans += bb[idx][1]
print(ans)

Measured memory_bytes: 108968
n,a,b = map(int,input().split(' '))

sum = 0
for i in range(n+1):
    digitSum = 0
    digitCheck = i
    while digitCheck>0:
        digitSum += digitCheck%10
        digitCheck = digitCheck//10
    if a <= digitSum <= b:
        sum +=i
    
    
print(sum)

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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

int main() {
	int n;
	
	while (cin >> n, n) {
		int a = 0, b = 0;
				
		for_(i,0,n) {
			int aa, bb;
			cin >> aa >> bb;
			
			if (aa > bb) a += (aa + bb);
			else if (aa < bb) b += (aa + bb);
			else a += aa, b += bb;
		}
		
		cout << a << " " << b << endl;
	}
}

Measured memory_bytes: 1160
import sys
input = sys.stdin.readline

class BIT:
    def __init__(self, size):
        self.bit = [0] * (size + 1)
        self.size = size

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

N = int(input())
P = list(map(int, input().split()))
idx = [-1] * (N+1)
for i, p in enumerate(P):
    idx[p] = i + 1
bit = BIT(N+1)
bit.add(0, 1)
ans = 0

def bin_search(target):
    lb, ub = -1, N+1
    while ub - lb > 1:
        m = (lb + ub) // 2
        if bit.sum(m) < target:
            lb = m
        else:
            ub = m
    return ub

for p in range(1, N+1)[::-1]:
    c = idx[p]
    s = bit.sum(c)
    a = bin_search(s-1)
    b = bin_search(s)
    d = bin_search(s+1)
    e = bin_search(s+2)
    ans += p * ((b-a) * (d-c) + (c-b) * (e-d))
    bit.add(c, 1)
print(ans)


Measured memory_bytes: 57488
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a)-1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a)-1; (i) >= (b); (i)--)
#define PI acos(-1.0)
#define DEBUG(C) cout<< C <<endl;
#define VI vector <int>
#define VII vector <VI>
#define VL vector <LL>
#define VLL vector <VL>
#define VD vector <double>
#define VDD vector <VD>
#define PII pair <int, int>
#define PDD pair <double, double>
#define PLL pair <LL, LL>
#define VPII vector <PII>
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define REVERSE(a) reverse(ALL(a))
#define MP make_pair
#define FORE(a, b) for (auto &&a:b)
#define FIND(s, e) (s.find(e) != s.end())
#define EB emplace_back

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 1e9;
const int MOD = INF+7;
const LL LLINF = 1e18;

int main(void) {
    int n, m;
    cin >> n >> m;
    set<int> se;
    VPII v(m);
    REP(i, n) se.insert(i + 1);
    REP(i, m) {
        cin >> v[i].first;
        se.erase(v[i].first);
        v[i].second = i;
    }
    REVERSE(v);
    set<int> se2;
    FORE(el, v) {
        if (!FIND(se2, el.first)) cout << el.first << endl;
        se2.insert(el.first);
    }
    FORE(el, se) cout << el << endl;
}

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

using namespace std;

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

  long long a;
  string s;
  cin >> a >> s;
  s.erase(s.begin() + 1);
  long long b = stoi(s);
  cout << a * b / 100;

  return 0;
}


Measured memory_bytes: 3656
x = int(input())

import math

serach_number = 100


import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

while not is_prime(x):
	x += 1
print(x)


Measured memory_bytes: 3060