akhauriyash/Code-Regression huggingface dataset:
def bfs(limit)
  queue = [*1..9]
  count = 0

  until queue.empty?
    ans = x = queue.shift
    count += 1
    return ans if count == limit

    d = x % 10

    if d == 0
      queue << 10 * x
      queue << 10 * x + 1
    elsif d == 9
      queue << 10 * x + d - 1
      queue << 10 * x + d
    else
      queue << 10 * x + d - 1
      queue << 10 * x + d
      queue << 10 * x + d + 1
    end
  end
end

k = gets.to_i

puts bfs(k)


Measured memory_bytes: 3964
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    string s;
    cin >> n;
    int ac=0,wa=0,tle=0,re=0;
    for(int i=0;i<n;i++){
        cin >> s;
        if(s=="AC") ac++;
        if(s=="WA") wa++;
        if(s=="TLE") tle++;
        if(s=="RE") re++;
    }
    cout << "AC x "<<ac<<endl;
    cout << "WA x "<<wa<<endl;
    cout << "TLE x "<<tle<<endl;
    cout << "RE x "<<re<<endl;
    
    
}


Measured memory_bytes: 3596
import sys
import math
import itertools
input = sys.stdin.readline


def main():
    N = int(input())
    A = []
    for _ in range(N):
        x, y = map(int, input().split())
        A.append((x, y))
    ans = 0
    for a in itertools.permutations(range(N)):
        for i in range(len(a)-1):
            dx = A[a[i]][0]-A[a[i+1]][0]
            dy = A[a[i]][1]-A[a[i+1]][1]
            ans += math.sqrt((dx**2) + (dy**2))
    n = 1
    for i in range(1, N+1):
        n *= i
    print(ans/n)


if __name__ == '__main__':
    main()


Measured memory_bytes: 40560
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const int INF = 1000000005;
const long double EPS = 1e-10;

ll ans = -1, res = 0;
void count(ll d, ll c) {
  ans += c - 1;
  ll sum = d * c, r;
  if (sum == 0) ans++;
  while (sum > 0) {
    r = sum % 10;
    res += r;
    ans++;
    if (res > 9) {
      res = 1 + res % 10;
      ans++;
    }
    sum /= 10;
    ans += max((ll)0, sum - 1);
  }
}

int main() {
  int m;
  cin >> m;
  vector<pair<ll, ll>> dc(m);
  rep(i, m) cin >> dc[i].first >> dc[i].second;

  repr(i, m - 1) {
    count(dc[i].first, dc[i].second);
  }
  cout << ans << endl;


  
  return 0;
}

Measured memory_bytes: 3328
S = list(input())
N = len(S)
K = int(input())
if N == 1:
  print(K//2)
  quit()

S = S + S + S
ans_first = ans_odd = ans_even = 0
for i in range(1, N):
  pre_s = S[i-1]
  s = S[i]
  if s == pre_s:
    ans_first += 1
    S[i] = '#'

for i in range(N, 2*N):
  pre_s = S[i-1]
  s = S[i]
  if s == pre_s:
    ans_even += 1
    S[i] = '#'

for i in range(2*N, 3*N):
  pre_s = S[i-1]
  s = S[i]
  if s == pre_s:
    ans_odd += 1
    S[i] = '#'

k_even = K // 2
k_odd = K - k_even - 1
print(ans_first + k_odd*ans_odd + k_even*ans_even)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll a[2222];
ll b[2222];
int main()
{
	//ios::sync_with_stdio(flase);
	ll n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		scanf("%lld",&a[i]);
	}
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(a[i]>a[j])
				b[i]++;
		}
	}
	ll sum=0;
	ll cnt=0;
	cnt=k%mod*((k-1)%mod)/2%mod;

		
	for(int i=0;i<n;i++)
	{
		sum=sum+(b[i]%mod)*((cnt)%mod)%mod;
	}
	ll sum1=0;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			if(a[i]>a[j])
				sum1++;
		}
	}
	sum1=k%mod*(sum1%mod)%mod;
	sum=(sum+sum1)%mod;
	cout<<sum%mod<<endl;
	return 0;
}

Measured memory_bytes: 256
//Created by Aminul on 3/28/2020.

import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int k = in.nextInt(), n = in.nextInt(), res = k;
        int arr[] = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        for (int i = 0; i < n - 1; i++) {
            res = min(res, k - (arr[i + 1] - arr[i]));
        }

        int distanceBetweenFirstAndLast = (arr[0] + (k - arr[n - 1]));
        res = min(res, k - distanceBetweenFirstAndLast);

        pw.println(res);
        pw.close();
    }

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

Measured memory_bytes: 85892
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>ve[N];
priority_queue<int> qe;
int main()
{
	int n,m;
	cin>>n>>m;
	int a,b;
	for(int i=1;i<=n;i++)
	{
		cin>>a>>b;
		if(m-a+1>0)ve[m-a+1].push_back(b);
	}
	int sum=0;
	for(int i=m;i>=1;i--)
	{
		for(int j=0;j<ve[i].size();j++)qe.push(ve[i][j]);
		if(qe.size())
		{
			sum+=qe.top();
			qe.pop();
		}
	}
	cout<<sum;
}

