akhauriyash/Code-Regression huggingface dataset:
n = int(input())
xy = []
for i in range(n):
    a = list(map(int, input().split()))
    xy.append(a)

def factorial(n):
    if n == 0:
        return 1
    else:
        a = 1
        for i in range(n):
            a *= n - i
        return a

def distance(a, b):
    l = ((a[0] - b[0])**2 + (a[1] - b[1])**2) ** 0.5
    return l

suml = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        suml += distance(xy[i], xy[j])

ave = (suml * 2 * factorial(n - 1)) / factorial(n)
print(ave)

Measured memory_bytes: 62420
#include <iostream>
#include <cmath>
#include <string>
#include <cassert>
using namespace std;

const long N = 4;
const long N2 = 16;
const long LIMIT = 100;
const long dx[4] = {0, -1, 0, 1};
const long dy[4] = {1, 0, -1, 0};
const char dir[4] = {'r', 'u', 'l', 'd'};
long MDT[N2][N2];

struct Puzzle {long f[N2], space, MD;};

Puzzle state;
long limit;
long path[LIMIT];

long getAllMD(Puzzle pz){
	long sum = 0;
	for (long i = 0; i < N2; i++){
		if (pz.f[i] == N2) continue;
		sum += MDT[i][pz.f[i] - 1];
	}
	return sum;
}

bool isSolved(){
	for (long i = 0; i < N2; i++){
		if (state.f[i] != i + 1) return false;
	}
	return true;
}

bool dfs(long depth, long prev){
	if (state.MD == 0) return true;
	if (depth + state.MD > limit) return false;

	long sx = state.space / N;
	long sy = state.space % N;
	Puzzle tmp;

	for (long r = 0; r < 4; r++){
		long tx = sx + dx[r];
		long ty = sy + dy[r];
		if (tx < 0 || ty < 0 || tx >= N || ty >= N) continue;
		if (max(prev, r) - min(prev, r) == 2) continue;
		tmp = state;

		state.MD -= MDT[tx * N + ty][state.f[tx * N + ty] - 1];
		state.MD += MDT[sx * N + sy][state.f[tx * N + ty] - 1];
		swap(state.f[tx * N + ty], state.f[sx * N + sy]);
		state.space = tx * N + ty;
		if (dfs(depth + 1, r)){
			path[depth] = r;
			return true;
		}
		state = tmp;
	}
	return false;
}

string iterative_deepening(Puzzle in){
	in.MD = getAllMD(in);

	for (limit = in.MD; limit <= LIMIT; limit++){
		state = in;
		if (dfs(0, -100)){
			string ans = "";
			for (long i = 0; i < limit; i++) ans += dir[path[i]];
			return ans;
		}
	}
	return "unsolvable";
}

int main(){
	for (long i = 0; i < N2; i++){
		for (long j = 0; j < N2; j++){
			MDT[i][j] = abs(i / N - j / N) + abs(i % N - j % N);
			Puzzle in;
		}
	}
	Puzzle in;
	for (long i = 0; i < N2; i++){
		cin >> in.f[i];
		if (in.f[i] == 0){
			in.f[i] = N2;
			in.space = i;
		}
	}
	string ans = iterative_deepening(in);
	cout << ans.size() << endl;

	return 0;
}

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

using namespace std;
typedef long long int ll;
//typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
//typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

const ll mod = 1e9 + 7;

int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N; std::cin >> N;
  string S; std::cin >> S;
  std::vector<ll> dp(N, 1);

  REP(i, N-1) {
    int L = dp.size();
    std::vector<ll> acc(L + 1, 0), _dp(L - 1);
    REP(j, L) acc[j+1] = (dp[j] + acc[j]) % mod;
    REP(j, L-1) {
      if (S[i] == '<') {
        _dp[j] = acc[j+1];
      } else {
        _dp[j] = (acc[L] - acc[j+1] + mod) % mod;
      }
    }
    dp = _dp;
  }
  assert(dp.size() == 1);
  std::cout << dp[0] << std::endl;
  return 0;
}


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

namespace A
{
    class Program
    {
        public static void Main(string[] args)
        {
            var n = ReadLine();
            var alpha = new string[]{ "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"};
            Console.WriteLine(alpha[Array.IndexOf(alpha, n) + 1]);
            ReadLine();
        }

        /// <summary>
        /// コンビネーション
        /// </summary>
        /// <param name="n"></param>
        /// <param name="m"></param>
        /// <returns></returns>
        static int nCm(int n, int m)
        {
            if (m == 0) return 1;
            if (n == 0) return 0;
            return n * nCm(n - 1, m - 1) / m;
        }

        /// <summary>
        /// stringを一文字ずつintにキャストして配列に変換します。
        /// </summary>
        /// <param name="str"></param>
        /// <returns></returns>
        public static int[] StringCharArrayIntArray(string str)
        {
            List<int> b = new List<int>();
            for (int i = 0; i < str.Length; i++) {
                b.Add( int.Parse(str[i].ToString()));
            }
            return b.ToArray();
        }

        public static string ReadLine()
        {
            return Console.ReadLine();
        }

        public static int ReadLineInt()
        {
            return int.Parse(Console.ReadLine());
        }

        public static string[] ReadLineStringSplit(char a = ' ')
        {
            return ReadLine().Split(a).ToArray();
        }

        public static int[] ReadLineIntSpilit(char a = ' ')
        {
            return ReadLine().Split(a).Select(x => int.Parse(x)).ToArray();
        }
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
	int tmp[30][2];
	int num[30];
	int num2[30];
	int w,n,i,j;
	
	//??????????????????
	for(j=0; j<2; j++){
		for(i=0; i<30; i++){
			tmp[i][j]=0;
			}
	}
	for(i=0; i<30; i++){
		num[i]=1+i;
		num2[i]=1+i;
	}
	
	//????£?w????¨??£?n?????°?????????
	cin >> w >> n;
	
	//?¨??£????????´??????????
	for(i=0; i<n; i++){
		scanf("%d,%d",&tmp[i][0],&tmp[i][1]);
	}
	
