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

using namespace std;

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

struct Edge{int to, d;};
struct Status{
  int cal, pos, bit;
  bool operator<(const Status &s) const {return cal > s.cal;}
};

template<class A, class B> B convert(A a) {
  stringstream ss;
  B b;
  ss << a;
  ss >> b;
  return b;
}

int main() {
  while (true) {
    int m, n, k, d;
    cin >> m >> n >> k >> d;
    if (m == 0) break;
    int c[m];
    rep (i, m) cin >> c[i];
    vector<Edge> edge[2 + m + n];
    rep (i, d) {
      string a, b;
      int dis;
      cin >> a >> b >> dis;
      int aa, bb;
      if (a == "H") aa = 0;
      else if (a == "D") aa = 1;
      else if (a[0] == 'C') aa = convert<string, int>(a.substr(1)) + 1;
      else aa = convert<string, int>(a.substr(1)) + 1 + m;
      if (b == "H") bb = 0;
      else if (b == "D") bb = 1;
      else if (b[0] == 'C') bb = convert<string, int>(b.substr(1)) + 1;
      else bb = convert<string, int>(b.substr(1)) + 1 + m;
      edge[aa].push_back((Edge){bb, dis * k});
      edge[bb].push_back((Edge){aa, dis * k});
    }
    priority_queue<Status> que;
    que.push((Status){0, 0, 0});
    int dis[1 << m][2 + m + n];
    rep (i, 1 << m) rep (j, 2 + m + n) dis[i][j] = 1e9;
    while (!que.empty()) {
      Status now = que.top();
      que.pop();
      if (dis[now.bit][now.pos] <= now.cal) continue;
      dis[now.bit][now.pos] = now.cal;
      rep (i, edge[now.pos].size()) {
	Edge e = edge[now.pos][i];
	if (2 <= e.to && e.to < 2 + m) {
	  if (now.bit & (1 << (e.to - 2))) continue;
	  que.push((Status){now.cal + e.d - c[e.to - 2], e.to, now.bit | (1 << (e.to - 2))});
	} else {
	  que.push((Status){now.cal + e.d, e.to, now.bit});
	}
      }
    }
    int res = 1e9;
    rep (i, 1 << m) res = min(res, dis[i][1]);
    cout << res << endl;
  }
}

Measured memory_bytes: 1508
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 505;
int n,m;
char s[MAXN][MAXN],ans[2][MAXN][MAXN];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		scanf("%s",s[i]+1);
	for(int i=1;i<=n;++i)
		ans[0][i][1]=ans[1][i][m]='#',ans[0][i][m]=ans[1][i][1]='.';
	for(int i=1;i<=n;++i){
		for(int j=2;j<m;++j){
			ans[i&1][i][j]='#';
			if(s[i][j]=='#')ans[(i&1)^1][i][j]='#';
			else ans[(i&1)^1][i][j]='.';
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j)
			printf("%c",ans[0][i][j]);
		puts("");
	}
	puts("");
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j)
			printf("%c",ans[1][i][j]);
		puts("");
	}
	return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