Measured memory_bytes: 8928
/***
	chauhan176's code

	DO WHATEVER IT TAKES!!!
	Nothing happens , nothing happens and then everything happens.
	But the thing is nothing happens in air:)-
***/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long int
#define fi first
#define se second
#define mod 1000000007
#define maxn 500005
#define all(v) v.begin(),v.end()
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define stringio cin.ignore(256, '\n')  //to take string input after taking integer inputs
#define go_t int t;cin>>t;while(t--)
#define go_pt int t;cin>>t;for(int tt=1;tt<=t;tt++)
#define set_ar(arr,v) memset(arr,v,sizeof(arr))
#define trace2(x, y)             cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define trace3(x, y, z)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define trace4(a, b, c, d)       cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
#define trace5(a, b, c, d, e)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<endl;
typedef pair<ll,ll>pii;
const ll inf = 0x3f3f3f3f3f3f3f3fll;//4x10e18
const int infi = 100005;
int main()
{
    #ifndef ONLINE_JUDGE
    // for getting input from input.txt
    //freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    //freopen("output.txt", "w", stdout);
    #endif

    fastio;
    int n;
    cin>>n;
    int a[n+2][n+2];
    map<pii,int>mpp;
    int node=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            mpp[{i,j}]=++node;
        }
    }
    vector<int>adj[node+1];
    int in[maxn]={0};
    for(int i=1;i<=n;i++)
    {
        int pre=0;
        for(int j=1;j<=n-1;j++)
        {
            int b;
            cin>>b;
            int a = i;
            if(b<a)
                swap(a,b);
            int cur = mpp[{a,b}];
            adj[pre].pb(cur);
            if(pre!=0)
                in[cur]++;
            pre=cur;
        }
    }
    queue<int>q;
    for(int i=1;i<=node;i++)
    {
        if(in[i]==0)q.push(i);
    }
    int ans=0;
    int cnt=0;
    while(!q.empty())
    {
        stack<int>st;
        while(!q.empty())
        {
            int job = q.front();
            q.pop();
            cnt++;
            for(int u : adj[job])
                {in[u]--;if(in[u]==0)st.push(u);}
        }
        while(!st.empty())
        {
            q.push(st.top());
            st.pop();
        }
        ans++;
    }
    if(cnt!=node)cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 60800
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい

#define ALL(x) x.begin(),x.end()
typedef long long ll; //long long
typedef pair<int,int> pii; //pair<int,int>
typedef vector<int> vi; //vector<int>
typedef vector<vector<int>> vvi; //vector<vector<int>>
typedef vector<ll> vll; //vector<long long>
typedef vector<vector<ll>> vvll; //vector<vector<long long>>
typedef priority_queue<int, vector<int>, greater<int> > gpq; //逆順priority_queue
typedef priority_queue<int> pq;

//const int MOD=998244353;
const int MOD=1000000007; //10^9+7
const double PI=3.1415926535;

int main(){
    string S;
    cin>>S;
    if(S[1]=='B'){
        cout<<"ARC"<<endl;
    }else{
        cout<<"ABC"<<endl;
    }
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define BIT(n) (1LL << (n))
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = 0; i < BIT(n); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORA(i, n) for (auto &&i : n)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define DEBUG(x) cerr << #x << ": " << x << "\n"
#define DEBUG2(x, y) cerr << #x << ": " << x << " " << #y << ": " << y << "\n"
#define DEBUG3(x, y, z)                                                        \
  cerr << #x << ": " << x << " " << #y << ": " << y << " " << #z << ": " << z  \
       << "\n"
#define PRINTALL(V)                                                            \
  for (auto v : (V)) {                                                         \
    cerr << v << " ";                                                          \
  }                                                                            \
  cerr << "\n";
#define ALL(v) v.begin(), v.end()
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define epb emplace_back
#define int long long
#define pint pair< int, int >
#define ld long double
using namespace std;
template < class T > bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template < class T > bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template < class T > using vec = std::vector< T >;
template < class T > void print(const T &x) { cout << x << "\n"; }
const int MOD = 1000000007, INF = 1061109567, INF2 = INF * INF;
const double EPS = 1e-10, PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
  cin.tie(0), ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int N, K;
  cin >> N >> K;
  vec< int > a(N);
  REP(i, N) cin >> a[i];
  vec< int > l(N + 1, 0);
  vec< int > r(N + 1, 0);
  REP(i, N) {
    l[i + 1] = l[i] + (a[i] > 0 ? a[i] : 0);
    r[i + 1] = r[i] + (a[N - 1 - i] > 0 ? a[N - 1 - i] : 0);
  }
  int val = 0;
  REP(i, K) val += a[i];
  int ans = (val > 0 ? val : 0) + l[0] + r[N - K];
  REP(i, N - K) {
    val += -a[i] + a[i + K];
    chmax(ans, (val > 0 ? val : 0) + l[i + 1] + r[N - K - i - 1]);
  }
  print(ans);
}

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

T= [[-1]*N for i in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        X,Y = list(map(int,input().split()))
        T[i][X-1] = Y

import itertools
cases = list(itertools.product([0,1], repeat=N))

out = []
for case in cases:
    flag = 0
    for i in range(N):
        if case[i]==1:
            ops = T[i]
            for j in range(N):
                if ops[j]!=-1 and ops[j]!=case[j]:
                    flag = 1
    if flag==0:
        out.append(sum(case))

print(max(out))

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

#define int long long
#define itn int
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL << (n))
constexpr int MOD = 1e9 + 7;

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = LLONG_MAX / 2;
using P = pair<int, int>;
using vec = vector<int>;
template <typename T>
using mat = vector<vector<T>>;

