akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
int main(){
    int n;
    cin >> n;
    cout << (n + 999) / 1000 * 1000 - n << endl;
}


Measured memory_bytes: 3640
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        BigInteger sum = BigInteger.ZERO;
        for (int i = 1; i <= N; i++) {
            if (i % 3 != 0 && i % 5 != 0) {
                sum = sum.add(BigInteger.valueOf(i));
            }
        }
        System.out.println(sum);
    }
}

Measured memory_bytes: 54036
N = int(input())
A = list( map(int, input().split()))
minus = len([ 1 for i in A if i<0])
abs_A = list(map(abs, A))
if minus % 2 == 0:
  print(sum(abs_A))
else:
  print(sum(abs_A) - 2 * min( abs_A))

Measured memory_bytes: 14412
class UnionFind:
    def __init__(self, size):
        import sys
        sys.setrecursionlimit(10**5)
        """
        リストの添字を集合の値として利用し
        リストの要素を根, 節の管理に用いる
        要素が負の添字は素集合の根であり、集合の要素数
        要素が0以上の添字は節であり
        要素は節の親の添字を指す
        """
        self.table = [-1] * size
        self.size = [1] * size
        
    def find(self, x):
        """
        xを持つ素集合の根を返す
        """
        if self.table[x] < 0:
            # 根の場合
            return x
        else:
            # 節の場合: 経路圧縮(path compression)
            self.table[x] = self.find(self.table[x])
            return self.table[x]
 
    def union(self, x, y):
        """
        x, yを持つ素集合を併合(Union)する
        """
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:  # x,yが異なる素集合に含まれている場合のみ併合
            if self.table[s1] >= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False
 
if __name__=="__main__":
    N, M = map(int, input().split())
    Q = [list(map(int, input().split())) for _ in range(M)]
    u = UnionFind(N)
    unconv = N*(N-1)//2
    ans = []
    for q in reversed(Q):
        ans.append(unconv)
        a = u.find(q[0]-1)
        b = u.find(q[1]-1)
        if a!=b:
            unconv -= u.table[a]*u.table[b]
        u.union(q[0]-1, q[1]-1)
    for a in reversed(ans):
        print(a)

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

int main(){
  int K, S;
  cin >> K >> S;
  
  int count = 0;
  for (int i=0;i<=K;i++){
    for (int j=0;j<=K;j++){
      if (S-i-j<=K && S-i-j>=0) count++;
    }
  }
  cout << count << endl;
}

  
  

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

typedef vector< ll > 	vi;
typedef vector< vi > 	vvi;
typedef pair< ll,ll > 	ii;
#define pb 		push_back
#define all(c) 		(c).begin(),(c).end()
#define tr(c,i) 	for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) 	((c).find(x) != (c).end())

#define MOD 	1000000007
#define INF 	(int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))

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

	ll n;
	cin>>n;
	ll t=n-1;
	ll ans= (t * (t+1)) /2;
		
	//if(n%2==0)
	//{
	//	cout<<ans-1;
	//}
	//else
	 cout<<ans;
	
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define dump(x) cerr << #x << " = " << (x) << endl;
typedef long long LL;
typedef vector<int> VI;
typedef vector<long long> VL;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = (int)1e9;
const long long mod = 998244353LL;
const double pi = acos(-1.0);

int main() {
	VI A(3); rep(i, 3)cin >> A[i];
	VI a = A; sort(all(a));
	puts(a[1] == A[2] ? "Yes" : "No");
}

