akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>
#include <tgmath.h>
#include <time.h>
#define ll long long
#define min(a, b) ((a) > (b) ? (b) : (a))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define miin(a, b, c) min((a), min((b), (c)))
#define maax(a, b, c) max((a), max((b), (c)))
#define mod 1000000007

int n, m, nyaa[9] = {-1, -1, -1, -1}, a, b;

main()
{
    scanf("%d%d", &n, &m);
    if (n == 1 && !m)
    {
        puts("0");
        return 0;
    }
    while (m--)
    {
        scanf("%d%d", &a, &b);
        a--;
        if (nyaa[a] < 0)
            nyaa[a] = b;
        else
        {
            if (nyaa[a] != b)
            {
                puts("-1");
                return 0;
            }
        }
    }
    if (nyaa[0] == 0 && n > 1)
    {
        puts("-1");
        return 0;
    }
    for (int i = 0; i < n; i++)
    {
        if (nyaa[i] < 0)
        {
            putchar(49 - (i > 0));
        }
        else
        {
            putchar(48 + nyaa[i]);
        }
    }
    putchar(10);
    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>

int main(){
  int a, b, ab, o, n;
  char in[3];
  a = b = ab = o = 0;
  while(scanf("%d,%s",&n, in) != EOF){
    if(strcmp(in, "A") == 0) a++;
    else if(strcmp(in, "B") == 0) b++;
    else if(strcmp(in, "AB") == 0) ab++;
    else o++;
    }

  printf("%d\n%d\n%d\n%d\n", a, b, ab, o);
  return 0;
}

Measured memory_bytes: 592
#define _USE_MATH_DEFINES

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

using namespace std;

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

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

int main(){
	
	int H, A, B;
	cin >> H >> A >> B;
	
	int ans = 0;
	
	for(int i = A; i <= B; i++){
		if(H % i == 0){
			ans += 1;
		}
	}
	
	cout << ans << endl;
	
	return 0;
}



Measured memory_bytes: 3096
# -*- coding: utf-8 -*-

from itertools import permutations
from math import sqrt, factorial

def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  N = readInts()[0]
  points = [readInts() for _ in range(N)]

  s = 0
  for r in permutations(points):
    for i in range(N-1):
      x1, y1 = r[i]
      x2, y2 = r[i+1]
      s += sqrt((x2 - x1)**2 + (y2 - y1)**2)
  print(s / factorial(N))

if __name__ == "__main__":
  main()


Measured memory_bytes: 3064
// AOJ 1280: Slim Span
// 2017.10.22 bal4u@uu

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 100
/* UNION-FIND library */
int p[MAX], rank[MAX], pp[MAX];
void make_set(int x) { p[x] = x, rank[x] = 0; }
void link(int x, int y) {
	if (rank[x] > rank[y]) p[y] = x;
	else { p[x] = y; if (rank[x] == rank[y]) rank[y] = rank[y] + 1;	}
}
int find_set(int x) { if (x != p[x]) p[x] = find_set(p[x]);	return p[x]; }
void union_set(int x, int y) { link(find_set(x), find_set(y)); }

typedef struct { int x, y, w; } EDGE;
EDGE edge[5000], *end;

int cmp(EDGE *a, EDGE *b) { return a->w - b->w; }
int main() 
{
	int n, m, i, j, k, ans, sz;
	EDGE *ep;

	for (j = 0; j < 100; j++)  pp[j] = j;
	while (scanf("%d%d", &n, &m) && n > 0) {
		sz = sizeof(int)*n;
		for (ep = edge, k = m; k--; ep++)
			scanf("%d%d%d", &i, &j, &ep->w), ep->x = i-1, ep->y = j-1;
		end = ep;

		qsort(edge, m, sizeof(EDGE), cmp);
	
		ans = -1;
		for (i = 0; i < m; i++) {
			memcpy(p, pp, sz), memset(rank, 0, sz);
			for (k = 1, ep = edge+i; ep < end; ep++) {
				if (find_set(ep->x) != find_set(ep->y)) {
					union_set(ep->x, ep->y);
					if (++k == n) {
						if (ans < 0 || ep->w - edge[i].w < ans) {
							ans = ep->w - edge[i].w;
							if (ans == 0) goto done;
						}
						break;
					}
				}
			}
		}
done:	printf("%d\n", ans);
	} 
	return 0; 
}

Measured memory_bytes: 1936
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

struct edge_t {
  int to, w;
};

using weight_t = pair<int, int>;

const weight_t inf = {400, 1e9 + 10};

vector<int> solve(const vec<edge_t, 2>& g, int L, int s) {
  vector<weight_t> dist(g.size(), inf);
  using P = pair<weight_t, int>;
  priority_queue<P, vector<P>, greater<P>> q;
  dist[s] = {0, 0};
  q.emplace(weight_t(0, 0), s);
  while (!q.empty()) {
    const P p = q.top();
    q.pop();
    const weight_t w = p.first;
    const int v = p.second;
    if (dist[v] < w) continue;
    vector<weight_t> ws = {w, {w.fst + 1, 0}};
    for (auto w : ws) {
      for (const auto& e : g[v]) {
        if (w.snd + e.w > L) continue;
        const weight_t nw = {w.fst, w.snd + e.w};
        if (dist[e.to] <= nw) continue;
        dist[e.to] = nw;
        q.emplace(nw, e.to);
      }
    }
  }
  vector<int> res(g.size(), -1);
  for (int v = 0; v < g.size(); v++) {
    if (dist[v] != inf) res[v] = dist[v].fst;
  }
  return res;
}

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int N, M, L;
  while (cin >> N >> M >> L) {
    vec<edge_t, 2> g(N);
    for (int i = 0; i < M; i++) {
      int a, b, c;
      cin >> a >> b >> c;
      --a;
      --b;
      if (c > L) continue;
      g[a].push_back({b, c});
      g[b].push_back({a, c});
    }
    vec<int, 2> ans(N);
    for (int i = 0; i < N; i++) ans[i] = solve(g, L, i);
    int Q;
    cin >> Q;
    for (int q = 0; q < Q; q++) {
      int s, t;
      cin >> s >> t;
      --s;
      --t;
      cout << ans[s][t] << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 2048
#include<algorithm>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cstdio>
#include<iomanip>
#include<cmath>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> H(N);
    map<int, bool> m;
    for (int i = 0; i < N; i++) {
        cin >> H[i];
    }
    int A, B;
    for (int i = 0; i < M; i++) {
        cin >> A >> B;
        if (H[A-1] > H[B-1]) {
            m[B-1] = true;
        } else if (H[A-1] < H[B-1]) {
            m[A-1] = true;
        } else {
            m[B-1] = true;
            m[A-1] = true;
        }
    }
    
    int count = 0;
    for (int i = 0; i < N; i++) {
        if (m[i] == false) {
            count++;
        }
    }
    
    cout << count;
    return 0;
}

Measured memory_bytes: 8316
# https://atcoder.jp/contests/abc049/tasks/arc065_a

s = list(input())
words = ['dream','dreamer','erase','eraser']

def check(w):
    return word in words

while s:
    word = ''.join([s.pop() for _ in range(5)][::-1])
    if check(word): continue
    
    for _ in range(2):
        word = s.pop() + word
        if check(word): break
    else:
        print('NO')
        exit()
print('YES')

Measured memory_bytes: 3956
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int []a=new int[n+1];
        int []b=new int[n];
        long ans2=0;
        for(int i=0;i<=n;i++){
            a[i]=sc.nextInt();
            ans2+=a[i];
        }
        for(int i=0;i<n;i++){
            b[i]=sc.nextInt();
        }
        for(int i=0;i<n;i++){
            int po=Math.max(a[i]-b[i],0);
            b[i]=Math.max(b[i]-a[i],0);
            a[i]=po;
            a[i+1]=Math.max(a[i+1]-b[i],0);
        }
        long ans=0;
        for(int i=0;i<n+1;i++){
            ans+=a[i];
        }
        System.out.println(ans2-ans);
    }
}