	//??\???????????????
	for(i=0; i<w; i++){		//????£??????°????????°?????????
		for(j=0; j<n; j++){		//?¨??£??????°????????°?????????
			//??\?????????
			if((num[i]==tmp[j][0]) || (num[i]==tmp[j][1])){
				if(num[i]==tmp[j][0]){
					num[i]=tmp[j][1];
				}else{
					num[i]=tmp[j][0];
				}		
			}
		}
	}
	for(i=0; i<w; i++){
		j=num[i];
		num2[j-1]=i+1;
	}
	
	
	
	
	//????????¨???
	for(i=0; i<w; i++){
		cout << num2[i] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1240
#include <iostream>

using namespace std;

int main() {
    int n;
    while (cin >> n) {
        int cnt = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 10; k++) {
                    for (int l = 0; l < 10; l++) {
                        if (i + j + k + l == n) {
                            cnt++;
                        }
                    }
                }
            }
        }
        cout << cnt << endl;
    }

    return 0;
}

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

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

    vint A,B;
    rep(i,N){
        int a;cin>>a;
        if(a>=0)A.pb(a);
        else B.pb(-a);
    }
    reverse(all(B));

    int ans=LLONG_MAX;
    rep(t,2){
        for(int i=0;i<K&&i<A.size();i++){
            if(K-i-1>B.size())continue;
            int sum=A[i];
            if(i+1!=K)sum+=A[i]+B[K-i-1-1];
            chmin(ans,sum);
        }
        swap(A,B);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1656
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>

using namespace std;


#define all(c) ((c).begin()), ((c).end())
#define debug(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)

#define mp make_pair
#define fst first
#define snd second
#define pb push_back


const double EPS = 1e-10;


typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef complex<double> P;



inline double dot(const P &a, const P &b) {
	return (conj(a) * b).real();
}


int main(){
	int n; cin >> n;
	while (n--) {
		P ps[4];
		rep(i, 4) {
			double x, y; cin >> x >> y;
			ps[i] = P(x, y);
		}
		cout << (dot(ps[0] - ps[1], ps[2] * P(0, 1) - ps[3] * P(0, 1)) == 0 ? "YES" : "NO") << endl;
	}
	
	return 0;
}

Measured memory_bytes: 0
def main
  n, w = gets.split(" ").map(&:to_i)
  arr = Array.new(w + 1, nil)
  arr[0] = 0
  goods = []
  n.times do
    goods << gets.split(" ").map(&:to_i)
  end
  goods.each{|good|
    -1.downto(-w - 1){|weight|
      if arr[weight] and (weight + good[1]) < 0 and (!arr[weight + good[1]] or arr[weight + good[1]] < (arr[weight] + good[0]))
        arr[weight + good[1]] = arr[weight] + good[0]
      end
    }
  }
  puts arr.select{|i|i}.max
end
main

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

#define HAS_TEST_CASE 0

namespace rG{

typedef long long ll;

const int N=1e6;

int n,m,k,a[N+10];
char s[N+10];
int prime[N+10],totp,notPrime[N+10];
std::set<int> cnt[N+10];
int cntt[N+10];

void init(){
	notPrime[1]=1;
	for(int i=2;i<=N;i++){
		if(!notPrime[i])prime[++totp]=i;
		for(int j=1;j<=totp&&i*prime[j]<=N;j++){
			notPrime[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}

#define pc puts("pairwise coprime")
#define sc puts("setwise coprime")
#define no puts("not coprime")

int gcd(int x,int y){return (!y)?x:gcd(y,x%y);}

inline void main(){
	init();
	scanf("%d",&n);
	bool f1=1;
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		for(int j=1;j<=sqrt(a[i]);j++){
			if(a[i]%j==0&&!notPrime[j])cntt[j]++;
			if(a[i]%j==0&&j*j!=a[i]&&!notPrime[a[i]/j])cntt[a[i]/j]++;
			if(cntt[j]>=2){f1=0;break;}
			if(a[i]%j==0&&cntt[a[i]/j]>=2){f1=0;break;}
		}
		if(f1==0){
			for(int j=i+1;j<=n;j++)
				scanf("%d",a+j);
			break;
		}
	}
	if(f1==1)return pc,void();
	int gcdd=a[1];
	for(int i=2;i<=n;i++)
		gcdd=gcd(gcdd,a[i]);
	if(gcdd==1)return sc,void();
	else no;
}

} // namespace rG

int main(){
#if defined(LOCAL)&&HAS_TEST_CASE
	freopen("tmp.out","w",stdout);
#endif
#if HAS_TEST_CASE
	int T;
	scanf("%d",&T);
	while(T--)rG::main();
#else
	rG::main();
#endif
	return 0;
}


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


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

    string s;
    cin >> s;
    bool a = false;
    bool b = false;
    for(int i=0; i<len(s); i++){
      if(s[i] == 'C') a = true;
      if(a == true && s[i] == 'F'){
        cout << "Yes" << endl;
        return 0;
      }
    }
    cout << "No" << endl;
}


Measured memory_bytes: 256
N = int(input())
A = [int(s) for s in input().split(' ')]
A.sort()
print(A[N - 1] + sum([abs(a) for a in A[1:N - 1]]) - A[0])
answer = ''
for i in range(1, len(A) - 1):
    if(A[i] > 0):
        answer += "{} {}\n".format(A[0], A[i])
        A[0] -= A[i]
    else:
        answer += "{} {}\n".format(A[N - 1], A[i])
        A[N - 1] -= A[i]
answer += "{} {}\n".format(A[N - 1], A[0])
print(answer)

Measured memory_bytes: 14264
// Created by Bingoo on 7/8/2020.
#include"bits/stdc++.h"
using namespace std ;
#define ll  long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

template <class ...Args>
auto &see(const Args &...args) {return ((cerr << " " << args), ...) << '\n';}
#define bug(...)  cerr << "[ "#__VA_ARGS__" ] = "; see(__VA_ARGS__) << '\n';
//C++17
template<typename... Args>
void read(Args&... args){((cin >> args), ...);}
template<typename... Args>
void write(Args... args){((cout << args << " "), ...);}



int n,k ;
int main(){
    IOS
    cin >> n ;

    ll dp[n]={0} ,a[n];

    for (int j = 0; j <n ; ++j) {
        cin >> a[j] ;
    }
    dp[1]= abs(a[0]-a[1]);

    for(int i=2 ; i<n ;i++){
        dp[i]= min(abs(a[i]-a[i-1])+dp[i-1],dp[i-2]+abs(a[i]-a[i-2]));

    }

    cout << dp[n-1] <<'\n';


}




Measured memory_bytes: 5196
K,N = map(int, input().split())
A = list(map(int,input().split()))


l_s = []
check = 0
for i in range(0,N):
    if(A[i] == 0):
        check =1
if(check == 1):
    for i in range(1,N):
          l_s.append(A[i]-A[i-1])
    l_s.append(K-A[N-1])
    num = 0
    ans = 99999999999999999
    for i in range(0,N):
        num = K - l_s[i]
        ans = min(ans,num)
    print(ans)
    
else: 
    for i in range(1,N):
        l_s.append(A[i]-A[i-1])
    l_s.append(K-A[N-1]+A[0])
    m1 = max(l_s)
    ans = K-m1
    print(ans)

Measured memory_bytes: 26444
// {{{
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
// }}}

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

static constexpr int mod = (int)1e9 + 7;
static constexpr int inf = 100100100;
static constexpr ll linf = 1e18;
static constexpr double eps = 1e-9;
static constexpr double pi = 3.14159265359;

#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rrep(i, n) for (ll i = n; i >= 0; --i)
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define pb push_back
#define ist insert
#define fst first
#define snd second


using P = pair<ll, ll>;

int main() {
    // cin.tie(0);
    // ios_base::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    vector<P> S;
    rep (i, N) {
        ll t, d;
        cin >> t >> d;
        S.pb({d, t});
    }
    sort(rall(S));

    priority_queue<P, vector<P>, greater<P>> Q1;
    set<ll> T;
    ll base = 0;
    rep (i, K) {
        base += S[i].fst;
        if (!T.count(S[i].snd)) {
            T.ist(S[i].snd);
        } else {
            Q1.push(S[i]);
        }
    }
    priority_queue<P, vector<P>, less<P>> Q2;
    for (ll i = K; i < N; ++i) {
        Q2.push(S[i]);
    }
    ll ans = base + T.size() * T.size();
    while (!Q1.empty() && !Q2.empty()) {
        P p2 = Q2.top();
        Q2.pop();
        if (T.count(p2.snd)) continue;
        T.ist(p2.snd);
        P p1 = Q1.top();
        Q1.pop();
        base -= p1.fst;
        base += p2.fst;
        ans = max(ans, (ll)(base + T.size() * T.size()));
    }
    cout << ans << endl;
}


Measured memory_bytes: 6256
/*
THE BEST IS YET TO COME
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define r(i, s, l) for (int i = s; i < l; i++)
#define mod 1000000007
#define INT_BITS 32
#define ld long double
#define pp pair<long long, long long>
#define ss second
#define ff first
#define N 2000005
#define all(a) a.begin(), a.end()
#define pb push_back
using namespace std;
void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
int main()
{
    fast();
    ld r;
    cin>>r;
    r = r*2*3.1415926535;
    cout<<r;
  
    return 0;
}

Measured memory_bytes: 3808
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;

int vs[5];

int main(void) {
  REP(i, 3) {
    scanf("%d", &vs[i]);
  }
  int res = 0;
  for(;; ++res) {
    sort(vs, vs+3);
    // cerr << vs[0] << " " << vs[1] << " " << vs[2] << endl;
    if(vs[0] + 2 <= vs[2]) {
      vs[0] += 2;
      continue;
    }
    if(vs[0] == vs[1]) { 
      if(vs[1] == vs[2]) { // 0,0,0
        break;
      } else { // 0,0,1
        assert(vs[0] + 1 == vs[2]);
        res += 1;
        break;
      }
    } else { // 0,1,1
      assert(vs[0] + 1 == vs[1]);
      assert(vs[1] == vs[2]);
      res += 2;
      break;
    }
  }
  cout << res << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template <typename T> using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //greater<T> for sorting decreasingly

#define ll         long long
#define pll        pair<ll,ll>
#define unique(a)  a.resize(unique(a.begin(), a.end()) - a.begin())
#define fill(v, p) memset(v,p,sizeof v)
#define all(x)     x.begin(), x.end()
#define at_(x,i)   x.find_by_order(i)
#define koto_(x,i) x.order_of_key(i)
#define PI         acos(-1.0)
#define EPS        0.000000001
#define INF        1LL<<62
#define MAX        300005
#define MOD        1000000007


signed int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(0);
	
	ll n, k;
	cin >> n >> k;
	
	ll a[n];
	for(int i=0;i<n;i++)
	{
		cin >> a[i];
	}
	
	sort(a,a+n);
	reverse(a,a+n);
	
	ll sum=0;
	for(int i=k;i<n;i++)
	{
		sum+=a[i];
	}
	
	cout << sum << endl;
	
	return 0;
}


Measured memory_bytes: 1792
import sys

lines = sys.stdin.readlines()
input_list = list(lines[0].rstrip())
int12 = int("".join([input_list[0],input_list[1]]))
int34 = int("".join([input_list[2],input_list[3]]))
if 1 <= int12 <= 12:
  if 1 <= int34 <= 12:
    print("AMBIGUOUS")
  else:
    print("MMYY")
else:
  if 1 <= int34 <= 12:
    print("YYMM")
  else:
    print("NA")

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
long long n,x,m;
struct node
{
	long long num,v;
}f[100010];
long long l,r;
long long sum,ans;
bool cnt[100010];
int main()
{
	scanf("%lld%lld%lld",&n,&x,&m);
	f[1].v=x;
	cnt[x]=1;
	f[x].num=1;
	l=1,r=n;
	for(long long i=2;i<=n;i++)
	{
		f[i].v=(f[i-1].v*f[i-1].v)%m;
		if(cnt[f[i].v])
		{
			l=f[f[i].v].num;
			r=i-1;
			break;
		}
		cnt[f[i].v]=1;
		f[f[i].v].num=i;
	}
	for(long long i=1;i<l;i++)
	{
		ans+=f[i].v;
	}
	for(long long i=l;i<=r;i++)
	{
		sum+=f[i].v;
	}
	ans+=((n-l+1)/(r-l+1))*sum;
	long long x=(n-l+1)%(r-l+1);
	for(long long i=l;i<l+x;i++)
	{
		ans+=f[i].v;
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 5240
#include<stdio.h>
int main(void)
{
  int a,b;
  scanf("%d %d",&a,&b);
  int max=a+b;
  if(a-b>max&&a-b>a*b){
    max=a-b;
  }else if(a*b>max&&a*b>a-b){
    max=a*b;
  }
  printf("%d\n",max);
  return 0;
}


Measured memory_bytes: 128
/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
template<typename T> using v=vector<T>;
#define int long long
typedef string str;
typedef vector<int> vint;
#define rep(a,l,r) for(int a=(l);a<(r);a++)
#define pb push_back
#define sz(a) ((int)(a).size())
const long long inf=4611686018427387903;//2^62-1
#if 0 //FileIO
ifstream fin ("input.txt" );
ofstream fout("output.txt");
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
void read(){}             template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get   (arg)     ;read(args...) ;}
void print(){}            template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put   (arg)<<" ";print(args...);}
void debug(){cout<<endl;} template<typename Arg,typename... Args> void debug(Arg  arg,Args...  args){cout<<(arg)<<" ";debug(args...);}
int getInt(){int a; get a; return a;}
//code goes here
void run(){
    int a,b;read(a,b);
    rep(i,1,10010){
        int d1=i*(i+1)/2,d2=(i+1)*(i+2)/2;
        if(d1<a||d2<b)continue;
        else if (d1-a==d2-b){put d1-a;return;}
    }
}
int32_t main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);run();return 0;}


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

using namespace std;

int main(void){
    string S;
    string T;
    int N;

    cin >> S >> T;
    
    cin >> N;

    int s_s, s_e, t_s, t_e;

    int S_asum[100005];
    S_asum[0] = 0;
    for(int j=1;j<=S.length();j++){
        S_asum[j] = (S_asum[j-1] + S[j -1] - 'A' + 1) % 3;
    }
    int T_asum[100005];
    T_asum[0] = 0;
    for(int j=1;j<=T.length();j++){
        T_asum[j] = (T_asum[j-1] + T[j -1] - 'A' + 1) % 3;
    }

    for(int i=0;i<N;i++){

        /*cin >> s_s >> s_e >> t_s >> t_e;*/
        scanf("%d%d%d%d", &s_s, &s_e, &t_s, &t_e);

        int s_tmp = 0;
        int t_tmp = 0;

        s_tmp = S_asum[s_e] - S_asum[s_s-1] + 3;
        t_tmp = T_asum[t_e] - T_asum[t_s-1] + 3;

        /*string ans = "NO";*/
        if((s_tmp - t_tmp) % 3 == 0){
            /*ans = "YES";*/
            printf("YES\n");
        }
        else{printf("NO\n");}
        /*else{printf("NO\n");}*/
        /*cout << ans << endl;*/
    }
    return 0;
}

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

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

    ll N, K;
    cin >> N >> K;
    ll R, S, P;
    cin >> R >> S >> P;
    string T;
    cin >> T;
    int size = T.size();
    int rounds = size / K;
    if(size % K > 0){
        rounds++;
    }
    //剰余ごとに一つ前が何を出したかのdpに帰着
    // % / rounds / 0:1:2
    vector<vector<vector<ll>>> dp(K, vector<vector<ll>>(rounds + 1, vector<ll>(3, 0)));//0:r 1:s 2:p　を
    for(int i = 0; i < size; i++){
        int jyoyo = i % K;
        int currentRound = i / K;
        //初回roundも全0により結果が変わらず統合可能
        //0:r
        if(T.at(i) == 's'){
            dp.at(jyoyo).at(currentRound + 1).at(0) = max(dp.at(jyoyo).at(currentRound).at(1), dp.at(jyoyo).at(currentRound).at(2)) + R;
        } else {
            dp.at(jyoyo).at(currentRound + 1).at(0) = max(dp.at(jyoyo).at(currentRound).at(1), dp.at(jyoyo).at(currentRound).at(2));
        }
        //1:s
        if(T.at(i) == 'p'){
            dp.at(jyoyo).at(currentRound + 1).at(1) = max(dp.at(jyoyo).at(currentRound).at(0), dp.at(jyoyo).at(currentRound).at(2)) + S;
        } else {
            dp.at(jyoyo).at(currentRound + 1).at(1) = max(dp.at(jyoyo).at(currentRound).at(0), dp.at(jyoyo).at(currentRound).at(2));
        }
        //2:p
        if(T.at(i) == 'r'){
            dp.at(jyoyo).at(currentRound + 1).at(2) = max(dp.at(jyoyo).at(currentRound).at(0), dp.at(jyoyo).at(currentRound).at(1)) + P;
        } else {
            dp.at(jyoyo).at(currentRound + 1).at(2) = max(dp.at(jyoyo).at(currentRound).at(0), dp.at(jyoyo).at(currentRound).at(1));
        }
    }
    ll answer = 0;
    int oneLessIndex = size % K;
    for(int i = 0; i < K; i++){
        ll currentAnswer = max(dp.at(i).at(rounds).at(0), dp.at(i).at(rounds).at(1));
        currentAnswer = max(currentAnswer, dp.at(i).at(rounds).at(2));
        answer += currentAnswer;
        if(i == oneLessIndex - 1){
            rounds--;
        }
    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 17616
while True:
  try:
    a,b,c,d,e,f=map(float,input().split())
    x=(c*e-b*f)/(a*e-b*d)
    y=(c*d-a*f)/(b*d-a*e)
    if x==-0: x=0
    if y==-0: x=0
    print(f'{x:.3f} {y:.3f}')
  except EOFError: break


Measured memory_bytes: 5600
n = int(input())
d = [0] * n
present = [[] for i in range(n)]
for i in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    if u > v:
        u, v = v, u
    d[v] += 1
    present[u].append(v)
ans = 0
cur = 0
for v in range(n):
    cur += (n - v) * d[v]
for l in range(n):
    ans += (l + 1) * (l + 2) // 2
    ans -= cur
    for v in present[l]:
        cur -= (n - v)
print(ans)


Measured memory_bytes: 97800
#include <bits/stdc++.h>
#define INF 1e18
#define PI M_PI
#define ll long long
#define vi vector<int>
#define all(v) v.begin(), v.end()
#define REP(i, n) for (int i=0; i<n; i++)
#define REPD(i, n) for (int i=n-1; i>=0; i--)
#define print(x) cout << x << endl;
#define debug(x) cout << #x << " = " << endl;

using namespace std;

void solve()
{
    int r;
    cin >> r;
    print(3*r*r);
}

int main()
{
    solve();

    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A,B=[0]*N,[0]*N
for i in range(N):
    A[i],B[i]=map(int,input().split())
A.sort()
B.sort()
if N%2:
    ans=B[N//2]-A[N//2]+1
else:
    ans=int(((B[N//2]+B[N//2-1])/2-(A[N//2]+A[N//2-1])/2)*2)+1
print(ans)

Measured memory_bytes: 75028
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int r = sc.nextInt();
    if(r < 1200){
      System.out.println("ABC");
    }else if(r < 2800){
      System.out.println("ARC");
    }else{
      System.out.println("AGC");
    }
  }
}

Measured memory_bytes: 23892
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using System.Collections;
static class Extensions
{
    public static int ToInt(this string s) => int.Parse(s);
    public static long ToLong(this string s) => long.Parse(s);
    public static char ToChar(this string s) => char.Parse(s);
    public static double ToDouble(this string s) => double.Parse(s);
    public static int[] ToIntArray(this string s) => s.Replace(',', ' ').Split(' ').Select(x => x.ToInt()).ToArray();
    public static long[] ToLongArray(this string s) => s.Replace(',', ' ').Split(' ').Select(x => x.ToLong()).ToArray();
    public static double[] ToDoubleArray(this string s) => s.Replace(',', ' ').Split(' ').Select(x => x.ToDouble()).ToArray();
}

class Program
{
    static string[] ReadLines(int n) => Enumerable.Range(0, n).Select(s => Console.ReadLine()).ToArray();

    static void Main()
    {
        int[] ab = Console.ReadLine().ToIntArray();
        int a = ab[0];
        int b = ab[1];

        var ans = a - 1;

        if (a <= b)
        {
            ans += 1;

        }

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13268
#include<cstdio>
#include<vector>
const int MaxN=1<<17|10;
int N,ch[MaxN][2],v[MaxN];
long long dep[MaxN];
struct Point{long long x,y;};
void ins(std::vector<Point>&v,long long x,long long y){
	if(!v.size()||y<v[v.size()-1].y)v.push_back((Point){x,y});
}
void find(std::vector<Point>&v,int&p,long long M){
	while(p<v.size()&&v[p].x<=M)p++;
}
std::vector<Point>chk(int i,long long M){
	std::vector<Point>f;
	if(!*ch[i]){
		f.push_back((Point){dep[i],dep[i]});
		return f;
	}
	std::vector<Point>fl=chk(ch[i][0],M),fr=chk(ch[i][1],M);
	for(int pl=0,pr=0,ql=0,qr=0;;pl++){
		for(;pr<fr.size()&&(pl>=fl.size()||fr[pr].x<fl[pl].x);pr++){
			find(fl,ql,M+2*dep[i]-fr[pr].y);
			if(ql)ins(f,fr[pr].x,fl[ql-1].y);
		}
		if(pl>=fl.size())break;
		find(fr,qr,M+2*dep[i]-fl[pl].y);
		if(qr)ins(f,fl[pl].x,fr[qr-1].y);
	}
	return f;
}
int main(){
	scanf("%d",&N);
	for(int i=2,f;i<=N;i++){
		scanf("%d%d",&f,v+i);
		if(*ch[f])ch[f][1]=i;
		else ch[f][0]=i;
		dep[i]=dep[f]+v[i];
	}
	long long l=-1,r=1ll<<34,mid;
	while(r-l>1)chk(1,mid=l+r>>1).size()?r=mid:l=mid;
	printf("%lld\n",r);
}

Measured memory_bytes: 15104
#include<iostream>
#include<math.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<deque>
using namespace std;

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

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

	long long sum=0;
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				
				if(i==1 || j==1 || k==1){
					sum++;
					continue;
				}
				
				if(i==j&&j==k){
					sum+=i;
					continue;
				}
				
				sum+=gcd(i,gcd(j,k));
			}
		}
	}
	
	cout << sum << endl;
}


Measured memory_bytes: 3636
N=int(input())
C=input()
ans=0
while C!="":
  if C[0]=="R":
    C=C[1:]
  elif C[len(C)-1]=="W":
    C=C[0:len(C)-1]
  else:
    C=C[1:len(C)-1]
    ans+=1
print(ans)

Measured memory_bytes: 9480
#include<stdio.h>
int main(void)
{
	int e,y,M,T,S,H;
	scanf("%d %d",&e,&y);
	if(e==0){
		if(1868<=y && 1911>=y){
			printf("M%d\n",44-(1911-y));
		}
		if(1912<=y && 1925>=y){
			printf("T%d\n",14-(1925-y));
		}
		if(1926<=y && 1988>=y){
			printf("S%d\n",63-(1988-y));
		}
		if(1989<=y && 2016>=y){
			printf("H%d\n",28-(2016-y));
		}
	}
	else if(e==1){
		printf("%d\n",1867+y);
	}
	else if(e==2){
		printf("%d\n",1911+y);
	}
	else if(e==3){
		printf("%d\n",1925+y);
	}
	else{
		printf("%d\n",1988+y);
	}
	return 0;
}

		
		
		
		


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

class Problem {
    private int N;

    Problem() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
    }

    void solve() {
        int n = N % 2 == 1 ? N : N + 1;
        int M = N % 2 == 1 ? (N - 1) / 2 : N / 2;

        ArrayList<String> edges = new ArrayList<>();

        for (int i = 1; i < M; i++) {
            edges.add(i + " " + (i + 1));
            edges.add(i + " " + (n - (i + 1)));
            edges.add((i + 1) + " " + (n - i));
            edges.add((n - (i + 1)) + " " + (n - i));
        }

        if (N % 2 == 0 && M > 2) {
            edges.add(1 + " " + M);
            edges.add(1 + " " + (M + 1));
            edges.add(M + " " + (n - 1));
            edges.add((M + 1) + " " + (n - 1));
        } else if (N % 2 == 1) {
            edges.add(1 + " " + N);
            edges.add((n - 1) + " " + N);
            if (M > 1) {
                edges.add(M + " " + N);
                edges.add((M + 1) + " " + N);
            }
        }
        System.out.println(edges.size());
        for (String e: edges){
            System.out.println(e);
        }
    }
}

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


Measured memory_bytes: 22608
while True:
    n=int(input())
    if n==0:
        break
    l=[0]*10 
    for i in range(n):
        c=int(input())
        l[c] +=1
    for j in l:
        if j==0:
            print("-")
        else:
            for k in range(j):
                print("*",end='')
            print('')


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

int main(){
  int i = 0,ans=0,n;
  string s;cin >> s;
  n = s.size();
  if(n!=1){
    while(i<n){
      i++;
      if(s[i] == s[i-1]){
        ans++;
        i++;
        while((s[i]!=s[i-1])&&i<n){
          ans++;
          i++;
        }
      }
    }
  }
  cout << min(ans,n-ans) << endl;

  return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H=INT_MAX;
  int W=INT_MAX;
  while(H+W!=0){
    cin>>H>>W;
    if(H+W==0)break;
    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
        cout<<'#';
      }
      cout<<endl;
    }
    cout<<endl;
  }
  return 0;
}