// clang-format off
template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) { return stream << p.first << "," << p.second; }
template <typename T>
void print(const vector<T> vec) { rep (i, vec.size() - 1) cout << vec[i] << ' '; cout << vec[vec.size() - 1] << '\n'; }
template <typename Arg>
void print(const Arg arg) { cout << arg << '\n'; }
template <typename Head, typename... Args>
void print(const Head head, const Args... args) { cout << head << " "; print(args...); }
template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) { rep (i, v.size()) cin >> v[i] >> w[i]; }
template <typename T>
void init(vector<T>& v) { rep (i, v.size()) cin >> v[i]; }
template <typename T>
T sum_(vector<T> vec, T init = 0) { return std::accumulate(all(vec), T(init)); }
template<typename T>
bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template<typename T>
bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <typename T>
int index(const T& vec, const typename T::iterator it) { return distance(vec.begin(), it); }
template <typename T = int>
mat<T> mmat(int n, int m=0) { return mat<T>(n, vector<T>(m)); }
template <typename T = int>
vector<T> ivec(int n) { vector<T> v(n); init(v); return v; }
// clang-format on

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// -------------------------------------------------------------------
// sort 1 2 3 4
// pqr 1 2 3 must impl >

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vec a = ivec(n);
    map<int, int> mp;
    repall (x, a)
        mp[x]++;

    int tot = 0;
    repall (e, mp)
        tot += e.second * (e.second - 1) / 2;

    repall (x, a) {
        int origin = mp[x] * (mp[x] - 1) / 2;
        int cnt = mp[x] - 1;
        int ne = cnt * (cnt - 1) / 2;
        print(tot - (origin - ne));
    }

    return 0;
}


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

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long
#define sc(n) scanf("%lld",&n)
#define scc(n1,n2) scanf("%lld %lld",&n1,&n2)
#define sccc(n1,n2,n3) scanf("%lld %lld %lld",&n1,&n2,&n3)
#define debug(x) cerr<<#x<<": "<<x<<endl;

signed main() {
    int n, sum=0;
    sc(n);
    map<int, int> m;
    for(int i=0; i<n; i++){int x; sc(x); sum+=x; m[x]++;}
    int q;
    sc(q);
    while(q--){
        int b, c;
        scc(b, c);
        sum-=m[b]*b;
        sum+=m[b]*c;
        m[c]+=m[b];
        m[b]=0;
        cout<<sum<<endl;
    }
}



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

int main() {
    //char a, b, c; cin >> a >> b >> c;
    vector<char> vec(3);
    int count = 0;
    for (int i=0; i<vec.size(); i++) {
        cin >> vec[i];
        if (vec[i] == '1') count++;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>

#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

typedef long long int64;

typedef long double lld;

using namespace std;

lld _abs(lld x) {
    if (x < 0) return -x;
	return x;
}

lld sqr(lld x) {
   return x * x;
}

lld det(const vector<vector<lld>> a) {
	
	return a[0][0] * (a[1][1] * a[2][2] - a[1][2] * a[2][1]) -
	       a[1][0] * (a[0][1] * a[2][2] - a[2][1] * a[0][2]) +
		   a[2][0] * (a[0][1] * a[1][2] - a[0][2] * a[1][1]);
}

pair<lld, lld> find(lld x1, lld y1, lld x2, lld y2, lld x3, lld y3) {
	lld len1 = sqr(x1) + sqr(y1);
	lld len2 = sqr(x2) + sqr(y2);
	lld len3 = sqr(x3) + sqr(y3);	
	vector<vector<lld>> a = { {len1, y1, 1} ,  {len2, y2, 1}, {len3, y3, 1} };
	vector<vector<lld>> b = { {x1, len1, 1} ,  {x2, len2, 1}, {x3, len3, 1} };
	vector<vector<lld>> c = { {x1, y1, 1} ,  {x2, y2, 1}, {x3, y3, 1} };
	lld sx = 0.5 * det(a);
    lld sy = 0.5 * det(b);
	lld A = det(c);
	if (_abs(A) < 1e-9) return {0, 0};
	sx /= A;
	sy /= A;
	if (_abs(sx) > 1000000 || _abs(sy) > 1000000) return {0, 0}; 
	return {sx, sy};
	
	
}	

int main() {
	ios_base::sync_with_stdio(0);

    int n;
	cin >> n;
	vector<long double> x(n);
    vector<long double> y(n);
	
	for (int i = 0; i < n; ++i) {
	    cin >> x[i] >> y[i];
	}
	
	long double ans = -1;
	for (int i = 0; i < n; ++i) {
	    for (int j = i + 1; j < n;  ++j) {
		    long double xr = (x[i] + x[j]) / 2;
			long double yr = (y[i] + y[j]) / 2;
			long double res = 0;
			for (int l = 0; l < n; ++l) {
			    res = max(res, sqr(xr - x[l]) + sqr(yr - y[l]));
			}
			if (ans < -0.5 || ans >= res) {
			    ans = res;
			}
			
			
			for (int k = j + 1; k < n; ++k) {
				auto p = find(x[i], y[i], x[j], y[j], x[k], y[k]);
				long double xr = p.first;
				long double yr = p.second;
				long double res = 0;
			
				for (int l = 0; l < n; ++l) {
					res = max(res, sqr(xr - x[l]) + sqr(yr - y[l]));
				}
				if (ans < -0.5 || ans >= res) {
					ans = res;
				}
				
				
			}
			
		}
	}
	cout.precision(15);
	cout << sqrt(ans) << endl;

    return 0;
}


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

int main() {
  int n; cin >> n;
  map<char, int> cnt; rep (i, 3) cin >> cnt['A'+i];
  vector<string> s(n); for (string &i : s) cin >> i;
  string ans;
  rep (i, n) {
    char t1 = s[i][0], t2 = s[i][1], t3 = t1 ^ t2 ^ 'A' ^ 'B' ^ 'C';
    if (cnt[t1] == 0 && cnt[t2] == 0) {
      cout << "No" << endl;
      return 0;
    }
    if (cnt[t1] < cnt[t2]) swap(t1, t2);
    if (cnt[t1] == 1 && cnt[t2] == 1){// and cnt[t3] == 0) {
      if (i + 1 < n) {
        if (t1 == s[i+1][0] or t1 == s[i+1][1]) {
          swap(t1, t2);
        }
      }
    }
    ans += t2;
    cnt[t2]++;
    cnt[t1]--;
  }

  cout << "Yes" << endl;
  for (char i : ans) cout << i << endl;
  return 0;
}


Measured memory_bytes: 6696
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;
using static System.Array;
using static Read;

class Program
{
    public static void Main()
    {
        var n = Int();
        Int();
        string[] s = new string[n];
        for(int i = 0; i < n; i++)
        {
            s[i] = String();
        }
        Sort(s);
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++)
        {
            sb.Append(s[i]);
        }
        WriteLine($"{sb}");
    }
}

static class Read
{
    static Queue<string> queue = new Queue<string>();
    static void Enqueue()
    {
        ReadLine().Split(' ').ToList().ForEach(a => queue.Enqueue(a));
    }
    public static int Int()
    {
        if(queue.Count == 0)
            Enqueue();
        return int.Parse(queue.Dequeue());
    }
    public static long Long()
    {
        if(queue.Count == 0)
            Enqueue();
        return long.Parse(queue.Dequeue());
    }
    public static double Double()
    {
        if(queue.Count == 0)
            Enqueue();
        return double.Parse(queue.Dequeue());
    }
    public static string String()
    {
        if(queue.Count == 0)
            Enqueue();
        return queue.Dequeue();
    }
    public static int[] IntArray()
    {
        return ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
    }
    public static long[] LongArray()
    {
        return ReadLine().Split(' ').Select(a => long.Parse(a)).ToArray();
    }
    public static double[] DoubleArray()
    {
        return ReadLine().Split(' ').Select(a => double.Parse(a)).ToArray();
    }
    public static string[] StringArray()
    {
        return ReadLine().Split(' ');
    }
}


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

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

  int n=0;
  if(N%1000==0){
    cout << (N%1000) << endl;
  }
  else{
    n=N/1000;
    cout << (1000*(n+1)-N) << endl;
  }
  return 0;
}