Measured memory_bytes: 63620
#include <bits/stdc++.h>
#define int long long
using namespace std;

typedef pair<int,int> PII;
typedef pair<PII, int> PPI;
typedef pair<int, PII> PIP;

const int MAXN = 1000000 + 10;
int n;
int a[MAXN];

pair<int,int> p[MAXN];

int dist(int a, int b) {
    return min(abs(p[a].first - p[b].first), abs(p[a].second - p[b].second));
}

vector<PIP> edges;
int par[MAXN], siz[MAXN];


int fi(int x) {
    if (par[x] != par[par[x]])
        par[x] = fi(par[x]);
    return par[x];
}

int uni(int a, int b) {
    a = fi(a);
    b = fi(b);

    if (a == b) return 0;

    if (siz[a] > siz[b]) {
        siz[a] += siz[b];
        par[b] = a;
    } else {
        siz[b] += siz[a];
        par[a] = b;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin >> n;

    vector<pair<pair<int,int>, int>> v;
    for (int i = 0; i < n; i++) {
        cin >> p[i].first >> p[i].second;
        v.push_back({p[i], i});
    }

    sort(begin(v), end(v), [](PPI a, PPI b) { return a.first.first < b.first.first; });
    for (int i = 0; i + 1 < v.size(); i++) {
        int a = v[i].second;
        int b = v[i+1].second;
        edges.push_back({dist(a, b), {a, b}});
    }
    sort(begin(v), end(v), [](PPI a, PPI b) { return a.first.second < b.first.second; });
    for (int i = 0; i + 1 < v.size(); i++) {
        int a = v[i].second;
        int b = v[i+1].second;
        edges.push_back({dist(a, b), {a, b}});
    }
    sort(begin(edges), end(edges));


    for (int i = 0; i < n; i++) {
        siz[i] = 1;
        par[i] = i;
    }
    int res = 0;
    for (int i = 0; i < edges.size(); i++) {
        int d = edges[i].first;
        int a = edges[i].second.first;
        int b = edges[i].second.second;

        if (fi(a) != fi(b)) {
            uni(a, b);
            res += d;
        }
    }

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


Measured memory_bytes: 18412
#include <stdio.h>
#include <vector>
#include <iostream>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<vs> vvs;

typedef vector<pair<int, int> > vpi;


int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    ll n, i;
    cin >> n;
    map<vi, ll> mp;
    for (i=0;i<n;i++){
        string si;
        cin >> si;
        vi cnt(26);
        for (char c:si) cnt[c-'a']++;
        mp[cnt]++;
    }
    ll cnt=0;
    for (auto pair:mp){
        if (pair.second > 1){
            cnt += (pair.second * (pair.second - 1) / 2);
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 19072
#include<iostream>
#include<vector>

using namespace std;

double abs(double a){
  if (a<0.0){
    return -a;
      }
  return a;
}

int main(){
  vector<vector<double > >a;

  double x,y;
  char comma;
  int data_num=0;
  for (int i=0;i<30;i++){
    while(cin >> x >> comma >>y ){
vector<double> hoge;
        hoge.push_back(x);
        hoge.push_back(y);
        a.push_back(hoge);
      data_num+=1;
    }
  }
  double x0,y0;
  x0=a[0][0];
  y0=a[0][1];
  for (int i=0;i< static_cast<int>(a.size()) ;i++){
    a[i][0]=a[i][0]-x0;
    a[i][1]=a[i][1]-y0;
  }
  double sum=0.0;
  for (int i=1;i<=data_num-2;i++){
    sum+=abs(a[i][0]*a[i+1][1]-a[i+1][0]*a[i][1])/2.0;
  }
  cout<<sum<<endl;
  return 0;
}

Measured memory_bytes: 1304
# LCS 最長共通部分列
# reference: http://9871225.blog.fc2.com/blog-entry-304.html
# ただし最適化のため縦ではなく横に確認

s = gets.chomp.split("")
s_len = s.length
t = gets.chomp.split("")
t_len = t.length
dp = Array.new(s_len + 1) { Array.new(t_len + 1, 0) }

# dpテーブルを埋める
s_len.times do |s_index|
  dp_current = dp[s_index]
  dp_next = dp[s_index + 1]
  t_len.times do |t_index|
    if s[s_index] == t[t_index]
      dp_next[t_index + 1] = dp_current[t_index] + 1
    else
      up = dp_current[t_index + 1]
      left = dp_next[t_index]
      dp_next[t_index + 1] = up > left ? up : left
    end
  end
end

# dpテーブルを右下から左上に辿って文字列を復元
count = dp.last.last
current_s = s_len
current_t = t_len
restored = []
while count > 0
  loop do
    if dp[current_s - 1][current_t] == count
      current_s -= 1
    else
      break
    end
  end
  loop do
    if dp[current_s][current_t - 1] == count
      current_t -= 1
    else
      break
    end
  end
  restored.unshift(s[current_s - 1])
  current_s -= 1
  current_t -= 1
  count -= 1
end

puts restored.join("")


Measured memory_bytes: 73084
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector> 
#include <cstring>
#include <queue>
#include <ctime>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int INF = 10e8;
const int maxM = 1000010;
//const int maxN = 100010;
const int maxN = 110;

int a[maxN];
int n; 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	a[0] = -1;
	a[n+1] = 1000001;
	int ans = 0;
	int st = 1,ed = 1;
	int i = 2;
	while(i<=n+1)
	{
		if(a[i] != a[i-1])
		{
			ed = i-1;
			int len = ed - st + 1;
			ans += (len/2);
			st = ed = i;
		}
		i++;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
def digit(x):
    div = 26
    digit = 0
    while x>0:
        x -= div
        digit += 1
        div *= 26
    return digit, x + div//26

n = int(input())

keta, rem = digit(n)
div = 26**(keta-1)
ans = ""
for i in range(keta):
    a = rem // div
    b = rem % div
    
    if b==0:
        a -= 1
        b += div
    ans += chr(97+a)
    
    rem = b
    div //= 26
    
print(ans)

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

int main() {
    int h,w,count=0;
    cin>>h>>w;
    vector<string> a(h);
    rep(i,h) cin>>a[i];
    rep(i,h) {
        rep(j,w) {
            if (a[i][j]=='#') count++;
        }
    }
    if (count==(h+w-1)) cout<<"Possible"<<endl;
    else cout<<"Impossible"<<endl;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
X = []
Y = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
Xs = sorted(X)
Ys = sorted(Y)
ans = float('inf')
for left in range(N - 1):
    for right in range(left + 1, N):
        for down in range(N - 1):
            for up in range(down + 1, N):
                count = 0
                for i in range(N):
                    if Xs[left] <= X[i] <= Xs[right] and Ys[down] <= Y[i] <= Ys[up]:
                            count += 1
                if count >= K:
                    ans = min(ans, (Xs[right] - Xs[left]) * (Ys[up] - Ys[down]))
print(ans)

Measured memory_bytes: 49200
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;
// auto mod int
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {if ((x += a.x) >= mod) x -= mod; return *this;}
  mint& operator-=(const mint a) {if ((x += mod-a.x) >= mod) x -= mod; return *this;}
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
// combination mod prime
struct Combination {
  vector<mint> fact, ifact;
  Combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};


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

  Combination c(h*w);

  mint ans;
  rep(d,h) ans += mint(d*(h-d))*w*w * c(h*w-2, k-2);
  rep(d,w) ans += mint(d*(w-d))*h*h * c(h*w-2, k-2);
  cout << ans << endl;
}


Measured memory_bytes: 3328
#include <stdio.h>

int main()
{
  long a,b,c;
  scanf("%lu %lu %lu",&a,&b,&c);
  long cal=c-(a+b);
  if (cal<=0)
    printf("No");
  else if (4*a*b<cal*cal)
    printf("Yes");
  else
    printf("No");
}

Measured memory_bytes: 128
#![allow(unused_imports)]
use std::io;
use std::cmp::*;
use std::collections::*;
#[allow(dead_code)]
const M: i64 = 1e9 as i64 + 7;

fn read_line() -> String {
    let stdin = io::stdin();
    let mut buf = String::new();
    stdin.read_line(&mut buf).unwrap();
    buf
}
#[allow(dead_code)]
fn read<T>() -> T where T: std::str::FromStr, T::Err : std::fmt::Debug {
    read_line().trim().parse().unwrap()
}
#[allow(dead_code)]
fn readv<T>() -> Vec<T> where T: std::str::FromStr, T::Err : std::fmt::Debug {
    read_line().split(' ').map(|a| a.trim().parse().unwrap()).collect()
}

use std::time::Instant;
fn main() {
    let _ = read::<usize>();
    let aa = readv::<usize>();
    let bb = readv::<usize>();
    let x = aa.iter().fold(0, |acc, &a| acc ^ a);
    let (mut aa, bb): (Vec<_>, Vec<_>) = aa.iter().zip(bb.iter()).filter(|&(&a, &b)| a != b).unzip();
    let n = aa.len();
    aa.push(x);
    let mut nums = HashMap::with_capacity(n + 1);
    for &a in &aa {
        *nums.entry(a).or_insert(0) += 1;
    }
    // let mut nums: HashMap<_, i32> = aa.iter()
    //     .fold(HashMap::with_capacity(n + 1), |mut acc, &a| { *acc.entry(a).or_insert(0) += 1; acc });
    for &b in &bb {
        *nums.entry(b).or_insert(0) -= 1;
        if nums[&b] < 0 {
            println!("{}", -1);
            return;
        }
    }

    let mut dests = bb.iter().enumerate()
        .fold(HashMap::new(), |mut acc, (a, b)| { (acc.entry(b).or_insert(Vec::new())).push(a); acc });
    let mut q: VecDeque<_> = std::iter::once(n).collect();
    let mut rems: BTreeSet<_> = (0..n + 1).collect();
    let mut r2: HashSet<_> = (0..n + 1).collect();
    let mut ans = n;
    #[cfg(local)] println!("{}: {:?}", "(aa, bb)", (&aa, &bb));
    let mut cnt = 1;
    while !rems.is_empty() {
        while let Some(s_idx) = q.pop_front() {
            r2.remove(&s_idx);
            if !rems.remove(&s_idx) { continue; }
            let s_num = aa[s_idx];
            // if let Some(destv) = dests.remove(&s_num) {
            //     for dest in destv {
            //         q.push_back(dest);
            //     }
            // }
            if let Some(destv) = dests.get_mut(&s_num) {
                for &dest in destv.iter() {
                    q.push_back(dest);
                }
                destv.clear();
            }
        }
        if let Some(&rem) = rems.iter().next() {
            q.push_back(rem);
            ans += 1;
        }
        if let Some(&_) = r2.iter().next() {
            cnt += 1;
        }
    }
    if cnt > 1e9 as u64{
        println!("{}", "hoge");
    }
    println!("{}", ans);
    std::process::exit(0);
}


Measured memory_bytes: 27576
open Printf
open Scanf

module Pqueue = struct

  type 'a t = {mutable cnt : int; hp : 'a array; cmp : 'a -> 'a -> int}

  let create n v f =
    let rec g x = if n <= x then x + 1 else g (2 * x + 1) in
    {cnt = 0; hp = Array.make (g 3) v; cmp = f}

  let push k pq =
    let swap i j =
      let t = pq.hp.(i) in
      pq.hp.(i) <- pq.hp.(j);
      pq.hp.(j) <- t in
    let rec iter i =
      let p = i / 2 in
      if p = 0 || pq.cmp pq.hp.(p) pq.hp.(i) >= 0 then ()
      else (swap p i; iter p)
    in
    pq.cnt <- pq.cnt + 1;
    pq.hp.(pq.cnt) <- k;
    iter (pq.cnt)

  let max_heapify pq n =
    let swap i j =
      let t = pq.hp.(i) in
      pq.hp.(i) <- pq.hp.(j);
      pq.hp.(j) <- t in
    let rec iter i =
      let l = 2 * i in
      let r = 2 * i + 1 in
      let mi =
        let ti = if l <= pq.cnt && pq.cmp pq.hp.(l) pq.hp.(i) > 0 then l else i in
        if r <= pq.cnt && pq.cmp pq.hp.(r) pq.hp.(ti) > 0 then r else ti in
      if mi <> i then
        begin
          swap mi i;
          iter mi
        end
    in
    iter n

  let pop pq =
    let ret = pq.hp.(1) in
    pq.hp.(1) <- pq.hp.(pq.cnt);
    pq.cnt <- pq.cnt - 1;
    max_heapify pq 1;
    ret

  let top pq = pq.hp.(1)

  let is_empty pq = pq.cnt = 0

  let length pq = pq.cnt

end

let solve n m =
  let adj = Array.init n @@ fun _ -> [] in
  let pq = Pqueue.create (n * n * 3) (0, 0, 0) (fun (_, _, x) (_, _, y) -> compare y x) in
  let cost = Array.make_matrix n 3 1000000 in
  let rec loop () =
    if Pqueue.is_empty pq then ()
    else begin
        let (i, t, c) = Pqueue.pop pq in
        if c > cost.(i).(t) then loop ()
        else begin
            if t = 2 || t = 0 then
              begin
                List.iter (fun (j, w) ->
                           if cost.(j).(t) > cost.(i).(t) + w then
                             begin
                               cost.(j).(t) <- cost.(i).(t) + w;
                               Pqueue.push (j, t, cost.(j).(t)) pq
                             end else ()
                          ) adj.(i)
              end;
            if t = 2 || t = 1 then
              begin
                List.iter (fun (j, w) ->
                           if cost.(j).(t-1) > cost.(i).(t) then
                             begin
                               cost.(j).(t-1) <- cost.(i).(t);
                               Pqueue.push (j, t-1, cost.(j).(t-1)) pq
                             end else ()
                          ) adj.(i)
              end;
            loop ()
          end
      end in
  for i = 1 to m do
    let a, b, c = scanf "%d %d %d " @@ fun x y z -> (x-1, y-1, z) in
    adj.(a) <- (b, c) :: adj.(a);
    adj.(b) <- (a, c) :: adj.(b)
  done;
  cost.(0).(2) <- 0;
  Pqueue.push (0, 2, 0) pq;
  loop ();
  cost.(n-1).(0)

let () = 
  let rec loop () = 
    let n, m = scanf "%d %d " @@ fun n m -> (n, m) in
    if n = 0 && m = 0 then ()
    else
      begin
        solve n m |> printf "%d\n";
        loop ()
      end
  in loop ()



Measured memory_bytes: 8424
#include <iostream>
using namespace std;
int main(void){
    string s;
    cin>>s;
    int l = s.size();
    
    int ans1=0,ans2=0;
    
    for (int i=0;i<l;i++){
        if (i%2==0 ^ s[i]=='0'){
            ans1++;
        }
    }
    for (int i=0;i<l;i++){
        if (i%2==0 ^ s[i]=='1'){
            ans2++;
        }
    }
    if (ans1>ans2){
        ans1=ans2;
    }
    cout<<ans1;
    
}


Measured memory_bytes: 512
/*######################################################
#########~~~~~####~~~~###~~##~~##~~##~~##~~##~~#########
#########~~##~~##~~##~~##~~~#~~##~~~#~~##~~##~~#########
#~~~~~~##~~~~~###~~~~~~##~~#~~~##~~#~~~##~~##~~##~~~~~~#
#########~~######~~##~~##~~##~~##~~##~~##~~##~~#########
#########~~######~~##~~##~~##~~##~~##~~###~~~~##########
######################################################*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

#pragma GCC optimize("O3")
#define rtn return
#define endl '\n'
#define F first
#define S second
#define mt make_tuple
#define pb push_back
#define int long long
#define value_at find_by_order
#define index_of order_of_key
#define fill(a, v) memset(a,v,sizeof(a))
#define copy(a, b) memcpy(b,a,sizeof(a))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i, n) for(int i=0;i<(int)n;++i)
#define per(i, n) for(int i=(int)n-1;i>=0;--i)
#define rep1(i, n) for(int i=1;i<=(int)n;++i)
#define per1(i, n) for(int i=(int)n;i>=1;--i)
#define loop(i, begin, end) for(int i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cerr << name << " = " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " = " << arg1 << " |";
  __f(comma + 1, args...);
}
#else
#define trace(...)
#endif

typedef string str;
typedef long double db;
typedef long long ll;
typedef pair<int, int> pll;
typedef vector<int> vll;
typedef vector<pll> vpll;
typedef vector<db> vdb;

template<class T, class V> void remin(T &a, V b) { a > b ? a = b : a = a; }
template<class T, class V> void remax(T &a, V b) { a < b ? a = b : a = a; }
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e18;
const db EPS = 1e-15;
const int MOD = 1e9 + 7;
const int N = 1e5 + 7;

int n, W;
int w[105], v[105];
int dp[N];

int32_t main() {
  FAST_IO;
  cin >> n >> W;
  rep(i, n)
    cin >> w[i] >> v[i];
  rep(i, N) dp[i] = INF;
  dp[0] = 0;
  rep(i, n) {
    for (int j = N - 1; j >= v[i]; j--) {
      remin(dp[j], w[i] + dp[j - v[i]]);
    }
  }
  int ans = 0;
  rep(i, N)
    if (dp[i] <= W)
      ans = i;
  cout << ans;
  rtn 0;
}


Measured memory_bytes: 1024
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int fie[152][1002][78];
int main(){
    while(1){
        int M,N;
        cin>>M>>N;
        if(M==0&&N==0)break;
        int lis[154][1002];
        for(int i=0;i<154;i++){
            for(int j=0;j<1002;j++){
                if(i!=0&&i!=M+1)lis[i][j]=-1;
                else lis[i][j]=0;
            }
        }
        for(int i=0;i<152;i++){
            for(int j=0;j<1002;j++){
                for(int k=0;k<78;k++){
                    if(i!=0||k!=0)fie[i][j][k]=2000000000;
                    else fie[i][j][k]=0;
                }
            }
        }
        for(int i=0;i<M;i++){
            int a;
            cin>>a;
            for(int j=1;j<=a;j++){
                int b,c;
                cin>>b>>c;
                lis[i+1][b]=c;
            }
        }
        for(int i=0;i<=M;i++){
            for(int j=0;j<1002;j++){
                for(int k=0;k<76;k++){
                    if(fie[i][j][k]<2000000000){
                        for(int l=0;l<1002;l++){
                            if(lis[i+1][l]!=-1)fie[i+1][l][k]=min(fie[i+1][l][k],fie[i][j][k]+(lis[i][j]+lis[i+1][l])*(int)fabs(j-l));
                            if(lis[i+2][l]!=-1)fie[i+2][l][k+1]=min(fie[i+2][l][k+1],fie[i][j][k]+(lis[i][j]+lis[i+2][l])*(int)fabs(j-l));
                        }
                    }
                }
            }
        }
        int ans=2000000000;
        for(int j=0;j<1002;j++){
            for(int k=0;k<76;k++){
                if(k<=N)ans=min(ans,fie[M+1][j][k]);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 48164
#  --*-coding:utf-8-*--


def f(s):
    for i in range(len(s)//2):
        if s[i] != s[-i-1]:
            return False

    return True


S = input()
N = len(S)

print('Yes' if f(S) and f(S[:N//2]) and f(S[N//2+1:]) else 'No')


Measured memory_bytes: 2940
#include<stdio.h>
#include<string.h>
#define N 100000
 
typedef struct pp{
  char name[100];
  int t;
}P;
 
int head, tail, n, c=0, q;
P Q[N];
void enqueue(){
  Q[head].t = Q[head].t -q;
  Q[tail] = Q[head];
  if(tail > n+1) tail = 0;
  else tail++;
}
 
void dequeue(){
  printf("%s %d\n",Q[head].name, Q[head].t+c);
}
 
int main(){
  int i;
   
  scanf("%d %d", &n, &q);
  for ( i = 1; i <= n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  head = 1;
  tail = n+1;
  i = 1;
  while(head != tail){
    if(Q[head].t > q){
    enqueue();
    c = c + q;
    }
    else{
      dequeue();
      c = c + Q[head].t;
    }
  if(head > n+1) head = 0;
  else head++;
  }
  return 0;
}

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

int main(void){
 


    string S;
    cin>>S;
    int N,T,t;
    N=S.size();
    T=0;
    t=0;

    if(S[0]!='A'){
        cout<<"WA"<<endl;
                return 0;  
    }

    for(int i=2;i<=(N-2);i++){
        if(S[i]=='C'){
            T=T+1;
        }
    }
    if(T!=1){
        cout<<"WA"<<endl;
        return 0;  
    }
    
    for(int i=1;i<N;i++){    
        if('a' <=S[i] && S[i] <= 'z'){
            t=t+1;
        }
    }

    if(t==N-2){
        cout<<"AC"<<endl;
    }else{
        cout<<"WA"<<endl;
    }

    return 0;
}

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

int main(){
  int n,w;
  bool table[100100];
  int f[1000],num;

  cin >> n >> w;
  int cnt = w;
  cout << cnt << (w==n?"\n":" ");
  for(int i=1;i<=w;i++)table[i] = true;
  for(int i=w+1;i<=n;i++)table[i] = false;

  for(int z=w+1;z<=n;z++){
    int prv = z-w;
    num = 0;
    for(int i=1;i*i<=prv;i++){
      if(prv%i==0){
	f[num++] = i;
	if(i*i!=prv)f[num++] = prv/i;
      }
    }

    for(int i=0;i<num;i++){
      if(!table[f[i]])continue;
      int pre = (prv+1)/f[i];
      if((prv+1)%f[i]!=0)pre++;
      int suf = (z-1)/f[i];
      if(suf-pre<=0){
	table[f[i]] = false;
	cnt--;
      }
    }
    
    num = 0;
    for(int i=1;i*i<=z;i++){
      if(z%i==0){
	f[num++] = i;
	if(i*i!=z)f[num++] = z/i;
      }
    }
    
    for(int i=0;i<num;i++){
      if(table[f[i]])continue;
      int pre = (prv+1)/f[i];
      if((prv+1)%f[i]!=0)pre++;
      int suf = (z-1)/f[i];
      if(suf-pre>=0){
	table[f[i]] = true;
	cnt++;
      }
    }
    table[z] = true; cnt++;

    cout << cnt << (z==n?"\n":" ");
  }
}
    

Measured memory_bytes: 1264
#include <bits/stdc++.h>
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nyan "(=^･ω･^=)"
#define mkp make_pair
#define lP pair<ll, ll>
#define iP pair<int,int>
typedef long long ll;
using namespace std;

string S;

int main() {
	cin >> S;
	if (S[5] == '0' && S[6] <= '4')
		cout << "Heisei" << endl;
	else
		cout << "TBD" << endl;
	return 0;
}

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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
ll MOD = 1e9+7;
//ll MOD = 998244353;
ll INF = 1e18;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void anss(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}   
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}

int main(){
  ll i,j,o;
  ll res=0,res1=0,res2=INF,buf=0,buf1=0,buf2=0,buf3=0,buf4=0;
  bool judge = true;
  ll n;cin>>n;
  vector<ll> hash(8);
  for(i=0;i<n;i++){
    cin>>buf;
    if(buf<3200){
      if(hash[buf/400]==0){
        res++;
        hash[buf/400]=1;
      }
    }
    else{
      res1++;
    }
  }
  if(res!=0){
  cout<<res spa res+res1<<endl;
  }
  else{
    cout<<1 spa res1<<endl;
  }


  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
  int n,q;
  scanf("%d",&n); 
  int a[n];
  for(int i=0;i<n;i++){
      scanf("%d",&a[i]);
  }
  scanf("%d",&q);
  for(int i=0;i<q;i++){
      int b,e,com,x=0,y;
      scanf("%d %d %d",&com,&b,&e);
      x=a[b];
      
          for(int j=b;j<e;j++){
              
              if(com==0){
              if(x>a[j]){
                  y=x; x=a[j]; 
              }
              }
              else {
                  if(x<a[j]){
                      y=x; x=a[j];
                  }
              }
          }
          printf("%d\n",x);
        
      }
   return 0;
    }



Measured memory_bytes: 2112
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

void solve() {
  int n;
  cin >> n;
  rep(_, n) {
    vvi v(9, vi(9)), c(9, vi(9));
    rep(i, 9) rep(j, 9) cin >> v[i][j];
    rep(i, 9) rep(j, 9) {
      int x  = v[i][j];
      auto f = [&]() {
        int c = 0;
        rep(k, 9) c += v[i][k] == x;
        return c > 1;
      };
      auto g = [&]() {
        int c = 0;
        rep(k, 9) c += v[k][j] == x;
        return c > 1;
      };
      auto h = [&]() {
        int c = 0;
        rep(k, 3) rep(l, 3) c += v[i / 3 * 3 + k][j / 3 * 3 + l] == x;
        return c > 1;
      };
      c[i][j] = f() || g() || h();
    }
    rep(i, 9) {
      rep(j, 9) cout << (c[i][j] ? "*" : " ") << v[i][j];
      cout << endl;
    }
    if (_ != n - 1) cout << endl;
  }
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
constexpr double EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max()/2;
constexpr int MOD = 1e9+7;

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

    int n,k;cin>>n>>k;
    if(n%k==0) cout<<0<<endl;
    else cout<<1<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) {
    if (b==0) return a;
    else return gcd(b, a%b);
}

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

ll choose2(ll n){
    return n*(n-1)/2;
}

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    int ans = c - (a - b);
    if(ans <= 0) ans = 0;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
s = input()
n = int(input())
for i in range(n):
    tmp = input().split()
    a = int(tmp[1])
    b = int(tmp[2])
    if tmp[0] == "print":
        print(s[a:b+1])
    elif tmp[0] == "reverse":
        s = s[:a] + s[a:b+1][::-1] + s[b+1:]
    elif tmp[0] == "replace":
        s = s[:a] + tmp[3] + s[b+1:]


Measured memory_bytes: 5608
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#ifndef LOCAL
#define cerr if(0)cout
#endif
typedef long long ll;
const int mod = 1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it, len;
	fastio() {it=len=0;}
	inline char get()
	{
		if (it<len) return s[it++]; it=0;
		len=fread(s, 1, 100000, stdin);
		if (len==0) return EOF; else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while (c==' '||c=='\n') c=get();
		if (it>0) it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0; bool ng=0; char c; c=_buff.get();
	while (c!='-'&&(c<'0'||c>'9')) c=_buff.get();
	if (c=='-') ng=1, c=_buff.get();
	while (c>='0'&&c<='9') r=r*10+c-'0', c=_buff.get();
	return ng?-r:r;
}
template <class T> inline void putnum(T x)
{
	if (x<0) putchar('-'), x=-x;
	register short a[20]={}, sz=0;
	while (x) a[sz++]=x%10, x/=10;
	if(sz==0) putchar('0');
	for (int i=sz-1; i>=0; i--) putchar('0'+a[i]);
}
inline char getreal() {char c=_buff.get(); while (c<=32) c=_buff.get(); return c;}
ll qpow(ll x, ll k) {return k==0? 1: 1ll*qpow(1ll*x*x%mod,k>>1)*(k&1?x:1)%mod;}
int n, m;
char g[1011][1011];
int dis[1011][1011];
int q[2000111], qn;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int main()
{
	getii(n, m);
	memset(dis, -1, sizeof(dis));
	for (int i=1; i<=n; i++) for (int j=1; j<=m; j++)
	{
		g[i][j] = getreal();
		if (g[i][j]=='#')
		{
			q[qn++] = i;
			q[qn++] = j;
			dis[i][j] = 0;
		}
	}
	int ans = 0;
	for (int i=0; i<qn; i+=2)
	{
		int x = q[i], y = q[i+1];
		for (int d=0; d<4; d++)
		{
			int nx = x+dx[d], ny = y+dy[d];
			if (nx>=1&&nx<=n&&ny>=1&&ny<=m&&dis[nx][ny]==-1)
			{
				dis[nx][ny]=dis[x][y]+1;
				q[qn++] = nx;
				q[qn++] = ny;
				ans = dis[nx][ny];
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 13184
import numpy as np
N = int(input())

*V, = map(int, input().split())
*C, = map(int, input().split())

V   = np.array(V)
C   = np.array(C)


C   = V-C

sum = 0

for i in range(N):
    if C[i] > 0:
        sum = sum + C[i]

print(sum)




Measured memory_bytes: 15756
#include <iostream>

using namespace std;
int len[]={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 main(){
    int K;
    cin>>K;
    cout<<len[K-1]<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

LL gcd(LL x, LL y) {
    while (1) {
	if (x) y %= x; else return y;
	if (y) x %= y; else return x;
    }
}
const int MAX = 20000;
int min_factor[MAX+1];
vector<int>prime;
void make_prime() {
    for (int i=2; i<=MAX; i+=2) min_factor[i] = 2;
    for (int i=3; i<=MAX; i+=3) if (!min_factor[i]) min_factor[i] = 3;
    for (int i=5, d=2; i*i<=MAX; ) {
	if (!min_factor[i]) {
	    min_factor[i] = i;
	    for (int j=i*i; j<=MAX; j+=i)
		if (!min_factor[j]) min_factor[j] = i;
	}
	i += d; d = 6 - d;
    }
    for (int i=2; i<=MAX; i++) {
	if (min_factor[i]==0) min_factor[i] = i;
	if (min_factor[i]==i) prime.push_back(i);
    }
}

int N;
int A[10011];
VI ans;

void go() {
    LL g = 0;
    REP (i, N) g = gcd(g, abs(A[i]));
    for (int i=2; i*i<=g; i++) {
	if (g % i == 0) {
	    ans.push_back(i);
	    while (g % i == 0) g /= i;
	}
    }
    if (g > 1) ans.push_back(g);
}

void MAIN() {
    make_prime();
    scanf("%d", &N);
    N++;
    REP (i, N) scanf("%d", A+i);
    reverse(A, A+N);

    go();

    for (int i=0; prime[i]<=N; i++) {
	int p = prime[i];
	bool ok = (A[0] % p == 0);
	for (int s=0; ok && s<N && s<p-1; s++) {
	    LL sum = 0;
	    for (int t=s; t<N; t+=p-1) {
		sum += A[t];
	    }
	    if (sum % p != 0) {
		ok = false;
		break;
	    }
	}

	eprintf("%d %d\n", (int)p, ok);
	if (ok) ans.push_back(p);
    }

    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    REP (i, ans.size()) printf("%d\n", ans[i]);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
    int a,b;
    cin>>a>>b;
    string s;
    cin>>s;
    int f=0;
    for(int i=0;i<s.length();i++){
        if(i!=a){
            if(s[i]=='-'){
                cout<<"No";
                f=1;
                break;
            }
        }else if(i==a){
            if(s[i]=='-'){
                continue;
            }else {
                cout<<"No";
                f=1;
                break;
            }    
        }
    }
    if(f==0)cout<<"Yes";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define INF 100005
#define MOD 1000000007

int main()
{
	//freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    int n;
    cin >> n;
    int a[n+5];
    int tot=0;
    for(int i=0;i<n;i++)
    {
    	int num;
    	cin >> num;
    	a[i]=num;
    	tot=tot+num;
    }
    tot=tot/n;
    int tot2=tot+1;
    int temp=0;
    int temp2=0;
    for(int i=0;i<n;i++)
    {
    	temp=temp+((a[i]-tot)*(a[i]-tot));
    	temp2=temp2+((a[i]-tot2)*(a[i]-tot2));
    }
    cout << min(temp,temp2) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define pa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};

using ll = long long;
using namespace std;
using P = pair<int,int>;
ll mod=1e9+7;

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a; } //最大公約数
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; } //最大公倍数

int main(){
  int a,b;
  cin>>a>>b;
  if (a > 8 || b > 8){
    cout << ":(" << endl;
  }else{
    cout << "Yay!" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef long long int lli;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

int main(){
    string s;
    cin >> s;
    int sz = s.size();
    int cnt = 0;
    rep(i, sz/2){
        if (s[i] != s[sz-i-1]) cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
 
int main(){
 int A,B,C;
 
 cin >> A >> B >> C;
 
 if (A == 5 && B == 7 && C == 5){
     cout << "YES" << endl; 
 }
 else if (B == 5 && A == 7 && C == 5){
     cout << "YES" << endl;
 } 
 else if (A == 5 && C == 7 && B == 5){
     cout << "YES" << endl;
 }
 else{
     cout << "NO" << endl;}
     return 0;}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cctype>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template<typename key, typename val>
//using ordered_tree =
//  tree<key, val, std::less<>, rb_tree_tag, tree_order_statistics_node_update>;
using namespace std;
typedef long long int64;
typedef unsigned long long uint64;
typedef complex<double> comp;
const double pi = 3.14159265358979323846;
const int inf = (int)1e+9 + 2;
const int64 inf64 = (int64)1e+18 + 2;
const double dinf = 1e+20;
const int mod = 1'000'000'007;//*/998244353;
const int base = 2187;
const double eps = 1e-9;
const int N = 300'000;
const int LOGN = 19;

int n, m, k;

void solve(int) {
  cin >> n;
  double x = n / 3.;
  cout.setf(ios::fixed);
  cout.precision(11);
  cout << x * x * x << '\n';
}

void precalc() {
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  precalc();
  int test = 1;
  //cin >> test;
  //auto start = chrono::high_resolution_clock::now();
  for (int i = 1; i <= test; ++i) {
    solve(i);
  }
  //cerr << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() << '\n';
  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(a)  (a).begin(),(a).end()
typedef long long ll;
ll mod=1000000007;

int main() {
  ll n;cin >>n;
  vector<ll> v(n);
  int cnt_minus = 0;
  ll out = 0LL;
  for(ll i=0;i<n;++i){
    cin >> v[i];
    if(v[i]<0) {
      ++cnt_minus;
      v[i] *= -1;
    }
    out += v[i];
  }
  sort(all(v));
  if(cnt_minus%2 == 1) out -= 2* v[0];
  cout << out << endl;
  return 0;
}


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

int main() {
	string s;
	cin >> s;
	int l = (int)s.size();
	while (l > 0) {
		l--;
		string t, u;
		t = s.substr(0, l / 2);
		u = s.substr(l / 2, l - l / 2);
		if (t == u) break;
	}
	cout << l << endl;
	return 0;
}

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

#define int long long
#define ll long long
#define f1(i,a,b) for(i=a;i<b;i++)
#define f2(i,a,b) for(i=a;i>=b;i--)
#define endl '\n'
#define pb push_back
#define gp " "
#define ff first
#define ss second
#define mp make_pair

const int mod=1000000007;
int i,j;
ll temp;

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // #ifndef ONLINE_JUDGE
    //     freopen("in.txt","r",stdin);
    //     freopen("out.txt","w",stdout);
    // #endif
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    f1(i,0,n)
    {
        if(i==k-1)
            cout<<char(s[i]-'A'+'a');
        else
        cout<<s[i];
    }
    return 0;
}

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

int main() {
    int n; cin >> n;
    vector<int> f(3, 0);

    for(int i = 0; i < n; ++i) {
        int x; cin >> x;
        int cnt = 0;
        while(x % 2 == 0) {
            x /= 2;
            cnt += 1;
        }
        cnt = min(cnt, 2);
        f[cnt] += 1;
    }

    if(f[0] > f[2] + 1) {
        cout << "No\n";
        return 0;
    } else if(f[0] == f[2] + 1) {
        if(f[1] == 0) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
      return 0;
    } else {
        cout << "Yes\n";
    }
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      	String n = sc.next();
	   	if(n.charAt(0)=='9' || n.charAt(1)=='9'){
        	System.out.println("Yes");
        }else{
        	System.out.println("No");
        }
    }
}

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

int main() {
    int N;
    string S;
    cin >> S;
    N = S.length();
    string ans = "Yes";

    for(int i = 0; i < N; i++){
        char tmp;
        tmp = S[i];
        if(i % 2 == 0){
            if(tmp != 'h'){
                ans = "No";
                break;
            }
        }
        else{
            if(tmp != 'i'){
                ans = "No";
                break;
            }
        }
    }
    if(N % 2 == 1) ans = "No";

    cout << ans << endl;
}

Measured memory_bytes: 256