Measured memory_bytes: 256
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define fore(x, c) for(auto &&x : c)
#define rep(i, a, n) for(int i = a, i##len = (int)(n); i < i##len; ++i)
#define rrep(i, a, n) for(int i = (int)(n - 1); i >= a; --i)
#define sz(c) ((int)c.size())
#define contains(c, x) (c.find(x) != end(c))
#define inseg(l, x, r) ((l) <= (x) && (x) < (r))
#define dump(...)
#define pb push_back
#define eb emplace_back
#define _ 0
const signed INF_ = 1001001001; const long long INF = 1001001001001001001LL;
const int DX[9] = {0,1,0,-1,1,1,-1,-1,0}, DY[9] = {-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os, const vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is, vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
  is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a, const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a, const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap = priority_queue<T, deque<T>, greater<T>>;
struct before_main_function {
  before_main_function() {
      cin.tie(nullptr); ios::sync_with_stdio(false);
      cout << setprecision(15) << fixed;
  }
} before_main_function;
// clang-format on
//------------------8<------------------------------------8<--------------------

bool solve() {
  int n;
  cin >> n;
  vi a(n);
  cin >> a;

  map<int, int> cnt;
  for (int x : a) cnt[x]++;
  switch (n % 3) {
    case 0: {
      int m = n / 3;
      switch (sz(cnt)) {
        case 1:
          return (cnt.begin()->first == 0);
        case 2: {
          int x, nx, y, ny;
          tie(x, nx) = *cnt.begin();
          tie(y, ny) = *next(cnt.begin());
          return x == 0 && nx == m && ny == 2 * m;
        }
        case 3: {
          int x, nx, y, ny, z, nz;
          tie(x, nx) = *cnt.begin();
          tie(y, ny) = *next(cnt.begin());
          tie(z, nz) = *next(next(cnt.begin()));
          return (x ^ y ^ z) == 0 && nx == m && ny == m && nz == m;
        }
        default:
          return false;
      }
      break;
    }
    case 1:
    case 2:
      return sz(cnt) == 1 && (cnt.begin()->first == 0);
      break;
  }
  return false;
}
signed main() {
  cout << (solve() ? "Yes" : "No") << endl;
  return (0 ^ _ ^ 0);
}



Measured memory_bytes: 8720
// c++include
#include <iostream>
#include <algorithm>
// cinclude
#include <stdio.h>
#include<string.h>
#include<math.h>
//c++標準ライブラリ
#include<vector>
#include<string>
//std使用<-namespace
using namespace std;

// define, typedef
#define rpt(i, n) for(ll i = 0; i < (n); i++)
typedef long long ll;


// main関数
int main(void) {
	int n;
	cin >> n;
	double count = 0;
	rpt(i, n + 1) {
		if (i % 2 != 0)
			count += 1.0;
	}
	cout << count / n;

	return 0;
}

Measured memory_bytes: 256
import bisect

n = int(input())
lis = list(map(int,input().split()))

a = sorted(lis, reverse=True)
c = sorted(lis)
d = 0

for i in range(n):
    for j in range(i + 1, n):
        e = c[:-j-1]
        b = bisect.bisect_right(e, int(a[i]-a[j]))
        d += max(0, len(e) - b)
print(d)


Measured memory_bytes: 58716
import java.util.Scanner;

public class Main{
    public static void main(String args[]){
        
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        String S = sc.next();
        char[] c = new char[N];
        for(int i = 0; i < N; i++){
            char tmp = S.charAt(i);
            if(i == K - 1){
                tmp += 32;
            }
            System.out.print(tmp);
        }
        System.out.println();
        
    }
}

Measured memory_bytes: 21332
#include<iostream>
#include<math.h>
#include<iomanip>
using namespace std;
int main(){
	double a,l,x;
	while(cin>>a>>l>>x){
		double b,c;
		b=(double)sqrt((double)l*l-a*a/4);
		c=(double)sqrt((double)(l+x)*(l+x)-l*l);
		cout<<fixed<<setprecision(10)<<a*b/2+l*c/2<<endl;
	}
	return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr LL INF = 1E18;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    for (int i = 0; i < n; ++i)
        cin >> h[i];
    vector<vector<LL>> dp(n + 1);
    for (int i = 0; i <= n; ++i)
        dp[i].assign(k + 1, INF);
    dp[0][k] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            for (int l = 0; l <= k; ++l)
                dp[i + 1][l] = min(dp[i + 1][l], dp[j][l] + max(0, h[i] - (j == 0 ? 0 : h[j - 1])));
            for (int l = 0; l < k; ++l)
                dp[j][l] = dp[j][l + 1];
            dp[j][k] = INF;
        }
    }
    LL ans = INF;
    for (int i = 0; i <= n; ++i)
        ans = min(ans, dp[i][0]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using iii = pair<ii, int>;
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define __lcm(a, b) a * b / __gcd(a, b)
const int MOD = 1e9 + 7;
const int INF = 2e9;
const int N = 1e5 + 5;

int n;
int a[N];

int SlidingWindow(int x) {
    int l = 1, r = 1, maxim = 0;
    while(r <= x) {
        while(a[r + 1] <= a[r]) {
            r++;
        }
        maxim = max(maxim, r - l);
        r++; l = r;
    }
    return maxim;
}

/* 
5
10 4 8 7 3
     ^
         ^
*/

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    a[n + 1] = INF;
    cout << SlidingWindow(n) << "\n";
}

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

Measured memory_bytes: 3968
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define mod 1000000007
#define inf 1e18+42
#define endl "\n"

#define out1(a) cout<<#a<<" "<<a<<endl
#define out2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define out3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define fori(it,A) for(auto it=A.begin();it!=A.end();it++)

#define ft first
#define sd second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define zero(x) memset(x,0,sizeof(x));
 
using namespace std;

int binpow(int,int);
void dfs( vector< vector<int> >&, int , vector<int>& );
void bfs( vector< vector<int> >&, int , vector<int>& );

bool chkprime( int n )
{
    if ( n == 2 )
    {
        return true;
    }
    rep(i,2,sqrt(n)+1)
    {
        if ( n % i == 0 )
        {
            return false;
        }
    }

    return true;
}

void solve()
{
    int a,b;
    cin>>a>>b;

    int x = __gcd(a,b);
    // out1(x);
    vector<int> div;
    int cnt = 0;
   for ( int i = 1 ; i <= sqrt(x) ; i++ )
    {
        if ( x % i == 0 )
        {
            div.pb(i);
            if ( i != x/i )
            {
                div.pb(x/i);
            }
        }
    }
    // rep(i,0,div.size())
    // {
    //     out1(div[i]);
    // }
    rep(i,0,div.size())
    {
        if ( chkprime(div[i]) == true )
        {
            cnt++;
            // out1(cnt);
        }
    }

    cout<<cnt<<endl;
}

signed main()
{
    fast;
    int t = 1;
    // cin>>t;

    while(t--)
    {
        solve();
    }
    return 0;
}

int binpow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

void dfs ( vector< vector<int> > &v , int x , vector<int> &vis )
{
    vis[x] = 1;

    rep(i,0,v[x].size())
    {
        if( vis[v[x][i]] == 0 )
        {
            dfs(v,v[x][i],vis);
        }
    }
}

void bfs( vector< vector<int> > &v , int x , vector<int> &vis )
{
    queue<int> q;
    q.push(x);

    while( !q.empty() )
    {
        int p = q.front();
        q.pop();

        rep(i,0,v[p].size())
        {
            if ( vis[v[p][i]] == 0 )
            {
                vis[v[p][i]] = 1;
                q.push(v[p][i]);
            }
        }
    }
}

