akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main
{
  private static ArrayList<Integer> primeNumberList = new ArrayList<>();

  public static void main(String[] args) throws NumberFormatException, IOException
  {
    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    ArrayList<Integer> inputList = new ArrayList<>(50);

    while (input.ready())
    {
      int inputNum = Integer.valueOf(input.readLine());
      if (inputNum == 0)
      {
        break;
      }
      inputList.add(inputNum);
    }

    int max = 0;
    for (Integer each : inputList)
    {
      if (max < each)
        max = each;
    }

    setPrimeNumberList(max);

    for (int num : inputList)
    {
      System.out.println(sumOfPrimeNumbers(num));
    }
  }

  private static int sumOfPrimeNumbers(int count)
  {
    int ans = 0;
    for (int i = 0; i < count; i++)
    {
      ans += primeNumberList.get(i);
    }
    return ans;
  }

  private static void setPrimeNumberList(int listSize)
  {
    int num = 3;

    primeNumberList.add(2);
    while (primeNumberList.size() < listSize)
    {
      if (isPrimeNumber(num))
      {
        primeNumberList.add(num);
      }
      num++;
    }
  }

  private static boolean isPrimeNumber(int number)
  {
    final int limit = (int) Math.sqrt(number);
    for (int each : primeNumberList)
    {
      if (number % each == 0)
      {
        return false;
      }
      if (each > limit)
      {
        break;
      }
    }
    return true;
  }
}

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

const double PI = 3.14159;
const int modi = 1e9+7;
int main(){
	int n,k;
	cin >> n >> k;
	long long pref[n+1],suff[n+1];
	pref[0] = 0;
	suff[n]=n;
	long long ans = 0;
	for(long long i =1;i<=n;i++){
		pref[i]=pref[i-1]+i;
		suff[n-i] = suff[n-i+1] + (n-i);
	}

	for(int i =k;i<=n;i++){
		ans = ans+(suff[n-i+1]- pref[i-1]+1);
		ans%=modi;
		// cout << ans << endl;
	}
 	ans++;
 	ans%=modi;
	cout << ans << endl;

}

Measured memory_bytes: 6772
import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)

  val n = sc.nextInt

  val a = (1 to 9).find{ num =>
    n % num == 0 && 1 <= (n / num) && (n / num) <= 9
  }

  val res = if(a.nonEmpty) "Yes" else "No"

  println(res)



}


Measured memory_bytes: 27332
#include<bits/stdc++.h>
#define all(x) x.begin() , x.end()
#define ll long long 
#define pb push_back
#define mp make_pair

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n , a , b;cin>>n>>a>>b;
    cout<<min(n * a , b)<<endl;

}

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

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int x[n];
    int sum = 0;
    for(int i = 0; i < n; i++) {
        scanf("%d", x + i);
        sum += x[i];
    }

    int pos = round((double)sum / n);

    int temp;
    int res = 0;
    for(int i = 0; i < n; i++) {
        temp = x[i] - pos;
        res += temp * temp;
    }

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

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

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

using namespace std;

int main(){
	string s; cin>>s;
	cout<<((s.length()%2==0)==(s.front()==s.back())?"First":"Second")<<'\n';
	return 0;
}


Measured memory_bytes: 512
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

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

var sc = bufio.NewScanner(os.Stdin)

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

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

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

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

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

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

type item struct {
	priority, value, index int
}

type pQ []*item

func (pq pQ) Len() int {
	return len(pq)
}

func (pq pQ) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

func (pq pQ) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *pQ) Push(x interface{}) {
	n := len(*pq)
	it := x.(*item)
	it.index = n
	*pq = append(*pq, it)
}

func (pq *pQ) Pop() interface{} {
	old := *pq
	n := len(old)
	it := old[n-1]
	it.index = -1
	*pq = old[0 : n-1]
	return it
}

// End Priority Queue
type link struct {
	u, v, a, b int
}

type edge struct {
	to, cost int
}

type node struct {
	e []edge
}

const inf = 1001001001001001

func dijkstra(s, N int, n []node) []int {
	pq := make(pQ, 0)
	heap.Init(&pq)
	dist := make([]int, N)
	for i := 0; i < N; i++ {
		dist[i] = inf
	}
	dist[s] = 0
	heap.Push(&pq, &item{0, s, 0})
	for pq.Len() > 0 {
		it := heap.Pop(&pq).(*item)
		v := it.value
		if dist[v] < it.priority {
			continue
		}
		for _, e := range n[v].e {
			if dist[e.to] > dist[v]+e.cost {
				// out(v, e)
				dist[e.to] = dist[v] + e.cost
				heap.Push(&pq, &item{dist[e.to], e.to, 0})
			}
		}
	}
	return dist
}

func pos(n, c, m int) int {
	return n*m + c
}

func main() {
	sc.Split(bufio.ScanWords)

	N, M, S := getInt(), getInt(), getInt()
	ma := 0
	l := make([]link, M*2)
	for i := 0; i < M; i++ {
		u, v, a, b := getInt()-1, getInt()-1, getInt(), getInt()
		l[i*2] = link{u, v, a, b}
		l[i*2+1] = link{v, u, a, b}
		ma = max(ma, a)
	}

	c := make([]int, N)
	d := make([]int, N)
	for i := 0; i < N; i++ {
		c[i], d[i] = getInt(), getInt()
	}

	// make nodes
	ma *= N
	n := make([]node, ma*N)
	for i := 0; i < N; i++ {
		// out("---", ma)
		for j := 0; j <= ma; j++ {
			to := j + c[i]
			cost := d[i]
			if to >= ma {
				break
			}
			f := pos(i, j, ma)
			t := pos(i, to, ma)
			// out(f, "->", t, cost)
			n[f].e = append(n[f].e, edge{t, cost})
		}
	}
	for i := 0; i < M*2; i++ {
		from := l[i].u
		to := l[i].v
		coin := l[i].a
		cost := l[i].b
		for j := 0; j < ma; j++ {
			if j-coin < 0 {
				continue
			}
			f := pos(from, j, ma)
			t := pos(to, j-coin, ma)
			// out(from, to, "f,t", f, t, cost, len(n))
			n[f].e = append(n[f].e, edge{t, cost})
		}
	}

	S = min(S, ma-1)
	dist := dijkstra(S, ma*N, n)

	for i := 1; i < N; i++ {
		m := inf
		for j := 0; j < ma; j++ {
			m = min(m, dist[i*ma+j])
		}
		// out(dist[i*ma : (i+1)*ma])
		out(m)
	}
	//out("dist=", dist)
}


