akhauriyash/Code-Regression huggingface dataset:
import sys
readline = sys.stdin.readline
import math

def main():
    N = int(readline())
    CSF = [list(map(int, readline().rstrip().split())) for _ in range(N-1)]
    
    for i in range(N):
        t = 0
        for c, s, f in CSF[i:]:
            m = (t - s) / f
            m = max(math.ceil(m), 0)
            t = s + f * m + c
        print(t)


if __name__ == '__main__':
    main()

Measured memory_bytes: 3188
n, x = map(int, input().split())

num = [2 ** (i + 2) - 3 for i in range(n+1)]
pnum = [2 ** (i+1) - 1 for i in range(n+1)]

def ans(m, y):
  if m == 0:
    return 1
  elif y == 1:
    return 0
  elif y < 2 ** (m + 1) - 1:
    return ans(m - 1, y - 1)
  elif y == 2 ** (m+1) -1:
    return pnum[m-1] + 1
  elif y != num[m]:
    r = y - (2 ** (m+1)-1)
    return pnum[m-1] + 1 + ans(m-1, r)
  else:
    return pnum[m]

print(ans(n, x))


Measured memory_bytes: 3188
#include <cstdio>
#include <cstdlib>
#include <cmath>

const int LEN = 100005;

typedef struct pp {
    char name[100];
    int t;
} P;

P queue[LEN];

int head, tail, n;

void enqueue(P p) {
    queue[tail] = p;
    tail = (tail + 1) % LEN;
}

P dequeue() {
    P p = queue[head];
    head = (head + 1) % LEN;
    return p;
}

int main() {
    int elaps = 0, c;
    int q;
    P p;
    scanf("%d %d", &n, &q);

    for (int i = 1; i <= n; ++i) {
        scanf("%s", queue[i].name);
        scanf("%d", &queue[i].t);
    }

    head = 1;
    tail = n + 1;

    while (head != tail) {
        p = dequeue();
        c = p.t < q ? p.t : q;
        elaps += c;
        p.t -= c;
        if (p.t > 0) {
            enqueue(p);
        } else {
            printf("%s %d\n", p.name, elaps);
        }
    }

    return 0;
}



Measured memory_bytes: 12740
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
ll ans = 0, d[N];
int a[N], b[N], c[N];

int main() {
  int n;
  scanf("%d", &n);
  for(int i = 1; i <= n; ++i) 
    scanf("%d", &a[i]);
  for(int i = 1; i <= n; ++i)
    scanf("%d", &b[i]);
  for(int i = 1; i <= n; ++i)
    scanf("%d", &c[i]);
  sort(a + 1, a + 1 + n);
  sort(b + 1, b + 1 + n);
  sort(c + 1, c + 1 + n);
  int lt = 0;
  for(int i = 1; i <= n; ++i) {
    while(lt + 1 <= n && a[lt + 1] < b[i]) lt++;
    d[i] = lt;
  }
  lt = 0;
  ll now = 0;
  for(int i = 1; i <= n; ++i) {
    while(lt + 1 <= n && b[lt + 1] < c[i]) lt++, now += d[lt];
    ans += now;
  }
  printf("%lld\n", ans);
  return 0;
}

Measured memory_bytes: 2176
def input_int():
    return(int(input()))

def input_int_list():
    return(list(map(int,input().split())))

def input_int_map():
    return(map(int,input().split()))


def run():
    a, b, x = input_int_map()
    result = count_num(b, x) - count_num(a - 1, x)
    print(result)

def count_num(num, x):

    if num < 0:
        return 0

    return num // x + 1

run()

# 2 4 3

# 3 4 3

# 2 6 3

















Measured memory_bytes: 61820
#include <stdio.h>
const int N=1e5+10;
int min(int a,int b){return a>b?b:a;}
int abs(int n){return n>0?n:-n;}
int a[N],ans[N];
int dp(int n){
if(n<=1)return 0;
  if(n==2)return abs(a[n]-a[n-1]);
if(ans[n]>=0)return ans[n];
return ans[n]=min(abs(a[n]-a[n-1])+dp(n-1),abs(a[n]-a[n-2])+dp(n-2));
}
int main(){
int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++)scanf("%d",&a[i]);
  for(int i=1;i<=n;i++)ans[i]=-1;
  printf("%d\n",dp(n));
}

Measured memory_bytes: 2560
#include <cstdio>
#include <algorithm>
const long long MOD = 1000000007;
int N, M, A, B, a[1000][1000];
long long K;
long long POWER(long long a, long long b)
{
	long long r = 1;
	for (; b; b >>= 1)
	{
		if (b & 1)
			r = r * a % MOD;
		a = a * a % MOD;
	}
	return r;
}
struct matrix
{
	long long a, b, c, d;
	inline matrix operator * (const matrix &y)
	{
		return { (a * y.a + b * y.c) % MOD, (a * y.b + b * y.d) % MOD, (c * y.a + d * y.c) % MOD, (c * y.b + d * y.d) % MOD };
	}
};
int main()
{
	scanf("%d%d%lld", &N, &M, &K);
	if (K <= 1)
	{
		puts("1");
		return 0;
	}
	for (int i = 0; i < N; i++)
	{
		static char _a[1001];
		scanf("%s", _a);
		for (int j = 0; j < M; j++)
			a[i][j] = _a[j] == '#';
	}
	for (int i = 0; i < M; i++)
		if (a[0][i] && a[N - 1][i])
		{
			A = 1;
			break;
		}
	for (int i = 0; i < N; i++)
		if (a[i][0] && a[i][M - 1])
		{
			B = 1;
			break;
		}
	if (A && B)
	{
		puts("1");
		return 0;
	}
	if (!A && !B)
	{
		long long c = 0;
		for (int i = 0; i < N; i++)
			c += std::count(a[i], a[i] + M, 1);
		printf("%lld\n", POWER(c, K - 1));
		return 0;
	}
	if (A)
	{
		int D = std::max(N, M);
		for (int i = 0; i < D; i++)
			for (int j = i + 1; j < D; j++)
				std::swap(a[i][j], a[j][i]);
		std::swap(N, M);
	}
	int Side = 0, Block = 0, Connect = 0;
	for (int i = 0; i < N; i++)
	{
		if (a[i][0] && a[i][M - 1])
			Side++;
		for (int j = 0; j < M; j++)
			if (a[i][j])
				Block++;
		for (int j = 1; j < M; j++)
			if (a[i][j - 1] && a[i][j])
				Connect++;
	}
	matrix r = { 1, 0, 0, 1 }, a = { Block, (MOD - Connect) % MOD, 0, Side };
	for (long long b = K - 1; b; b >>= 1)
	{
		if (b & 1)
			r = r * a;
		a = a * a;
	}
	printf("%lld\n", (r.a + r.b) % MOD);
	return 0;
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int H, A;
    cin >> H >> A;

    int ans = H / A;
    if (H % A) ans++;

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

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

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

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

    vector<int> l(n),r(n);
    for(int i=0;i<n-1;i++) l[i+1]=gcd(l[i],a[i]);
    for(int i=n-1;i>=1;i--) r[i-1]=gcd(r[i],a[i]);
    int ans=0;
    for(int i=0;i<n;i++) ans=max(ans,gcd(l[i],r[i]));
    cout<<ans<<endl;
}