Measured memory_bytes: 3076
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int n;
    cin >> n;
    vector <ii> a(n);
    for (int i = 0; i < n; ++i) {
        int x, len;
        cin >> x >> len;
        a[i] = mp(x - len, x + len);
    }   
    auto comp = [](ii a, ii b) {
        return a.s < b.s;
    };   
    sort(all(a), comp);

    int r = -1e18;
    int ans = 0;
    for (auto e : a) {
        if (r <= e.f) {
            r = e.s;
            ++ans;
        }   
    }   
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<cstdio>
#define MAXA 100000
#define MAX 2000000000?
#define s(i) scanf("%d", &(i))
#define p(i) printf("%d", (i))
#define ps() printf(" ") 
#define rer(i,j,k) for((i)=(j);(i)<(k);++(i))
#define ret(i,j,k) for((i)=(j);(i)>(k);--(i))
using namespace std;
int main(){
	int k, x, i;
	cin >> k >> x;
	if(k==1){
		cout << x << endl;
	}else{
		for(i = x-k+1; i <= x+k-1; i++){
			cout<< i ;
			if(i!= x+k-1)
				cout << " ";
		}
		cout << endl;
	}
	return 0;
} 

Measured memory_bytes: 256
s  = input()
f = True
if s[0] != "A":
    f = False