Measured memory_bytes: 31864
n = int(input())
s = input()
count = 0

for i in range(n-2):
    #print(s[i],s[i+1],s[i+2])
    if s[i] == "A":
        if s[i+1] == "B":
            if s[i+2] == "C":
                count += 1
print(count)

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



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(var,cnt) for(int (var)=0; (var)<(int)(cnt); ++(var))
#define Rep(var,init,cnt) for(int (var)=(init); (var)<(cnt); ++(var))
#define ran(var,vec) for(auto &(var):(vec))
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define SORT(v) sort(all(v))
#define RSORT(v) sort(rall(v))
#define SUM(v) accumulate(all(v),0)
#define tget(tp,idx) get<idx>(tp)
#define TF(flag) (flag)?1:0
#define yn(f) cout<<(f?"yes":"no")<<endl
#define Yn(f) cout<<(f?"Yes":"No")<<endl
#define YN(f) cout<<(f?"YES":"NO")<<endl
#define COUT(x) cout<<(x)<<endl
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using ti = tuple<int,int,int>;
using tl = tuple<ll,ll,ll>;

template<typename T>
using vec = vector<T>;
template<typename T>
using mat = vector<vec<T>>;
template<typename T>
using cub = vector<mat<T>>;
template<typename T>
using val = valarray<T>;

template<typename T>
using pq = priority_queue<T>;
template<typename T>
using rpq = priority_queue<T,vec<T>,greater<T>>;

template<typename T1,typename T2>
ostream &operator<<(ostream &os, const pair<T1,T2> &p){
  os<<"P("<<p.first<<", "<<p.second<<") ";
  return os;
}

template<typename T1,typename T2>
istream &operator>>(istream &is, pair<T1,T2> &p){
  is>>p.first>>p.second;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  cout<<"V{";
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  cout<<"}";
  return os;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &v){
  for(T &in:v) is>>in;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const valarray<T> &v){
  cout<<"V{";
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  cout<<"}";
  return os;
}

template<typename T>
istream &operator>>(istream &is, valarray<T> &v){
  for(T &in:v) is>>in;
  return is;
}

// Usual Template End ================================================

// Template End ======================================================

constexpr int MOD=1e9+7;

int main(void){
  vec<int> v(3); cin>>v; SORT(v); COUT(v[2]-v[0]);
}













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

typedef long long ll;
static const ll MOD = 998244353;
static const int MAX = 500000+100;

ll fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll ModPow(ll a, ll cur=MOD-2) {
	ll r=1;
	while(cur) r=r*((cur%2)?a:1)%MOD,a=a*a%MOD,cur>>=1;
	return r;
}


int main(){
    ll N,M,K;
    cin>>N>>M>>K;
    /*
    先頭の選び方がM
    iが[0,K]で、
    先頭と同じ色のブロックの選び方はcomb(N-1,i)
    残りのブロックの色の選び方はM^(N-1-i);
    */

   ll ans = 0;
   COMinit();

   for(int i=0; i<=K; i++){
       ans += M*COM(N-1,i)%MOD*ModPow(M-1,N-1-i)%MOD;
   }

   cout<<ans%MOD<<endl;

    return 0;
}

Measured memory_bytes: 15400
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,n1;
  cin >>a>>b>>n1;
  bool n[1000];
  for(int i=0;i<1000;i++){
    n[i]=0;
  }
  int s[n1];
  int f[n1];
  for(int i=0;i<n1;i++){
    cin >>s[i]>>f[i];
  }
  for(int i=0;i<n1;i++){
    for(int j=s[i];j<f[i];j++){
      n[j]=1;
    }
  }
  int count=0;
  for(int i=a;i<b;i++){
    if(n[i]==0)count++;
  }
  if(count==b-a)cout <<0<<endl;
  else cout <<1<<endl;
}

Measured memory_bytes: 3088
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <tuple>
#include <cstring>
#define FOR0(var, max) for (ui (var) = 0; (var) < (max); ++(var))
#define FOR_INV(var, min, max) for (ui (var) = (max) - 1; (var) + 1 > (min); --(var))
#define FORITER(var, iter) for (auto (iter) = (var).begin(); (iter) != (var).end(); (iter)++)
#define FORITER_INV(var, iter) for (auto (iter) = (var).rbegin(); (iter) != (var).rend(); (iter)++)

using namespace std;

using uc = unsigned char;
using ui = unsigned int;
using ul = unsigned long long int;

const static ui NMAX = 50;

static char S[NMAX];
static char S_[NMAX];
static char T[NMAX];
static ui N;
static ui M;

bool try_replace(ui idx) {
  char cache[NMAX];
  strncpy(cache, S_, N);
  FOR0(j, M) {
    ui k = j + idx;
    if (cache[k] != '?' && cache[k] != T[j]) {
      return false;
    }
    cache[k] = T[j];
  }
  FOR0(j, N) {
    if (cache[j] == '?') {
      cache[j] = 'a';
    }
  }
  if (strncmp(S, cache, N) > 0) {
    strncpy(S, cache, N);
  }
  return true;
}