Measured memory_bytes: 3620
#pragma GCC optimize ("-O3","unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<cmath>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<fstream>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<typeinfo>
#include<typeindex>
#include<type_traits>
#include<utility>
#include<valarray>
#include<vector>
#include<array>
#include<forward_list>
#include<random>
#include<ratio>
#include<tuple>
#include<unordered_map>
#include<unordered_set>
#include<cstring>

using namespace std;
using Int = long long;
typedef pair<int,int> Pi; typedef pair<Int,Int> Pl;
const int mod = 1e9+7;
const Int Inf = 1e17;
#define END {cout<<ans<<'\n'; return 0;}
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define mp make_pair
#define Pr(t) priority_queue<t>
#define gPr(t) priority_queue<t,vector<t>,greater<t>>
#define V(t) vector<t>
#define rep1(i,n) for(int(i)=0; i<n; i++)
#define rep(i,n) for(unsigned int(i)=0; i!=n; ++i)
#define rer(i,l,r) for(int i=l; i<=r; i++)
#define gnr(i,l,r) for(int i=r; i>=l; i--)
#define eb emplace_back
#define pri1(a) cout<<(a)<<'\n'
#define pri2(a,n) {rep(pri2i,n-1)cout<<a[pri2i]<<' '; cout<<a[n-1]<<'\n';}
#define prip(p) cout<<p.fi<<' '<<p.se<<'\n'
#define var(type) valarray<type>
template<class T> inline bool cmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool cmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

Int n,m,_,x,y,q;
string s,sb;
bool ok;
char cf,cb;

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

  cin>>n; m=floor(sqrt(n+0.01));
  gnr(i,1,m)if((n%i)==0){x=i; n/=i; break;}
  pri1(x+n-2);
}

Measured memory_bytes: 256
import sys
import bisect

