akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <queue>

using namespace std;

struct bar {
  int height;
  int a;
  int b;
  bool operator<(const bar &right) const {
    return height < right.height;
  }
};

int main() {

  int n, m, a;
  while (cin >> n >> m >> a) {
    if (n == 0 && m == 0 && a == 0) break;
    priority_queue<bar> que;
    while (m--) {
      int h, p, q;
      cin >> h >> p >> q;
      bar b = { h, p, q };
      que.push(b);
    }
    int num = a;
    while (!que.empty()) {
      bar b = que.top(); que.pop();
      if (num == b.a) num = b.b;
      else if (num == b.b) num = b.a;
    }
    cout << num << endl;
  }

  return 0;
}

Measured memory_bytes: 928
n=int(input())
t,a=map(int,input().split())
h=list(map(int,input().split()))
b=float("INF")
ans=n+1
for i in range(1,n+1):
    tmp=t-h[i-1]*0.006
    if b>abs(tmp-a):
        b=min(b,abs(tmp-a))
        ans=i
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define N_MAX 21

struct Edge {
  int to, cost;
  Edge(int to, int cost) : to(to), cost(cost) {}
};

int N;
vector<Edge> E[N_MAX];

int dfs(int p, int from) {
  int res = 0;
  for(int i = 0; i < E[p].size(); ++i) {
    int &cost = E[p][i].cost;
    int &to = E[p][i].to;
    if(to == from) continue;
    if(E[to].size() == 1) continue;
    res += dfs(to, p) + cost*2;
  }
  return res;
}

int dfs2(int p, int from) {
  int res = 0;
  for(int i = 0; i < E[p].size(); ++i) {
    int &cost = E[p][i].cost;
    int &to = E[p][i].to;
    if(to == from) continue;
    if(E[to].size() == 1) continue;
    res = max(res, dfs2(to,p) + cost);
  }
  return res;
}

void solve() {
  cout << dfs(0, -1) - dfs2(0, -1) << endl;
  /*for(int i = 0; i < N; ++i) {
    vector<Edge>::iterator it = E[i].begin();
    while(it != E[i].end()) {
      if(E[it->to].size() == 0) {
	it = E[i].erase(it);
      } else {
	it++;
      }
    }
    }*/

}

main() {
  while((cin >> N) && N) {
    for(int i = 0; i < N_MAX; ++i) E[i].clear();
    for(int i = 0; i < N-1; ++i) {
      int a, b, t;
      cin >> a >> b >> t;
      a--, b--;
      if(a > b) swap(a, b);
      E[a].push_back(Edge(b, t));
      E[b].push_back(Edge(a, t));
    }
    solve();
  }
}

Measured memory_bytes: 0
fn main() {
    // input
    // S
    let s = read_line::<String>();

    let mut ans = "Yes";

    for (i, c) in s.chars().enumerate() {
        if i % 2 == 0 {
            // 偶数
            if c == 'L' {
                ans = "No";
                // println!("{}", i);
                // println!("{}", c);
                break;
            }
        } else {
            // 奇数
            if c == 'R' {
                ans = "No";
                // println!("{}", i);
                // println!("{}", c);
                break;
            }
        }
    }
    println!("{}", ans);
}

#[allow(dead_code)]
fn read_line<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_line::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 4352
#include <iostream>
typedef long long ll;
using namespace std;
int main() {
    ll n, a;
    cin >> n;
    int min=1e9;
    int max=0;
    for(int i=0; i<n; i++) {
        cin >> a;
        if(min>a) min=a;
        if(max<a) max=a;
    }
    cout << max - min << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<(int)(m);i++)
#define rrep(i,n,m) for(int i=((int)(n)-1);i>=m;i--)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int MOD=1000000007;
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    
    ll ans=0;
    
    rep(b,k+1,n+1){
        int a=0,p=0;
        a=(n/b)*(b-k);
        if(n%b!=0) {
            if(k==0) p=n%b;
            else p=max(0,n%b-(k-1));
        }
        
        ans+=a+p;
    }
    
    cout<<ans<<endl;
}


Measured memory_bytes: 256
H,W = map(int,input().split())
Pic = [[i=="." for i in input()] for j in range(H)]
ans = "Yes"
for h,row in enumerate(Pic):
    for w,p in enumerate(row):
        if p:continue
        if all([
            h==0 or Pic[h-1][w],
            h==H-1 or Pic[h+1][w],
            w==0 or Pic[h][w-1],
            w==W-1 or Pic[h][w+1]
            ]):ans = "No"
print(ans)