Measured memory_bytes: 1408
#ifndef _TEMPLATE_ROOT
#define _TEMPLATE_ROOT
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define repl(i, a, b) for(ll i = a; i < (b); ++i)
#define repd(i, a, b) for(int i = a; i >= (b); --i)
#define repdl(i, a, b) for(ll i = a; i >= (b); --i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
#endif
#ifndef _TEMPLATE_IO
#define _TEMPLATE_IO

template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); }
template<typename ...T> void writef(T ...tail) { write(tail...); cout << flush; }
template<typename ...T> void die(T ...tok) { write(tok...); exit(0); }
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  if (v.size()) {
    rep(i, 0, sz(v) - 1)
      out << v[i] << " ";
    out << v.back();
  }
  return out;
}
#endif
using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

  vi ans;
  
  int n; read(n);
  int a[n + 1];
  rep(i, 1, n + 1)
    read(a[i]);
  repd(i, n, 1) {
    int id = 0;
    rep(j, 1, i + 1)
      if (a[j] == j)
        id = j;
    if (!id)
      die(-1);
    rep(j, id, i)
      a[j] = a[j + 1];
    ans.push_back(id);
  }
  reverse(all(ans));
  for (int i : ans) write(i);
}



Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        int ans=0;
        for(int i=1;i<=n/2;i++){
            if(i!=n-i) ans++;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

Measured memory_bytes: 256
pub fn read1<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

pub fn readn<T: std::str::FromStr>(delimiter: &str) -> Vec<T> {
    let s = read1::<String>();
    s.split(delimiter).map(|e| e.parse().ok().unwrap()).collect::<Vec<T>>()
}

pub struct UnionFind {
    pub par: Vec<usize>,
    pub rank: Vec<usize>,
}

impl UnionFind {
    pub fn new(n: usize) -> UnionFind {
        let par = (0..n).collect::<Vec<usize>>();
        let rank = vec![0; n];
        UnionFind { par: par, rank: rank }
    }

    pub fn root(&mut self, x: usize) -> usize {
        let cand = self.par[x];
        if cand == x {
            return x;
        } else {
            let ret = self.root(cand);
            self.par[x] = ret;
            return ret;
        }
    }

    pub fn same(&mut self, x: usize, y: usize) -> bool {
        self.root(x) == self.root(y)
    }

    pub fn unite(&mut self, x: usize, y: usize) {
        let root_x = self.root(x);
        let root_y = self.root(y);
        if root_x == root_y { return; }

        if self.rank[root_x] < self.rank[root_y] {
            self.par[root_x] = self.par[root_y];
        } else {
            self.par[root_y] = self.par[root_x];
            if self.rank[root_y] == self.rank[root_x] {
                self.rank[root_x] += 1;
            }
        }
    }
}

fn main() {
    let nm = readn::<usize>(" ");
    let n = nm[0];
    let m = nm[1];
    let p = readn::<usize>(" ");
    let mut uf = UnionFind::new(n);

    for _ in 0..m {
        let xy = readn::<usize>(" ");
        let x = xy[0] - 1;
        let y = xy[1] - 1;
        uf.unite(x, y);
    }

    let root = (0..n).map(|i| uf.root(i)).collect::<Vec<usize>>();

    let mut ans = 0;
    for i in 0..n {
        if root[i] == root[p[i]-1] {
            ans += 1;
        }
    }

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

Measured memory_bytes: 8444
#include <bits/stdc++.h>
#define _xx ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
typedef long long ll;

ll C(ll n,ll m)
{
    if(m==0||n==m) return 1;
    ll sb=min(m,n-m);
    ll f=1,f1;
    for(ll i=1;i<=sb;i++)
    {
        f1=f*(n-i+1)/(i);
        f=f1;
    }
    return f1;
}
int main()
{
    string s;
    cin>>s;
    int ans=0;
    for(int i=0;i<3;i++){
        if(s[i]=='o') ans++;
    }
    ans=ans*100+700;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    int a,b,d;
    char c;
    while(cin>>a>>c>>b&&!(c=='?'))
    {
        if(c=='+')
        {
            d=a+b;
        }
        else if(c=='-')
        {
            d=a-b;
        }
        else if(c=='*')
        {
            d=a*b;
        }
        else
            d=a/b;
        cout<<d<<endl;
    }
return 0;
}

Measured memory_bytes: 3092
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int MAX_N = 15;
int h, w, N;
string dir = "RDLU";
char field[MAX_N][MAX_N];
char route[50];
bool range_check(int y, int x) { return (y < 0 || x < 0 || y >= h || x >= w) ? true : false; }
void dfs(int y, int x, int pos, int cnt)
{
    if(cnt == N) 
    {
        for(int i = 0; i < N; i++) cout << route[i];
        cout << endl;
        return;
    }
    for(int i = 0; i < 4; i++)
    {
        if(i == (pos + 2) % 4) continue;
        int ty = y, tx = x;
        while(!range_check(ty, tx))
        {
            if(field[ty][tx] == 'o')
            {
                //cout << ty << " " << tx << " " << cnt << endl;
                field[ty][tx] = '.';
                route[cnt] = dir[i];
                dfs(ty, tx, i, cnt + 1);
                field[ty][tx] = 'o';
                break;
            }
            ty += dy[i];
            tx += dx[i];
        }
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> h >> w;
    int sy, sx, spos;
    for(int i = 0; i < h; i++)
    {
        for(int j = 0; j < w; j++)
        {
            char ch;
            cin >> ch;
            field[i][j] = ch;
            if(ch == 'o') N++;
            if(ch != '.' && ch != 'o')
            {
                sy = i, sx = j;
                for(int k = 0; k < dir.size(); k++) if(dir[k] == ch) spos = k;
            }
        }
    }
    dfs(sy, sx, spos, 0);
    return 0;
}


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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (int i = (int)a; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
#define EPS 1e-12

int main(void) {
  while (true) {
    double n, p;
    int m;
    cin >> n >> m >> p;
    if(!n && !m && !p) break;
    double x[100], sum = 0;
    REP(i, n) {
      cin >> x[i];
      sum += x[i];
    }
    //cout << sum << endl;
    //cout << (sum * 100 * (1 - p / 100)) << " " << x[m - 1] << endl;

    if (x[m - 1] == 0)
      cout << 0 << endl;
    else {
      double temp = (sum * (100-p));
      int ans = temp/x[m-1];
      cout << ans << endl;
    }
    //cout << (int)((sum * 100 * (1 - p / 100)) / x[m - 1]) << endl;
  }
  return 0;
}

Measured memory_bytes: 3132
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"
int main() {
	int N; cin >> N;
	int a = 1;
	for (int i = 0; i < a; ++i) {
		
		vector<int>nums;
		while (N) {
			nums.push_back(N % 3);
			N /= 3;
		}
		nums.push_back(0);
		reverse(nums.begin(), nums.end());
		for (int i = nums.size()-1; i >=0; --i) {
			if (nums[i] >= 2) {
				nums[i - 1] ++;
				nums[i] -=3;
			}
		}
		if (*nums.begin() == 0)nums.erase(nums.begin());
		for (auto n : nums) {
			if (n == 0)cout << '0';
			else if (n == 1)cout << '+';
			else if (n == -1)cout << '-';
			else assert(false);
		}
		cout << endl;
	}
	
	return 0;
}

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

typedef long long ll;
const int mod = 1e+9 + 7;

ll r1, r2, c1, c2;

ll qPow(ll a, ll b)
{
    a %= mod;
    
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return res;
}

ll C(ll n, ll m)
{
    if(n < m) return 0;
    
    ll res = 1;
    for(int i = 1; i <= m; ++i)
        res = res * (n - i + 1) % mod * qPow(i, mod - 2) % mod;
    return res;
}

int main()
{
    scanf("%lld%lld%lld%lld", &r1, &c1, &r2, &c2);
    
    ++r2, ++c2;
    printf("%lld", ((C(r2 + c2, c2) - C(r1 + c2, c2) - C(r2 + c1, c1) + C(r1 + c1, c1)) % mod + mod) % mod);
}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.HashSet;
import java.math.BigDecimal;

public class Main {
    public static void main(String[] args) {
        FastScanner fs = new FastScanner();
        long a = fs.nextLong();
        double b = fs.nextDoutble();
     	BigDecimal b1 = BigDecimal.valueOf(a);
	    BigDecimal b2 = new BigDecimal(String.valueOf(b));
	    BigDecimal t3 = (b1.multiply(b2));
        System.out.println(t3.longValue()); 

        
  }
  public static int calcMin(int[] array) {

    int intMin = array[0];

    for (int i = 1; i < array.length; i++ ) {
        if(intMin > array[i]) {
            intMin = array[i];
        }
    }
    return intMin;
}
}
class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte(){
        if(ptr < buflen){
            return true;
        }else{
            ptr = 0;
            try{
                buflen = in.read(buffer);
            }catch(IOException e){
                e.printStackTrace();
            }
            if(buflen <=0){
                return false;
            }
        }
        return true;
    }

    private int readByte(){
        if(hasNextByte())return buffer[ptr++];
        else return -1;
    }

    private static boolean isPrintableChar(int c){
        return 33<=c && c<=126;
    }
    public boolean hasNext(){
        while(hasNextByte() && !isPrintableChar(buffer[ptr]))ptr++;
        return hasNextByte();
    }

    public String next(){
        if(!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)){
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong(){
        if(!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        if(b < '0' || '9' < b){
            throw new NumberFormatException();
        }
        while(true){
            if('0' <= b && b<='9'){
                n*=10;
                n+=b-'0';
            }else if(b==-1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt(){
        long nl = nextLong();
        if(nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDoutble(){return Double.parseDouble(next());}
}


Measured memory_bytes: 33460
using System;
using System.Linq;

class Node{
  public int key = 0;
  public int parent = 0;
  public int left = 0;
  public int right = 0;
}

class Max{
  public void maxHeap(ref Node[] node,int i){
    int left = i * 2, right = i * 2 + 1,large = i;
    Node change = new Node();
    if(left < node.Length && node[left].key > node[i].key){
      large = left;
    }if(right < node.Length && node[right].key > node[large].key){
      large = right;
    }if(large != i){
      change = node[large];
      node[large] = node[i];
      node[i] = change;
      maxHeap(ref node,large);
    }
  }
}

class B9{
  public static void Main(){
   int n = int.Parse(Console.ReadLine());
   Node[] node = new Node[n + 1];
   for(int i = 0;i <= n;i++){
     node[i] = new Node();
   }
   int[] input = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
   for(int i = 0;i < n;i++){
     node[i + 1].key = input[i];
   }
   for(int i = 1;i <= n;i++){
     if(i / 2 > 0){
       node[i].parent = node[i / 2].key;
     }
     if(i * 2 <= n){
       node[i].left = i * 2;
     }
     if(i * 2 + 1 <= n){
       node[i].right = 2 * i + 1;
     }
   }
   Max max = new Max();
   for(int i = n / 2;i > 0;i--){
     max.maxHeap(ref node,i);
   }
   for(int i = 1;i <= n;i++){
     Console.Write(" " + node[i].key);
   }
   Console.WriteLine();
  }
}



Measured memory_bytes: 72368
module app;

import core.bitop;

import std.algorithm;
import std.array;
import std.bigint;
import std.conv;
import std.stdio;
import std.string;
import std.traits;

struct Input
{
	int[][] a;
    int n;
    int[] b;
}

void parseInput(T)(out Input input, T file)
{
	with (file) with (input)
	{
        foreach (i; 0..3)
            a ~= readln().strip().split().map!(to!int).array();
		n = readln().strip().to!int;
        foreach (i; 0..n)
            b ~= readln().strip().to!int;
	}
}

auto main2(Input* input)
{
	with (input)
	{
        foreach (bb; b)
            foreach (aa; a)
                foreach (ref aaa; aa)
                    if (aaa == bb)
                        aaa = 0;
        for (int i = 0; i < 3; i++)
        {
            if (a[i].all!((e)=>e==0))
                return "Yes";
        }
        for (int i = 0; i < 3; i++)
        {
            if (a.map!((e)=>e[i]).all!((e)=>e==0))
                return "Yes";
        }

        if (a[0][0] == 0 && a[1][1] == 0 && a[2][2] == 0)
            return "Yes";

        if (a[0][2] == 0 && a[1][1] == 0 && a[2][0] == 0)
            return "Yes";

        return "No";
	}
}

alias retType = ReturnType!main2;
static if (!is(retType == void))
{
	unittest { writeln("begin unittest"); }
	auto _placeholder_ = ReturnType!main2.init;

	unittest // example1
	{
		string example =
`84 97 66
79 89 11
61 59 7
7
89
7
87
79
24
84
30`;
		if (example.empty) return;
		Input input = void;
		parseExample(input, example);
		auto result = main2(&input);
		printResult(result);
		assert(result == "Yes");
	}

	unittest // example2
	{
		string example =
`41 7 46
26 89 2
78 92 8
5
6
45
16
57
17`;
		if (example.empty) return;
		Input input = void;
		parseExample(input, example);
		auto result = main2(&input);
		printResult(result);
		assert(result == "No");
	}

	unittest // example3
	{
		string example =
`60 88 34
92 41 43
65 73 48
10
60
43
88
11
48
73
65
41
92
34`;
		if (example.empty) return;
		Input input = void;
		parseExample(input, example);
		auto result = main2(&input);
		printResult(result);
		assert(result == "Yes");
	}

	unittest { writeln("end unittest"); }

	void parseExample(out Input input, string example)
	{
		struct Adapter
		{
			string[] _lines;
			this(string input) { _lines = input.splitLines(); }
			string readln() { auto line = _lines[0]; _lines = _lines[1..$]; return line; }
		}
		parseInput(input, Adapter(example));
	}
}

void printResult(T)(T result)
{
	static if (isFloatingPoint!T) writefln("%f", result);
	else writeln(result);
}

void main()
{
	Input input = void;
	parseInput(input, stdin);
	alias retType = ReturnType!main2;
	static if (is(retType == void))
		main2(&input);
	else
	{
		auto result = main2(&input);
		printResult(result);
	}
}


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

namespace ProconLib{
    struct MonoidExample{
        using value_t=int;
        static constexpr value_t E(){return 0;}
        static value_t op(value_t lhs,value_t rhs){return lhs+rhs;}
    };
    template<class Monoid>
    class SegmentTree{
        public: 
        using value_t= typename Monoid::value_t;
        private:
        std::vector<value_t> dat;
        int N;
        static int calcN(int n){int res=1; while(res<n) res*=2; return res;}
        value_t queryImpl(int a,int b,int k,int l,int r);

        public:
        SegmentTree(int N);
        void update(int pos,value_t val);        
        void updateALL(std::vector<value_t> x);
        value_t query(int a,int b);
    };

    template<typename Monoid>
    SegmentTree<Monoid>::SegmentTree(int n):N(calcN(n)),dat(2*N-1,Monoid::E()){}

    template<typename Monoid>
    void SegmentTree<Monoid>::update(int pos,value_t val){
        pos+=N-1;
        dat[pos]=val;
        while(pos!=0){
            int par=(pos-1)/2;
            dat[par]=Monoid::op(dat[par*2+1],dat[par*2+2]);
            pos=par;
        }
    }

    template<typename Monoid>
    void SegmentTree<Monoid>::updateALL(std::vector<value_t> x){
        for(int i=0;i<x.size();i++) dat[N-1+i]=x[i];
        for(int i=N-2;i>=0;i--) dat[i]=Monoid::op(dat[i*2+1],dat[i*2+2]);
    }

    template<typename Monoid>
    typename SegmentTree<Monoid>::value_t SegmentTree<Monoid>::query(int a,int b){
        return queryImpl(a,b,0,0,N);
    }

    template<typename Monoid>
    typename SegmentTree<Monoid>::value_t SegmentTree<Monoid>::queryImpl(int a,int b,int k,int l,int r){
        if(a<=l && r<=b) return dat[k];
        if(r<=a || b<=l) return Monoid::E();
        int mid=(l+r)/2;
        value_t c1v=queryImpl(a,b,k*2+1,l,mid);
        value_t c2v=queryImpl(a,b,k*2+2,mid,r);
        return Monoid::op(c1v,c2v);
    }
}

/*verfy(AOJ DSL_2_A)*/
#include<iostream>
using namespace ProconLib;
struct MyMonoid{
    using value_t=int;
    static constexpr value_t E(){return (1u<<31)-1;}
    static value_t op(value_t lhs,value_t rhs){return std::min(lhs,rhs);}
};

int main(){
    int n,q;
    std::cin>>n>>q;
    SegmentTree<MyMonoid> seg(n);
    for(int i=0;i<q;i++){
        int com,x,y;
        std::cin>>com>>x>>y;
        if(com){
            y++;
            std::cout<<seg.query(x,y)<<std::endl;
        }
        else{
            seg.update(x,y);
        }
    }
    return 0;
}



Measured memory_bytes: 35576
N, K = map(int, input().split())
P = (N-1)*(N-2)//2
if K > P:
    print(-1)
    exit()
M = (N-1)+ (P-K)
print(M)
for i in range(2,N+1):
    print(1, i)
cnt = 1
i = 2
j = i+1
while cnt <= P-K:
    if j > N:
        i+= 1
        j = i+1
    print(i, j)
    j += 1
    cnt += 1


Measured memory_bytes: 74584
import sys
input = sys.stdin.readline
N=int(input())
ki=[[] for f in range(N)]
for i in range(N-1):
 u,v,w = map(int,input().split())
 ki[u-1].append([v-1,w%2])
 ki[v-1].append([u-1,w%2])
stack = [[0,0]]
check = [0]*N #チェック済みリスト
ans=[2]*N
ans[0]=0
while stack != [] :
 a=stack.pop()
 if check[a[0]]==0:
  check[a[0]]=1
  for i in range(len(ki[a[0]])):
   if check[ki[a[0]][i][0]]==0:
    stack.append([ki[a[0]][i][0],(ki[a[0]][i][1]+ans[a[0]])%2])
    ans[ki[a[0]][i][0]]=(ki[a[0]][i][1]+ans[a[0]])%2
for i in ans:
 print(i)


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

int main(){
    long long s;
    cin >> s;

    long long ans1 = ceil(sqrt(s));
    long long Y = ans1 * ans1 - s;
    if(Y == 0){
        cout << 0 << " " << 0 << " " << ans1 << " " << 0 << " " << 0 << " " << ans1 << endl;
    }else{
        cout << 0 << " " << 0 << " " << ans1 << " " << 1 << " " << Y << " " << ans1 << endl;        
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <limits>
#include <functional>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define in(v) cin>>v;
#define out(v) cout<<v<<"\n"
const int INF = numeric_limits<int>::max();
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template <typename T> T gcd(T a, T b){return b?gcd(b,a%b):a;}

template<class T> struct SegTree {
  private:
    int size;
    vector<T> v;
    using F = function<T(T,T)>;
    F f; T default_value;
  public:
    SegTree(int n, T default_value, F f) : default_value(default_value), f(f) {
      size = 1;
      while (size < n) size *= 2;
      v.resize(2 * size - 1, default_value);
    }
    void update(int index, T val) {
      index = index + size - 1;
      v[index] = val;
      while (index > 0) {
        index = (index - 1) / 2;
        v[index] = f(v[2 * index + 1], v[2 * index + 2]);
      }
    }
    T query(int l, int r) { return query(l, r, 0, size, 0); }
    T query(int l, int r, int cur_l, int cur_r, int index) {
      // [l, r)に対するクエリ
      if (cur_r <= l || r <= cur_l) return default_value;
      if (l <= cur_l && cur_r <= r) return v[index];

      int mid = (cur_l + cur_r) / 2;
      return f(query(l, r, cur_l, mid, 2 * index + 1), query(l, r, mid, cur_r, 2 * index + 2));
    }
};



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

SegTree<int> T(N, 0, [](int a, int b){return gcd(a, b);});
  rep(i, N) {
    int a; in(a);
    T.update(i, a);
  }
  int ans = 1;
  rep(i, N) {
    int l = T.query(0, i),
        r = T.query(i+1, N);
    if (l == INF)
      chmax(ans, r);
    else if (r == INF)
      chmax(ans, l);
    else
      chmax(ans, gcd(l, r));
  }
  out(ans);

  return 0;
}


Measured memory_bytes: 1280
//おまじない
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#define INF 1e9+7
#define rep(i,m,n) for(int i=m;i<n;i++)
#define mrep(i,m,n) for(int i=m;i>n;i--)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない

int main(){

	int m, n;
	ll mod = 1000000007;
	ull mon = 1;
	ull dog = 1;

	cin >> n >> m;  //nイヌ　mサル

	if (abs(m - n) > 1) {
		cout << 0 << endl;
		return 0;
	}
	else if (abs(m - n) == 0) {
		rep(i, 1, n+1) {
			mon = (mon * i)%mod;
		}
		dog = mon;
		cout << mon * dog * 2 % mod << endl;
	}
	else {
		rep(i, 1, m+1) {
			mon = (mon * i)%mod;
		}
		rep(i, 1, n + 1) {
			dog = (dog * i)%mod;
		}
		cout << (mon * dog)%mod << endl;
	}



	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  private static class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
      reader = new BufferedReader(new InputStreamReader(in));
      tokenizer = null;
    }

    public String next() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public String nextLine() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          return reader.readLine();
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }

      return tokenizer.nextToken("\n");
    }

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

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

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

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

    public long[] nextLongArray(int n) {
      long[] a = new long[n];
      for (int i = 0; i < n; i++)
        a[i] = nextLong();
      return a;
    }
  }

  public static void main(String[] args) {
    FastScanner sc = new FastScanner(System.in);
    String s = sc.next();
    if (s.length() == 2) {
      System.out.println(s);
      return;
    }
    System.out.println(new StringBuilder(s).reverse().toString());
  }
}

Measured memory_bytes: 32856
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long lint;
const int N=302;
const int mod=1e9+7;
int n,m,dp[N][N];
struct limit{
	int l,r,x;
	bool operator < (const limit b) const {
		return r<b.r;
	}
}lt[N];

inline void twk(int &x){
	if(x>=mod) x-=mod;
}

inline int nxi(){
	int x=0;
	char c;
	while((c=getchar())>'9'||c<'0');
	while(x=x*10+c-48,(c=getchar())>='0'&&c<='9');
	return x;
}

int main(){
#ifndef ONLINE_JUDGE
	//  freopen("a.in","r",stdin);
#endif
	n=nxi(),m=nxi();
	for(int i=1;i<=m;++i){
		lt[i].l=nxi();
		lt[i].r=nxi();
		lt[i].x=nxi();
	}
	std::sort(lt+1,lt+m+1);
	dp[0][0]=1;
	for(int q=1,i=1;i<n;++i){
		int p=i&1;
		while(lt[q].r<i&&q<=m) ++q;
		for(int j=i;j>=0;--j){
			for(int k=i;k>=j;--k){
				int tp=q,f=0;
				while(lt[tp].r==i){
					if((k>=lt[tp].l)+(j>=lt[tp].l)+1!=lt[tp].x){
						f=1;
						break;
					}
					++tp;
				}
				if(f==1){
					dp[j][k]=0;
					continue;
				}
				int cur=dp[j][k];
				twk(dp[j][i]+=cur);
				if(j!=k) twk(dp[k][i]+=cur);
			}
		}
	}
	for(int j=0;j<=n;++j){
		for(int k=j;k<=n;++k){
			int tp=m,f=0;
			while(lt[tp].r==n){
				if((k>=lt[tp].l)+(j>=lt[tp].l)+1!=lt[tp].x){
					f=1;
					break;
				}
				--tp;
			}
			if(f) dp[j][k]=0;
		}
	}
	int ans=0;
	for(int i=0;i<=n;++i){
		for(int j=i;j<=n;++j){
			if(i==0&&j==0) ans=(ans+(lint)dp[i][j]*3)%mod;
			else ans=(ans+(lint)dp[i][j]*6)%mod;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#define H 251

int main()
{
	int i,n;
	int A[H];
	
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&A[i]);
	}
	
	for(i=1;i<=n;i++){
		printf("node %d: key = %d, ",i,A[i]);
		
		if(i/2 != 0){
			printf("parent key = %d, ",A[i/2]);
		}
		
		if(2*i <= n){
			printf("left key = %d, ",A[2*i]);
		}
		
		if(2*i+1 <= n){
			printf("right key = %d, ",A[2*i+1]);
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 600
#include<iostream>
#include<vector>
#include<string>
#include<stdlib.h>
using namespace std;
typedef long long ll;

ll absint(ll a){
    if (a<0)
        return -a;
    else
        return a;
}
int main(){
    int N;
    cin >> N;
    vector<int> X(N);
    vector<int> Y(N);
    vector<int> h(N);
    vector<int> non_zero_set(3);
    for(size_t i = 0; i < N; i++)
    {
        cin >> X[i] >> Y[i] >> h[i];
        if(h[i]!=0)
            non_zero_set = {X[i], Y[i], h[i]};
    }
    for(size_t x = 0; x < 101; x++) // 100
    {
        for(size_t y = 0; y < 101; y++) // 100
        {
            bool ok = true;
            ll H = non_zero_set[2] + absint(x-non_zero_set[0]) + absint(y-non_zero_set[1]);
            for(size_t i = 0; i < N; i++) // 100
            {
                ll thish = max<ll>(H - absint(x-X[i]) - absint(y-Y[i]), 0);
                if (h[i] != thish){
                    ok = false;
                    break;
                }
            }
            if (ok) {
                if (H == -1)
                    H = 1; // otherwise the center cannot be determined
                cout << x << " " << y << " " << H << endl;
                return 0;
            }   
        }
    }
    return 0;
}

Measured memory_bytes: 256
///Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
#define u64 uint64_t
#define ll long long
#define endl "\n"
#define PI acos(-1)
#define pi pair<ll,ll>
#define fi first
#define si second
#define mkp make_pair
#define pb push_back
#define clr(arr) memset(arr,0,sizeof(arr))
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
deque<ll>dq;
map<ll,ll>mp;
set<ll>st;
vector<ll>vt;
ll mod=1e9+7;
const int N=1e6+5;
ll arr[N];

int main()
{
    IOS;
    ll n,m,x,y,z,i,j,k,p,f=0,tc,cnt=0,sum=0,mul=1,mi=1e18,ma=-1e18,a,b,c,d,sz;
    string str;
    char ch;
    double db;
    //code
    cin>>n>>k>>x>>y;
    k=min(n,k);
    sum+=x*k;
    k=n-k;
    if(n>k)
        sum+=y*k;
    cout<<sum<<endl;




    //code
    return 0;
}


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

int main(){
	double x1,y1,x2,y2;
	double distance;
	
	cin >> x1 >> y1 >> x2 >> y2;
	
	distance = sqrt(pow(x1-x2,2) + pow(y1-y2,2));
	
	printf("%.5f\n",distance);
	return 0;
}

Measured memory_bytes: 1236
program main
	implicit none
    integer(8):: N,i,j,k
	character(200000):: S,T
	read *, S
	read *, T	
	k=0
	do i=1,Len(S)
	if(S(i:i)/=T(i:i))k=k+1	
	end do
	print'(I0)',k
end program main

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

int main(){
    int X, N;
    cin >> X >> N;
    vector<int> p(N);
    for(int i=0; i<N; i++) cin >> p.at(i);
    vector<bool> P(102, true);
    for(int i=0;i<N; i++) P.at(p.at(i)) = false;
    if(P.at(X)) cout << X << endl;
    else{
        int l = X - 1;
        int R = X + 1;
        while(true){
            if(P.at(l)){
              cout << l << endl;
              break;
            }
            if(P.at(R)){
                cout << R << endl;
                break;
            }
            l--;
            R++;
        }
    }
}

Measured memory_bytes: 3600
#AtCorder Beginner Contest 081 B-Shift only
num = int(input())
list = [int(x) for x in input().split()]

cnt = 0
min = 100000000000

for i in list:
    while i%2 == 0:
        i = i/2
        cnt += 1
    if cnt == 0:
        min = cnt
        break
    elif cnt < min:
        min = cnt
    cnt = 0

print(str(min))

Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))


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

    string s;
    cin >> s;

    int n = s.size();

    vs64 num(2019, 0);
    num[0]++;
    int remain = 0;
    s64 mul = 1;
    for (int i = n - 1; i >= 0; --i)
    {
        int temp = (s64)(s[i] - '0') * mul % 2019;
        remain = (temp + remain) % 2019;
        ++num[remain];
        mul = mul * 10 % 2019;
    }

    s64 ans = 0;
    rep (i, 2019)
    {
        ans += num[i] * (num[i] - 1) / 2;
    }

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



Measured memory_bytes: 3784
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional> 
#include <iomanip>
#include <unordered_map>
#include <memory.h>

using namespace std;
 
int main(void)
{
	int n, a, b;
	int sum = 0;

	cin >> n >> a >> b;

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

		while (num > 0)
		{
			digit += (num % 10);
			num /= 10;
		}

		if (digit >= a && digit <= b)
		{
			sum += i;
		}
	}

	cout << sum << '\n';

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n, x, a[30]; bool dp[1000001], prime[1000001]; vector<int> p;
int main() {
	for(int i = 2; i <= 1000000; i++) prime[i] = true;
	for(int i = 2; i <= 1000; i++) {
		if(!prime[i]) continue;
		for(int j = i * i; j <= 1000000; j += i) prime[j] = false;
	}
	p = {0};
	for(int i = 2; i <= 1000000; i++) {
		if(prime[i]) p.push_back(i);
	}
	while(scanf("%d%d", &n, &x), n) {
		for(int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n);
		for(int i = 0; i < x; i++) dp[i + 1] = false; dp[0] = true;
		for(int i = 1; i <= x; i++) {
			for(int j = 0; j < n && i >= a[j]; j++) {
				if(dp[i - a[j]]) {
					dp[i] = true; break;
				}
			}
		}
		int pos = upper_bound(p.begin(), p.end(), x) - p.begin();
		for(int i = pos - 1; i >= 0; i--) {
			if(dp[p[i]]) {
				printf(i ? "%d\n" : "NA\n", p[i]); break;
			}
		}
	}
}

Measured memory_bytes: 5004
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main{
	static final Scanner s=new Scanner(System.in);
	static int getInt(){
		return Integer.parseInt(s.next());
	}
	static int m,t,p,r;
	static class Team{
		int wa[],time=0,id,ac;
		Team(int ID){
			id=ID;
			wa=new int[p];
		}
		int getId(){
			return id;
		}
		int getTime(){
			return time;
		}
		int getAc(){
			return ac;
		}
		Integer getRank(){
			return ac*10000000-time;
		}
	}
	public static void main(String[] __){
		while(true){
			m=getInt();
			if(m==0) return;
			t=getInt();
			p=getInt();
			r=getInt();
			
			Team[] teams=IntStream.rangeClosed(1,t).mapToObj(Team::new).toArray(Team[]::new);
			for(int i=0;i<r;i++){
				int m=getInt(),t=getInt(),p=getInt(),j=getInt();
				final Team team=teams[t-1];
				switch(j){
				case 0:
					team.time+=m+team.wa[p-1]*20;
					team.ac++;
					break;
				default:
					team.wa[p-1]++;
					break;
				}
			}
			TreeMap<Integer,TreeSet<Integer>> v=Arrays.stream(teams)
					.collect(Collectors.groupingBy(
							Team::getRank,
							()->new TreeMap<>(Comparator.<Integer> reverseOrder()),
							Collectors.mapping(Team::getId,Collectors.toCollection(
									()->new TreeSet<>(Comparator.<Integer> reverseOrder())))));
			System.out.println(
					v.entrySet().stream().map(
							o->o.getValue().stream()
									.map(Object::toString)
									.collect(Collectors.joining("=")))
							.collect(Collectors.joining(",")));
		}
	}
}

Measured memory_bytes: 57904
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 2147483647 / 2;
const long long int llINF = 9223372036854775807 / 2;

using namespace std;
using ll = long long int;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;

typedef pair<ll, ll> pll;
bool paircomp(const pll &a, const pll &b) {
  if (a.first == b.first)
    return a.second < b.second;
  return a.first < b.first;
}

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define RREP(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define ARGMAX(vec)                                                            \
  std::distance(vec.begin(), std::max_element(vec.begin(), vec.end()))
#define ARGMIN(vec)                                                            \
  std::distance(vec.begin(), std::min_element(vec.begin(), vec.end()))
#define REV(T) greater<T>()
#define PQ(T) priority_queue<T, vector<T>, greater<T>>
#define VVL(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define VVVL(a, b, c, d)                                                       \
  vector<vector<vector<ll>>>(a, vector<vector<ll>>(b, vector<ll>(c, d)))
#define SP(a) setprecision(a)
#define SQRT(a) sqrt((long double)(a))
#define DPOW(a, b) pow((long double)(a), (long double)(b))
#define UNIQUE(vec)                                                            \
  do {                                                                         \
    sort(ALL((vec)));                                                          \
    (vec).erase(std::unique(ALL((vec))), (vec).end());                         \
  } while (0)

ll POW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = POW(n, m / 2);
    return (tmp * tmp);
  } else {
    return (n * POW(n, m - 1));
  }
}

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  string S;
  cin >> S;
  regex e("x");
  string po = regex_replace(S, e, "");
  bool ok = true;
  ll posize = po.size();
  REP(i, posize / 2) {
    if (po[i] != po[posize - 1 - i])
      ok = false;
  }
  if (!ok)
    cout << -1 << endl;
  else {
    ll r = S.size() - 1;
    ll l = 0;
    ll ans = 0;
    while (l < r) {
      // cout << l << "," << r << endl;
      if (S[l] == S[r]) {
        l++;
        r--;
      } else if (S[l] == 'x') {
        ans++;
        l++;
      } else if (S[r] == 'x') {
        ans++;
        r--;
      }
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define F first
#define S second
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define maxp 22
#define EPS (ld)(1e-18)
#define mod (int)(1e9+7)
#define N (int)(1e5+1)


int main (){
fastio;

int x,n;
set<int> s;
cin>>x>>n;
int i;
for(i=0;i<n;i++){
    int temp;
    cin>>temp;;
    s.insert(temp);
}

int l=x,r=x;

while(1){
    if(s.count(l)==0){
        cout<<l;
        return 0;
    }
    if(s.count(r)==0){
        cout<<r;
        return 0;
    }
    l--;
    r++;

}



}


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

double helperfn(vector<double> &p,int i,int count,int total,vector<vector<double> >& dp)
{
	if(count==total)
		return 1;
	if(i==p.size())
		return 0;
	if(dp[i][count]!=-1)
		return dp[i][count];
	dp[i][count]= (p[i]*helperfn(p,i+1,count+1,total,dp))+helperfn(p,i+1,count,total,dp)*(1-p[i]);
	return dp[i][count];
}

int main()
{
	int n;
	cin >> n;
	vector<double> p(n);
	for(int i=0;i<n;i++)
		cin >> p[i];
	double ans=0;
	// cout<<endl;
	
	vector<double> ab(n+1,-1.0);
	vector<vector<double> >dp(n+1,ab);

		ans+=helperfn(p,0,0,n/2+1,dp);
		// cout<<ans<<endl;
	

	cout<<fixed<<setprecision(10)<<ans;
	return 0;
}

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

using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  map<int, vector<int>> PtoY;
  vector<int> P(M), Y(M);
  for (int i = 0; i < M; ++i) {
    cin >> P[i] >> Y[i];
    PtoY[P[i]].push_back(Y[i]);
  }
  for (auto& p : PtoY) sort(p.second.begin(), p.second.end());
  for (int i = 0; i < M; ++i)
    printf("%06d%06d\n", P[i],
           lower_bound(PtoY[P[i]].begin(), PtoY[P[i]].end(), Y[i]) -
               PtoY[P[i]].begin() + 1);
  return 0;
}

Measured memory_bytes: 13184
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#include<set> 
using ll = long long;
int main(){
  int n;
  cin>>n;
  if(n<100){
    if(n%10==3)cout<<"bon"<<endl;
    else if(n%10==0||n%10==1||n%10==6||n%10==8)cout<<"pon"<<endl;
    else cout<<"hon"<<endl;
  }
  if(n>=100){
    n = n%100;
    if(n%10==3)cout<<"bon"<<endl;
    else if(n%10==0||n%10==1||n%10==6||n%10==8)cout<<"pon"<<endl;
    else cout<<"hon"<<endl;
  }
  
  
  



}


Measured memory_bytes: 3592
#include <iostream>
#include <map>

#define rep(i, n) for(int i=0; i<n; i++)

using namespace std;

int main(){
  string S;
  cin >> S;
  // 入力終了

  map<char, int> count;
  rep(i, S.size() ){
    count[ S[i] ]++;
  }

  // 東に移動するが，西には移動しない
  if(count['E'] > 0 && count['W'] == 0){
    cout << "No" << endl;
    return 0;
  }

  // 西に移動するが，東には移動しない                                                     
  if(count['W'] > 0 && count['E'] == 0){
    cout << "No" << endl;
    return 0;
  }

  // 南に移動するが，北には移動しない                                                     
  if(count['S'] > 0 && count['N'] == 0){
    cout << "No" << endl;
    return 0;
  }

  // 北に移動するが，南には移動しない                                                     
  if(count['N'] > 0 && count['S'] == 0){
    cout << "No" << endl;
    return 0;
  }

  // 上記以外ならOK
  cout << "Yes" << endl;
  
  
  return 0;
}


Measured memory_bytes: 3644
#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
map<long long,long long> a;
int n;
long long tot;
int h[201000];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&h[i]);
		a[h[i]-i]++;
	}
	for(int i=1;i<=n;i++)
	{
		tot+=a[-h[i]-i];
	}
	cout<<tot;
}

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

#define ll long long
#define F first
#define S second
#define ii pair < int , int >
#define ever (;;)

const int N = 410;

bool vis[N][N];
int n;
ll mem[N][N],a[N],cum[N];

ll dp(int l,int r)
{
    if( l == r )
        return 0;

    ll &ret = mem[l][r];
    if( vis[l][r] == 1 )
        return ret;
    vis[l][r] = 1;

    ret = 1e18;

    for(int i=l;i<r;i++)
        ret = min( ret , cum[r] - cum[l-1] + dp(l,i) + dp(i+1,r) );

    return ret;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        cum[i] = cum[i-1] + a[i];
    }

    printf("%lld\n",dp(1,n));
}


Measured memory_bytes: 1664