input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7
# mod = 998244353


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


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class UF:
    def __init__(self, N):
        self.state = [-1] * N
        self.rank = [0] * N
        self.num_group = N

    def get_parent(self, a):
        p = self.state[a]
        if p < 0:
            return a

        q = self.get_parent(p)
        self.state[a] = q
        return q

    def make_pair(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa == pb:
            return

        if self.rank[pa] > self.rank[pb]:
            pa, pb = pb, pa
            a, b = b, a
        elif self.rank[pa] == self.rank[pb]:
            self.rank[pb] += 1

        self.state[pb] += self.state[pa]
        self.state[pa] = pb
        self.state[a] = pb
        self.num_group -= 1

    def is_pair(self, a, b):
        return self.get_parent(a) == self.get_parent(b)

    def get_size(self, a):
        return -self.state[self.get_parent(a)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, M = read_values()
    L = []
    D = [[10 ** 10 for _ in range(N)] for __ in range(N)]
    for _ in range(M):
        a, b, c = read_values()
        a -= 1
        b -= 1
        D[a][b] = c
        D[b][a] = c
        L.append((c, a, b))
    L.sort()

    for i in range(N):
        D[i][i] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    res = 0
    for c, a, b in L:
        if D[a][b] < c:
            res += 1

    print(res)


if __name__ == "__main__":
    main()


Measured memory_bytes: 39792
#include <bits/stdc++.h>
#define newl "\n"
using namespace std;
using lli = long long int;
using vvint = vector <vector <int>>;
const int mod = 1e9 + 7;

const int N = 2e5 + 1;

void solve(){
	int n,a;
	cin >> n >> a;
	cout << n * n - a << newl;
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(10);
	#ifdef EXECUTE_LOCALLY
		   freopen("in.txt","r",stdin);
	#endif
	int t = 1;
	//cin >> t;
	while(t--) solve();
	#ifdef EXECUTE_LOCALLY
    	cout << setprecision(3) << "program time: " << (double)clock() / CLOCKS_PER_SEC << newl;
	#endif
	return 0;
}


Measured memory_bytes: 3568
#include <iostream>
using namespace std;
const int N = 100;
int a[N];
const int INF = 1e+9;

int cost(int x, int y){
	return (x - y) * (x - y);
}

int total_cost(int y, int n){
	int total = 0;
	for(int i = 0; i < n;i++)
		total += cost(a[i],y);
	return total;
}

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

	int mymin = INF;
	for(int i = -100; i <= 100; i++){
		mymin = min(mymin,total_cost(i,n));
	}
	cout << mymin << endl;
}



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

#define STANDARD (22.0)

double BMI(double h, double w)
{
	return (w / ((h / 100) * (h / 100)));
}

typedef struct {
	int id;
	double bmi;
} SUPER;

int main(void)
{
	int number, i, n;
	double h, w;
	SUPER super;
	
	while (scanf("%d", &n), n){
		super.bmi = 10000.0;
		
		for (i = 0; i < n; i++){
			scanf("%d %lf %lf", &number, &h, &w);

			if ( fabs(super.bmi - STANDARD) > fabs(BMI(h, w) - STANDARD) ){
				super.id = number;
				super.bmi = BMI(h, w);
			}
		}
		
		printf("%d\n", super.id);
	}
	
	return (0);
}

Measured memory_bytes: 628
#pragma region noncode
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1'010'000'000'000'000'017LL;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#pragma endregion

int main() {
    // AtCoder
    // template
    string s;
    cin >> s;
    if(s == "ABC")
        cout << "ARC";
    else
        cout << "ABC";
}


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

using namespace std;
typedef long long ll;
typedef double dd;
#define all(v) v.begin(),v.end()
#define endl "\n"
#define clr(n, r) memset(n,r,sizeof(n));

void fast() {

    cin.tie(0);
    cin.sync_with_stdio(0);
}

ll n, m;
int freq[26];

int main() {
    fast();
    string s;cin>>s;
    int left=-1,right=-1;
    for (int i = 0; i+2 < s.length(); ++i) {
        if(s[i]==s[i+1]){
            left=i+1,right=i+2;
            break;
        }
        if(s[i]==s[i+2]){
            left=i+1,right=i+3;
            break;

        }
    }
    if(s[s.size()-1]==s[s.size()-2])left=s.size()-1,right=s.size();
    cout<<left<<" "<<right;

}

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

using namespace std;

int main()
{
    int l, r, d;
    cin >> l >> r >> d;

    int m, n;

    m = l / d;

    if( d * m < l )
        m += 1;
    
    n = r / d;

    cout << n + 1 - m << "\n";
    
    return 0;
}

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

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

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

		String S = sc.next();

		sc.close();

		if (S.charAt(0) == S.charAt(1) && S.charAt(1) == S.charAt(2)) {
			out.println("No");
		} else {
			out.println("Yes");
		}

	}

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


Measured memory_bytes: 21844
from collections import defaultdict

def dfs(i, comb):
    key = (i, comb)
    if key in memo:
        return memo[key]
    if comb == 75:
        return 1
    if i == m:
        return 0
    k, v = p[i]
    res = 0
    for j in range(v + 1):
        if comb * (j + 1) <= 75:
            res += dfs(i + 1, comb * (j + 1))
    memo[key] = res
    return res

n = int(input())
index = defaultdict(int)

for x in range(2, n + 1):
    y = 2
    while y ** 2 <= x:
        while x % y == 0:
            x //= y
            index[y] += 1
        y += 1
    if x > 1:
        index[x] += 1

*p, = index.items()
m = len(p)
memo = {}
print(dfs(0, 1))


Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll a,b,c;
    cin >> a >> b >>c;
    ll remain = a - b;
    ll have = c;
    if (have <= remain) cout << 0 << endl;
    else cout << have - remain << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,j,n) for(int i = j; i < n; i++)
#define RFOR(i,j,n) for(int i = j-1; i >= n; i--)
#define PREC(n) fixed << setprecision(n)
#define print_array(v) REP(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define _LIBCPP_DEBUG 0
using namespace std;
int64_t MOD = 1000000007;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a, b, t, sum = 0;
  cin >> a >> b >> t;
  int now = a;
  while(now <= t) {
    sum += b;
    now += a;
  }
  cout << sum << endl;
  return 0;
}
//templete by private_yusuke

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace c
{
    class Program
    {
        static void Main(string[] args)
        {
            var strnm = Console.ReadLine().Split(' ');
            var n = int.Parse(strnm[0]);
            var m = int.Parse(strnm[1]);

            var graph = new List<int>[n];
            for (int i = 0; i < n; i++)
            {
                graph[i] = new List<int>();
            }

            for (int i = 0; i < m; i++)
            {
                var strab = Console.ReadLine().Split(' ');
                var a = int.Parse(strab[0]);
                var b = int.Parse(strab[1]);
                graph[a - 1].Add(b);
                graph[b - 1].Add(a);
            }

            var isPassed = new bool[n];
            for (int i = 0; i < n; i++)
            {
                isPassed[i] = false;
            }

            var pathCount = search(1, graph, isPassed);

            Console.WriteLine(pathCount.ToString());
        }

        static int search(int start, List<int>[] graph, bool[] isPassed)
        {
            var workIsPassed = new bool[isPassed.Length];
            for (int i = 0; i < isPassed.Length; i++)
            {
                workIsPassed[i] = isPassed[i];
            }

            workIsPassed[start - 1] = true;

            var isAllPassed = true;
            foreach (var b in workIsPassed)
            {
                if (!b)
                {
                    isAllPassed = false;
                    break;
                }
            }
            if (isAllPassed)
            {
                return 1;
            }

            int pathCount = 0;
            foreach (int i in graph[start - 1])
            {
                if (!workIsPassed[i - 1])
                {
                    pathCount += search(i, graph, workIsPassed);
                }
            }

            return pathCount;
        }
    }
}