Measured memory_bytes: 3064
//INCLUDE
//------------------------------------------
#include <bits/stdc++.h>
//DEFINE
//------------------------------------------
#define ll long long
#define ld long double
#define ALLv(a)  (a).begin(),(a).end()
#define ALL(a,n)  (a),(a)+n
#define vi vector<long long>
#define vd vector<long double>
#define vs vector<string>
//CONST
//------------------------------------------
#define INF 1010000000000000017LL
#define MOD 1000000007LL
#define EPS 1e-12
#define PI 3.14159265358979323846
//REPEAT
//------------------------------------------
#define   FOR(i,m,n) for(ll (i)=(m);   (i)<(n);  (i)++)
#define   REP(i,n)   for(ll (i)=0;     (i)<(n);  (i)++)
#define  REPS(i,x)   for(ll (i)=1;     (i)<=(x); (i)++)
#define  RREP(i,x)   for(ll (i)=(x)-1; (i)>=0;   (i)--)
#define RREPS(i,x)   for(ll (i)=(x);   (i)> 0;   (i)--)
#define  WREP(i,in,j,jn) REP(i,in)REP(j,jn)
//-----------------------------------------
#define dcml(n) fixed<<setprecision(n)
using namespace std;
vector<ll> G[101000];
int main(void){
    ll N,M;cin>>N>>M;
    vector<ll> H(N);
    REP(i,N)cin>>H[i];
    
    REP(i,M){
        ll a,b;
        cin>>a>>b; a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    ll cnt=0;
    REP(i,N){
        bool f=true;//一番大きいか
        for(auto r:G[i]){
            //r : 各展望台からいける展望台
            if(H[i]<=H[r]){
                f=false;
                break;
            }
        }
        if(f)cnt++;
    }
    cout<<cnt<<"\n";
}

Measured memory_bytes: 9860
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;

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

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn argsort<T: std::cmp::Ord + std::marker::Copy>(v: &Vec<T>) -> Vec<usize> {
    let mut sort_v = Vec::new();
    for i in 0..v.len() {
        sort_v.push((v[i], i));
    }
    sort_v.sort();
    sort_v.iter().map(|x| x.1).collect::<Vec<usize>>()
}

fn main() {
    let v: Vec<usize> = read_vec();
    let (n, m) = (v[0], v[1]);
    let mut a = vec![0; n];
    let mut b = vec![0; n];
    for i in 0..n {
        let v: Vec<usize> = read_vec();
        a[i] = v[0];
        b[i] = v[1];
    }
    let indexes = argsort(&a);

    let mut m = m;
    let mut ans = 0;
    for i in 0..n {
        let ind = indexes[i];
        if m > b[ind] {
            ans += a[ind] * b[ind];
            m -= b[ind]
        } else {
            ans += a[ind] * m;
            break;
        }
    }
    println!("{0}", ans);
}


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

int main() {
  long long A,B,K;
  cin>>A>>B>>K;
  if(A>=K){cout<<A-K<<" "<<B<<endl;}else if(A+B>=K){cout<<0<<" "<<A+B-K<<endl;}
  else{cout<<0<<" "<<0<<endl;}
}

Measured memory_bytes: 3576
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF=1LL<<60;
const int inf=1<<30;
const int mod=1e9+7;
const int MOD=998244353;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k;cin >> n >> k;
    int K=2*k;
    vector<vector<int>> a(K,vector<int>(K)),b(K,vector<int>(K)),w(K,vector<int>(K));
    for(int i=0;i<n;i++){
        int x,y;cin >> x >> y;
        char c;cin >> c;
        if(c=='B'){
            a[x%K][y%K]++;
        }
        else{
            a[x%K][(y+k)%K]++;
        }
    }
    for(int i=0;i<K;i++){
        for(int j=0;j<K;j++){
            b[i][j]=a[i][j]+a[(i+k)%K][(j+k)%K];
            w[i][(j+k)%K]=b[i][j];
        }
    }
    for(int i=0;i<K;i++){
        for(int j=1;j<K;j++){
            b[i][j]+=b[i][j-1];
            w[i][j]+=w[i][j-1];
        }
    }
    for(int j=0;j<K;j++){
        for(int i=1;i<K;i++){
            b[i][j]+=b[i-1][j];
            w[i][j]+=w[i-1][j];
        }
    }
    int ans=0;
    for(int i=k;i<K;i++){
        for(int j=k;j<K;j++){
            chmax(ans,max(b[i][j]-b[i-k][j]-b[i][j-k]+b[i-k][j-k],w[i][j]-w[i-k][j]-w[i][j-k]+w[i-k][j-k]));
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 47360
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
    string a,b,c;
    cin>>a>>b>>c;
    if(a[a.size()-1]==b[0]&&b[b.size()-1]==c[0]){cout<<"YES"<<endl;}
    else{cout<<"NO"<<endl;}
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
	int a, b, c;

	cin >> a >> b >> c;
	
	int div_cnt = 0;

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

	cout << div_cnt << endl;

	return 0;
}

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

const int MAXN = 101010;

int a[MAXN];
int cnt[21];
int f[1<<17];
int n;

int res[21];
int cntr;

int main() {
	scanf("%d", &n);
	int u, v, w;
	for(int i = 1; i < n; ++i) {
		scanf("%d%d%d", &u, &v, &w);
		a[u] ^= w;
		a[v] ^= w;
	}
	for(int i = 0; i < n; ++i)
		cnt[a[i]]++;
	int ans = 0;
	for(int i = 1; i <= 15; ++i) {
		ans += cnt[i] >> 1;
		if(cnt[i] & 1) {
			res[cntr++] = i;
		}
	}
	f[0] = 0;
	for(int i = 1; i < 1<<cntr; ++i) {
		int tmp = 0;
		for(int j = 0; j < cntr; ++j) {
			if(i & (1<<j))
				tmp ^= res[j];
		}
		tmp = !tmp;
		for(int j = 0; j < cntr; ++j) {
			if(i & (1<<j)) {
				f[i] = max(f[i], f[i ^ (1<<j)] + tmp);
			}
		}
	}
	ans += cntr;
	ans -= f[(1<<cntr) - 1];
	printf("%d\n", ans);
	
	return 0;
}

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

int partition(vector<int>& A, const int l, const int r) {
    const int pivot = A[r - 1];
    int head = l;
    for(int i = l; i < r; i++) {
        if(A[i]<= pivot) {
            swap(A[head], A[i]);
            head++;
        }
    }
    return head - 1;
}

int main() {
    int N; cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int g = partition(A, 0, N);
    for(int i = 0; i <= g; i++) {
        if(i == g) cout << '[' << A[i] << ']';
        else cout << A[i];
        cout << (i == N - 1 ? '\n' : ' ');
    }
    for(int i = g + 1; i < N; i++) {
        cout << A[i];
        cout << (i == N - 1 ? '\n' : ' ');
    }
}

Measured memory_bytes: 1532
import java.util.Scanner

import scala.collection.Searching._
import scala.annotation.tailrec
import scala.collection.immutable.{NumericRange, Queue}
import scala.collection.mutable
import scala.io.StdIn.readLine

class IUnionFind(val size: Int) {

  private case class Node(var parent: Option[Int], var treeSize: Int)

  private val nodes = Array.fill[Node](size)(new Node(None, 1))

  def union(t1: Int, t2: Int): IUnionFind = {
    if (t1 == t2) return this

    val root1 = root(t1)
    val root2 = root(t2)
    if (root1 == root2) return this

    val node1 = nodes(root1)
    val node2 = nodes(root2)

    if (node1.treeSize < node2.treeSize) {
      node1.parent = Some(t2)
      node2.treeSize += node1.treeSize
    } else {
      node2.parent = Some(t1)
      node1.treeSize += node2.treeSize
    }
    this
  }

  def connected(t1: Int, t2: Int): Boolean = t1 == t2 || root(t1) == root(t2)

  @tailrec
  private def root(t: Int): Int = nodes(t).parent match {
    case None => t
    case Some(p) => root(p)
  }
}


object Main {
  def solve(sc: => Scanner): Unit = {
    val N = sc.nextInt
    if (N != 0) {
      val ans = Array.fill(N)((sc.nextInt, sc.nextInt + sc.nextInt)).maxBy(a => a._2)
      println(ans._1 + " " + ans._2)
      solve(sc)
    }
  }

  def gcd(i: Long, j: Long): Long = {
    if (i < j) (gcd(j, i)) else (if (j == 0) (i) else (gcd(j, i % j)))
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)
    solve(sc)
  }
}


Measured memory_bytes: 440820
fn main() {
    let n: u32 = read();
    let mut yen = 0;
    loop {
        yen += 1000;
        if yen >= n {
            println!("{}", yen - n);
            return;
        }
    }
}

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()
}