int main(void) {
  bool is_replaced = false;
  cin >> S_;
  cin >> T;
  N = strlen(S_);
  M = strlen(T);
  strncpy(S, S_, N);
  FOR0(i, N) {
    if (S[i] == '?') {
      S[i] = 'z';
    }
  }
  FOR0(i, N - M + 1) {
    is_replaced |= try_replace(i);
  }
  if (is_replaced) {
    cout << S << endl;
  } else {
    cout << "UNRESTORABLE" << endl;
  }
  return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second

set<ll> divisor(ll n) {
  set<ll> ret;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.insert(i);
      if (i * i != n) ret.insert(n / i);
    }
  }
  return ret ;
}

int main(int argc, char const *argv[]) {
  int n; cin >> n;
  ll _max = 1e6 + 5;
  int dp[_max] = {0};
  vector<int> a(n);
  
  REP(i,n) cin >> a[i];
  for (int i : a) {
    if (dp[i] != 0) {
      dp[i] = 2;
      continue;
    }
    for (int j = i; j <= _max; j += i) dp[j]++;
  }

  int ans = 0;
  for (int now : a) {
    if (dp[now] == 1) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 7940
n=int(input()) 
h=list(map(int,input().split())) 
if n==2: 
    print(abs(h[1]-h[0])) 
else: 
    dp=[0]*(n-1) 
    dp[0]=abs(h[1]-h[0]) 
    dp[1]=min(dp[0]+abs(h[2]-h[1]),abs(h[2]-h[0])) 
    
    for i in range(2,n-1): 
        dp[i]=min(dp[i-1]+abs(h[i+1]-h[i]),dp[i-2]+abs(h[i+1]-h[i-1])) 
        
    print(dp[-1])

Measured memory_bytes: 13980
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(ll i=0;i<n;i++)
#define int long long
using namespace std;
int a[114514], b[114514], c[114514];
signed main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i] >> b[i] >> c[i];
	if ((a[0] - (b[0] + c[0])) % 2 == 0 && a[0] >= b[0] + c[0]) {
		for (int i = 0; i < n-1; i++) {
			if (abs((a[i + 1] - a[i] - abs(b[i] - b[i + 1]) - abs(c[i] - c[i + 1]))) % 2 != 0 || a[i + 1] - a[i] < abs(b[i] - b[i + 1]) + abs(c[i] - c[i + 1])) {
				puts("No");
				return 0;
			}
		}
		puts("Yes");
	}
	else puts("No");
	getchar(); getchar(); return 0;
}

Measured memory_bytes: 2560
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cmath>
#include <queue>

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr ll LLINF {1001002003004005006};//ll = 9*LLINF
constexpr int INTINF {1000000000};//int = 2*INTINF

#define  rep(i,n)   for(int i = 0; i < (n); ++i)
#define rrep(i,n)   for(int i = 1; i <= (n); ++i)
#define drep(i,n)   for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for(int i = s; i < t;  ++i)

template<typename T>
void maxs(T& x, T&& y) {
  x=std::max(x,y);
}
template<typename T>
void maxs(T& x, T& y) {
  x=std::max(x,y);
}

template<typename T>
void mins(T& x, T&& y) {
  x=std::min(x,y);
}
template<typename T>
void mins(T& x, T& y) {
  x=std::min(x,y);
}

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

  ull n;
  cin >> n;

  std::string stone;
  std::cin >> stone;

  std::queue<int> w_pos;
  std::queue<int> r_pos;

  rep(i, n) {
    if (stone[i] == 'W') w_pos.push(i);
  }
  drep(i, n) {
    if (stone[i] == 'R') r_pos.push(i);
  }

  ull ans {};
  for (;w_pos.size() != 0 && r_pos.size() != 0;++ans) {
    int w_p = w_pos.front(); w_pos.pop();
    int r_p = r_pos.front(); r_pos.pop();
    if (w_p > r_p) break;
  }
  cout << ans << '\n';
}


Measured memory_bytes: 4364
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