c = 0
for i in range(2, len(s) - 1):
    if s[i] == "C":
        c += 1
if c != 1:
    f=False
ss = s[1:].replace("C", "")
for i in range(len(ss)):
    if ss[i] < "a" or ss[i] > "z":
        f = False
if f:
    print("AC")
else:
    print("WA")

Measured memory_bytes: 3064
import numpy as np

N = int(input())
works = np.array([list(map(int, input().split())) for _ in range(N)])

timing = 0
is_safe = True
for item in works[(works[:,1].argsort(0))]:
    time, limit = item
    timing += time
    if timing > limit:
        is_safe = False
        break
print("Yes" if is_safe else "No")

Measured memory_bytes: 62364
#include<bits/stdc++.h>
using namespace std;
 
typedef vector<int> vi; 
typedef pair<int,int> pi;
typedef long long ll;
#define F first 
#define S second 
#define PB push_back 
#define MP make_pair
#define REP(i,a,b) for (int i = a; i <= b; i++)

vector< vector<ll> > dp;

int main(){
	
	ll n,a,b,c;
	
	cin >> n;
	
	dp.assign(3, vector<ll>(n+1,0) );
	
	cin >> a >> b >> c;
	
	dp[0][0] = a;
	dp[1][0] = b;
	dp[2][0] = c;  
 	 	
 	n--;
 	 	
	for(ll i = 1; i <= n; i++){
		
		cin >> a >> b >> c;
	
		dp[0][i] = max( dp[0][i] , max( dp[1][i-1], dp[2][i-1] ) + a );
		dp[1][i] = max( dp[1][i] , max( dp[0][i-1], dp[2][i-1] ) + b );
		dp[2][i] = max( dp[2][i] , max( dp[0][i-1], dp[1][i-1] ) + c );
	}
	
		
	ll maxi = 0;
	
	maxi = max(maxi, dp[0][n]);
	maxi = max(maxi, dp[1][n]);
	maxi = max(maxi, dp[2][n]);
	
	cout << maxi << endl;

	return 0;
}

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