Measured memory_bytes: 2132
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	int INF = 1 << 28;

	void run() {
		Scanner sc = new Scanner(System.in);
		for(;sc.hasNext();) {
			String str1 = sc.next();
			String str2 = sc.next();
			int n = str1.length();
			int m = str2.length();
			short[][] dp = new short[n+1][m+1];
			int max = 0;
			for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
//				dp[i][j] = dp[i][j-1];
				if( str1.charAt(i-1) == str2.charAt(j-1) )
					dp[i][j] = (short)(dp[i-1][j-1]+1);
				max = max(max, dp[i][j]);
			}
//			for(int[] a: dp) debug(a);
			
			System.out.println(max);
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}

Measured memory_bytes: 58000
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
typedef long long ll;
const ll mod = 1e+9+7;

int main(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1,true);
    vector<ll> dp(n+1);
    rep(i,m){
        int q;
        cin>>q;
        a[q]=false;
    }
    //////
    dp[0]=1;
    for(int i=0;i<n;++i){
        for(int j=i+1;j<=min(n,i+2);++j){
            if(a[j]){
                dp[j]+=dp[i];
                dp[j]%=mod;
            }
        }
    }
        cout<<dp[n]<<endl;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define MAX 45

int F[MAX];

int fib(int n) {
	if (n == 0 || n == 1)
		return F[n] = 1;
	else if (F[n] != 0)
		return F[n];
	else
		return F[n] = fib(n - 1) + fib(n - 2);
}

int main(void) {
	int n;
	cin >> n;
	cout << fib(n) << endl;
}


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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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



void solve() {
  int N; cin >> N;
  double res = 0;
  vector<double> xv(N), yv(N);
  rep(i, N) cin >> xv[i] >> yv[i];
  
  rep(i, N){
    Rep(j, i+1, N){
      res += sqrt((xv[i]-xv[j])*(xv[i]-xv[j]) + (yv[i]-yv[j])*(yv[i]-yv[j]));
    }
  }
  
  ll a = fact[N];
  
  cout << res * 2 / N << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s,t;
  cin >> s >> t;
  int ls=s.size();
  int lt=t.size();
  int i,j,ans,temp;
  temp=0;
  ans=0;
  for(j=0;j<=ls-lt;++j)
  {
  for(i=0;i<lt;++i)
  {
  if(s.at(i+j)==t.at(i)) temp++;
  }
  if(temp>ans) ans=temp;
    temp=0;
  }
  ans=lt-ans;
  cout << ans;

return 0;}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

/* REPmacro */
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOREACH(x, a) for(auto x : a)

/* exchange */
#define CHMIN(a, b) (a) = min((ll)(a), (ll)(b))
#define CHMAX(a, b) (a) = max((ll)(a), (ll)(b))

/* function */
#define IN(x) cin >> x
#define DEBUG(x) cerr << (x) << " "
#define LN() cerr << "\n"
#define PRINT(x) cout << (x) << endl
#define BR cout << endl

/* const */
const int ARRAY = 100005;
const int INF = 1001001001; // 10^9
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;

ll N = 0;
vl L;
ll table[ARRAY];
ll t;
ll ret = 0;