int d[10][10];
int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W; cin >> H >> W;
    rep(i, 10) rep(j, 10) cin >> d[i][j];
    rep(k, 10) {
        rep(i, 10) {
            rep(j, 10) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    int ans = 0;
    rep(i, H) {
        rep(j, W) {
            int a; cin >> a;
            if(a != -1)
                ans += d[a][1];
        }
    }
    cout << ans << endl;

    return 0;
}


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

using namespace std;

template <typename T>
struct LazySegtree {
	private:
		size_t n;
		vector<T> node, lazy;
		T M0, L0;

	public:
		LazySegtree(size_t sz, T m0, T l0) {
			n = 1;
			M0 = m0;
			L0 = l0;
			while (n < sz) { n *= 2; }
			node.assign(2*n - 1, M0);
			lazy.assign(2*n - 1, L0);
		}

		T merge(T a, T b) { return min(a, b); }
		void updateNode(int k, T x) { lazy[k] = min(lazy[k], x); }
		void propagate(int k) { node[k] = min(node[k], lazy[k]); }

		void eval(int k, int l, int r) {
			if (lazy[k] == L0) { return; }
			propagate(k);
			if (r - l > 1) {
				updateNode(2*k + 1, lazy[k]);
				updateNode(2*k + 2, lazy[k]);
			}
			lazy[k] = L0;
		}

		void update(int a, int b, T x, int k=0, int l=0, int r=-1) {
			if (r < 0) { r = n; }
			eval(k, l, r);
			if (r <= a || b <= l) { return; }
			if (a <= l && r <= b) {
				updateNode(k, x);
				eval(k, l, r);
			} else {
				update(a, b, x, 2*k + 1, l, (l + r) / 2);
				update(a, b, x, 2*k + 2, (l + r) / 2, r);
				node[k] = merge(node[2*k + 1], node[2*k + 2]);
			}
		}

		T query(int a, int b, int k=0, int l=0, int r=-1) {
			if (r < 0) { r = n; }
			eval(k, l, r);
			if (r <= a || b <= l) { return M0; }
			if (a <= l && r <= b) { return node[k]; }
			T vl = query(a, b, 2*k + 1, l, (l + r) / 2);
			T vr = query(a, b, 2*k + 2, (l + r) / 2, r);
			return merge(vl, vr);
		}
};

int main() {
	Int N, Q;
	cin >> N >> Q;
	vector<int> f(Q), x(Q);
	for (int i = 0; i < Q; ++i) {
		cin >> f[i] >> x[i];
	}

	LazySegtree<Int> segH(N, N, N);
	LazySegtree<Int> segW(N, N, N);

	Int ans = (N - 2) * (N - 2);
	for (int i = 0; i < Q; ++i) {
		Int X = x[i];
		if (f[i] == 1) {
			Int t = segW.query(X, X + 1);
			ans -= (t - 2);
			segH.update(1, t, X);
		}
		if (f[i] == 2) {
			Int t = segH.query(X, X + 1);
			ans -= (t - 2);
			segW.update(1, t, X);
		}
	}
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 21148
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define n_l '\n'

#ifndef ONLINE_JUDGE
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; cout << to_string(__VA_ARGS__) << endl
template <typename T, size_t N> int SIZE(const T (&t)[N]){ return N; } template<typename T> int SIZE(const T &t){ return t.size(); } string to_string(const string s, int x1=0, int x2=1e9){ return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c){ return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1=0, int x2=1e9){ string t = ""; for(int __iii__ = min(x1,SIZE(b)),  __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){ t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1=0, int x2=1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if(l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2-x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if(e != l){ if(rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else{ t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if(l_v_l_v_l == 0) res += n_l; return res; } void dbgm(){;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgm(T...); } 
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgm(__VA_ARGS__); cout << endl
#endif

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef double db;
typedef vector<vi> vvi;
const ll mod=1000000007;
const ll N=200005; //check this
int dx[] = {-1, 0, 1, 0, 1, 1, -1, -1};
int dy[] = {0, -1, 0, 1, 1, -1, 1, -1};

ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll powb(ll a,ll b) {ll res=1;a ; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a;a=a*a;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

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

    #ifndef ONLINE_JUDGE
    freopen("inputf.in", "r", stdin);
    freopen("outputf.in", "w", stdout);
    #endif

    int t=1;
    //cin>>t;
    while(t--){
    	ll n;cin>>n;
    	// string s;cin>>s;
    	ll ans=(n+999)/1000;
    	cout<<1000*ans-n;
    }
}


Measured memory_bytes: 3644
import numpy as np
def cumsum(x):
    return list(np.cumsum(x))

def cumsum_number(N,K,x):
    ans=[0]*(N-K+1)
    number_cumsum = cumsum(x)
    number_cumsum.insert(0,0)
    for i in range(N-K+1):
        ans[i]=number_cumsum[i+K]-number_cumsum[i]
    return ans
"""
int #整数
float #小数

#for
for name in fruits: #fruitの頭から操作
    print(name)

#リスト
list0 = [] #リスト生成
list0 = [1,2,3,4] #初期化
list0 = [0]*10 #[0,0,0,0,0,0,0,0,0,0]
list1= [i for i in range(10)] #>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
list1 = list(map(int, input().split()))　# 複数の入力をリストに入れる
number=[int(input()) for i in range(int(input()))] #複数行の入力をリストに
list1 = list1 + [6, 7, 8] #リストの追加
list2.append(34) #リストの追加　最後に（）内が足される
list.insert(3,10) #リストの追加　任意の位置（追加したい位置,追加したい値）
len(list4) #リストの要素数
max(sa) #list saの最小値
list5.count(2) #リスト(文字列も可）内の2の数
list1.sort() #並び替え小さい順
list1.sort(reverse=True)  #並び替え大きい順
set(list1) #list1内の重複している要素を削除し、小さい順に並べる
sum([2,3,   ,3]) #リストの合計

abs(a) #aの絶対値
max(a,b) min(a,b) #最大値　最小値
text1 = text1.replace("34","test") #text1内の"34"を"test"に書き換える(文字列内の文字を入れ替える)

exit(0) #強制終了

cumsum(リスト) #累積和をリストで返す
cumsum_number(N,K,x) #N個の数が含まれるリストx内のK個からなる部分和をリストで返す
"""
K=int(input())
A,B=map(int,input().split())
for i in range(A,B+1):
    if i%K==0:
        print("OK")
        exit(0)
print("NG")


Measured memory_bytes: 27008
def inpl(): return list(map(int, input().split()))

import numpy as np

N = int(input())
X = np.zeros(N, dtype=np.int64)
Y = np.zeros(N, dtype=np.int64)
H = np.zeros(N, dtype=np.int64)

Q = sorted([inpl() for _ in range(N)], key=lambda x: x[2], reverse=True)

for i, q in enumerate(Q):
    X[i], Y[i], H[i] = q

assert H[0] > 0

for cx in range(101):
    for cy in range(101):
        cH = H[0] + np.abs(X[0] - cx) + np.abs(Y[0] - cy)
        if np.all(H == np.maximum(cH - np.abs(X - cx) - np.abs(Y - cy), 0)):
            print(cx, cy, cH)

Measured memory_bytes: 21764
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    if(n==1){
      System.out.println("Hello World");
    }else if(n==2){
          int a = sc.nextInt();
    int b = sc.nextInt();
      System.out.println(a+b);
    }else{
      return;
    }
  }
  

  
}


Measured memory_bytes: 21972
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


q = int(input())
def _sub(a):
    v = []
    for i in range(35):
        a,val = divmod(a,3)
        v.append(val)
    return v
def sub(a,b,c,d):
    va,vb,vc,vd = _sub(a), _sub(b), _sub(c), _sub(d)
    ans = 0
    m1 = True
    m2 = True
    for i in reversed(range(35)):
        aa,bb,cc,dd = va[i],vb[i],vc[i],vd[i]
        if aa==cc==1 and m1 and ((m2 and bb!=dd) or (not m2 and abs(b-d)>2*pow(3,i))):
#             print(aa,bb,cc,dd,m1,m2,i)
            ta = a % pow(3,i)
            tc = c % pow(3,i)
            ans = abs(b-d) + min(ta+tc+2, 2*pow(3,i)-(ta+tc))
            break
        elif bb==dd==1 and m2 and ((m1 and aa!=cc) or (not m1 and abs(a-c)>2*pow(3,i))):
#             print(aa,bb,cc,dd,m1,m2,i)
            tb = b % pow(3,i)
            td = d % pow(3,i)
            ans = abs(a-c) + min(tb+td+2, 2*pow(3,i)-(tb+td))
            break
        else:
            if aa!=cc:
                m1 = False
            if bb!=dd:
                m2 = False
    else:
        ans = abs(a-c) + abs(b-d)
    return ans
ans = [None]*q
for i in range(q):
    a,b,c,d = list(map(lambda x: int(x)-1, input().split()))
    ans[i] = sub(a,b,c,d)
write("\n".join(map(str, ans)))

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

using namespace std;

const int M = 1e5 + 5;

int n, k = 0, colors[M];
vector<array<int, 2>> g[M];

void DFS(int x, int p, int clr) {
    int color = 1;
    for (auto a : g[x]) {
        if (a[0] == p) continue;
        if (color == clr) color++;
        colors[a[1]] = color++;
        DFS(a[0], x, colors[a[1]]);
    }
}

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

    cin >> n;
    for (int i = 1, a, b; i < n; i++) {
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    } // Max Degree = K (Editorial TIME)
    for (int i = 1; i <= n; i++) k = max(k, (int) g[i].size()); cout << k << '\n';
    DFS(1, -1, -1);
    for (int i = 1; i < n; i++) cout << colors[i] << '\n';

    return 0;
}

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

// 型名の省略
typedef unsigned int uint;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> P;
typedef pair<lint, lint> Plint;
 
const int MOD = 1000000007;
const int INF = 1<<18;
const lint INFLINT = 1LL << 60;
const double PI=acos(-1.0);
 
// cinとcoutの高速化
#define endl "\n"
struct cinacc{cinacc(){cin.tie(0);ios::sync_with_stdio(false);}}cinaccc;
struct coutacc{coutacc(){cout.setf(ios::fixed);cout.precision(12);}}coutaccc;
 
// 繰り返し
#define rep(i,n) for(lint i=0;i<(lint)(n);i++)
#define reps(i,n) for(lint i=0;i<=(lint)(n);i++)
#define rrep(i,n) for(lint i=(lint)(n)-1;i>0;i--)
#define rreps(i,n) for(lint i=(lint)(n)-1;i>=0;i--)

#define pb push_back

#define ALL(s) (s.begin(), s.end())
#define SZ(s) (s.size())

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(b<a){a=b;return true;}return false;}

// Union-Find-Tree
class UnionFind {
	vector<int> par;
	UnionFind(int n):par(n){rep(i,n)par[i]=i;}
	int root(int x){if(par[x]==x)return x;return par[x]=root(par[x]);}
	void unite(int x,int y){int rx=root(x);int ry=root(y);if(rx==ry)return;par[rx]=ry;}
	bool same(int x,int y){return root(x)==root(y);}
};

int main() {
    int n, m, x, y;
    string s;
    int a, total = 0;
    
    cin >> n >> m;
    rep(i, m) { 
        cin >> a;
        total += a;
    }
    
    int ans = n - total;
    if(ans < 0) cout << -1;
    else cout << ans;
    
    return 0;
}


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

int main()
{
	int a, b;
	int flag=0;
	int i, j;

	int m4 = (int)pow(4.0, 13);
	int c = m4;
	while (scanf("%d", &a), a != -1){
		flag = 0;
		if (a == 0) printf("0");
		else{
			c = m4;
			for (i = 0; c != 0; c /= 4){
				b = a / c;
				a %= c;
				if (b != 0){ printf("%d", b); flag = 1; }
				else{
					if (flag != 0)printf("0");
				}
			}
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 1032
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(int i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<int,int> Pi;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)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 dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

ll a,b,c,d;

int main(){
	cin>>a>>b>>c>>d;
	ll cd=lcm(c,d);
	ll ca=b/c-(a-1)/c;
	ll da=b/d-(a-1)/d;
	ll cda=b/cd-(a-1)/cd;
	ll ans=(b-a+1)-(ca+da-cda);
	cout<<ans<<endl;
	return 0;
}

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

using namespace std;
using ll = long long int;
#define vll vector<ll>

#define FOR(i, b, e) for(int i = (b); i < (e); ++i)
#define REP(i, e) FOR(i, 0, e)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define OUT(v) cout << (v) << endl;
#define YN(b) OUT((b) ? "YES" : "NO")
#define Yn(b) OUT((b) ? "Yes" : "No")
#define yn(b) OUT((b) ? "yes" : "no")

const ll MOD = 1000000007;

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

  ll n, k, r = 0;
  cin >> n >> k;
  r = n % k;
  r = min(abs(r - k), r);
  cout << r << endl;

  return 0;
}

Measured memory_bytes: 256
h,w,k=map(int,input().split())
c=[]
for _ in range(h): c+=[input()]
ch,cw=[0]*h,[0]*w
for i in range(h):
  ch[i]=c[i].count('#')
for i in range(w):
  for j in range(h):
    cw[i]+=(c[j][i]=='#')
x=sum(ch)-k
a=0
for i in range(2**h):
  for j in range(2**w):
    t=0
    for k in range(h):
      if i>>k&1:
        t+=ch[k]
        for l in range(w):
          if j>>l&1: t-=(c[k][l]=='#')
    for l in range(w):
      if j>>l&1: t+=cw[l]
    if t==x: a+=1
print(a)

Measured memory_bytes: 9236
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define REP(i,x,n) for(int i = (x); i < (n); ++i)
#define ll long long
#define P pair<ll,ll>
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1);

int main(void)
{
    int n, m;
    cin >> n >> m;
    vector<bool> ok(n+1,true);
    rep(i,m){
        int a;
        cin >> a;
        ok[a] = false;
    }
    vector<long long> dp(n+1);
    dp[0]=dp[1]=1;
    if(ok[1]==false) dp[1]--;
    REP(i,2,n+1){
        if(!ok[i]) dp[i] = 0;
        else dp[i] = ((dp[i-1]%mod)+(dp[i-2]%mod))%mod;
        dp[i] %= mod;
    }
    cout << dp[n] << endl;
    return 0;
}


Measured memory_bytes: 3968
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int W, H;
int p[100010], q[100010];
ll cumq[100010];

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> W >> H;
  ll ans = 0;
  for (int i = 0; i < W; i++) {
    cin >> p[i];
    ans += p[i];
  }
  for (int i = 0; i < H; i++) {
    cin >> q[i];
    ans += q[i];
  }
  sort(p, p + W);
  sort(q, q + H);
  for (int i = 0; i < H; i++) {
    cumq[i + 1] = cumq[i] + q[i];
  }
  for (int i = 0; i < W; i++) {
    int pos = upper_bound(q, q + H, p[i]) - q;
    ans += cumq[pos] + (ll)p[i] * (H - pos);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1792
from copy import deepcopy
N, x = map(int, input().split())
A = [int(a) for a in input().split()]

minA = deepcopy(A)
Ans = sum(minA) #全て直接捕まえる場合
for i in range(1, N): #i回魔法を唱える
    for j in range(N):
        minA[j] = min(minA[j], A[j-i])
    Ans = min(Ans, x * i + sum(minA))
print(Ans)

Measured memory_bytes: 3700
def main():
    buf = input()
    buflist = buf.split()
    R = int(buflist[0])
    G = int(buflist[1])
    B = int(buflist[2])
    N = int(buflist[3])
    combination = 0
    for i in range(3001):
        if i * R > N:
            break
        for j in range(3001):
            if i * R + j * G > N:
                break
            if (N - (i * R + j * G)) % B == 0:
                combination += 1
    print(combination)


if __name__ == '__main__':
    main()


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

int main() {
	int n,counter=0;
	string s;
	cin >> n >> s;
	for(int i=0;i<n;i++){
		if(s[i]=='A'&&s[i+1]=='B'&&s[i+2]=='C') counter++;
	}cout << counter;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <map>
#include <set>
using namespace std;
typedef long long ll;

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

	int N;
	cin >> N;

	ll a, b;
	cin >> a >> b;
	N--;
	while(N--) {
		ll T, A;
		cin >> T >> A;
		ll k = 1;
		if(T < a) {
			if(a % T == 0) k = max(k, a / T);
			else k = max(k, a / T + 1);
		}
		if(A < b) {
			if(b % A == 0) k = max(k, b / A);
			else k = max(k, b / A + 1);
		}
		a = T * k, b = A * k;
	}
	cout << a + b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC omodtimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<long long ,long long> ii; 	
typedef complex<long double> com;
 
const ll mod = 998244353;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n;
	cin >> n;
	map <ll,ll> count;
	vector <ll> arr(n);
	for (int z=0;z<n;z++){
		cin >> arr[z];
		count[arr[z]]++;
	}
	ll ans = 0;
	for (ii i : count){
		ans += i.second*(i.second-1)/2; 
	}
	for (int z=0;z<n;z++){
		ans -= count[arr[z]]*(count[arr[z]]-1)/2;
		ans += (count[arr[z]]-1)*(count[arr[z]]-2)/2;
		cout << ans << endl;
		ans -= (count[arr[z]]-1)*(count[arr[z]]-2)/2;
		ans += count[arr[z]]*(count[arr[z]]-1)/2;
	}
}

Measured memory_bytes: 13184
#include<bits/stdc++.h>
using namespace std;
int main(){
  int H,W,cnt=0;
  cin>>H>>W;
  for(int i=0;i<H*W;i++){
    char c;
    cin>>c;
    if(c=='#')cnt++;
  }
  if(cnt==H+W-1)puts("Possible");
  else puts("Impossible");
}

Measured memory_bytes: 3640
#!/usr/bin/env python3
def main():
    from bisect import bisect, bisect_left

    N = int(input())
    A = sorted([int(x) for x in input().split()])
    B = sorted([int(x) for x in input().split()])
    C = sorted([int(x) for x in input().split()])

    print(sum([bisect_left(A, b) * (N - bisect(C, b)) for b in B]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 29124
#include <stdio.h>

int main(void) {
   
   int W,H,x,y;
   
   scanf("%d%d%d%d",&W,&H,&x,&y);
   
   if (W%2 == 0 && H%2 == 0) {
      if (W/2 == x && H/2 == y) {
         printf("%lf %d\n",(double)W*0.5*H, 1);
      }
      else {
         printf("%lf %d\n",(double)W*0.5*H, 0);
      }
   }
   else {
      printf("%lf %d\n",(double)W*0.5*H, 0);
   }
   
   return 0;
   
}


Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <stdarg.h>
#include <algorithm>
#include <iostream>

using namespace std;

int
main() {
  int n;
  scanf("%d\n", &n);
  
  string s;
  cin>>s;

  if (n % 2 == 1) {
    cout<<"No"<<endl;
  }
  else {
    bool valid = true;
    int len = n/2;
    for (int i=0; i<len; i++)
      if (s[i] != s[i+len])
        valid = false;

    if (valid)
      cout<<"Yes"<<endl;
    else
      cout<<"No"<<endl;
  }

  return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include"math.h"

#define MAX 100000000
int a[MAX];
using namespace std;

int main(){
    int n, m, sum = 0, count = 0;
    cin >> n >> m;
    for(int i=0;i<n;i++) {
        cin >> a[i];
        sum += a[i];
    }
    double sumd = (double)sum/(4.0*m);
    for(int i=0;i<n;i++){
        if(a[i]>=sumd) count++;
    }
    if(count>=m)cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

Measured memory_bytes: 256
#include <math.h>

#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
using ll = long long;

int main() {
  int n;
  cin >> n;
  vector<int> b(n);
  rep(i, n - 1) cin >> b.at(i);

  int sum = b.at(0) + b.at(n - 2);

  for (int i = 0; i < n - 2; i++) {
    sum += min(b.at(i), b.at(i + 1));
  }

  cout << sum;
  return 0;
}


Measured memory_bytes: 256
x,y = map(int,input().split())
A = [1,3,5,7,8,10,12]
B = [4,6,9,11]
C = [2]

if((x in A)and(y in A)):
  print('Yes')
elif((x in B)and(y in B)):
  print('Yes')
elif((x in C)and(y in C)):
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3064
N = int(input())
L = list(map(int, input().split()))

ans = 0
for i in range(0,N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      if L[i] != L[j] and L[i] != L[k] and L[j] != L[k] and L[i]+L[j] > L[k] and L[i]+L[k] > L[j] and L[j]+L[k] > L[i]:
        ans += 1
print(ans)


Measured memory_bytes: 9116
n, m = map(int, input().split())
drink = [list(map(int, input().split())) for _ in range(n)]

drink.sort(key=lambda x: x[0])

ans = 0
for i in range(n):
    if m <= 0:
        break
    if m >= drink[i][1]:
        ans += drink[i][0] * drink[i][1]
        m -= drink[i][1]
    else:
        ans += drink[i][0] * m
        m = 0
        break

print(ans)

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

void Main()
{
    int n;
    cin >> n;
    cout << (n+1)/2 << endl;
}

int main(int argc, char **argv)
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    Main();
    return 0;
}


Measured memory_bytes: 3608
#include <iostream>
using namespace std;
int n, mx, c[300005], d[300005];
string a;
int main() {
	int i;
	cin>>n>>a;
	for(i=n; i; i--) d[i] = d[i+1] + (a[i-1]=='W');
	for(i=1; i<=n; i++) {
		c[i] = c[i-1] + (a[i-1]=='E');
		mx = max(mx, c[i-1] + d[i+1]);
	}
	cout<<n-mx-1;
	return 0;
}

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

int N, K;
int A[100000];
vector<int> G[100000];
int C;

int dfs(int x) {
  int h = 1;
  for (int v : G[x]) {
    h = max(h, 1+dfs(v));
  }
  if (h >= K) {
    if (A[x] != 0) C++;
    return 0;
  }
  return h;
}

int main() {
  cin >> N >> K;
  for (int i=0; i<N; i++) {
    cin >> A[i];
    A[i]--;
    if (i > 0) G[A[i]].push_back(i);
  }
  if (A[0] != 0) {
    A[0] = 0;
    C++;
  }
  dfs(0);
  cout << C << "\n";
  return 0;
}


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

#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define RSORT(a) sort((a).rbegin(),(a).rend())
#define ll long long
#define pb(a) push_back(a)

#define PRINTV(v) {for(ll deB=0; deB<(v).size(); deB++){cout << (v)[deB] << " ";}cout << endl;}

int main(){
	
	
	ll N;
	vector<ll> c(4,0);
	cin >> N;
	REP(i,N){
		string s;
		cin >> s;
		if(s=="AC"){
			c[0]++;
		}else if(s=="WA"){
			c[1]++;
		}else if(s=="TLE"){
			c[2]++;
		}else{
			c[3]++;
		}
	}
	cout << "AC x " << c[0] << endl;
	cout << "WA x " << c[1] << endl;
	cout << "TLE x " << c[2] << endl;
	cout << "RE x " << c[3] << endl;
	
	return 0;
}

Measured memory_bytes: 3592
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long ans = Long.MAX_VALUE, suml = 0, sumr = 0;
        int a[] = new int[n];
        for(int i = 0;i < n;i++){
            a[i] = scan.nextInt();
            sumr += a[i];
        }

        for(int i = 0;i < n-1;i++){
            suml += a[i];
            sumr -= a[i];
            ans = Math.min(ans, Math.abs(suml-sumr));
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 65092
fn main() {
    let _ = read::<usize>();
    let mut a = read_vec::<u64>();
    a.sort();
    let mut b = 0;
    let mut v = vec![];
    while let Some(x) = a.pop() {
        if x != b {
            b = x;
        } else {
            b = 0;
            v.push(x);
            if v.len() == 2 {
                break;
            }
        }
    }
    if v.len() < 2 {
        println!("{}", 0);
    } else {
        println!("{}", v[0] * v[1]);
    }
}

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 8444
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
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;
}
int main() {
  cout << fixed << setprecision(10);
  int d;
  cin >> d;
  vector<int> c(26);
  rep(i,26)cin>>c[i];
  vector<vector<int>> s(d,vector<int>(26));
  rep(i,d){
    rep(j,26)cin>>s[i][j];
  }
  /*
  vector<int> t(d);
  rep(i,d)cin>>t[i];
  ll ans = 0;
  vector<int> last(26,0);
  rep(i,d){
    ans+=s[i][t[i]-1];
    last[t[i]-1]=i+1;
    rep(j,26){
      ans-=c[j]*(i+1-last[j]);
    }
    cout << ans << endl;
  }
  */
  rep(i,d){
    int ans = -INF;
    int p=0;
    rep(j,26){
      if(chmax(ans,s[i][j])){
        p=j+1;
      }
    }
    cout << p << endl;
  }

}


Measured memory_bytes: 3680
<?php

fscanf(STDIN, '%d %d', $N, $M);

$products = explode(' ', trim(fgets(STDIN)));

$sumVotes = array_sum($products);
$standard = $sumVotes / (4*$M);

$okCount = 0;
foreach ($products as $product) {
    if ($product >= $standard) {
        $okCount++;
    }
}

if ($okCount >= $M) {
    echo 'Yes';
} else {
    echo 'No';
}

echo PHP_EOL;


Measured memory_bytes: 16252
N, W = map(int, input().split())
w = []
v = []
for i in range(N):
	wi, vi = map(int, input().split())
	w.append(wi)
	v.append(vi)

dp = [0] * (W + 1)
dp[w[0]] = v[0]

for i in range(1, N):
	for j in range(W, -1, -1):
		if j - w[i] >= 0 and dp[j - w[i]] + v[i] > dp[j]:
			dp[j] = max(dp[j], dp[j - w[i]] + v[i])
print(max(dp))

Measured memory_bytes: 69456
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

int a,b,c;

int main()
{
    scanf("%d%d%d",&a,&b,&c);
    if(a<b)
        swap(a,b);
    printf("%d\n",(c-1)/a+1);
    return 0;
}


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

result = True
for i in reversed(range(1, N)):
    if h_list[i] < h_list[i - 1]:
        if h_list[i - 1] - h_list[i] >= 2:
            result = False
            break
        else:
            h_list[i - 1] -= 1
if result:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 14396
#include <bits/stdc++.h>
#define spIO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long ll;
typedef long double lb;
int main()
{
    spIO;
    string s,t;
    ll k;
    cin>>t>>k;
    ll con=0;
    s=t;
    for(int i=1;i<s.size();i++)
    {
        if(s[i]==s[i-1])
        {
            s[i]='.';
            con++;
        }
    }
    ll ans1=con*k;
    if(s[0]==s[s.size()-1])
        ans1+=(k-1);
    con=1;
    s=t;
    bool open=false;
    if(s.size()>1&&s[0]==s[1])
    {
        s[0]='.';
        open=true;
    }
    for(int i=1;i<s.size();i++)
        if(s[i]==s[i-1])
        {
            s[i]='.';
            con++;
        }
    //cout<<con<<'\n';
    ll ans2=con*k;
    //cout<<ans1<<' '<<ans2<<'\n';
    bool check=true;
    for(int i=1;i<s.size();i++)
        if(t[i]!=t[0])
        {
            check=false;
            break;
        }
    ll ans3;
    if(check)
    {
        ans3=t.size()*k/2;
    }
    if(open)
        ans1=min(ans1,ans2);
    if(check)
        ans1=min(ans1,ans3);
    cout<<ans1;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a[25],b[25],c[25],h;
int main()
{
	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]);
	for(int i=1;i<=n;i++)
	{
		h+=b[a[i]];
		if(a[i]==a[i-1]+1&&i!=1)h+=c[a[i-1]];
	}
	printf("%d",h);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;


int main(){
 ll X,k,d;
 cin>>X>>k>>d;
 ll x = abs(X);
 ll kaisuu = min (k,x/d);
 x -= kaisuu * d ;
 k -= kaisuu;
  if (k % 2 == 0) {
        cout << x << endl;
    } else {
        cout << d-x << endl;
    }
}

Measured memory_bytes: 3676
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>

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

using namespace std;
int main(){
	int a, b;
	char c;
	cin >> a >> c >> b;

	if (c == '+')
		cout << a + b << endl;
	else
		cout << a - b << endl;

	return 0;
}

Measured memory_bytes: 256
using System;
using System.IO;
using System.Net;
using System.Net.Sockets;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using static System.Math;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;

public static class P
{
    public static void Main()
    {
        int n = Reader.NextUInt;
        int last = 0;
        int cur = 0;
        int max = 0;
        for (int i = 0; i < n; i++)
        {
            var h = Reader.NextUInt;
            if (last >= h) max = Max(max, ++cur);
            else cur = 0;
            last = h;
        }
        Console.WriteLine(max);
    }
}

static class Reader
{
    const int BUF_SIZE = 1 << 12;
    static Stream Stream;
    static byte[] buffer = new byte[BUF_SIZE];
    static int ptr = 0;
    static Reader() { Stream = Console.OpenStandardInput(); }

    private static void Read()
    {
        Stream.Read(buffer, 0, BUF_SIZE);
    }

    private static byte Next { get { if (ptr == buffer.Length) { Read(); ptr = 0; } return buffer[ptr++]; } }

    public static int NextUInt
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        get
        {
            int res = 0; byte next;
            do { next = Next; } while (next < 48);
            do { res = res * 10 + next - 48; next = Next; } while (48 <= next);
            return res;
        }
    }
}


Measured memory_bytes: 13140