using namespace std;
using ll = long long;
using P = pair<string, int>;
using PP = pair<P, int>;

bool comp(PP x, PP y) {
	P xf = x.first, yf = y.first;
	if (xf.first != yf.first) { return xf.first < yf.first; }
	return xf.second > yf.second;
}

int main() {
	int N;
	cin >> N;
	vector<PP> v(N);
	for (int i = 0; i < N; ++i) {
		string s;
		int p;
		cin >> s >> p;
		v[i] = PP(P(s, p), i + 1);
	}

	sort(v.begin(), v.end(), comp);
	for (int i = 0; i < N; ++i) {
		cout << v[i].second << endl;
	}

	return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
a1, a2, a3 = [], [], []
for i in a:
    if i%4 == 0:
        a1.append(i)
    elif i%2 == 0:
        a2.append(i)
    else:
        a3.append(i)
if len(a2) > 0:
    if len(a1) >= len(a3):
        print("Yes")
    else:
        print("No")
else:
    if len(a1)+1 >= len(a3):
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 63000
/*
  AtCoder Beginner Contest 105
  B - Cakes and Donuts
*/

#include<iostream>
using namespace std;

int N;

int main() {
  scanf("%d", &N);

  int n; // 7ドルのドーナッツの個数
  if (N % 2 == 0) n = 0;
  else n = 1;

  while (n * 7 <= N) {
    if ((N - n * 7) % 4 == 0) {
      printf("Yes\n");
      return 0;
    }

    n += 2;
  }

  printf("No\n");
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long N;
  double rrN;
  int rN,A,B,digit;
  digit = 0;
  cin >> N;
  rrN = sqrt(N);
  rN = rrN;
  for(int i=0;true;i++){
    if(N%(rN-i)!=0) continue;
    else{
      A=rN-i;
      break;
    }
  }
  B=N/A;
  digit = log10(B) + 1;
  cout << digit <<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define pai 3.14159265358
int main()
{
    double a,b,x,h,jiaodu=0;
    scanf("%lf %lf %lf",&a,&b,&x);


    if((a*a*b/2)>x)
    {
        h=2*x/a/b;
        jiaodu=acos((b/sqrt(h*h+b*b)));
        printf("%.10lf",90-jiaodu*180/pai);
    }
    else
    {
        x=a*a*b-x;
        h=2*x/a/a;
        jiaodu=acos((a/sqrt(h*h+a*a)));
        printf("%.10lf",jiaodu*180/pai);
    }


    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>

#define MAX_N (100)
#define INF (1 << 30)
#define ABS(x) ((x) > 0 ? (x) : -(x))

int main(int argc, char *argv[]) {
  // read inputs
  int N, a[MAX_N];
  scanf("%d", &N);
  for (int i = 0 ; i < N; i++)
    scanf("%d", &a[i]);

  // calculate average
  double average = 0;
  for (int i = 0 ; i < N; i++)
    average += a[i];
  average /= N;

  // find closest
  double d_min = INF;
  int i_min = -1;
  for (int i = 0 ; i < N; i++) {
    double diff = ABS(average - a[i]);
    if (diff < d_min) {
      d_min = diff;
      i_min = i;
    }
  }
  printf("%d\n", i_min);
  
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define  ll long long int
vector<vector<ll>>v(100002);
ll dp[100002];
ll dfs(ll a)
{
    ll res=0;
    for(ll i=0;i<v[a].size();i++)
    {
        if(dp[v[a][i]]==-1)
        {
            dp[v[a][i]]=dfs(v[a][i]);
        }
        res=max(res,dp[v[a][i]]+1);
    }
    return res;
}
int main()
{
    ll n,m;cin>>n>>m;
    //vector<vector<ll>>v(m+1);
    memset(dp,-1,sizeof(dp));
    for(ll i=1;i<=m;i++)
    {
        ll a,b;cin>>a>>b;
        v[a].push_back(b);
    }
   /* for(ll i=1;i<=n;i++)
    {
        for(ll j=0;j<v[i].size();j++)
            cout<<v[i][j]<<" ";
        cout<<endl;
    }*/
    ll ans=0;
    for(ll i=1;i<=n;i++)
    {
        ans=max(ans,dfs(i));
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 8576
def cin():  return list(map(int,input().split()))

def alpha2num(alpha):
    num = 0
    for index, item in enumerate(list(alpha)):  num += pow(26, len(alpha) - index - 1) * (ord(item) - ord('a') + 1)
    return num

def rol_hash(l):

    b, h = 1007, 10 ** 9 + 9
    base = pow(b, l, h)
    hash_s = 0
    dic = {}
    for i in range(l):  hash_s = (hash_s * b + alpha2num(S[i])) % h
    dic[hash_s] = l - 1
    for i in range(1, N - l + 1):
        hash_s = (hash_s * b - base * alpha2num(S[i - 1]) + alpha2num(S[i + l - 1])) % h
        if hash_s in dic:
            if S[dic[hash_s] - l + 1:dic[hash_s] + 1] == S[i:i + l] and dic[hash_s] < i:  return 1
        else:  dic[hash_s] = i + l - 1
    return 0

def is_ok(mid):  return rol_hash(mid)

def binary_search(left, right):
    while (abs(right - left) > 1):
        mid = (left + right) // 2
        if is_ok(mid):  right = mid
        else:  left = mid
    return right

N = cin()[0]
S = input()

left = N + 1
right = -1
ret = binary_search(left, right)
if ret == right:  print(0)
else:  print(ret)

Measured memory_bytes: 75164
#include<iostream>
using namespace std;
int main()
{
	int n,maxx=0,ms=0;
	char s[103];
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
	}
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='I'){
			ms++;
			if(ms>maxx) maxx=ms;
		}
		if(s[i]=='D') ms--;
	}
	cout<<maxx<<endl;
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,ans,a,b;
	scanf("%d",&n);
	m=n%1000;
	ans=n/1000;
	if(m==0)
	printf("0\n");
	else
	{
		b=(ans+1)*1000-n;
		printf("%d",b);
	}
}

Measured memory_bytes: 3824
s = input() + 'L'
a = []
b = []
c = [0]*(len(s)-1)

chflag = 0
tmp = []
for i in range(len(s)-1):
    if chflag <= 1:
        tmp.append(s[i])
    elif chflag == 2:
        a.append(tmp)
        tmp = [s[i]]
        chflag = 0
    if s[i] != s[i+1]:
        chflag += 1
        if chflag == 1:
            b.append(i)
a.append(tmp)

for l,idx in zip(a,b):
    nr = l.count("R")
    nl = l.count("L")
    c[idx] = int(nr/2) + nr%2 + int(nl/2)
    c[idx+1] = int(nl/2) + nl%2 + int(nr/2)

print(" ".join(map(str, c)))

Measured memory_bytes: 18340
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <fstream>
#include <bitset>
#include <array>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define erep(i, n) for (int i = 0; i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define clr(a, x) memset(a, x, sizeof(a))
#define sz(a) ((int)(a).size())
#define mp(a, b) make_pair(a, b)
#define ten(n) ((long long)(1e##n))

const int INF = -1;

typedef long long ll;
typedef pair<int, int> pii;

int n;
ll a[101], ans, r;

ll dp[101][21];

int main() {
    cin >> n;
    rep(i,n) cin >> a[i];

    dp[0][a[0]] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= 20; ++j) {
            if (j + a[i] <= 20) {
                dp[i][j + a[i]] += dp[i-1][j];
            }
            if (j - a[i] >= 0) {
                dp[i][j - a[i]] += dp[i - 1][j];
            }
        }
    }

    cout << dp[n-2][a[n-1]] << endl;

    return 0;
}

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

int main(){

  int MAX = 100200;
  vector<int> is_prime(MAX, 1);
  is_prime[0] = 0, is_prime[1] = 0;
  for (int i = 2; i < MAX; ++i) {
      if (!is_prime[i]) continue;
      for (int j = i*2; j < MAX; j += i) is_prime[j] = 0;
  }

  vector<int> a(MAX, 0);
  for (int i = 0; i < MAX; ++i) {
    if (i % 2 == 0) continue;
    if (is_prime[i] && is_prime[((i+1)/2)]) a[i] = 1;
  }
  // 累積和
  vector<int> s(MAX+1, 0);
  for (int i = 0; i < MAX; ++i) s[i+1] = s[i] + a[i];

    // クエリ処理
    int Q; cin >> Q;
    for (int q = 0; q < Q; ++q) {
        int l, r;
        cin >> l >> r;
        ++r;
        cout << s[r] - s[l] << endl;
    }
}

Measured memory_bytes: 4544
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
    
using namespace std;    
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

int main(){

    ll N, H;
    cin >> N >> H;

    vector<ll> a(N);
    vector<ll> b(N);
    for(ll i = 0; i < N; i++){
        cin >> a[i];
        cin >> b[i];
    }

    sort(rall(a));
    sort(rall(b));

    ll ans = 0;
    for(int i = 0; i < N; i++){
        if(b[i] > a[0]){
            ans ++;
            H -= b[i];
            if(H <= 0){
                cout << ans << endl;
                return 0;
            }
        }
        else{
            break;
        }
    }

    if(H % a[0] == 0) cout << ans + H / a[0] << endl;
    else cout << ans + H / a[0] + 1 << endl;

}

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

ll n;

int main() {
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> n;
    vector<pair<ll, ll>> a(n);
    for (auto& i : a) cin >> i.first >> i.second;

    ll tv = a[0].first, av = a[0].second;
    for (ll i = 1; i < n; ++i) {
        ll tt = ceil((long double)tv / a[i].first), at = ceil((long double)av / a[i].second);
        ll times = max(tt, at);
        tv = a[i].first * times, av = a[i].second * times;
    }

    cout << tv + av;
}


Measured memory_bytes: 3624
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;

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



	int n,x = 0,k=-2000; char c[105]; cin >> n;
	for (int i = 0; i < n; i++){
		cin >> c[i];
		if (c[i] == 'I') x++;
		if (c[i] == 'D')x--;
		if (x > k)
			k = x;
	} 
	if (k> 0)
		cout << k << endl;
	else 
		cout << 0 << endl;
		return 0;
	
}


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