template <typename T> bool chmax(T &u, const T z) { if (u < z) {u = z; return true;} else return false; }
template <typename T> bool chmin(T &u, const T z) { if (u > z) {u = z; return true;} else return false; }
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
typedef pair<ll, ll> P;
const ll INF = 1LL << 60;
const int MOD = 1000000007;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
//解説写し
struct mint {
  long long x; // typedef long long ll;
  mint(long long x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(long long t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime MOD
  mint inv() const { return pow(MOD-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int n;
vector<int>to[200005];
mint ans;
int dfs(int v,int p=-1){
  int res=1;
  vector<int>ts;
  for(int u:to[v]){
    if(u==p)continue;
    int t=dfs(u,v);
    res+=t;
    ts.push_back(t);
  }
  if(p!=-1){
    ts.push_back(n-res);
  }
  mint now=mint(2).pow(n-1)-1;
  for(int t:ts){
    now-=mint(2).pow(t)-1;
  }
  ans+=now;
  return res;
}
int main(){
  cin>>n;
  rep(i,n-1){
    int a,b;
    cin>>a>>b;
    --a;--b;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  dfs(0);
  ans/=mint(2).pow(n);
  cout<<ans.x<<endl;
  return 0;
}


Measured memory_bytes: 32516
#include <bits/stdc++.h>
using namespace std;
long long INF = 1000000000000000000;
pair<long long, bool> mul(long long A, long long B){
  long long ans = 0;
  bool A_inf = false;
  while (B > 0){
    if (B % 2 == 1){
      ans += A;
      if (A_inf){
        return make_pair(-1, true);
      }
      if (ans > INF){
        return make_pair(-1, true);
      }
    }
    A = A + A;
    if (A > INF){
      A_inf = true;
    }
    B /= 2;
  }
  return make_pair(ans, false);
}
int main(){
  int N;
  cin >> N;
  vector<long long> A(N);
  bool zero = false;
  for (int i = 0; i < N; i++){
    cin >> A[i];
    if (A[i] == 0){
      zero = true;
    }
  }
  if (zero){
    cout << 0 << endl;
  } else {
    long long tmp = 1;
    bool inf = false;
    for (int i = 0; i < N; i++){
      pair<long long, bool> res = mul(tmp, A[i]);
      if (res.second){
        inf = true;
      } else {
        tmp = res.first;
      }
    }
    if (inf){
      cout << -1 << endl;
    } else {
      cout << tmp << endl;
    }
  }
}

Measured memory_bytes: 4052
#include <iostream>
#include <string>

using namespace std;

int main(){

  int N;
  cin >> N;
  string moji;
  cin >> moji;
  int ans = 0;

  for(int i = 0;i < N-2;i++){
    if(moji[i] == 'A' && moji[i + 1] == 'B' && moji[i + 2] == 'C')
      ans++;
  }

  cout << ans;

  return 0;
}


Measured memory_bytes: 256
require 'prime'

MOD = 10 ** 9 + 7

n, m = gets.split.map(&:to_i)
inv = Array.new(2*n+1)
inv[1] = 1
fac = Array.new(2*n+1)
fac[0] = fac[1] = 1
f_inv = Array.new(2*n+1)
f_inv[0] = f_inv[1] = 1
(2..2*n).each do |i|
  inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
  fac[i] = fac[i-1] * i % MOD;
  f_inv[i] = f_inv[i-1] * inv[i] % MOD
end

pd = m.prime_division

count = 1
pd.each do |_, k|
  next if k > n
  count = count * (fac[n + k - 1] * (f_inv[k] * f_inv[n-1] % MOD) % MOD) % MOD
end
puts count

Measured memory_bytes: 6652
using System;

namespace B.Exponential
{
    class Program
    {
        static void Main(string[] args)
        {
            var X = int.Parse(Console.ReadLine());
            int ans = 0;

            for (int b = 1; b <= Math.Floor(Math.Sqrt(X)); b++)
            {
                for (int p = 2; Math.Pow(b, p) <= X; p++)
                {
                    ans = Math.Max(ans, (int)Math.Pow(b,p));
                    if (b == 1) break;
                }
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13268
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define _ ios::sync_with_stdio(0);cin.tie(0);

using namespace std;

typedef long long ll;

const int MAX = 1e5+5;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int main(){_
	int a,b;
	cin >> a >> b;
	cout << max(0, a-2*b) << endl;

}


Measured memory_bytes: 256
N = int(input())

G = [list(map(int, input().split())) for _ in range(N)]
cur = [0] * N
edge = [0] * N
for i in range(N):
    edge[i] = G[i][0] - 1

day = 0
player = set(range(N))
cnt = 0
while len(player) > 0:
    day += 1
    game = set()
    for i in player:
        e = edge[i]
        if i == edge[e] and i != e:
            game.add(i)
            game.add(e)
    player = set()
    for j in game:
        cur[j] += 1
        c = cur[j]
        if c >= N - 1:
            edge[j] = j
        else:
            edge[j] = G[j][c] - 1
            player.add(j)

if min(cur) != N - 1:
    ans = -1
else:
    ans = day
print(ans)


Measured memory_bytes: 55132
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> Pii;
typedef pair<int,string> Pis;
typedef pair<Pii,Pis> P;
int n,m;P t[10];
int main(){
  while(cin>>n&&n){
    for(int i=0;i<n;i++){
      cin>>t[i].second.second;
      t[i].second.first=i;
      t[i].first.first=t[i].first.second=0;
      for(int j=0;j<n-1;j++){
	cin>>m;
	if(m==0)t[i].first.first--;
	else if(m==1)t[i].first.second++;
      }
    }
    sort(t,t+n);for(int i=0;i<n;i++)cout<<t[i].second.second<<endl; 
  }
}


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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int main(){
	string s;
	ll k;
	cin >> s >> k;
	int n=s.length();

	vector<int> v;
	int cnt=1;
	char c=s[0];
	for(int i=1; i<n; i++){
		if(s[i]==c) cnt++;
		else{
			v.push_back(cnt);
			cnt=1;
			c=s[i];
		}
	}
	v.push_back(cnt);

	ll ans=0;
	if(v.size()==1){
		ans=k*n/2;
	}else if(s[0]!=s[n-1]){
		for(int i=0; i<v.size(); i++) ans+=v[i]/2;
		ans*=k;
	}else{
		ans=v[0]/2;
		ll t=0;
		for(int i=1; i<v.size()-1; i++) t+=v[i]/2;
		ans+=k*t+(k-1)*((v[0]+v[v.size()-1])/2);
		ans+=v[v.size()-1]/2;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <list>
using namespace std;
using link = pair<int, int>;
static const int N = 100000;

list<link> g[N];
int out[N];
bool v[N];
int k = 1;


void dfs(int s, int l) {
    v[s] = true;
    int m = 1;
    for (auto li : g[s]) {
        int t = li.first;
        if (v[t] == true) continue;
        if (m == l) m++;
        if (m > k) k = m;
        out[li.second] = m;
        dfs(t, m);
        m++;
    }
}


int main() {
    int n; cin >> n;
    int a, b;

    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(link(b, i));
        g[b].push_back(link(a, i));
    }

    for (int i = 0; i < n; i++) {
        if (!v[i]) dfs(i, 0);
    }

    cout << k << endl;
    for (int i = 0; i < n - 1; i++) {
        cout << out[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 8704
#!/usr/bin/env python3
#ABC107 C
n,k = map(int,input().split())
x = list(map(int,input().split()))

ans = float('inf')
for i in range(n-k+1):
    l = x[i]
    r = x[i+k-1]
    ans = min(ans,abs(r)+abs(l-r))
    ans = min(ans,abs(l)+abs(r-l))
print(ans)


Measured memory_bytes: 62576
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Fast() ios_base::sync_with_stdio(false);cin.tie(NULL);
int main()
{
     Fast();
     ll n,t,x,y,i,j,k,mini=LONG_LONG_MAX,maxi=LONG_LONG_MIN,flag =0 ,sum=0,mul=1;
     vector<ll>vi;
     vector<ll> :: iterator it;
     string s,s1="";
     cin>>n;
     for(i = 0 ;i<n; i++)
     {
         cin>>x;
         vi.push_back(x);
     }

     for(i = 0 ;i<n ;i++  )
     {
         if(vi[i]==sum+1)
            sum++;
     }
     if(sum == 0)
        cout<<-1<<endl;
     else
     cout<<n-sum<<endl;


}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int h, w;
  cin >> h >> w;
  
  vector<vector<char>> s(h + 2, vector<char>(w + 2, '#'));
  for(int i = 1; i <= h; i++){
    for(int j = 1; j <= w; j++){
      cin >> s.at(i).at(j);
    }
  }
  
  vector<vector<int>> x(h + 2, vector<int>(w + 2, 9999));
  x.at(1).at(1) = 0;
  
  queue<pair<int, int>> q;
  q.push(make_pair(1, 1));
  vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
  while(!(q.empty())){
    pair<int, int> p = q.front();
    q.pop();
    for(int i = 0; i < 4; i++){
      if(s.at(p.first + dx[i]).at(p.second + dy[i]) == '.' && x.at(p.first + dx[i]).at(p.second + dy[i]) == 9999){
        x.at(p.first + dx[i]).at(p.second + dy[i]) = x.at(p.first).at(p.second) + 1;
        q.push(make_pair(p.first + dx[i], p.second + dy[i]));
      }
    }
  }
  
  if(x.at(h).at(w) == 9999){
    cout << -1 << "\n";
    return 0;
  }
  
  int count = 0;
  for(int i = 1; i <= h; i++){
    for(int j = 1; j <= w; j++){
      if(s.at(i).at(j) == '.') count++;
    }
  }
  cout << count - x.at(h).at(w) - 1 << "\n";
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.text.*;

public class Main {
	static class Data{
		int x,y;
		public Data(int xx, int yy){
			x = xx;
			y = yy;
		}
	}
	
	public static void main(String args[]){
		Scanner in = new Scanner(System.in);
		while(true){
			int w = in.nextInt();
			int h = in.nextInt();
			if((w|h)==0) break;
			boolean[][] field = new boolean[h][w];
			int[][] counter = new int[h][w];
			int sx=0,sy=0;
			
			for(int i=0; i<h; i++){
				String str = in.next();
				char[] ch = str.toCharArray();
				for(int j=0; j<w; j++){
					counter[i][j] = 0;
					if(ch[j]=='#') field[i][j] = false;
					else{
						field[i][j] = true;
						if(ch[j] == '@'){
							sx = i;
							sy = j;
							counter[i][j] = 1;
						}
					}
				}
			}
			
			LinkedList<Data> queue = new LinkedList<Data>();
			queue.add(new Data(sx,sy));
			while(!queue.isEmpty()){
				Data now = queue.poll();
				if(now.x>0 && field[now.x-1][now.y] && counter[now.x-1][now.y]==0){
					counter[now.x-1][now.y]=1;
					queue.add(new Data(now.x-1,now.y));
				}
				if(now.y>0 && field[now.x][now.y-1] && counter[now.x][now.y-1]==0){
					counter[now.x][now.y-1]=1;
					queue.add(new Data(now.x,now.y-1));
				}
				if(now.x<h-1 && field[now.x+1][now.y] && counter[now.x+1][now.y]==0){
					counter[now.x+1][now.y]=1;
					queue.add(new Data(now.x+1,now.y));
				}
				if(now.y<w-1 && field[now.x][now.y+1] && counter[now.x][now.y+1]==0){
					counter[now.x][now.y+1]=1;
					queue.add(new Data(now.x,now.y+1));
				}
			}
			
			int ans = 0;
			for(int i=0; i<h; i++){
				for(int j=0; j<w; j++){
					ans += counter[i][j];
				}
			}
			
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 12000
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

vector<ll> A;
vector<ll> F;

bool isOK(ll preans, ll key){
  ll counter = 0;
  ll n = (int)A.size();
  rep(i,n){
    if(A[i]*F[i] > preans){
      ll toa = preans/F[i];
      counter += A[i] - toa;
    }
  }
  if(counter <= key) return true;
  else return false;
}

int main(){
  ll ans;
  ll N, K; cin >> N >> K;
  A.resize(N); rep(i,N) cin >> A[i];
  F.resize(N); rep(i,N) cin >> F[i];
  sort(rall(A));
  sort(all(F));
  ll ans_min = 0;
  ll ans_max = 0;
  rep(i,N){
    ans_max = max(ans_max, A[i]*F[i]);
  }

  ll ng = -1;
  ll ok = ans_max;
  while(abs(ok-ng) > 1){
    ll mid = (ok+ng)/2;
    if(isOK(mid,K)) ok = mid;
    else ng = mid;
  }
  cout << ok << endl;
  return 0;
}


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

#define INF 1e9
#define llINF 1e18
#define MOD 1e9+7
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
using namespace std;
string hash;
int a,b,c,d;
int po=0;
int op(int left,int right,char ope){
  if(ope=='+')
    return left | right;
  if(ope=='^')
    return left ^ right;
  if(ope=='*')
    return left & right;
}

int dfs(){
  if(hash[po]=='['){
    po++;
    dfs();
  }else if(hash[po]=='+'||hash[po]=='*'||hash[po]=='^'){
    char ope=hash[po];
    po++;
    int left=dfs();
    int right=dfs();
    po++;
    return op(left,right,ope);
  }else{
    if(hash[po]=='a'){
      po++;
      return a;
    }else if(hash[po]=='b'){
      po++;
      return b;
    }else if(hash[po]=='c'){
      po++;
      return c;
    }else if(hash[po]=='d'){
      po++;
      return d;
    }
  }
}
int main(){
  while(cin>>hash,hash!="."){
    po=0;
    string num;cin>>num;
    a=num[0]-'0';b=num[1]-'0';
    c=num[2]-'0';d=num[3]-'0';
    int ori=dfs();
    int cnt=0;
    for(int i=0;i<10000;i++){
      po=0;
      a=i/1000;b=(i/100)%10;
      c=(i/10)%10;d=i%10;
      if(ori==dfs())cnt++;
    }
    cout<<ori<<" "<<cnt<<endl;
  }
  return 0;
}



Measured memory_bytes: 3080
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";
		Main main = new Main();

		while ((line = br.readLine()) != null) {
			if (line.contains(" ")) {
				String[] sp = line.split(" ");
				double[] dp = new double[6];
				for (int i = 0; i < dp.length; i++) {
					dp[i] = Double.parseDouble(sp[i]);
				}
				Circle circle1 = main.new Circle(dp[0], dp[1], dp[2]);
				Circle circle2 = main.new Circle(dp[3], dp[4], dp[5]);
				System.out.println(circle1.getTopology(circle2));
			}
		}
	}

	public class Circle {

		public static final int TOPOLOGY_OUTER = 2;
		public static final int TOPOLOGY_INNER = -2;
		public static final int TOPOLOGY_CROSS = 1;
		public static final int TOPOLOGY_FARAWAY = 0;

		private double x;
		private double y;
		private double r;

		public Circle(double x, double y, double r) {
			this.x = x;
			this.y = y;
			this.r = r;
		}

		public double x() {
			return this.x;
		}

		public double y() {
			return this.y;
		}

		public double r() {
			return this.r;
		}

		public int getTopology(Circle other) {

			int retval = TOPOLOGY_FARAWAY;

			// 中心間の距離
			double distance;
			distance = Math.sqrt(Math.pow(x - other.x(), 2)
					+ Math.pow(y - other.y(), 2));
			// 位相
			if (distance + other.r() < r)
				return TOPOLOGY_OUTER;
			if (distance + r < other.r())
				return TOPOLOGY_INNER;
			if (distance <= r + other.r())
				return TOPOLOGY_CROSS;
			if (distance > r + other.r())
				return TOPOLOGY_FARAWAY;

			return retval;
		}
	}
}

Measured memory_bytes: 16944
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

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

func main() {
	var n, h int
	fmt.Scan(&n, &h)
	var a, amax int
	b := make([]int, n)
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	for i := 0; i < n; i++ {
		sc.Scan()
		a, _ = strconv.Atoi(sc.Text())
		amax = max(amax, a)
		sc.Scan()
		b[i], _ = strconv.Atoi(sc.Text())
	}
	sort.Sort(sort.Reverse(sort.IntSlice(b)))
	ans := 0
	for _, e := range b {
		if amax < e {
			h -= e
			ans++
			if h <= 0 {
				break
			}
		}
	}
	if h > 0 {
		ans += (h + amax - 1) / amax
	}
	fmt.Println(ans)
}


Measured memory_bytes: 4608
#include <iostream>
#include <string>
#include <vector>
#include <random>
#include <algorithm>

using std::cout;
using std::cerr;
using std::cin;
using std::endl;

using std::vector;
using std::string;

void func() {

	int N;
	cin >> N;
	//int H[100];
	vector<int> H;
	for (int i = 0; i < N; i++) {
		int h;
		cin >> h;
		H.push_back(h);
	}


	int cnt = 0;
	while (true) {
		
		for (int i = 0; i < N; i++) {
			cerr << H[i] << " ";
		}
		cerr << endl;

		int i0=-1;
		bool flag = false;
		for (int i = 0; i < N; ++i) {
			if (H[i] > 0) {
				flag = true;
				H[i]--;
			}
			else if(flag==true && H[i] == 0){
				break;
			}
		}
		if (flag == false) {
			break;
		}
		cnt++;
	}
	cout << cnt << endl;

}
int main() {
	//funcB();
	func();

}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100005;
vector<int> v[nmax];
int d[nmax],nxt[nmax],dpth[nmax],viz[nmax],cyc[nmax];
int n,k,cate,i,x,nr;
void recu(int x)
{
    if(x==1) return;
    if(d[x]) return;
    recu(nxt[x]);
    d[x]=d[nxt[x]]+1;
    v[nxt[x]].push_back(x);
}
void dfs(int x)
{
    dpth[x]=1;
    for(int i=0;i<v[x].size();i++)
    {
        dfs(v[x][i]);
        dpth[x]=max(dpth[x],dpth[v[x][i]]+1);
    }
    if(dpth[x]==k&&nxt[x]!=1)
        dpth[x]=0,cate+=1;
}
int solve()
{
    int ret=0;
    if(nxt[1]!=1) ret++,nxt[1]=1;
    if(k==1)
    {
        for(i=2;i<=n;i++)
            ret+=(nxt[i]!=1);
        return ret;
    }
    dfs(1);
    ret+=cate;
    return ret;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>k;
    for(i=1;i<=n;i++)
        cin>>nxt[i];
    int x=i;
    while(!viz[x])
    {
        viz[x]=1;
        cyc[++nr]=x;
        x=nxt[x];
    }
    for(i=2;i<=nr;i++)
    {
        v[cyc[i-1]].push_back(cyc[i]);
        d[cyc[i]]=nr+1-i;
    }
    for(i=2;i<=n;i++)
        if(!d[i])
            recu(i);
    cout<<solve();
    return 0;
}

Measured memory_bytes: 11648
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N, K = map(int, input().split())
for i in range(1,K+1):
    print(cmb(N-K+1,i,mod)*cmb(K-1,i-1,mod)%mod)


Measured memory_bytes: 4596
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF 1e18L
#define MININF -1e18L
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> intint;

int main(void)
{
    int a;
    cin >> a;
    vector<int> p(a);
    for (int i = 0; i < a; i++) {
        cin >> p[i];
    }
    sort(ALL(p));

    int ans = 0;
    for (int i = 0; i < a - 1; i++) {
        ans += p[i];
    }
    ans += p[a - 1] / 2;

    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	static ArrayList<Long> tableA= new ArrayList<Long>();
	static ArrayList<Long> tableB= new ArrayList<Long>();
	static int numA;
	static int numB;
	static long timeLimit;

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		numA = sc.nextInt();
		numB = sc.nextInt();
		timeLimit = sc.nextLong();

		long tmp;
		int firstNum = 0;

		// A棚のN冊の本を読む時間を格納する
		tmp = 0;
		tableA.add(tmp);
		for(int i=1;i<=numA;i++) {
			tmp = tmp + sc.nextLong();
			tableA.add(tmp);
		}

		// B棚のN冊の本を読む時間を格納する
		tmp = 0;
		tableB.add(tmp);
		for(int i=1;i<=numB;i++) {
			tmp = tmp + sc.nextLong();
			tableB.add(tmp);
		}
		sc.close();

		int result = 0;
		int indexB = 0;
		for(int i=0;i <= numA;i++) {

			if(result - i < 0) {
				indexB = 0;
			}else {
				indexB = result - i;
			}

			for(;indexB <= numB;indexB++) {

				if(indexB > numB) {
					break;
				}

				if(tableA.get(i) + tableB.get(indexB) <= timeLimit) {
					if(i+indexB > result) {
						result = i + indexB;
					}
				}else {
					break;
				}

			}
		}

		System.out.println(result);

	}

}

Measured memory_bytes: 64052
import collections

x, y = map(int, input().split())
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
z=gcd(x,y)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
print(len(collections.Counter(prime_factorize(z))) +1 )


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

int main(){
    int N,T,A,H,divi;
    int min = 1000000,idx = 6;
    cin >> N >> T >> A;
    for(int i = 1;i <= N; i++){
        cin >> H;
        divi = (T * 1000 - H * 6) -  A * 1000;
        if(divi < 0)  divi = - divi;
        if(min > divi) min = divi , idx = i;
    }
    cout << idx << endl;
}


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

int main() {
  int N, M;
  cin >> N >> M;

  vector<int> town(N, 0);
  rep(i, M) {
    int a, b;
    cin >> a >> b;
    town.at(a-1)++;
    town.at(b-1)++;
  }

  rep(i, N) cout << town.at(i) << endl;;
}



Measured memory_bytes: 256
a, b =map(int,input().split())
A = 0
B = 0
for i in range(b):
    A += a*(10**i)
    
for i in range(a):
    B += b*(10**i)

if a < b:
    print(A)
elif a >b:
    print(B)
else:
    print(min(A,B))

Measured memory_bytes: 3060
// 基本テンプレート
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

const int S = 100;
int dp[S+10][S+10], is_prime[S+10];
signed main() {
    fill(is_prime, is_prime + S, true);
    is_prime[0] = is_prime[1] = false;

    vector<int> primes;
    for(int k=2; k<S; k++) {
        if(is_prime[k]) {
            primes.push_back(k);
            for(int num=2*k; num<S; num+=k) {
                is_prime[num] = false;
            }
        }
    }

    int N; cin >> N;
    dp[0][1] = 1;

    for(size_t i=0; i<primes.size(); i++) {
        int x = primes[i];
        int cnt = 0;
        for(int k=1; k<=N; k++) {
            int num = k;
            while(num % x == 0) cnt++, num /= x;
        }

        /*
        if(cnt == 0) {
            for(int j=0; j<S; j++) {
                dp[i+1][j] = dp[i][j];
            }
            continue;
        }
        */

        for(int j=0; j<S; j++) {    
            for(int k=1; k<=cnt+1; k++) {
                int nj = j * k;
                if(nj > S) continue;
                // if(k > 0) fprintf(stderr, "prime = %lld, cnt = %lld, nj = %lld, add = %lld\n", x, cnt, nj, dp[i][j]);
                dp[i+1][nj] += dp[i][j];
            }
        }
    }

    int M = primes.size();
    cout << dp[M][75] << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
using int64 = long long;
const int INF = 1 << 30;
 
 
int main() {
  int A, B;
  cin >> A >> B;
  cout << (B - A) * ((B - A) + 1) / 2 - B << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.regex.Matcher;
import java.util.regex.Pattern;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String input = br.readLine();
		int q = Integer.parseInt(input);
		
//		System.out.println("start init");
		PrimeNumberGenerator pg = new PrimeNumberGenerator();
		
		int similar[] = new int[100000+1];
		for(int i = 1; i < similar.length ; i++){
			similar[i] = similar[i - 1];
			
			if(pg.isPrime(i) && pg.isPrime((i+1)/2)){
				similar[i] ++;
			}
		}
		
//		System.out.println("end init");
		
		for(int i = 0; i < q; i++){
			String[] tmpArray = br.readLine().split(" ");
			int l = Integer.parseInt(tmpArray[0]);
			int r = Integer.parseInt(tmpArray[1]);
			
			System.out.println(similar[r] - similar[l - 1]);
		}
	}

}

class PrimeNumberGenerator {
    private final int N = 100000;
    private boolean[] isPrime= new boolean[N + 1];
 
    public PrimeNumberGenerator() {
        Arrays.fill(isPrime, true);
 
        isPrime[0] = false;
        isPrime[1] = false;
 
        int limit = (int)Math.sqrt(N);
        for(int i = 2; i <= limit ; i++){
 
            if(isPrime[i] == false){
                continue;
            }
 
            for(int j = i * 2; j <= N; j += i){
                isPrime[j] = false;
            }
        }
    }
 
    public boolean isPrime(int index){
        return isPrime[index];
    }
}


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

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

    long long int a,b,c,k;
    cin>>a>>b>>c>>k;
    long long int result=0;
    if(k<=a)
        result=k*1;
    else if(k<=(a+b))
        result=a*1;
    else{
        int temp=k;
        temp=temp-(a+b);
        //cout<<temp;
        result=(a-temp)*1;
    }
    cout<<result;
}


Measured memory_bytes: 3632
n = input()
data = []
space = []
for i in ['S ', 'H ', 'C ', 'D ']:
    for j in map( str , xrange(1, 14)):
        data.append(i + j)   
for i in xrange(n):
    data.remove(raw_input())
for i in xrange(len(data)):
    print data[i]

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

int p[100010];

int root(int x){
    if(p[x] == x) return x;
    return p[x] = root(p[x]);
}

void unite(int x, int y){
    x = root(x);
    y = root(y);
    if(x == y) return;
    p[x] = y;
}

int main(){
    int n, m;
    cin >> n >> m;
    rep(i, n){
        p[i] = i;
    }
    rep(i, m){
        int a, b;
        cin >> a >> b;
        a--; b--;
        unite(a, b);
    }
    set<int> out;
    rep(i, n){
        out.insert(root(i));
    }
    cout << out.size() - 1 << endl;
}

Measured memory_bytes: 7864
#include <bits/stdc++.h>
#define LL long long
#define pr pair<LL, LL>
#define FASTER ios_base::sync_with_stdio(false); cin.tie(0);
using namespace std;

int main()
{
    FASTER;

    int N;
    cin >> N;
    LL cnt = 0;
    while(N--){
        int l, r;
        cin >> l >> r;
        cnt += (r-l+1);
    }
    cout << cnt << "\n";
    return 0;
}


Measured memory_bytes: 256
main =
  fmap (map read . words ) getLine >>= \[x,y] ->
  let z = y `div` x
      ans = if z > 0 then (solve z) + 1 else 0
  in print ans

-- 3,6,12,   24
-- 12 = 3 * 2^2
-- 20 = 3 * 2^2 + 8
-- 24 = 3 * 2^3
--
-- 8 = 2^3 + 0
-- 6 = 2^2 + 2

solve :: Integer -> Integer
solve 0 = 0
solve 1 = 0
solve n = 1 + solve (n `div` 2)

Measured memory_bytes: 508
#include<queue>
#include<stack>
#include<math.h>
#include<cmath>
#include<bitset>
#include<stdio.h>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<iostream>
#include<utility>
#include<functional>
#include<deque>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
template<typename T>
vector<T> zaatsu(vector<T> &c1){
  vector<T> vals;
  int n=(int)c1.size();
  for(int i=0;i<n;i++){
    for(T d=0;d<=1;d++){
      vals.push_back(c1[i]+d);
    }
  }
  sort(vals.begin(),vals.end());
  vals.erase(unique(vals.begin(),vals.end()),vals.end());
  for(int i=0;i<n;i++){
    c1[i]=lower_bound(vals.begin(),vals.end(),c1[i])-vals.begin();
  }
  return vals;
}
int main(){
  ll n,k,i,j,l,m;
  cin >> n >> k;
  vector<ll> x1(n),y1(n);
  for(i=0;i<n;i++){
    cin >> x1[i] >> y1[i];
  }
  vector<ll> x=zaatsu(x1);
  vector<ll> y=zaatsu(y1);
  ll a[110][110],s[110][110];
  for(i=0;i<=x.size();i++){
    for(j=0;j<=y.size();j++){
      s[i][j]=0,a[i][j]=0;
    }
  }
  for(i=0;i<n;i++){
    a[x1[i]][y1[i]]++;
  }
  for(i=0;i<x.size();i++){
    for(j=0;j<y.size();j++){
      s[i+1][j+1]=s[i+1][j]+s[i][j+1]-s[i][j]+a[i][j];
    }
  }
  ll ans=5000000000000000000;
  for(i=0;i<x.size();i++){
    for(j=0;j<y.size();j++){
      for(l=i+1;l<=x.size();l++){
        for(m=j+1;m<=y.size();m++){
          if(s[l][m]+s[i][j]-s[l][j]-s[i][m]>=k){
            ans=min(ans,(x[l-1]-x[i])*(y[m-1]-y[j]));
          }
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 384
#define _CRT_SECURE_NO_WARNINGS
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<random>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())


#define MOD 1000000007




long long dp[41][1 << 16];


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, x, y, z;
	cin >> n >> x >> y >> z;

	const int haiku = (1 << x - 1) | (1 << x + y - 1) | (1 << x + y + z - 1);
	dp[0][0] = 1;
	rep(i,n) {
		rep(j,1<<x+y+z-1) if(dp[i][j]){
			dp[i][j] %= MOD;
			for (int a = 1; a <= 10;a++) {
				int b = j << a;
				b |= 1 << a - 1;
				if ((b&haiku) != haiku) {
					dp[i + 1][b&((1 << x + y + z - 1) - 1)] += dp[i][j];
				}
			}
		}
	}

	long long ans = 1;
	rep(i, n)(ans *= 10) %= MOD;
	rep(i,1<<x+y+z-1) {
		(ans -= dp[n][i]) %= MOD;
	}
	ans += MOD;
	ans %= MOD;
	cout << ans << endl;

	return 0;
}

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

n = int(input())


l = []

for i in range(n):
    ll = []
    s, p = input().split()
    ll.append(s)
    ll.append(int(p))
    ll.append(i+1)
    l.append(ll)

l.sort(key=lambda x: x[1], reverse = True)
l.sort(key=lambda x: x[0])

for i in range(n):
    print(l[i][2])

Measured memory_bytes: 3064
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define MOD 100000
int main()
{
	while(1)
	{
		int dp[50][3010];
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		int n,m,s;
		cin >> n >> m >> s;
		if(n==0&&m==0&&s==0)break;
		for(int i=1;i<=m;i++)
		{
			for(int j=n*n-1;j>=0;j--)
			{
				for(int k=i;k<=s;k++)
				{
					dp[j+1][k]+=dp[j][k-i];
					dp[j+1][k]%=MOD;
				}
			}
		}
		cout << dp[n*n][s] << endl;
	}
	return 0;
}

Measured memory_bytes: 1756
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int h,w,n,cur=0; cin>>h>>w>>n;
    vector<int> a(n,0);
    vector<vector<int>> ans(h,vector<int>(w,0));
    rep(i,n) cin>>a[i];
    rep(i,h){
        if(i%2){
            for(int j=0;j<w;j++){
                if(a[cur]==0) cur++;
                a[cur]--;
                ans[i][j]=cur+1;
            }
        }
        else{
            for(int j=w-1;j>=0;j--){
                if(a[cur]==0) cur++;
                a[cur]--;
                ans[i][j]=cur+1;
            }
        }
    }
    rep(i,h){
        rep(j,w-1) cout<<ans[i][j]<<" ";
        cout<<ans[i][w-1]<<endl;
    }
}

Measured memory_bytes: 384
info = [0.0]

a= gets

info = a.split()

W = info[0].to_i
H = info[1].to_i
x = info[2].to_i
y = info[3].to_i
r = info[4].to_i

if (x-r) >=0 && (y-r) >=0 && (x+r) <= W && (y+r) <= H then
	print "Yes\n"
else
	print "No\n"
end

Measured memory_bytes: 6108
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for (int i=a; i<b; ++i)
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string T;
    cin >> T;
    for (int i=0; i<T.length(); ++i) {
        if (T[i]=='?') T[i]='D';
    }
    cout << T << "\n";
    return 0;
}

Measured memory_bytes: 3764
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define Rep(i,n) for(intl i=0,nn=(intl)(n);i<nn;++i)
#define Rep1(i,n) for(intl i=1,nn=(intl)(n)+1;i<nn;++i)
#define vec vector
#define fi first
#define se second
#define pub push_back
#define pob pop_back
#define SortA(v) sort(v.begin(), v.end())
#define SortD(v) sort(v.rbegin(),v.rend())
#define All(a) (a).begin(),(a).end()
#define Input(a) for(intl ii=0,nn=(intl)(a.size());ii<nn;ii++){cin>>(a).at(ii);}
#define Input2(a,b) for(intl ii=0,nn=(intl)(a.size());ii<nn;ii++){cin>>(a).at(ii);cin>>(b).at(ii);}
#define mp make_pair
#define mt make_tuple
using intl = int64_t;
using vi = vec<intl>;
using vvi = vec<vi>;
using pi = pair<intl,intl>;
using vpi = vec<pi>;
using si = set<intl>;
using vsi = vec<si>;
using mii = map<intl,intl>;
using vmii = vec<mii>;
vec<intl> dx = {0, 1, 0, -1, 1, 1, -1, -1};
vec<intl> dy = {1, 0, -1, 0, 1, -1, 1, -1};
constexpr intl INF = 9223372036854775807;


int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  intl N,M;
  cin >>N>>M;
  //if(M==0&&N==1){ cout <<"0";return 0;}
  //if(M==0&&N==2){cout << "10";return 0;}
  //if(M==0&&N==3){cout << "100";return 0;}
  vi s(M),c(M);
  Input2(s,c);
  intl ans = -1;
  Rep(i,1000){
    string I = to_string(i);
    bool OK = 1;
    if(I.size() != N){OK=0;continue;}
    Rep(j,M){
      if(I.size() < s[j]){OK=0;break;}
      if(I.at(s[j]-1) != '0'+c[j]){OK=0;break;}
    }
    if(OK){ans = i;break;}
  }
  
  cout <<ans;
}
    
    

Measured memory_bytes: 3700
#include<bits/stdc++.h>
#define int long long
using namespace std;
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; }

const int mod=1e9+7;

signed main()
{   
    int N,K; cin>>N>>K;

    if(N<K) cout<<0<<endl;
    else{
        N=N-K;
        vector<vector<int> > P(N+1,vector<int>(K+1));
        for(int j=0;j<=K;j++) P[0][j]=1;
        
        for(int i=1;i<=N;i++){
            for(int j=1;j<=K;j++){
                if(i-j>=0){
                    P[i][j]=(P[i][j-1]+P[i-j][j])%mod;
                }else{
                    P[i][j]=P[i][j-1];
                }
            }
        }
        cout<<P[N][K]<<endl;
    }
}



Measured memory_bytes: 4480
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;

using namespace std;
int main() {
	int n, k;
	cin >> n >> k;
	cout << n - k + 1 << endl;
	return 0;
}

Measured memory_bytes: 256
from fractions import *
from math import *

def lcm(x, y):
    return (x * y) // gcd(x, y)

a, b, c, d = map(int, input().split())
def f(x):
    xc = x // c
    xd = x // d
    cd = x // lcm(c, d)
    return x - xc - xd + cd

print(f(b) - f(a-1))

Measured memory_bytes: 5076
N, S = map(int, input().split())
T = list(map(int, input().split()))
t0 = T[0]
cnt = 0
for i in range(1, N):
    t1 = T[i]
    cnt += min(S, t1 - t0)
    t0 = t1
cnt += S
print(cnt)


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

int main(){
  int n,m; cin>>n>>m;
  int ans=1;
  for(int i=m/n;i>=2;i--){
    int rest=m-n*i;
    if(rest%i==0){
      ans=i;
      break;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define pb push_back
#define fi first
#define se second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void chOut(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using v_bool = vector<bool>;
using v_Pii = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

const int mod = 1000000007;
//const int mod = 998244353;



signed main(){

    int X; cin >> X;
    Out(8 - (X - 400) / 200);

    return 0;
}


Measured memory_bytes: 3648
import sys

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 LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    a,b,c,d=MI()
    while 1:
        c-=b
        if c<=0:
            print("Yes")
            break
        a-=d
        if a<=0:
            print("No")
            break

main()

Measured memory_bytes: 9080
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

def get_primes(n):
    ps = [2]
    for i in range(3, n, 2):
        for p in ps:
            if i%p == 0:
                break
        else:
            ps.append(i)
    return ps


Yes = 'Yes'
No = 'No'


import numpy as np
def main():
    N=ii()
    A=lmis()
    A.sort()
    d = np.zeros(A[-1]+1, dtype=np.uint8)
    for i in range(N):
        a = A[i]
        pa = A[i-1]
        if a != pa:
            d[a::a] += 1
        else:
            d[a] += 1
    print(sum(d[a]==1 for a in A))

main()



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

int main() {
  int N,A;
  cin >> N >> A;
  
  bool ans = false;
  
  for (int i; i <= A; i++) {
  if ((N - i) % 500 == 0) 
    ans = true;
  }
  
  if (ans)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 3636
#include <stdio.h>
#define N 500
#define M 10000

main(){
  int i, j, n, q, S[M], T[N], C=0;
 
  scanf("%d", &n);
  for(i = 0; i < n; i++){
    scanf("%d", &S[i]);
  }
  
  scanf("%d", &q);
  for(i = 0; i < q; i++){
    scanf("%d", &T[i]);
  } 

  for(i = 0; i < q; i++){
    for(j = 0; j < n; j++){
      if(S[j] == T[i]){
    C++;
    break;
      }
    }
  }
  printf("%d\n", C);
  return 0;
}

Measured memory_bytes: 640
using System;
using System.Collections.Generic;

public class CSharp
{
    public static void Main()
    {
        Kyopuro chokudai = new Kyopuro();
        chokudai.AtCoder();
    }
}

public class Kyopuro
{

    int n, m;
    int x, y;
    int[] l, r;

    public void AtCoder()
    {
        string[] input;
        input = Console.ReadLine().Split(' ');
        n = int.Parse(input[0]);
        m = int.Parse(input[1]);
        l = new int[m];
        r = new int[m];
        x = 1;
        y = n;
        for(int i=0; i<m; i++)
        {
            input = Console.ReadLine().Split(' ');
            l[i] = int.Parse(input[0]);
            r[i] = int.Parse(input[1]);
            if (x <= l[i]) x = l[i];
            if (r[i] <= y) y = r[i];
        }
        Console.WriteLine(Math.Max(y - x + 1, 0));
    }
    public static void DebugWL(object x) { System.Diagnostics.Debug.WriteLine(x); }
}


Measured memory_bytes: 17312
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


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


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'NO', True: 'YES'}
yn = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
# sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    s = S()
    skip = [0] * len(s)

    for i in range(len(s)):
        if s[i:i+5] == 'dream':
            for idx in range(i, i+5):
                skip[idx] = 1

    for i in range(len(s)):
        if s[i:i+5] == 'erase':
            for idx in range(i, i+5):
                skip[idx] = 2

    for i in range(len(s)-1):
        if skip[i] == 0 and skip[i+1] == 0 and skip[i-1] == 1 and s[i] == 'e' and s[i+1] == 'r':
            skip[i] = 3
            skip[i+1] = 3

    for i in range(len(s)):
        if skip[i] == 0 and skip[i-1] == 2 and s[i] == 'r':
            skip[i] = 4

    print(YN[all(skip)])


if __name__ == '__main__':
    main()


Measured memory_bytes: 44524