Measured memory_bytes: 13268
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353LL

ll f[410][410],g[410],h[410],fac[410],ifac[410],inv[410];
int A[410],B[410],n;

inline int rd()
{
	int x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

inline ll pls(const ll &x,const ll &y) { return (x+y<mod)?x+y:x+y-mod; }
inline ll mns(const ll &x,const ll &y) { return (x-y<0)?x-y+mod:x-y; }
inline ll ksm(ll x,ll y) { ll res=1;for (;y;y>>=1,x=x*x%mod) if (y&1) res=res*x%mod;return res; }

inline void pre_gao()
{
	fac[0]=1;
	for (int i=1;i<=400;i++) fac[i]=fac[i-1]*i%mod;
	ifac[400]=ksm(fac[400],mod-2);
	for (int i=399;~i;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
	inv[1]=1;
	for (int i=2;i<=400;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}

inline void mul(ll *a,ll *b,ll *c,int n,int m)
{
	static ll res[410];
	memset(res,0,sizeof(ll)*(n+m+1));
	for (int i=0;i<=n;i++) for (int j=0;j<=m;j++) res[i+j]=(res[i+j]+a[i]*b[j])%mod;
	memcpy(c,res,sizeof(ll)*(n+m+1));
}

int main()
{
	n=rd();pre_gao();
	for (int i=1;i<=n;i++) A[i]=rd(),B[i]=rd();
	int sum=0;
	for (int i=1;i<=n;i++) sum+=A[i];
	f[0][0]=1;
	int sum1=0,sum2=0;
	for (int i=1;i<=n;i++)
	{
		ll now=1,hh=A[i]*inv[sum]%mod;
		for (int j=0;j<B[i];j++)
		{
			if (j>0) now=now*hh%mod;
			g[j]=mns(0,now*ifac[j]%mod);
		}
		for (int j=sum1;j>=0;j--)
		{
			for (int k=0;k<=sum2;k++) f[j+A[i]][k]=pls(f[j+A[i]][k],f[j][k]);
			mul(f[j],g,f[j],sum2,B[i]-1);
		}
		sum1+=A[i];sum2+=B[i];
	}
	for (int i=0;i<sum;i++) for (int j=0;j<=sum2;j++) f[i][j]=mns(0,f[i][j]);
	ll ans=0;
	for (int i=0;i<sum;i++)
	{
		ll now=i*inv[sum]%mod,Inv=ksm(mns(1,now),mod-2);
		g[0]=Inv;
		for (int j=1;j<=sum2;j++)
		{
			ll hh=mns(g[j-1],fac[j-1])*j%mod;
			g[j]=pls(hh,fac[j])*Inv%mod;
		}
		for (int j=0;j<=sum2;j++) ans=pls(ans,f[i][j]*g[j]%mod);
	}
	printf("%lld\n",ans);
	return 0;
}

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

int main(){
  int n;
  cin >> n;
  vector<string>w(n);
  for(int i = 0; i < n; i++)cin >> w[i];
  bool flag1 = true;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(w[i] == w[j] && i != j)flag1 = false;
    }
  }
  bool flag2 = true;
  for(int i = 0; i < n - 1; i++){
    if(w[i][w[i].size() - 1] != w[i+1][0] )flag2 = false;
  }
  string ans = (flag1 == true && flag2 == true)? "Yes": "No";
  cout << ans << endl;
}


Measured memory_bytes: 256
def main():

    while True:
        strDeck = input()
        if strDeck == "-":
            break
        else:
            intTime = int(input())
            intNum = 0

            for _ in range(intTime):
                intNum += int(input())

            intLenDeck = len(strDeck)
            intShuffle = intNum % intLenDeck

            print(strDeck[intShuffle:]+strDeck[:intShuffle])


if __name__ == '__main__':
    main()



Measured memory_bytes: 5600
#pragma GCC optimize("O3")
#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;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;

#define all(a) (a).begin(), (a).end()

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

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

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

    ll asum = accumulate(all(a), 0LL);
    ll amin = *min_element(all(a));

    if(asum % 2 == 1){
        cout << "First" << endl;
        return 0;
    }

    if(asum % 2 == 0 && n % 2 == 0 && amin % 2 == 1){
        cout << "First" << endl;
        return 0;
    }

    cout << "Second" << endl;

    return 0;
}


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

int main() {
  int n,a,res=0,max=0;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> a;
    if(max<=a){
      res++;
      max=a;
    }
  }
  cout << res << endl;
}