int main(){
	string str;
	cin >> str;
	int len = str.size();
	if(len < 6) cout << "INVALID" << endl;
	else {
		int f1=0,f2=0,f3=0;
		for(int i=0;i<len;i++){
			if(str[i] >= '0' && str[i] <= '9') f1=1;
			else if(str[i] >= 'A' && str[i] <= 'Z') f2=1;
			else f3=1;
		}
		if(f1 && f2 && f3) cout << "VALID" << endl;
		else cout << "INVALID" << endl;
	}
}

Measured memory_bytes: 1180
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

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

n = int(input())
a = LI()
ans = [0]*n
for i in a:
    ans[i-1] += 1
for i in ans:
    print(i)

Measured memory_bytes: 30952
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define all(x) (x.begin()),(x.end())
#define allr(x) (x.rbegin()),(x.rend())
#define sz(x)  ((ll)x.size())
#define FAST_IO ios_base :: sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
using namespace std;
#ifdef LOCAL
#include "uj.h"
#endif


void tokenize(string str,const char delim,vector<string> & res){
	stringstream p(str);
	string token;
	while(getline(p,token,delim)){
		res.push_back(token);
	}
	return;
}
// Your workSpace ...
int n ;
const int maxn = 1e5+100;

void test_case(){
  	cin>>n;
  	vector<int> a(n),b(n),c(n);
  	for(int i = 0;i<n;++i)
  	    cin>>a[i]>>b[i]>>c[i];
  	int dp[maxn][3];
  	dp[0][0] = a[0],dp[0][1] =  b[0],dp[0][2] = c[0];
  	for(int i = 1;i<n;++i){
  	    dp[i][0] = a[i] + max(dp[i-1][1],dp[i-1][2]);
  	    dp[i][1] = b[i] + max(dp[i-1][0],dp[i-1][2]);
  	    dp[i][2] = c[i] + max(dp[i-1][0],dp[i-1][1]);
  	}
  	cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<endl;
  	return;
}