Measured memory_bytes: 384
import java.util.Scanner;
     
     
    public class Main {
        

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String s = sc.next();
            int n =s.length();
            String a=s.substring(0,(n-1)/2);
            String b=s.substring(((n+3)/2)-1,n);
             if (a.equals(b)){
                System.out.println("Yes");
             }else{
                System.out.println("No");
             }
           } 
        }
    


Measured memory_bytes: 35588
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <functional>

using namespace std;

int n, p[22];

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> p[i];

	int cnt = 0;
	for (int i = 1; i < n-1; ++i)
		if ((p[i-1] < p[i] && p[i] < p[i+1]) || (p[i-1] > p[i] && p[i] > p[i+1]))
			++cnt;

	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#pragma region Macros
#define int long long
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define LAST(x) x[x.size()-1]
#define ALL(x) (x).begin(),(x).end()
#define swap(a,b) (a += b,b = a - b,a -= b)
#define CEIL(a,b) ((a+b-1)/b)
int GCD(int a, int b) // assuming a,b >= 1
{
	if (a < b)
		swap(a, b);
	if (b == 0)
		return a;
	if (a % b == 0)
		return b;
	return GCD(b, a % b);
}
int LCM(int a, int b) // assuming a,b >= 1
{
	return  a * b / GCD(a, b);
}
double LOG(int a, int b) {
	return log(b) / log(a);
}
inline bool BETWEEN(int x, int min, int max) {
	if (min <= x && x <= max)
		return true;
	else
		return false;
}

using namespace std;
#pragma endregion
signed main() {
	int N, H, x;
	cin >> H >> N;
	rep(i, N) {
		cin >> x;
		H -= x;
	}
	if (H <= 0)
		cout << "Yes";
	else
		cout << "No";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
using namespace std;
string a, b;
const int MAXN = 3005;
ll dp[MAXN][MAXN];
int n,m;
string ans;
ll solve(int i, int j){
    if(i == n) return 0;
    if(j == m) return 0;
    ll r = dp[i][j];
    if(r != -1) return r;
    if(a[i] == b[j])
        r = solve(i + 1, j + 1) + 1;
    else r = max(solve(i + 1,j), solve(i, j + 1));
    return dp[i][j] = r;
}
void build(int i,int j){
    if(i == n)return;
    if(j == m)return;
    ll answer = solve(i,j);
    if(a[i] == b[j] && answer == solve(i + 1, j + 1) + 1){
        ans.push_back(a[i]);
        build(i + 1, j + 1);
    }
    else if(answer == solve(i + 1,j))build(i + 1, j);
    else if(answer == solve(i, j + 1))build(i, j + 1);
    return;
}
int main(){
    fast;
    cin >> a >> b;
    n = a.size();
    m = b.size();
    memset(dp, -1, sizeof dp);
    solve(0, 0);
    build(0, 0);
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 74432
#include <iostream>

using namespace std;

int main(void){
  int x, y, z;
  cin >> x >> y >> z;
  if(x>y){
    if(z>=x){
      cout << x+y << endl;
    }else{
      cout << y+z << endl;
    }
  }else if(y>=x){
    if(z>=y){
      cout << x+y << endl;
    }else{
      cout << x+z << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % mod;
}
int mod_pow(int x, int y, int mod_) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod_;
		}
		x = x * x % mod_;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x)* mod_pow(kai(x - y), mod - 2, mod) % mod * mod_pow(kai(y), mod - 2, mod) % mod;
}
/*--------Library Zone!--------*/


int n, a[214514], b[214514];
signed main() {
	cin >> n;
	rep(i, n)cin >> a[i];
	rep(i, n)cin >> b[i];
	int ans = 0;
	rep(i, 30) {
		int moda[214514], modb[214514];
		rep(j, n) {
			moda[j] = a[j] % ((int)1 << (i + 1));
			modb[j] = b[j] % ((int)1 << (i + 1));
		}
		sort(modb, modb + n);
		int memo = 0;
		rep(j, n) {
			int cnt = 0;
			int k = (int)1 << i, l = (int)1 << (i + 1), m = (int)1 << (i + 2);
			cnt += upper_bound(modb, modb + n, l - 1 - moda[j]) - lower_bound(modb, modb + n, k - moda[j]);
			cnt += upper_bound(modb, modb + n, m - 1 - moda[j]) - lower_bound(modb, modb + n, k + l - moda[j]);
			memo += cnt; memo %= 2;
		}
		if (memo)ans += (int)1 << i;
	}
	cout << ans << endl;
}


Measured memory_bytes: 6656
#include<bits/stdc++.h>
using   namespace      std;
typedef long long      LL;
typedef vector<int>    VI;
typedef pair<int,int>  PII;

int main(){

	int n, l;
	cin>> n>> l;
	int sum = 0;
	int x = INT_MAX, elem = 0;;
	for(int i=0; i<n; i++){
		sum += (l + i);
		if(x > abs(l + i)){
			x = abs(l + i);
			elem = l + i;
		}
	}
	cout<< sum - elem<< endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ld double
#define lds pair<ld,ld>
#define F first
#define S second
ld dist(lds a, lds b){
  	//printf("%.10f %.10f %.10f %.10f %.10f\n",a.F,a.S,b.F,b.S,
      //     sqrtl((a.F-b.F)*(a.F-b.F)+(a.S-b.S)*(a.S-b.S)));
	return sqrtl(((a.F-b.F)*(a.F-b.F))+((a.S-b.S)*(a.S-b.S)));
}

int main(){
	int n;
	cin>>n;
  	vector<lds> v(n);
  	for(int i=0;i<n;i++){
    	scanf("%lf %lf",&v[i].F,&v[i].S);
    	//printf("%.10lf %.10lf\n",v[i].F,v[i].S);
    }
  	ld dst = 0.0;
  	for(int i=0;i<n;i++){
    	 for(int j=0;j<n;j++){
         	dst += dist(v[i],v[j]);
         }
    }
  	printf("%.10lf",dst/n);
}

Measured memory_bytes: 256
from collections import deque
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
d = deque(A)

#print(d)

ans1 = []

for i in range(N):
    x = d.pop() if i % 2 == 0 else d.popleft()
    ans1.append(x)
x = ans1.pop()
ans1 = [x] + ans1

ans2 = []
d = deque(A)
for i in range(N):
    x = d.popleft() if i % 2 == 0 else d.pop()
    ans2.append(x)
x = ans2.pop()
ans2 = [x] + ans2


def amount(array):
    ret = 0
    for i in range(N-1):
        ret += abs(array[i+1]-array[i])
    return ret

#print(ans)
print(max(amount(ans1), amount(ans2)))


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

using namespace std;

int main(void) {
  int i, tmp, target_num;
  int N;
  bool isOK;
  vector<int> a;
  // get input ----------------------------
  cin >> N;
  for(i = 0; i < N; i++) {
    cin >> tmp;
    a.push_back(tmp);
  }
  // break brick
  target_num = 1;
  isOK = true;
  for(i = 0; i < N; i++) {
    if(a[i] == target_num) {
      target_num++;
    } else {
      isOK = false;
    }
  }
  
  // disp answer
  if(target_num == 1) {
    if(isOK) {
      cout << "0" << endl;
    } else {
      cout << "-1" << endl;
    }
  } else {
    cout << N - target_num + 1 << endl;
  }
  return 0;
}


Measured memory_bytes: 1400
//競技プログラミング　テンプレ
//負の時は逆!!
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cstdlib>

using namespace std;

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

int main() {
	int n, ans=0,max_n,min_n;
	bool f=0;
	cin >> n;
	vector <int> A(n);
	//string str;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	int min = 1000001, max = -1000001;
	REP(i,n){
		if(max < A[i]) {max = A[i]; max_n  =i;}
		if(min > A[i]) {min = A[i]; min_n = i;}
	}
	//sort(A.begin(), A.end());
	if( abs(A[min_n]) < abs(A[max_n]) ) f=1;
	//cout << f << endl;

	cout << 2*n-2 << endl;
	if(f){
		REP(i,n) { if( (i+1) != max_n + 1) cout << max_n+1 << " "<<  i+1 << endl; }
		REP(i,n-1) cout << i+1 <<" "<< i+2 << endl;
	}
	else{
		REP(i,n) { if(min_n + 1 != (i+1))cout << min_n+1 << " " << i+1 << endl; }
		REP(i,n-1) cout << n-i <<" "<< n-i-1 << endl;
	}


	return 0;
}


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

#define debug(x) cerr << #x << " = " << x << endl

const int N_MAX = 200003;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int n;
  cin >> n;
  bool ans = 0;
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
    ans ^= (x & 1) == 1;
  }
  cout << (ans ? "NO" : "YES") << endl;
  return 0;
}


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