Measured memory_bytes: 256
# a = int(input())
# b,c = map(int, input().split())
# s = input()
# print('{} {}'.format(a+b+c,s))
#
# a,b = map(int, input().split())
# if a*b%2 == 0:
#     print("Even")
# else :
#     print("Odd")
# l = list(input())
# l_new = [int(n) for n in l]
# count = 0
# for i in l_new:
#     if i == 1:
#         count += 1
# print(count)
# #Maxの答えを先に宣言して上限を設けておく
# ans = 10 **9
# N = int(input())
# A = list(map(int,input().split()))
# for i in A:
#     p = 0
#     while i % 2 ==0:
#         i //=2
#         p += 1
#     if p < ans:
#         ans = p
#         #一度ansに格納して大小の比較を行っている
# print(ans)

#切り捨て除算


# a = int(input())
# b = int(input())
# c = int(input())
# X = int(input())
# count = 0
# for i in range(a+1):
#     x = 500 * i
#     for j in range(b+1):
#         y = 100 * j
#         for k in range(c+1):
#             z = 50 * k
#             if x+y+z == X :

N = int(input())
l = list(map(int,input().split()))
l_r = sorted(l,reverse=True)
Alice = l_r[::2]
Bob = l_r[1::2]

m =0
n = 0
for i in Alice:
    m += i
for j in Bob:
    n += j
print(m-n)





Measured memory_bytes: 3060
//
//  main.cpp
//
 
#include <algorithm>
#include <array>
#include <assert.h>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
 
template<typename T>
vector<T> make_vec_nd(T init, size_t size) {
	return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, size_t size, Args... rest) {
	auto inner = make_vec_nd(init, rest...);
	return vector<decltype(inner)>(size, inner);
}
 
int main() {
	ll X, Y;
	cin >> X >> Y;
	if (abs(X-Y) >= 2) {
		cout << "Alice"  << endl;
	} else {
		cout << "Brown" << endl;
	}
}

Measured memory_bytes: 256
//abc046_b.cpp
//Sun Oct 21 11:11:12 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int n,m;
	cin >> n >> m;
	ll ans = m;
	for (int i=1;i<n;i++){
		ans *= m-1;
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <vector>
#include <map>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
main()
{
    int n, k;
    string s;
    cin >> n >> k >> s;
    int same = 0, dif = 0;
    rep(i, n - 1)
    {
        if (s[i] == s[i + 1])
            same++;
        else
            dif++;
    }
    cout << same + min(dif, k * 2) << endl;
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <cstring>
using namespace std;
int a[8][8], f[8], b[8], c[15], d[15];

void search(int n)
{
	if (n >= 8)
	{
		for (int k = 0; k < 8; ++k)
		{
			for (int j = 0; j < 8; ++j)
			{
				if (a[k][j])
					cout << "Q";
				else
					cout << ".";
			}
			cout << endl;
		}
	}
	else
	{
		if (f[n])
			search(n + 1);
		else
		for (int i = 0; i < 8; ++i)
		{
			if (!b[i] && !c[i + n] && !d[n - i + 7])
			{
				b[i] = 1;
				c[i + n] = 1;
				d[n - i + 7] = 1;
				a[n][i] = 1;
				search(n + 1);
				b[i] = 0;
				c[i + n] = 0;
				a[n][i] = 0;
				d[n - i + 7] = 0;
			}
		}
	}
}

int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		int v, c1;
		cin >> v >> c1;
		a[v][c1] = 1;
		b[c1] = 1;
		f[v] = 1;
		c[v + c1] = 1;
		d[v - c1 + 7] = 1;
	}
	search(0);
	return 0;
}


Measured memory_bytes: 3116
#include <iostream>
#define MOD 1000000007

using namespace std;
typedef long long ll;

ll exp(ll x,ll p){
    if(p==0)
        return 1LL;
    ll y=exp(x,p/2);
    if(p%2==0)
        return (y*y)%MOD;
    return (((y*y)%MOD)*x)%MOD;
}

ll f[2000005];
ll inv[2000005];

ll g(ll x,ll y){
    return (((((f[x+y+2]*inv[x+1])%MOD)*inv[y+1])%MOD)+MOD-1)%MOD;
}

ll i;
ll c1,c2,r1,r2;

int main()
{
    f[0]=1;
    inv[0]=1;
    for(i=1;i<=2000002;i++){
        f[i]=f[i-1]*i%MOD;
        inv[i]=exp(f[i],MOD-2);
    }
    cin>>r1>>c1>>r2>>c2;
    cout<<(MOD + g(r2,c2) - g(r2,c1-1) - g(r1-1,c2) + g(r1-1,c1-1))%MOD<<'\n';
    return 0;
}


Measured memory_bytes: 31488
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
S = input()[:-1]
acc = [0]

for i in range(N-1):
    if S[i]=='A' and S[i+1]=='C':
        acc.append(acc[-1]+1)
    else:
        acc.append(acc[-1])

acc.append(acc[-1])

for _ in range(Q):
    l, r = map(int, input().split())
    print(acc[r-1]-acc[l-1])

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

#define dump(...) do{print_vars(cout<<"# "<<#__VA_ARGS__<<'=',__VA_ARGS__);cout<<endl;}while(0)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;

template<typename T,typename U>bool chmin(T& a,const U& b){return a>b?(a=b,1):0;}
template<typename T,typename U>bool chmax(T& a,const U& b){return a<b?(a=b,1):0;}

void print_vars(ostream&){}
template<typename Car,typename... Cdr>
void print_vars(ostream& os,const Car& car,const Cdr&... cdr){
	print_vars(os<<car<<(sizeof...(cdr)?",":""),cdr...);
}

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