void input() {
  IN(N);
  REP(i, N) {
    IN(t);
    L.pb(t);
  }
}

void solve() {
  sort(ALL(L));

  ll a;
  ll b;
  for(ll low = 0; low < N; low++) {
    for (ll mid = low+1; mid < N; mid++) {
      a = L[low];
      b = L[mid];
      auto itr = lower_bound(ALL(L), a+b);
      ll les = N - distance(itr, L.end());
      ret += les - mid - 1;
    }
  }
  PRINT(ret);
}

int main(void){
  input();
  solve();
}


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

typedef long long ll;

int cnt[202020];

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

  int N, K; cin >> N >> K;
  for (int i = 1; i <= N; i++) {
    cnt[i % K]++;
  }
  ll ans = 0;
  for (int i = 0; i < K; i++) {
    if ((i + i) % K == 0) ans += 1ll * cnt[i] * cnt[i] * cnt[i];
  }
  cout << ans << "\n";
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main () {
  int k;
  cin >> k;
  vector<long long> a;

  for(int i = 1; i<=9; i++) a.push_back(i);
  while(1) {
      if(k <= a.size()) {
          cout << a[k - 1] << endl;
          return 0;
      }
      k -= a.size();
      vector<long long> old;
      swap(old, a);
      for(long long x : old) {
          for(int i = -1; i <= 1; i++) {
            int tmp = x % 10 + i;
            if(tmp < 0 || tmp > 9) continue;
            long long d = x * 10 + tmp;
            a.push_back(d);
          }
      }
  }

  return 0;
}

Measured memory_bytes: 1712
#include<stdio.h>
#include<iostream>
#include<list>
#include<map>
#include<vector>
#include<algorithm>
#include<string.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << x << endl;
using namespace std;

int main(){
    string s;
    int i;

    while(getline(cin, s)){
        i = 0;
        while(s[i + 4]){
            if(s.substr(i,5) == "apple"){
                s[i] = 'p';
                s[i+1] = 'e';
                s[i+2] = 'a';
                s[i+3] = 'c';
                s[i+4] = 'h';
            }else if(s.substr(i,5) == "peach"){
                s[i] = 'a';
                s[i+1] = 'p';
                s[i+2] = 'p';
                s[i+3] = 'l';
                s[i+4] = 'e';
            }
            i++;
        }
        cout << s << endl;
    }
}

Measured memory_bytes: 1188
#include<bits/stdc++.h>
using namespace std;
int n,i,mx;
int a[100001];
int l[100002],r[100002];
int main(){
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
  	for(i=1;i<=n;i++){
  		l[i]=__gcd(l[i-1],a[i]);
	}
  	for(i=n;i>=1;i--){
  		r[i]=__gcd(r[i+1],a[i]);
	}
	for(i=1;i<=n;i++){
		mx=max(mx,__gcd(l[i-1],r[i+1]));
	}
	cout<<mx;
    return 0;
}

Measured memory_bytes: 1408
#include<stdio.h>
int main(void)
{
	int n,m,k,i,j,a[101],temp;
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	k=1;
	while(1){
		for(i=0;i<n-1;i++){
			if(a[i]%k>a[i+1]%k){
				temp=a[i];
				a[i]=a[i+1];
				a[i+1]=temp;
			}
		}
		if(k==m)break;
		k++;
	}
	for(i=0;i<n;i++){
		printf("%d\n",a[i]);
	}
	return 0;
}

Measured memory_bytes: 596
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int A = sc.nextInt();
        int B = sc.nextInt();

        int C = sc.nextInt();
        int D = sc.nextInt();
        sc.close();

        boolean takahashiWin = false;

        while (true) {
            C -= B;
            if(C<=0 ) {
                takahashiWin = true;
                break;
            }
            
            A -= D;
            if(A<=0) {
                takahashiWin = false;
                break;
            }
        }

        System.out.println(takahashiWin ? "Yes" : "No");
    }

}