int main(){
	FAST_IO;
	int tt ;
	tt = 1;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
    cin>>tt;
#endif
	for(int i = 0;i<tt;++i)
	    test_case();
#ifndef ONLINE_JUDGE
 	cerr << "Running Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}

Measured memory_bytes: 5540
n = int(input())
a_list = list(map(int,input().split()))
b = 0
for i in range(n):
    if a_list[i]%2 == 0:
        if a_list[i]%5 != 0 and a_list[i]%3 != 0:
            b = 1
            break
if b == 1:
    print("DENIED")
else:
    print("APPROVED")

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
 
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define loop(i, l, r) for(int i = l; i < r; i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vec_i;
typedef vector<ll> vec_ll;

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
const int INF = 1e9;
const int MOD = 1e9+7;

int main()
{
	int n, W;
	cin >> n >> W;

	vec_ll dp[2];
	dp[0] = vec_ll(W+1, 0);
	dp[1] = vec_ll(W+1, 0);

	int pos = 0;
	rep(i, n){
		ll w, v;
		cin >> w >> v;
		dp[1-pos][w] = max(dp[1-pos][w], v);
		rep(j, W){
			if(dp[pos][j] != 0 && j + w <= W){
				dp[1-pos][j+w] = max(dp[pos][j+w], dp[pos][j] + v);
			}
			dp[1-pos][j] = max(dp[1-pos][j], dp[pos][j]);
		}
		pos = 1 - pos;
	}

	ll ans = 0;
	rep(i, W+1){
		if(ans < dp[pos][i]){
			ans = dp[pos][i];
		}
	}
	cout << ans << endl;
}

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,ans = 0;
    cin >> n;
    vector<pair<int,int>> r(n),b(n);
    for(int i = 0;i < n;i ++){
        cin >> r[i].second >> r[i].first;
    }
    for(int i = 0;i < n;i ++){
        cin >> b[i].first >> b[i].second;
    }
    sort(r.begin(),r.end());
    sort(b.begin(),b.end());
    reverse(r.begin(),r.end());
    map<int,bool> m;
    for(int i = 0;i < n;i ++){
        for(int j = 0;j < n;j ++){
            if(m[j]) continue;
            if(r[j].first < b[i].second && r[j].second < b[i].first){
                ans ++;
                m[j] = true;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256