template<int I,typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<int I,typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	os<<get<I>(t)<<(sizeof...(Cdr)?",":"");
	print_tuple<I+1,Cdr...>(os,t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<0,Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

struct FenwickTree{
	vector<ll> data;
	FenwickTree(int n):data(n+1){}
	void Add(int i,int x){
		for(i++;i<data.size();i+=i&-i)
			data[i]+=x;
	}
	ll Sum(int i){
		ll res=0;
		for(;i;i-=i&-i)
			res+=data[i];
		return res;
	}
	ll Sum(int i,int j){
		return Sum(j)-Sum(i);
	}
};

ll calc(const vi& a)
{
	int n=a.size();
	FenwickTree ft(n);
	ll res=0;
	rep(i,n){
		res+=ft.Sum(a[i],n);
		ft.Add(a[i],1);
	}
	return res;
}

ll solve(const string& s)
{
	int n=s.size();
	map<char,deque<int>> pos;
	rep(i,n) pos[s[i]].push_back(i);

	int odd=0;
	for(auto p:pos) odd+=p.second.size()&1;
	if(odd>1) return -1;

	int pivot=-1;
	for(auto p:pos) if(p.second.size()&1){
		pivot=p.second[p.second.size()/2];
		break;
	}

	vi ls;
	for(auto p:pos){
		const auto a=p.second;
		int m=a.size()/2;
		ls.insert(end(ls),begin(a),begin(a)+m);
	}
	sort(all(ls));
	deque<int> rs;
	for(int i:ls){
		char c=s[i];
		rs.push_front(pos[c].back());
		pos[c].pop_back();
	}

	vi is=ls;
	if(n&1)
		is.push_back(pivot);
	is.insert(end(is),all(rs));
	return calc(is);
}

int main()
{
	#ifndef _GLIBCXX_DEBUG
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	constexpr char endl='\n';
	#endif

	for(string s;cin>>s&&s!="#";){
		cout<<solve(s)<<endl;
	}
}


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

using namespace std;

int main() {

    string S;
    cin >> S;
    int N = S.size();


    //string current;
    char current;
    char begin;
    //string begin;


    begin = '0';
    current = begin;


    // vector<string> A(N);
    int ans_a = 0;
    for (int i = 0; i < N; ++i) {
        if (S[i] == current) {
            ans_a++;
            if (current == '0') {
                current = '1';
            } else {
                current = '0';
            }
        } else {
            current = S[i];
        }
    }

    begin = '1';
    current = begin;


    // vector<string> A(N);
    int ans_b = 0;
    for (int i = 0; i < N; ++i) {
        if (S[i] == current) {
            ans_b++;
            if (current == '0') {
                current = '1';
            } else {
                current = '0';
            }
        } else {
            current = S[i];
        }
    }


    int ans;
    if (ans_a >= ans_b) {
        ans = ans_b;
    } else {
        ans = ans_a;
    }

    cout << ans << endl;
}


Measured memory_bytes: 512
/* B - FizzBuzz Sum */

#include <stdio.h>

int main(void){
  long int N, i, sum = 0;
  scanf("%ld", &N);
  for(i = 1; i <= N; i++){
    if(i % 3 != 0 && i % 5 != 0){
      sum += i;
      // printf("%d ", i);
    }
  }
  printf("%ld\n", sum);

  return 0;
}


Measured memory_bytes: 1720
i = 1
n = int(input())
while i <= n:
	x = i
	if x % 3 == 0:
		print('' , i , end = '')
	else:
		while x:
	 		if x % 10 == 3:
	 			print('' , i , end = '')
	 			break
	 		x = int(x / 10)
	i = i + 1
print('')

Measured memory_bytes: 8200
#include <bits/stdc++.h>
using namespace std;
#define pi 3.1415926536
#define forn(i, a, b) for (int i = a; i < b; i++)
#define LL long long
#define MP make_pair
#define ff first
#define ss second
#define INF 2147483647
#define _INF -2147483647
#define pq priority_queue
#define MM multimap
#define PB push_back
#define ipair pair<int, int> s
#define lpair pair<LL, LL>
#define MAXN 100004

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x != i) cnt++;
    }
    if (cnt <= 2)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;
const char sp = ' ';

using namespace std;

struct Node{
    ll depthT;
    ll depthA;
    vector<ll> chi;
};
Node node[100004];

void dfsT(ll loca, ll depth, ll rem){
    node[loca].depthT=depth;
    rep(i, node[loca].chi.size()){
        if(node[loca].chi[i]==rem) continue;
        dfsT(node[loca].chi[i], depth+1, loca);
    }
}

void dfsA(ll loca, ll depth, ll rem){
    node[loca].depthA=depth;
    rep(i, node[loca].chi.size()){
        if(node[loca].chi[i]==rem) continue;
        dfsA(node[loca].chi[i], depth+1, loca);
    }
}

int main(void){
    ll N, u, v;
    cin>>N>>u>>v;
    rep(i, N-1){
        ll A, B;
        cin>>A>>B;
        node[A-1].chi.push_back(B-1);
        node[B-1].chi.push_back(A-1);
    }
    dfsT(u-1, 0, -1);
    dfsA(v-1, 0, -1);
    ll Maxim=0;
    rep(i, N){
        if(node[i].depthA-node[i].depthT>=0){
            ll ans=((node[i].depthA-node[i].depthT)%2==0 ? node[i].depthA-1 : node[i].depthA-1);
            
            Maxim=max(Maxim, ans);
        }
    }
    cout<<Maxim<<endl;
    return 0;
}


Measured memory_bytes: 12544