int main() {
    long long N, K; cin >> N >> K;
    int res = 1;
    long long cur = 1;
    while(true) {
        cur *= K;
        if(N / cur == 0) break;
        ++res;
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>

int main() {
  int A, B;
  std::cin >> A >> B;
  if (A > B) { std::cout << 2 *  A - 1 << std::endl; }
  else if (B > A) { std::cout << 2 * B - 1 << std::endl; }
  else { std::cout << A + B << std::endl; }
  return 0;
}

Measured memory_bytes: 888
let o = read_line ()
let e = read_line ()
let buf = Buffer.create (String.length o * 2)

let () =
  if String.length o = String.length e then
    for i = 0 to (String.length o - 1) do
      Buffer.add_char buf o.[i] ;
      Buffer.add_char buf e.[i] ;
    done
  else
    begin
      for i = 0 to (String.length e - 1) do
        Buffer.add_char buf o.[i] ;
        Buffer.add_char buf e.[i] ;
      done ;
      Buffer.add_char buf o.[String.length o - 1]
    end ;
  print_endline (Buffer.contents buf)

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define ll = long long int
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define REP3(i,x,n) for(int i=x; i>(n); i--)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int gcd(int x,int y){
    if (x < y) swap(x,y);
    while(y>0){
        int r = x % y;
        x = y;
        y = r;
    }
    return x;
}
int main(){
    tuple<int,int,int> a;
    long long K=0,sum=0;
    scanf("%lld",&K);
    REP2(i,1,K+1)REP2(j,1,K+1)REP2(k,1,K+1){
        sum += gcd(gcd(i,j),k);
        
    }
    printf("%lld",sum);
    return 0;
}

Measured memory_bytes: 3840
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
# gcdがNから順に数える、resetを用意、約数をそれぞれ引く

def make_divisors(n):  # nの約数を列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

N, K = lr()
answer = 0
reset = [0] * (K+1)
for x in range(K, 0, -1):
    #gcdがx
    nums = K // x
    add = pow(nums, N, MOD)
    add -= reset[x]
    answer += add * x
    answer %= MOD
    divs = make_divisors(x)
    for d in divs:
        reset[d] += add

print(answer%MOD)


Measured memory_bytes: 70128
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=1)
#print(a)
se=set()
for i in range(p):se.add(a[i])

s=a[p-1]
for i in range(p,n):
  x=max(v-(n-((i+1)-(p-1)))-1,0)
  if a[i]+m>=max(0--(s+m*x)//(i-p+1),a[p-1]):se.add(a[i])
  #print(i,x,s+m*x,s,0--(s+m*x)//(i-p+1))
  s+=a[i]

ans=0
for i in a:
  if i in se:ans+=1
print(ans)

Measured memory_bytes: 14736
import heapq
def main():
    N, M = map(int, input().split())
    A = list(map(lambda x: -int(x), input().split()))
    heapq.heapify(A)
    for _ in range(M):
        i = heapq.heappop(A)
        heapq.heappush(A, -(-i // 2))
    return -sum(A)

print(main())


Measured memory_bytes: 14380
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

class ModInteger {
	public static long MOD = 1_000_000_007;
	private long x;

	public ModInteger(long n) {
		x = (n % MOD);
	}

	/** 和 */
	public ModInteger add(long augend) {
		return new ModInteger((x + augend) % MOD);
	}

	/** 和 */
	public ModInteger add(ModInteger augend) {
		return add(augend.x);
	}

	/** 逆元 */
	public ModInteger inv() {
		return pow(MOD - 2);
	}

	/** 商 */
	public ModInteger divide(long divisor) {
		return divide(new ModInteger(divisor));
	}

	/** 商 */
	public ModInteger divide(ModInteger divisor) {
		return multiply(divisor.inv());
	}

	/** 積 */
	public ModInteger multiply(long muultiplicand) {
		return new ModInteger((x * muultiplicand) % MOD);
	}

	/** 積 */
	public ModInteger multiply(ModInteger multiplicand) {
		return multiply(multiplicand.x);
	}

	/** 累乗 O(logN) */
	public ModInteger pow(long n) {
		// 繰り返し二乗法
		if (n == 0) {
			return new ModInteger(1);
		}
		ModInteger a = pow(n / 2);
		a = a.multiply(a);
		if (n % 2 == 1) {
			a = a.multiply(x);
		}
		return a;
	}

	/** 差 */
	public ModInteger subtract(long subtrahend) {
		return new ModInteger((x - subtrahend + MOD) % MOD);
	}

	/** 差 */
	public ModInteger subtract(ModInteger subtrahend) {
		return subtract(subtrahend.x);
	}

	@Override
	public boolean equals(Object o) {
		if (o instanceof ModInteger) {
			return x == ((ModInteger) o).x;
		}
		return false;
	}

	public boolean equals(long l) {
		return x == (l % MOD);
	}

	@Override
	public int hashCode() {
		return Long.hashCode(x);
	}

	public int compareTo(long val) {
		return Long.compare(x, val);
	}

	public int compareTo(ModInteger val) {
		return compareTo(val.x);
	}

	public long longValue() {
		return x;
	}

	@Override
	public String toString() {
		return Long.toString(x);
	}

	public static ModInteger valueOf(long x) {
		return new ModInteger(x);
	}

}

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	private ModInteger f(int n) {
		ModInteger m = new ModInteger(1);
		for (int i = 1; i <= n; i++) {
			m = m.multiply(i);
		}
		return m;
	}

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int X = sc.nextInt();
		int Y = sc.nextInt();

		sc.close();

		if ((X + Y) % 3 != 0) {
			out.println("0");
			return;
		}

		// X>=Yにする
		if (Y > X) {
			int tmp = X;
			X = Y;
			Y = tmp;
		}

		int cx = (2*X-Y) / 3;
		int cy = (2*Y-X) / 3;

		if(cx < 0 || cy < 0) {
			out.println(0);
			return;
		}
		
		ModInteger ans;
		ans = f(cx + cy).divide(f(cx).multiply(f(cy)));

		out.println(ans);

	}

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


Measured memory_bytes: 43988
S = input()
N = len(S)

if N%2 == 1:
    ans = N//2
    s = S[N//2]
    a = N//2+1
    for i in range(N//2+1):
        if S[N//2+i] != s or S[N//2-i] != s:
            a = i
            break
    ans += a
else:
    ans = N//2
    s = S[N//2]
    a = N//2
    for i in range(N//2):
        if s != S[N//2-1-i] or s != S[N//2+i]:
            a = i
            break
    ans += a
print(ans)

Measured memory_bytes: 3188
require 'pp'

n, k = gets.chomp!.split(" ").map(&:to_i)
a_n = gets.chomp!.split(" ").map(&:to_i)

i = a_n.index(1)

left_count = i
right_count = n - i - 1

left_count1 = left_count
right_count1 = right_count

# 左から数える
count = 0
count += left_count / (k-1)
# 最後の一回
if left_count % (k-1) == 0
else
    count += 1

    if k - left_count % (k-1) >= 2
        right_count -= k - left_count % (k-1) - 1
    end
end
count += right_count / (k-1) + (right_count % (k-1) == 0 ? 0 : 1)

left_count = left_count1
right_count = right_count1

# 右から数える
count2 = 0
count2 += right_count / (k-1)
# 最後の一回
if right_count % (k-1) == 0
else
    count2 += 1
    if k - right_count % (k-1) >= 2
        left_count -= k - right_count % (k-1) - 1
    end
end
count2 += left_count / (k-1) + (left_count % (k-1) == 0 ? 0 : 1)

puts [count, count2].min


Measured memory_bytes: 8316
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int r=sc.nextInt();
        int c=sc.nextInt();
        int matrix[][]=new int[r][c];
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                matrix[i][j]=sc.nextInt();
            }
        }
        int rc_sum=0;
        for(int i=0;i<r;i++){
            int c_sum=0;
            for(int j=0;j<c;j++){
                System.out.print(matrix[i][j]+" ");
                c_sum+=matrix[i][j];
                if(i!=0)matrix[i][j]+=matrix[i-1][j];
            }
            System.out.println(c_sum);
            rc_sum+=c_sum;
        }
        for(int j=0;j<c;j++){
            System.out.print(matrix[r-1][j]+" ");
        }
        System.out.println(rc_sum);
    }
}



Measured memory_bytes: 41244
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    bool ans=false;
    while (n)
    {
        if(n%10==7)
        {
            ans = true;
            break;
        }
        n/=10;
    }
    if(ans)
        cout <<"Yes";
    else
        cout <<"No";

    return 0;
}

Measured memory_bytes: 3636
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    s=input()
    dp=[1]*n
    for i in range(1,n):
        ndp=[0]*n
        S=[0]*(n+1)
        for j in range(n):
            S[j+1]=S[j]+dp[j]
        for less in range(n-i):
            if(s[i-1]=='<'): ndp[less]=S[less+1]
            else: ndp[less]=S[n]-S[less+1]
            ndp[less]%=MOD
        dp=ndp
    print(dp[0])
resolve()

Measured memory_bytes: 42332
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define p (int)(1e9 + 7)

int MOD(int a){
	return (a %= p) >= 0 ? a : a + p;
}

int power(int a, int N){
	if(N == 0){
		return 1;
	}
	else if(N % 2 == 0){
		return power(MOD(a * a), N / 2);
	}
	else{
		return MOD(a * power(a, N - 1));
	}
}

int inverse(int a){
	return power(a, p - 2);
}

signed main(){
	int N, A, i, j;
	int M = 1000000;
	scanf("%lld", &N);
	vector<int> max_factor(M + 1, 0);
	int ans = 0;
	for(i = 0; i < N; i++){
//		printf("i = %lld\n", i);
		scanf("%lld", &A);
		ans =  MOD(ans + inverse(A));
		for(j = 2; j * j <= A; j++){
			if(A % j == 0){
				int num = 0;
				while(A % j == 0){
					A /= j;
					num++;
				}
//				printf("(j, num) = (%lld, %lld)\n", j, num);
				max_factor[j] = max(max_factor[j], num);
			}
		}
		if(A > 1){
			max_factor[A] = max(max_factor[A], 1ll);
		}
	}
	for(i = 2; i <= M; i++){
/*		if(max_factor[i] > 0){
			printf("max_factor[%lld] = %lld\n", i, max_factor[i]);
		}
*/		ans = MOD(ans * power(i, max_factor[i]));
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 8064
N = int(input())
S = input()
e = [0]
w = [0]
for i in range(N):
    if S[i] == "E":
        e.append(e[-1] + 1)
        w.append(w[-1])
    else:
        e.append(e[-1])
        w.append(w[-1] + 1)
ans = 10**9
for i in range(N):
    turn = w[i] + e[-1] - e[i + 1]
    if turn < ans:
        ans = turn
print(ans)


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

void dfs(int v, vector<int> & color, const vector<vector<int>> & Es){
    int c = color[v];
    for (int u : Es[v]){
        if (color[u] != 0) continue;
        color[u] = -c;
        dfs(u, color, Es);
    }
}

long long solve(long long N, long long M, const vector<vector<int>> & Es, const vector<pair<int, int>> & edges){
    vector<int> color(N, 0);
    color[0] = 1;
    dfs(0, color, Es);
    bool all_connected = false;
    for (auto &edge : edges){
        int v = edge.first;
        int u = edge.second;
        if (color[v] == color[u]){
            all_connected = true;
            break;
        }
    }
    if (all_connected){
        return N * (N - 1)/ 2 - M;
    }else{
        long long N1 = 0;
        long long N2 = 0;
        for (int i = 0; i < N; ++i){
            if (color[i] == 1){
                ++N1;
            }else{
                ++N2;
            }
        }
        return N1 * N2 - M;
    }
}



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long N, M;
    cin >> N >> M;
    vector<vector<int>> Es(N, vector<int>());
    vector<pair<int, int>> edges(M);
    for (int i = 0; i < M; ++i){
        int a, b;
        cin >> a >> b;
        Es[a - 1].push_back(b - 1);
        Es[b - 1].push_back(a - 1);
        edges[i].first = a - 1;
        edges[i].second = b - 1;
    }
    cout << solve(N, M, Es, edges) << endl;
    return 0;
}

Measured memory_bytes: 7552
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using v = vector<ll>;
void a(){
    string s,t;
    cin >> s >> t;
    int a, b;
    cin >> a >> b;
    string u;
    cin >> u;
    if(u==s){
        cout << a-1 << " "<<b;
    }else{
        cout << a << " "<<b-1;
    }
}

void b(){
    string s;
    cin >> s;
    for(auto i:s){
        cout << 'x';
    }
}

void c(){
    int n;
    cin >> n;
    auto a = map<int,int>();
    for(ll i=0;i<n;i++){
        int t;
        cin >> t;
        if(a[t]!=0){
            cout << "NO";
            return;
        }
        a[t]++;
    }
    cout << "YES";
}

void d(){
    ll n,k;
    cin >> n >> k;
    auto p = vector<double>(n,0);
    for(ll i=0;i<n;i++) cin >> p[i];
    cout << fixed << setprecision(10);
    if(k==1){
        auto _max=*max_element(p.begin(),p.end());
        cout << (_max+1)/2;
        return;
    }
    
    double now =0;
    for(ll i=0;i<k;i++){
        now+=(p[i]+1)/2;
    }
    double ans=now;
    
    for(ll i=k;i<n;i++){
        now += (p[i]+1)/2-(p[i-k]+1)/2;
        if(ans<now){
            ans = now;
        }
    }
    cout << ans;

}


int main(){
    d();
    return 0;
}

Measured memory_bytes: 1792
//#include <cstdio>
#include <iostream>

#include <cstring>

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
//#include <queue>
//#include <stack>
#include <cassert>

using namespace std;

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

#define DEBUG(x) cerr << #x << ": " << x << endl

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;



int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(nullptr);

   char c;
   cin >> c;
   
   cout << char(c+1) << endl;
   

   return 0;
}


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

int A[2][110];

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

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    int ans = 0;
    for (int x = 0; x < N; x++) {
        // xで下に行く
        int score = 0;
        for (int i = 0; i <= x; i++) score += A[0][i];
        for (int i = x; i < N; i++) score += A[1][i];
        ans = max(ans, score);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define li long long int
#define ld long double
const int MX1=1e5+5;
const int MX2=1e6+5;
const li inf=4e18;
const li mod=1e9+7;

li power(li a,li b){li res=1;while(b){if(b%2)res=(res*a)%mod;
a=(a*a)%mod;b/=2;}return res;}

li mmi(li a){return power(a,mod-2);}

li cntbit(li n){li cnt=0;while(n){n&=(n-1);cnt++;}return cnt;}

int n,d,x;
int a[105];
int ok[105];

void solve(){
	cin>>n>>d>>x;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=d;j+=a[i]){
			ok[j]++;
		}
	}
	int cnt=0;
	for(int i=1;i<=d;i++){
		cnt+=ok[i];
	}
	cout<<cnt+x;
}

int main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	int t=1;
	// cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Measured memory_bytes: 256
#import math
#=input()
#=int(input())
x,n=map(int,input().split())
p=list(map(int,input().split()))
#=[list(map(int,input().split())) for _ in range()]

if x not in p:
    ans = x
else:
    j = 1
    while True:
        if (x-j) not in p:
            ans = x - j
            break
        if (x+j) not in p:
            ans = x + j
            break
        j += 1
print(ans)

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

using namespace std;

void maxheapify(vector<int> &a, int i) {
	int l = i * 2;
	int r = i * 2 + 1;
	int largest = i;
	if (l <= a.size() - 1) {
		if (a[l] > a[i]) {
			largest = l;
		}
		else {
			largest = i;
		}
	}

	if (r <= a.size() - 1) {
		if (a[r] > a[largest]) {
			largest = r;
		}
	}
	if (largest != i) {
		swap(a[i], a[largest]);
		maxheapify(a, largest);
	}

}

void buildmaxheap(vector<int> &a) {
	for (int i = (a.size() - 1) / 2; i >= 1; i--) {
		maxheapify(a, i);
	}
}

void heapincreasekey(vector<int> &h, int i, int key) {
	if (key < h[i]) { return; }
	h[i] = key;
	while(i>1 && h[i/2]<h[i]){
		swap(h[i], h[i / 2]);
		i = i / 2;
	}
}

void insert(vector<int> &h,int key) {
	
	h.push_back(-INT_MIN);
	heapincreasekey(h, h.size()-1, key);
}

int extract(vector<int> &h) {
	if (h.size() == 1) { return 0; }
	int max = h[1];
	h[1] = h[h.size() - 1];
	h.pop_back();
	maxheapify(h, 1);
	return max;
}

int main() {

	vector<int> h(1, 0);
	while (1) {
		string s;
		cin >> s;
		
		int k;
		if (s == "insert") {
			cin >> k;
			insert(h, k);
		}
		else if (s == "extract") {
			cout << extract(h) << endl;
		}
		else if (s == "end") { return 0; }

	}
}


Measured memory_bytes: 7124
#import numpy as np
import math
import collections
import bisect
from difflib import SequenceMatcher


def main():
    S = input()
    T = input()

    ans = 0
    for i in range(len(S)):
        if S[i] != T[i]:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 10164
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18

using namespace std;

int main(void){
  ll n, k;
  cin >> n >> k;
  
  vector<ll> h(n);
  for (int i = 0; i < n; i++){
    cin >> h[i];
  }
  sort(h.begin(), h.end());
  
  ll ans = INF;
  for (int i = 0; i < n - k + 1; i++){
    ans = min(ans, h[i + k - 1] - h[i]);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1152
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    long A =sc.nextLong();
    long B = sc.nextLong();
    long C = sc.nextLong();
    long D = sc.nextLong();
    long LCM = lcm(C,D);
    long answer = 0;
    answer = B-A+1;
    answer = answer -(B/C)+((A-1)/C);
    answer = answer -(B/D)+((A-1)/D);
    answer = answer + ((B/LCM)-((A-1)/LCM));
    System.out.println(answer);
       
  }
  
  //最大公約数・最小公倍数（セットで使う）
  static long gcd (long a, long b) {return b>0?gcd(b,a%b):a;}
  static long lcm (long a, long b) {return a*b/gcd(a,b);}
}

Measured memory_bytes: 21844
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<math.h>
#include<bitset>
using namespace std;
using ll=long long;
using ld=long double;
using pint=pair<int,int>;
using pll=pair<ll,ll>;
#define LONG_INF 9223372036854775807
#define INF 1000000000LL
#define EPS 1e-10
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define dump(a) rep(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define all(v) v.begin(),v.end()
#define pb push_back


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

    int N;
    cin >> N;
    vector<int> X(N);
    rep(i, N) cin >> X[i];
    sort(all(X));
    int a = X[0], b = X[N-1];
    int ret = INF;

    for(int p=a; p<=b; p++){
        int sum = 0;
        rep(i, N) sum += pow(X[i]-p, 2);
        if (sum<ret) ret = sum;
    }
    cout << ret << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;

int main(){
    int n;
    ll L;
    cin >> n >> L;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    int id = -1;
    rep(i,n-1){
        if(a[i]+a[i+1]>=L){
            id = i;
            break;
        }
    }
    if(id==-1){
        cout << "Impossible" << endl;
        return 0;
    }else{
        cout << "Possible" << endl;
    }

    for(int i=0;i<id;i++){
        cout << i+1 << endl;
    }
    for(int i=n-2;i>=id;i--){
        cout << i+1 << endl;
    }


    return 0;
}

Measured memory_bytes: 4016
#include <bits/stdc++.h>
using namespace std;
#define int                     long long   
#define double                  long double
#define endl                    "\n"
#define pb                      push_back
#define PI                      3.1415926535897932384626433832795l
#define F                       first
#define S                       second
#define mp                      make_pair
#define f(i,n)                  for(int i=0;i<n;i++)
#define fastio                  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(v)                  (v).begin(),(v).end()
#define rall(v)                 (v).rbegin(),(v).rend()
#define gcd(a,b)                __gcd((a),(b))
#define fill(a,value)           memset(a,value,sizeof(a));
#define minn(v)                 *min_element(v.begin(), v.end());
#define maxx(v)                 *max_element(v.begin(), v.end());
#define print(x)                cout<<(x)<<endl;
#define sum(v)+x                accumulate(v.begin(), v.end(),x);
#define debug(x)                cout<<#x<<'='<<(x)<<endl;
typedef pair<int,int>           pii;
typedef vector<int>             vi;


signed main() 
{
    fastio;
    cout << fixed << setprecision(12);
    int n,x,y;
    cin>>n>>x>>y;
    vector<int> a(n+1);
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            a[min({(j-i),abs(i-x)+1+abs(j-y),abs(i-y)+1+abs(j-x)})]++;
        }
    }
    for(int i=1;i<n;i++)
    {
        print(a[i])
    }
    
    
    return 0;
}

Measured memory_bytes: 3632
N = int(input())
A = [int(a) for a in input().split()]
n = 0
flag = True
while flag:
  for i in range(N):
    if (A[i] % 2) == 0:
      A[i] /= 2
    else:
      flag = False
      break
  if flag:
    n += 1
print(n)

Measured memory_bytes: 3060
# https://atcoder.jp/contests/abc104/tasks/abc104_d
# in
# ????C?????B??????A???????
# out
# 979596887
# in
# ABCBC
# 3

MOD = (10**9) + 7
str = gets.strip
dp_a = 0
dp_ab = 0
dp_abc = 0

dp_none = 1

a = 'A'
b = 'B'
c = 'C'
str.chars do |s|
  case s
  when a
    dp_a = (dp_a + dp_none)%MOD
  when b
    dp_ab = (dp_ab + dp_a)%MOD
  when c
    dp_abc = (dp_abc + dp_ab)%MOD
  else
    dp_abc = (dp_abc * 3 + dp_ab)%MOD
    dp_ab = (dp_ab * 3 + dp_a)%MOD
    dp_a = (dp_a * 3 + dp_none)%MOD
    dp_none = (dp_none * 3)%MOD
  end
end

p dp_abc

Measured memory_bytes: 2044
import sys
def input():return sys.stdin.readline().strip()
from itertools import accumulate

def islike2017_list(n):
    primes = [True] * (n+1)
    primes[0] = False
    primes[1] = False

    # eratosthenes's sieve
    for i in range(2, int(n**0.5)+1):
        if not primes[i]:
            continue
        for j in range(i*2, n+1, i):
            primes[j] = False
    
    like2017 = [False] * (n+1)
    for i in range(n+1):
        if primes[i] and primes[(i+1)//2]:
            like2017[i] = True
    
    return like2017


def main():
    Q = int(input())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    MAX_X = 10**5
    like2017 = islike2017_list(MAX_X)
    CUSUM = tuple(accumulate(like2017))

    ans = [CUSUM[r] - CUSUM[l-1] for l, r in queries]
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()


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

using namespace std;

#define ll long long
#define all(x) (x).begin(),(x).end()
#define desc greater<int>()

void solve(){
    int n;
    cin >> n;
    int ans=1000-n%1000;
    cout << ans%1000;
}
int main()
{
/*
    string temp;
    int t;
    cin >> t;
    getline(cin, temp);
    while (t--){
        solve();
    }
*/
    solve();
    return 0;
}


Measured memory_bytes: 3644
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
a = LI()
print((n - 1) // (k - 1) + bool((n - 1) % (k - 1)))

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

long combiTable[50][50] = {};

long long combi(int n, int k)
{
    if (k == 0) {
        return 1;
    } else if (n == k) {
        return 1;
    } else if (combiTable[n - 1][k - 1] == 0) {
        combiTable[n - 1][k - 1] = combi(n - 1, k) + combi(n - 1, k - 1);
        return combiTable[n - 1][k - 1];
    } else {
        return combiTable[n - 1][k - 1];
    }
}

int main()
{
    int n, p;
    int odd = 0, even = 0;
    cin >> n >> p;
    for (int i = 0; i < n; ++i) {
        int tmp;
        cin >> tmp;
        if (tmp % 2 == 1) {
            odd++;
        } else {
            even++;
        }
    }

    long long ans = 0;
    if (p == 0) {
        for (int i = 0; i <= odd; i += 2) {
            for (int j = 0; j <= even; j++) {
                ans += combi(odd, i) * combi(even, j);
            }
        }
    } else if (p == 1) {
        for (int i = 1; i <= odd; i += 2) {
            for (int j = 0; j <= even; j++) {
                ans += combi(odd, i) * combi(even, j);
                //cout << "i = " << i << " j = " << j << " ans = " << ans << endl;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256