Measured memory_bytes: 35716
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	string a[n+1];
	int b[n+1];
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		cin>>b[i];
	}
	string x;
	cin>>x;
	int ans=0;
	int f=0;
	for(int i=1;i<=n;i++)
	{
		if(f==1)
		{
			ans+=b[i];
		}
		if(a[i]==x)
		{
			f=1;
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;

int main() {
  int N;
  cin >> N;
  int a[N];
  int abs_max = 0;
  int point = 0;
  bool all_zero = true;
  for (int i = 0; i < N; i++) {
    cin >> a[i];
    if (a[i] != 0) {
      all_zero = false;
    }
    if (abs_max < abs(a[i])) {
      abs_max = abs(a[i]);
      point = i;
    }
  }
  if (all_zero) {
    cout << 0 << endl;
    return 0;
  } 
  vector<P> move;
  for (int i = 0; i < N; i++) {
    if (point != i) {
      a[i] += a[point];
      move.push_back(make_pair(point,i));
    }
  }
  int R = 0;
  for (int i = 0; i < N; i++) {
    R += a[i];
  }  
  if (R > 0) {
    for (int i = 1; i < N; i++) {
      move.push_back(make_pair(i-1,i));
    }
  } else {
    for (int i = N-1; i >= 1; i--) {
      move.push_back(make_pair(i,i-1));
    }
  }
  cout << (int)move.size() << endl;
  for (int i = 0; i < (int)move.size(); i++) {
    cout << move[i].F + 1 << " " << move[i].S + 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 3604
package main

import "fmt"

func main() {
	var n, k int
	fmt.Scan(&n, &k)

	count := 0
	for i := 1; i <= n; i += 2 {
		count++
	}
	if count >= k {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int x = s.length();
    int a=0,b=0;
    for(int i=0;i<x;i++){
        if(s[i]=='A')
        a++;
        if(s[i]=='B')
        b++;
    }
    if(a==0||b==0)
    cout<<"No";
    else
    cout<<"Yes";

    return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.lang.*;
// ArrayList<Integer>[] arr=new ArrayList[n];
public class Main{    
public static void main(String[] args) throws FileNotFoundException, IOException{
        Scanner s = new Scanner(System.in);
         StringBuilder sb=new StringBuilder();
         BufferedWriter out=new BufferedWriter(new OutputStreamWriter(System.out));
         long n=s.nextLong();
        //Set<Integer>ss=new HashSet<>();
         long res=Long.MAX_VALUE;
         for(long i=1;i<=1000000;i++){
            if(n%i==0){
                res=(long)Math.min(res,i-1+n/i -1);
            }
         }
         /*if(res==(long)1e9+7){
            System.out.println(n-1);
         }
         else{
            System.out.println(res);
         }*/
        System.out.println(res);
    }
}

Measured memory_bytes: 25044
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
  ll n;
  cin >> n;
  ll a[n];
  rep(i,n)cin >> a[i];
  sort(a,a+n);
  if(a[n-1]-a[0]>1){
    cout << "No" << endl;
    return 0;
  }
  if(a[n-1]==a[0]){
    if(n>=2*a[0] || a[0]==n-1){
      cout << "Yes" << endl;
    }else cout << "No" << endl;
    return 0;
  }
  ll mincnt=0;
  rep(i,n){
    if(a[i]==a[0])mincnt++;
  }
  n-=mincnt;
  if((a[0]+1-mincnt>0 && n>=2*(a[0]+1-mincnt)) || (a[0]+1-mincnt==1 && n>1)){
    cout << "Yes" << endl;
  }else cout << "No" << endl;
return 0;}

Measured memory_bytes: 1024
use std::io;
use std::cmp;
use std::collections::*;


fn read<T>() -> Vec<T>
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split(' ')
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

fn read_one<T>() -> T
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

fn main() {
    let n = read::<usize>()[0];
    let mut n_map = HashMap::new();
    for _ in 0..n {
        let si = read_one::<String>();
        *n_map.entry(si).or_insert(0) += 1;
    }

    let m = read::<usize>()[0];
    let mut m_map = HashMap::new();
    for _ in 0..m {
        let ti = read_one::<String>();
        *m_map.entry(ti).or_insert(0) += 1;
    }

    let mut max = 0;

    for x in &n_map {
        let y = match m_map.get(x.0) {
            Some(v) => *v,
            None => 0,
        };

        max = cmp::max(max, x.1 - y);

    }

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

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define SORT(V) sort((V).begin(),(V).end())

int main(){
  std::string S;
  std::cin >> S;

  if(S=="ABC") {cout << "ARC"<<endl;}
  else{cout<<"ABC"<<endl;}

  return 0;
}


Measured memory_bytes: 3488
#include<stdio.h>
#include<string.h>
int main()
{
	char s[100];
	int k,l,i;
	scanf("%d",&k);
	scanf("%s",s);
	l=strlen(s);
	if(k<l)
	{for(i=0;i<k;i++)
	printf("%c",s[i]);
	printf("...");
	}
	else printf("%s",s);
	return 0;
}

Measured memory_bytes: 1696
#include <stdio.h>

int main(void)
{
    int i,j,N,a=0;
    scanf("%d",&N);
    int array[N-1];
    for(i=0;i<N-1;i++){
        scanf("%d",&array[i]);
    }

    a=array[0]+array[N-2];
    for(j=0;j<N-2;j++){
        a += array[j] < array[j+1] ? array[j] : array[j+1];
    }

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

    return 0;
}

Measured memory_bytes: 128
mod = 10**9+7
import sys
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations, combinations_with_replacement
from itertools import accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from math import ceil,floor
from copy import deepcopy
from heapq import heappop,heappush,heapify
import heapq


# l = ['a', 'a', 'a', 'a', 'b', 'c', 'c']
# c = Counter(l)

# d = defaultdict(int)

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

# リストの要素を改行を挟んで表示する
p2D = lambda x: print(*x, sep="\n")
# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())

def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())

# 入力全てを整数に変換したものの配列を受け取る
# def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LI(): return list(map(lambda x:int(x), sys.stdin.readline().split()))
def HI(): return list(map(lambda x:int(x)*(-1), sys.stdin.readline().split()))



n,m,q = MI()
A =[]
B = []
C = []
D = []



for _ in range(q):
	a,b,c,d = MI()
	A.append(a)
	B.append(b)
	C.append(c)
	D.append(d)


ll = list(combinations_with_replacement(range(1,m+1), n))
	
ans = 0
for l in ll:
	tmp = 0
	for i in range(q):
		if l[(B[i]-1)]-l[(A[i]-1)]==C[i]:
			tmp+=D[i]

	ans = max(tmp,ans)
print(ans)








Measured memory_bytes: 82564
import java.util.*;

public class Main{
	public static void main(String[]args){
		Scanner s = new Scanner(System.in);
		int a = s.nextInt();
		int b = s.nextInt();
		int pa = s.nextInt();
		if((a-pa) < 0){
			if((a+b) < pa){
			System.out.println("NA");
			}else{
				System.out.println(pa-a);
			}
		}else if(a >= pa){
			System.out.println(0);
		}else{}
	}
}


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

using namespace std;

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

    int n, m;
    cin >> n >> m;

    priority_queue<int> pq;

    while (n--)
    {
        int x;
        cin >> x;
        pq.push(x);
    }

    while (m--)
    {
        int t = pq.top();
        pq.pop();
        pq.push(t / 2);
    }

    long long res = 0;

    while (pq.size())
    {
        res += pq.top();
        pq.pop();
    }

    cout << res;
}

Measured memory_bytes: 3820
#include <bits/stdc++.h>
using namespace std; 
#define rep(i, N) for (int i = 0; i < (int)N; i++)

int main(){
    string s;
    cin >> s;
    if (s[0]==s[1]&& s[2]==s[3]&&s[0]!=s[2]) cout << "Yes"<<endl;
    else if (s[0]==s[2]&&s[1]==s[3]&&s[0]!=s[1]) cout << "Yes"<<endl;
    else if (s[0]==s[3]&&s[1]==s[2]&&s[0]!=s[1]) cout <<"Yes"<<endl;
    else cout << "No"<<endl;
}

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

#define         pb         push_back
#define         sf(x)      scanf("%d",&x)
#define         sfl(x)     scanf("%lld",&x)
#define         pf(x)      printf("%d\n",x)
#define         pfl(x)     printf("%lld\n",x)
#define         endl       '\n'
#define         pii        pair<int,int>
#define         mapii      map<int,int>
#define         mapll      map<ll,ll>
#define         mapci      map<char,int>
#define         mapcl      map<char,ll>
#define         mapsi      map<string,int>
#define         mapsl      map<string,ll>
#define         pll        pair<ll,ll>
#define         vi         vector<int>
#define         vl         vector<ll>
#define         vd         vector<double,double>
#define         all(c)     c.begin(),c.end()
#define         F          first
#define         S          second
#define         mp         make_pair
#define        ftc(x)      cerr << #x << ": " << x << " " << endl;
#define         PI         acos(-1)
#define         lcm(a,b)   ((a*b)/__gcd(a,b))
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};

//   cout<<std::setprecision(12)<<

 string s[110];

int solve(int x,int y,int n,int m)
{
    queue<pii>q;
    int xx,yy;
    q.push({x,y});
    int dist[n+10][m+10];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            dist[i][j] = 1e6;
        }
    }
    dist[x][y] = 0;

    while(!q.empty())
    {
        pii u;

        u = q.front();
        q.pop();

        for(int i=0; i<4; i++)
        {
            xx = u.F + dx[i];
            yy = u.S + dy[i];
            if(xx<0 || yy<0 ||xx>=n || yy>=m || dist[xx][yy]<=dist[u.F][u.S]+1 || s[xx][yy]=='#')
                continue;
            dist[xx][yy]=dist[u.F][u.S]+1;
            q.push({xx,yy});
        }
    }
    int d = 0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(s[i][j]!='#')
            d = max(d,dist[i][j]);
        }
    }
    return d ;
}
int main()
{
    int h,w,i,j,k,l,m,n;

    cin >> h >> w;

    int dp[h+10][w+10];


    for(i=0; i<h; i++)
        cin>>s[i];

    int ans = 0;

    for(i=0; i<h; i++)
    {
        for(j=0; j<w; j++)
        {
            if(s[i][j] == '.')
            ans = max(ans,solve(i,j,h,w));
        }
    }

    cout << ans << endl;

}


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

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

class ConnectNodeInfo{
	vector<vector<pair<ll,ll>>> graph;
public:
	ConnectNodeInfo(int node_num){
		graph.resize(node_num);
	}
	void AddNonDirectionalConnection(ll u,ll v,ll w){
		graph[u].emplace_back(v,w);
		graph[v].emplace_back(u,w);
	}
	void AddDirectionalConnection(ll u,ll v,ll w){
		graph[u].emplace_back(v,w);
	}
	vector<pair<ll,ll>>& operator[](ll index){
		return graph[index];
	}
	size_t size(){return graph.size();}
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);

	int N=in();
	vector<int> V(N,0);
	REP(i,N-1){
		V[in()-1]++;
	}

	for(auto& x:V){
		out(x);
	}
	return 0;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef pair<int,int> pii;
typedef pair<long long, int> pli;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) (x).size()

ll mod = 1000000007;

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

ll inv(ll x){
  ll res = 1;
  ll k = mod - 2;
  ll y = x;
  while(k){
    if(k&1)res = (res*y)%mod;
    y = (y*y) % mod;
    k /= 2;
  }
  return res;
}

struct Square {
  int h,w,cnt;
  Square(int _h,int _w,int _cnt){
    h = _h;
    w = _w;
    cnt = _cnt;
  }
};

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

  int n;
  cin >> n;
  vll a(n);
  rep(i,n)cin >> a[i];
  ll sum = 0;
  rep(i,n){
    sum += a[i];
    sum %= mod;
  }

  ll ret = 0;
  rep(i,n){
    ll b = sum - a[i];
    if(b < 0)b += mod;
    ret = (ret + a[i] * b % mod) % mod;
  }

  ret = ret * inv(2) % mod;

  cout << ret << endl;
}

Measured memory_bytes: 4776
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

ll frac[100005];

ll comb(ll a, ll b) {
  if(a<b) return 0;
  ll ans = frac[a];
  ll sh1, sh2;
  ll h=mod-2, two;
  while(h>0) {
    two = 1;
    sh1 = frac[b];
    sh2 = frac[a-b];
    while(2*two<h) {
      two *= 2;
      sh1 *= sh1;
      sh2 *= sh2;
      sh1 %= mod;
      sh2 %= mod;
    }
    h -= two;
    ans *= sh1*sh2%mod;
    ans %= mod;
  }
  return ans;
}

int main() {
  frac[0] = 1;
  for(ll i=1;i<100005;++i) frac[i] = frac[i-1]*i%mod;

  int N, K;
  cin>>N>>K;
  vector<ll> A(N);
  for(int i=0;i<N;++i) cin>>A[i];
  sort(A.begin(), A.end());
  ll ans = 0;
  for(int i=0;i<N;++i) {
    ans += A[i]*comb(i, K-1)%mod;
    ans %= mod;
    ans = (ans-A[i]*comb(N-i-1, K-1)%mod+mod)%mod;
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 4844
#include <stdio.h>

int main(void){
    long A,B,C,K;
    long ans;
    scanf("%ld %ld %ld %ld", &A, &B, &C, &K);
    
    if((A+B)>=K){
        if(K<A)ans=K;
        else ans=A;
    }else{
        ans=A+(-1)*(K-A-B);
    }
    printf("%ld",ans);
    return 0;
}

Measured memory_bytes: 1736
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const ll INF = 1001001001;
const ll LINF = 1001001001001001001;

void prvec(vector<ll> vec){
    ll n = vec.size();
    rep(i,n) cout << "i" << " " << vec.at(i) << "\n";
}

void pr2d(vector<vector<ll>> vvec){
    ll h = vvec.size();
    ll w = vvec.at(0).size();
    rep(i,h){
        rep(j,w){
            cout << vvec.at(i).at(j) << " ";
        }
        cout << "\n";
    }
}

int main(){
    ld pi = 3.14159265358979;
    ld r; cin >> r;
    cout << r*2.0*pi ;
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

int n, m;
string s, t;
int sum[100005], tum[100005];

int main() {
    ios_base::sync_with_stdio(false);
    cin >> s >> t;
    n = (int)s.size();
    m = (int)t.size();
    sum[0] = tum[0] = 0;
    forn(i, n) sum[i + 1] = sum[i] + (s[i] == 'A' ? 1 : 2);
    forn(i, m) tum[i + 1] = tum[i] + (t[i] == 'A' ? 1 : 2);
    int qc;
    cin >> qc;
    forn(i, qc) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        --a, --b, --c, --d;
        int s1 = sum[b + 1] - sum[a];
        int s2 = tum[d + 1] - tum[c];
        s1 %= 3;
        s2 %= 3;
        if (s1 == s2) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}


Measured memory_bytes: 1744
#全ての要素を奇数にできれば良い
#2で何回割れるか

n=int(input())
a=[int(i) for i in input().split()]

k=0
while True:
    f=0
    for i in range(n):
        if a[i]%2==0:
            k+=1
            f=1
            a[i]=a[i]//2
    if f==0:
        break

print(k)


Measured memory_bytes: 4148
#include<bits/stdc++.h>
#define ford(i,a,b) for(int i=(a);i>=b;i--)
#define rep1(i,a,b) for(int i=(a);(i)<=(b);(i)++)
#define rep(i,a,b) for(int i=(a);(i)<(b);(i)++)
#define ll long long
#define N 200005
#define pql priority_queue<ll>
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define rev(a,n) reverse(a,a+n)
using namespace std;
int n,t,a[N];
int main() {
	cin>>n>>t;
	ll ans=t;
	rep(i,0,n)cin>>a[i];
	rep(i,1,n){
		if(a[i]-a[i-1]>t) ans+=t;
		else ans+=a[i]-a[i-1];
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 4392
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
int main(void){
    int a,b;cin>>a>>b;
    char t[100][100];
    rep(i,100)rep(j,100){
        if(i<50)t[i][j]='#';
        else t[i][j]='.';
    }
    a--;b--;
    for(int i=0;i<50;i+=2){
        if(a==0)break;
        for(int j=0;j<100;j+=2){
            t[i][j]='.';a--;
            if(a==0)break;
        }
        if(a==0)break;
    }
    for(int i=51;i<100;i+=2){
        if(b==0)break;
        for(int j=0;j<100;j+=2){
            t[i][j]='#';b--;
            if(b==0)break;
        }
        if(b==0)break;
    }
    cout<<100<<" "<<100<<endl;
    rep(i,100){
        rep(j,100)cout<<t[i][j];
        cout<<endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
const long long inf2=0x3f3f3f3f3f3f3f3f;
const double eps=1e-6;
const int mod=1000000007;
typedef long long ll;
int n;
int dp[1<<21];
int a[22][22];
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)scanf("%d",&a[i][j]);
	dp[0]=1;
	for(int i=0;i<(1<<n);i++){
		int pos=i==0?0:__builtin_popcount(i);
		for(int j=0;j<n;j++){
			if(!(i&(1<<j))&&a[pos][j]){
				dp[i|(1<<j)]+=dp[i];
				dp[i|(1<<j)]%=mod;
			}
		}
	}
	printf("%d\n",dp[(1<<n)-1]);
	return 0;
}

Measured memory_bytes: 8448
#include<iostream>

using namespace std;

int n,m;
char seat[100];

void sitA()
{
	for(int i=0;i<n;i++){
		if(seat[i]=='#'){ seat[i]='A'; return; }
	}
}

void sitB()
{
	for(int i=n-1;i>=0;i--){
		if(seat[i]=='#'
		&&!(i+1<n &&seat[i+1]=='A')
		&&!(0<=i-1&&seat[i-1]=='A')){ seat[i]='B'; return; }
	}

	for(int i=0;i<n;i++){
		if(seat[i]=='#'){ seat[i]='B'; return; }
	}
}

void sitC()
{
	for(int i=0;i<n;i++){
		if(seat[i]!='#'){
			if(i+1<n &&seat[i+1]=='#'){ seat[i+1]='C'; return; }
			if(0<=i-1&&seat[i-1]=='#'){ seat[i-1]='C'; return; }
		}
	}
	seat[n/2]='C';
}

void sitD()
{
	int dmax=0,imax;
	for(int i=0;i<n;i++){
		if(seat[i]=='#'){
			int disL=0,disR=0;
			for(int j=i;seat[j]=='#';j--,disL++){
				if(j==0){ disL=10000; break; }
			}
			for(int j=i;seat[j]=='#';j++,disR++){
				if(j==n-1){ disR=10000; break; }
			}
			int dis=min(disL,disR);
			if(dmax<dis)	dmax=dis,imax=i;
		}
	}
	seat[imax]='D';
}

int main()
{
	for(;cin>>n>>m,n||m;){
		for(int i=0;i<n;i++)seat[i]='#';
		for(int i=0;i<m;i++){
			char c;	cin>>c;
			switch(c){
				case 'A':	sitA();	break;
				case 'B':	sitB();	break;
				case 'C':	sitC();	break;
				case 'D':	sitD();	break;
			}
		}
		for(int i=0;i<n;i++)	cout<<seat[i];
		cout<<endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
#include<ctype.h>

int main(void){

char str;
int char_count[26];
int i;
//for(i=0;i<1205;i++)str[i]='\n';
for(i=0;i<26;i++)char_count[i]=0;
while ( scanf("%c", &str) != EOF ){
	if(isupper(str)){str=tolower(str);}
	if(isalpha(str)){
		char_count[str-'a']++;
	    }
}
for(i=0;i<26;i++){
	printf("%c : %d\n",'a'+i,char_count[i]);
}
return 0;
}

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

using namespace std;

#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v) {std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

long long bfs(long long N, long long M, long long K, long long sum, long long count) {

    if (count == N) {
        return max(1LL, sum - K);
    }

    long long ret = 0;
    for (long long i = 1; i <= M; i++) {
        ret += bfs(N, M, K, sum + i, count + 1);
    }
    return ret;
}

int main() {

    while (true) {

        long long N, M, K;
        cin >> N >> M >> K;

        //n個
        //m面
        //-k
        if (!(N | M | K)) break;

        long long sum = bfs(N, M, K, 0, 0);
        long long denominator = 1LL;
        for (long long i = 1; i <= N; i++) denominator *= M;
        long double ans = (long double) sum / (long double) denominator;

        cout << fixed << setprecision(10) << ans << endl;

    }

    return 0;
}














































Measured memory_bytes: 3224
#include <stdio.h>

int top, a[10000];

void push(int x)
{
    a[++top] = x;
}

int pop()
{
    top--;
    return a[top + 1];
}

int main()
{
    int a, b;
    top = 0;
    char s[1000];
    while (scanf("%s", s) != -1)
    {
        if (s[0] == '+')
        {
            a = pop();
            b = pop();
            push(a + b);
        }
        else if (s[0] == '-')
        {
            b = pop();
            a = pop();
            push(a - b);
        }
        else if (s[0] == '*')
        {
            a = pop();
            b = pop();
            push(a * b);
        }
        else
        {
            push(atoi(s));
        }
    }
    printf("%d\n", pop());
    return 0;
}


Measured memory_bytes: 2088
s = input()
r = 'Yes'
s2 = s[0:((len(s)-1)//2)]
s3 = s[((len(s)+3)//2)-1:len(s)]
if s != s[::-1] or s2 != s2[::-1] or s3 != s3[::-1]:
	r = 'No'
print(r)

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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int dp[100010];
bool hole[100010];

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

	int N, M, a;
	cin >> N >> M;
	rep(i, 0, M)
	{
		cin >> a;
		hole[a - 1] = true;
	}

	dp[0] = 1;
	rep(i, 0, N)
	{
		if (hole[i])continue;
		dp[i + 1] += dp[i];
		if (0 < i)dp[i + 1] += dp[i - 1];
		dp[i + 1] %= MOD;
	}

	cout << dp[N] << endl;

	return 0;
}

Measured memory_bytes: 1152
#include<stdio.h>
typedef long long ll;
#define min(a, b) ((a)>(b)?(b):(a))
#define max(a, b) ((a)>(b)?(a):(b))
#define MAX 200200
const ll mod = 1000000007ll;
ll fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[0] = 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(int n, int k){
	if(n < k) return 0;
	if(n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n-k] % mod) % mod;
}
int main(){
	COMinit();
	ll N, M, K, ans = 0;
	scanf("%lld%lld%lld",&N,&M,&K);
	for(int i=0; i<N; i++){
		ans += (i * (N-i) * M * M) % mod;
	}
	for(int i=0; i<M; i++){
		ans += (i * (M-i) * N * N) % mod;
	}
	ans %= mod;
	ans *= COM(N*M-2, K-2);
	printf("%lld\n",ans%mod);
	return 0;
}

Measured memory_bytes: 6428
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a,b;
  cin >> a >> b;
  for (int i=1; i<=a; i++) {
    char s;
    cin >> s;
    if (i == b) {
      s = (s+32);
    }
    cout << s;
  }
}

Measured memory_bytes: 256