akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#define ll long long
#define MAX_N 100000
using namespace std;

ll a, b;
vector<ll> ans;

ll euclidean_gcd(ll a, ll b)
{
    return b != 0 ? euclidean_gcd(b, a % b) : a;
}

vector<ll> prime_factorize(ll N)
{
    vector<ll> res;
    for (ll a = 2; a * a <= N; ++a)
    {
        if (N % a != 0)
            continue;
        // 割れる限り割り続ける
        while (N % a == 0)
        {
            N /= a;
        }

        // その結果を push
        res.push_back(a);
    }

    // 最後に残った数について
    if (N != 1)
        res.push_back(N);
    return res;
}

void solve()
{
    ll n = euclidean_gcd(a, b);

    vector<ll> divs = prime_factorize(n);
    divs.push_back(1); // 1は答えに含まれる

    /*
    for (int i = 0; i < divs.size(); i++)
    {
        cout << divs[i] << " ";
    }
    */
    cout << divs.size();
}

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

    solve();
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
49min 40sec
"""
# 0番目の頂点から各頂点までの距離を求めて、
# その距離の偶奇を判定すればよいだろう。
# 木だから頂点同士の距離は1通りしかない。

def main():
    N = int(input())
    edge_list = [list(map(int, input().split()))  for i in range(N-1)]

    # 頂点uから頂点vに距離wの辺があることを、
    # 隣接リストadj_listのu番目の要素に[v, w]があることとして書く。
    # 今距離wは偶奇しか興味が無いので、w%2に置き換える。
    # 頂点の番号は、入力では1インデックスなので、0インデックスに変える。
    # 無向グラフなので、両向きとも入力する。
    adj_list = [[] for i in range(N)]
    for edge in edge_list:
        adj_list[edge[0]-1].append([edge[1]-1, edge[2]%2])
        adj_list[edge[1]-1].append([edge[0]-1, edge[2]%2])

    # 各頂点の頂点0からの距離のリスト
    INF = 2
    distance_list = [ INF for i in range(N)]
    distance_list[0] = 0

    # dfsのためのスタック
    dfs_list = [0]

    # dfs
    while dfs_list:
        now_node = dfs_list.pop(-1)
        now_dist = distance_list[now_node]
        for edge in adj_list[now_node]:
            if distance_list[edge[0]] == INF:
                distance_list[edge[0]] = (now_dist+edge[1])%2
                dfs_list.append(edge[0])
    
    # 答えの出力
    for dist in distance_list:
        print(dist)
    return

if __name__ == "__main__":
    main()



Measured memory_bytes: 65648
#include<iostream>
#include<vector>
using Int = long long;

int main() {

	Int N;
	std::cin >> N;

	std::vector<Int> a(N);
	for (int i = 0; i < N; i++) std::cin >> a[i];

	Int res = 0;
	for (int i = 0; i < N; i++)	if (a[i] % 2)res++;
	
	std::cout << (res % 2 ? "NO" : "YES") << std::endl;

}

Measured memory_bytes: 1024
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a) memset((a), 0, sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF (3e15)

using namespace std;

int N, A[100005];

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

    cin >> N;
    REP(i, N)
    {
        cin >> A[i];
    }

    map<int, int> count;
    REP(i, N)
    {
        count[A[i]]++;
    }

    int u = 0;
    int d = 0;
    for (auto kv : count)
    {
        u++;
        if (kv.second > 1)
            d += kv.second - 1;
    }
    if (d % 2 != 0)
        --u;
    cout << u << endl;

    return 0;
}


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

int main(){
  ll k;
  string s;
  cin>>k>>s;
  if(s.size()<=k){
    cout<<s<<endl;
  }
  else {
    string sub=s.substr(0,k);
    cout<<sub<<"..."<<endl;
  }
}

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

using ll=long long;

int main(){
    int n;
    cin>>n;
    vector<ll> a(n),b(n);
    for(int i=0;i<n;i++) cin>>a[i]>>b[i];
    vector<pair<ll,pair<int,int>>> com(2*n);
    for(int i=0;i<n;i++){
        com[i]=make_pair(a[i],make_pair(0,i));
    }
    for(int i=0;i<n;i++){
        com[n+i]=make_pair(b[i],make_pair(1,i));
    }
    
    //cerr<<"#"<<endl;
    sort(com.begin(),com.end());
    //cerr<<"#"<<endl;
    vector<int> amp(n),bmp(n);
    for(int i=0;i<2*n;i++){
        if(com[i].second.first==0) amp[com[i].second.second]=i;
        else{
            bmp[com[i].second.second]=i;
        }
    }
    
    //cerr<<"#"<<endl;
    ll asum=0;
    ll bsum=accumulate(b.begin(),b.end(),0LL);
    ll res=min(accumulate(a.begin(),a.end(),0LL),bsum);
    ll sum=0;
    for(int i=0;i<n;i++){
        sum+=com[i].first;
    }
    for(int i=0;i<n;i++){
        //cerr<<i<<endl;
        int idx=n;
        ll sc=sum;
        if(amp[i]<idx){
            sc+=com[idx].first-a[i];
            idx++;
            amp[i]=1e8;
        }
        if(bmp[i]<idx){
            sc+=com[idx].first-b[i];
            idx++;
        }
        if(amp[i]<idx){
            sc+=com[idx].first-a[i];
            idx++;
            amp[i]=1e8;
        }
        //cerr<<sc<<" "<<sum<<" "<<idx<<endl;
        res=min(res,sc);        
    }
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 5760
#include <stdio.h>


int main(){

  long i;
  long n, q;
  long S[100001], T[50001];
  long mc; //matchCounter
  long ps, pe; //pointStart, pointEnd
  long cp; //checkPoint

  // input
  scanf( "%ld", &n );

  for( i=0; i<n; i++ )
    scanf( "%ld", &S[i] );

  scanf( "%ld", &q );
  
  for( i=0; i<q; i++ )
    scanf( "%ld", &T[i] );

  // binary search
  mc=0;
  for( i=0; i<q; i++ ){

    // case 1
    if( T[i] > S[n-1] ) continue;

    // case 2
    ps = 0; pe = n;
    while( ps <= pe ){
      cp = ps + (pe - ps) / 2;
      if( T[i] == S[cp]){ 
        mc++;
        break;
      }
      if( T[i] < S[cp]) pe = cp-1;
      if( T[i] > S[cp]) ps = cp+1;
    }
  }

  // result
  printf( "%ld\n", mc );

  return 0;
}



Measured memory_bytes: 2848
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
#define w(x) int x;cin>>x;while(x--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vll vector<ll>
#define ppi pair<Sint,int>
#define ppl pair<ll,ll>
#define F first
#define S second 
#define LB lower_bound
#define UB upper_bound
#define mset multiset
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll binpow(ll x, ll y, ll p){  ll res = 1;x = x % p;if (x == 0)return 0;while (y > 0)  { if (y & 1) res = (res*x) % p; y = y>>1;x = (x*x) % p;}return res;}  
ll gcd(ll a, ll b){ if (b == 0) return a; return gcd(b, a % b); } 
bool parity(ll x,ll y){ bool f = ((x ^ y) < 0);return !f;}


int main()
{
    IOS

    ll n,m;
    cin>>n>>m;
    string s[n];
    
    for(int i=0;i<n;i++)
        cin>>s[i];
    

    ll dp[n][m];
    dp[0][0]=1;
    for(int i=1;i<m;i++)
    {
        if(s[0][i]=='.')
            dp[0][i]=dp[0][i-1];
        else
            dp[0][i]=0;
    }
    
    for(int i=1;i<n;i++)
    {
        if(s[i][0]=='.')
            dp[i][0]=dp[i-1][0];
        else
            dp[i][0]=0;
    }

    for(int i=1;i<n;i++)
    {
        for(int j=1;j<m;j++)
        {
            if(s[i][j]=='.')
                dp[i][j]=dp[i-1][j]%mod+dp[i][j-1]%mod;
            else
                dp[i][j]=0;
                
            dp[i][j]%=mod;
        }
    }    

    cout<<dp[n-1][m-1]%mod;

    return 0;
}

Measured memory_bytes: 9088
#include <string>
#include <iostream>
using namespace std;
int main(void){
    string S,O;
    int i,l;
    O="";
    
    cin >> S ;
    l =  S.length() ;
    //cout << l ;
    for (i=0;i<l;i++){
        O = O + "x";
    }
    cout << O ;
}


Measured memory_bytes: 256
package main

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

type Task struct {
	a int
	b int
}

type Tasks []Task

func (l Tasks) Len() int {
	return len(l)
}

func (l Tasks) Less(i, j int) bool {
	if l[i].b == l[j].b {
		return l[i].a < l[j].a
	}
	return l[i].b < l[j].b
}

func (l Tasks) Swap(i, j int) {
	l[i], l[j] = l[j], l[i]
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	tasks := make(Tasks, n)
	for i := 0; i < n; i++ {
		sc.Scan()
		a, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		b, _ := strconv.Atoi(sc.Text())
		tasks[i] = Task{a, b}
	}

	sort.Sort(tasks)

	time := 0
	for _, t := range tasks {
		time += t.a
		if time > t.b {
			fmt.Println("No")
			return
		}
	}

	fmt.Println("Yes")
}


Measured memory_bytes: 6272
#include<iostream>
using namespace std;
int main(){
  int n;
  int cnt;
  while(1){
    cin>>n;
    if(n==0)break;
    cnt=0;
    while(1){
      if(n==1)break;
      if(n%2==0){
	n=n/2;
	cnt++;
      }
      if(n%2!=0&&n!=1){
	n=n*3+1;
	cnt++;
      }
    }
    cout<<cnt<<endl;
  }
  return 0;
}

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

template <typename T>
bool contains(const vector<T>& vec, const T& item) {
  return std::find(vec.begin(), vec.end(), item) != vec.end();
}

int main() {
  int x, y;
  cin >> x >> y;

  vector<int> a = {1, 3, 5, 7, 8, 10, 12};
  vector<int> b = {4, 6, 9, 11};

  if (x == 2 || y == 2) {
    cout << "No" << endl;
    return 0;
  }

  if (contains(a, x) && contains(a, y)) {
    cout << "Yes" << endl;
    return 0;
  }

  if (contains(b, x) && contains(b, y)) {
    cout << "Yes" << endl;
    return 0;
  }

  cout << "No" << endl;
}


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

using namespace std;

int main(){

	int n;
	cin>>n;
	int i=1;
	while(1){
	int x=i;
	if(x % 3 == 0){
	cout<<" "<<i;
	}
	else{
	while(1){
	if(x % 10 == 3){
	cout<<" "<<i;
	break;}
	x /=10;
	if(x == 0) break;
	}
	}
	
	if(++i>n) break;

	}
	cout<<endl;

		
	return 0;
}


Measured memory_bytes: 3092
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
struct node{
    int key;
    node* parent,*left,*right;
};
node *root=NULL;
node * pre;
void Insert(int key){
    node * temp=new node;
    temp->key=key;
    temp->left=NULL;
    temp->right=NULL;

    if(root==NULL){
        root=temp;
        return ;
    }
    else{
        pre=root;
        while(1){
            if (key<pre->key){
                if (pre->left==NULL){
                    pre->left=temp;
                    temp->parent=pre;
                    return;
                }
                else
                    pre=pre->left;
            }
            else if(key > pre->key){
                if (pre->right==NULL){
                    pre->right=temp;
                    temp->parent=pre;
                    return;
                }
                else
                    pre=pre->right;
            }
            else
                return;
        }
    }
}
void Print_in(node* r){
    if(r->left!=NULL){
        Print_in(r->left);
    }
    cout<<" "<<r->key;
    if(r->right!=NULL){
        Print_in(r->right);
    }

}
void Print_pre(node *r){
    cout<<" "<<r->key;
    if(r->left!=NULL){
        Print_pre(r->left);
    }
    if(r->right!=NULL){
        Print_pre(r->right);
    }
}
void Print(node * r){
    Print_in(r);
    cout<<endl;
    Print_pre(r);
    cout<<endl;
}
int Find(node *r,int key){
        pre=r;
        while(1){
            if (key<pre->key){
                if (pre->left==NULL){
                    return 0;
                }
                else
                    pre=pre->left;
            }
            else if(key > pre->key){
                if (pre->right==NULL){
                    return 0;
                }
                else
                    pre=pre->right;
            }
            else
                return 1;
        }
}
int main(){
    int n;
    string cmd;
    int key;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>cmd;
        if(cmd[0]=='i'){
            cin>>key;
            Insert(key);
        }
        else if(cmd[0]=='p'){
            Print(root);
        }
        else if(cmd[0]=='f'){
            cin>>key;
            int re=Find(root,key);
            if(re==0)
                cout<<"no"<<endl;
            else
                cout<<"yes"<<endl;
        }
    }
    return 0;
}



Measured memory_bytes: 21916
#include <iostream>

using namespace std;

const int N = 1e2 + 10;

int n, a[N];

struct card
{
    char suit, value;
};

void bubble(struct card a[], int n)
{
    for(int i = 0; i < n; i++)
    {
        for(int j = n - 1; j >= i + 1; j--)
        {
            if(a[j].value < a[j - 1].value) swap(a[j], a[j - 1]);
        }
    }
}

void selection(struct card a[], int n)
{
    for(int i = 0; i < n; i++)
    {
        int minj = i;
        for(int j = i; j < n; j++)
        {
            if(a[j].value < a[minj].value) minj = j;
        }
        swap(a[i], a[minj]);
    }
}

void print(struct card a[], int n)
{
    for(int i = 0; i < n; i++)
    {
        if(i > 0) cout << ' ';
        cout << a[i].suit << a[i].value;
    }
    cout << endl;
}

bool isstable(struct card c1[], struct card c2[], int n)
{
    for(int i = 0; i < n; i++)
    {
        if(c1[i].suit != c2[i].suit) return false;
    }
    return true;
}

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

    cin >> n;

    card c1[N], c2[N];

    for(int i = 0; i < n; i++) cin >> c1[i].suit >> c1[i].value;

    for(int i = 0; i < n; i++) c2[i] = c1[i];

    bubble(c1, n);
    selection(c2, n);

    print(c1, n);
    cout << "Stable" << endl;

    print(c2, n);
    if(isstable(c1, c2, n))
        cout << "Stable" << endl;
    else
        cout << "Not stable" << endl;

    return 0;
}


Measured memory_bytes: 3204
from sys import stdin
N = stdin.readline().rstrip()

N=str(N)
o=0
if len(N)==4:
    if N[0]=="2": o+=1
    if N[1]=="2": o+=1  
    if N[2]=="2": o+=1  
    if N[3]=="2": o+=1  

print(o)

Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <map>

#define ll long long
#define REP(i,n) for(int i = 0; i < n; i++)
#define PI 3.141592653589
#define MOD 1000000007

using namespace std;

template<typename T> T gcd(T a, T b){return (a % b)? gcd(b, a % b) : b;}
template<typename T> T lcm(T a, T b){return a * b / gcd(a, b);}

int main(void){
    int n;
    cin >> n;
    int h[n];
    REP(i,n) cin >> h[i];

    vector<int> dp(n+5, 0);
    dp[0] = 0;
    dp[1] = fabs(h[1] - h[0]);
    for(int i = 2; i <= n+5; i++){
        dp[i] = min(dp[i-2] + fabs(h[i] - h[i-2]), dp[i-1] + fabs(h[i] - h[i-1]));
    }
    cout << dp[n-1] << endl;
    
    return 0;
}

Measured memory_bytes: 4004
#include<stdio.h>
#include<string.h>

int main()
{
    char str[1201];
    char c;
    int i;
    fgets(str,1200,stdin);
    for(i=0;i<strlen(str);i++){
        c=str[i];
        if((c>='a'&&c<='z')||(c>='A'&&c<='Z')){
            c=c^0x20;
        }
        printf("%c",c);
    }
    return 0;
}


Measured memory_bytes: 2044
import java.util.*;

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

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

        if(X>=t){
            System.out.println(X - t);
        }
        else{
            System.out.println(0);
        }
    }
}

Measured memory_bytes: 21844
#include <iostream>
#include <vector>
using namespace std;
int n;
int k;
vector<int> h(100000);
vector<int> cost(100000);

int ans(int n, int k)
{
    if (cost.at(n) != -1)
        return cost.at(n);
    cost.at(n) = ans(n - 1, k) + abs(h.at(n) - h.at(n - 1));

    for (int i = 2; i <= k; i++)
    {
        cost.at(n) = min(cost.at(n), ans(n - i, k) + abs(h.at(n) - h.at(n - i)));
    }

    return cost.at(n);
}

void init(int k)
{
    cost.at(0) = 0;
    for (int i = 1; i < k; i++)
    {
        cost.at(i) = cost.at(i - 1) + abs(h.at(i) - h.at(i - 1));
        for (int j = 2; j <= i; j++)
        {
            cost.at(i) = min(cost.at(i), cost.at(i - j) + abs(h.at(i) - h.at(i - j)));
        }
    }
}

int main()
{
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> h.at(i);
        cost.at(i) = -1;
    }
    init(k);
    cout << ans(n - 1, k) << endl;
}

Measured memory_bytes: 10368
#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <set>

#define rep(i,n)  for (int i = 0; i < (int)(n); i++)
#define INF 9999999999
#define PI 3.14159265359
using namespace std;

int main()
{
	int a,b;
	cin >> a>>b;
	cout << a*b << endl;
	return 0;
}


Measured memory_bytes: 3164
#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T a){for(auto itr :a){if(itr != *a.begin())cout << " "; cout << itr;} }
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
signed main(){
    int n,m;
    string s,t;
    map<int,int>mp;
    cin >> n >> m;
    vector<int>v(n); erep(e,v) cin >> e;
    sort(all(v));
    int ans = 0;
    rep(i,n){
        if(v[i] <= m and i != n-1) {
            m -= v[i];
            ans++;
        }
        if(i == n-1 and m == v[i]) ans++;
    }
    cout << ans << endl;
}




Measured memory_bytes: 256
def main():
    X = int(input())

    m = 100

    k = 0
    while m < X:
        k += 1
        m += m // 100
    print(k)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok


Measured memory_bytes: 9156
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(arg),key)-begin(arg)
 
using namespace std;
 
string recover(string s){
	int n=s.size();
	
	int na=1,nb=1,nc=1;
	rep(i,n){
		if(i+2<n && s.substr(i,3)=="ABC"){
			i+=2;
			continue;
		}
		if(s[i]=='A') na=0;
		if(s[i]=='B') nb=0;
		if(s[i]=='C') nc=0;
	}
	if(na+nb+nc!=1) return "";
	char nxt;
	if(na) nxt='A';
	if(nb) nxt='B';
	if(nc) nxt='C';
	
	string ns="";
	rep(i,n){
		if(i+2<n && s.substr(i,3)=="ABC")
			ns+=nxt,i+=2;	
		else 
			ns+=s[i];
	}
	//cout << ns << endl;
	return ns;
}
 
 
int main(void){
	string s;
	cin >> s;
	while(s.size()>3) s=recover(s);
	if(s=="ABC")
		puts("Yes");
	else
		puts("No");
	return 0;
}

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

int main(){
    int n; cin >> n;
    vector<int> h(n);
    int mx = 0;
    for(int i = 0; i < n; i++){
        cin >> h.at(i);
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        while(h.at(i) > 0){
            ans++;
            int j;
            for(j = i + 1; j < n; j++){
                if(h.at(j) == 0) break;
            }
            for(int k = i; k < j; k++) h.at(k)--;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

void sort4(int *a){
	int min, minID;
	
	for (int i=0; i<4; i++){
		min = a[i], minID = i;
		for (int j=i+1; j<4; j++){
			if (a[j] < min) min = a[minID=j];
		}
		a[minID] = a[i]; a[i] = min;
	}
}

int main(void){
	int n,l,s,cnt,a[4];
	
	while (scanf("%d",&n), n){
		if (n % 1111 == 0){
			puts("NA");
		} else {
			cnt = 0;
			while (n != 6174){
				for (int j=0; j<4; j++){
					a[j] = n%10; n /= 10;
				}
				sort4(a);
				l = a[0]+10*(a[1]+10*(a[2]+10*a[3]));
				s = a[3]+10*(a[2]+10*(a[1]+10*a[0]));
//				printf("l=%d, s=%d, n=%d\n", l, s, l-s);
				n = l-s;
				cnt++;
			}
			printf("%d\n", cnt);
		}
	}
	
	return 0;
}

Measured memory_bytes: 1036
from fractions import gcd

A, B, C, D = map(int, input().split())

CD_lcm = (C * D) // gcd(C, D)


def divided(a, b, target):
    return b // target - (a - 1) // target


all_num = B - A + 1

div_t1 = divided(A, B, C)
div_t2 = divided(A, B, D)
div_extra = divided(A, B, CD_lcm)

print(all_num - div_t1 - div_t2 + div_extra)


Measured memory_bytes: 5076
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

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

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const int N = 405;
int dp[N][N][N];

int main() {
    int h, w;
    cin >> h >> w;
    VVI a(h, VI(w));
    REP(i,h) REP(j,w){
        a[i][j] = in();
    }
    dp[1][1][0] = a[0][0] + a[1][0] + a[0][1];
    FOR(i,1,h+w-3) REP(xi,h) REP(yi,xi){
        int xj = i - xi;
        int yj = i - yi;
        if (xj < 0 || xj >= w) continue;
        if (yj < 0 || yj >= w) continue;
        if (xi < h - 1 && yi < h - 1){
            chmax(dp[i + 1][xi + 1][yi + 1], dp[i][xi][yi] + a[xi + 1][xj] + a[yi + 1][yj]);
        }
        if (xi < h - 1 && yj < w - 1){
            chmax(dp[i + 1][xi + 1][yi], dp[i][xi][yi] + a[xi + 1][xj] + a[yi][yj + 1]);
        }
        if (xj < w - 1 && yi < h - 1 && xi > yi + 1){
            chmax(dp[i + 1][xi][yi + 1], dp[i][xi][yi] + a[xi][xj + 1] + a[yi + 1][yj]);
        }
        if (xj < w - 1 && yj < w - 1){
            chmax(dp[i + 1][xi][yi], dp[i][xi][yi] + a[xi][xj + 1] + a[yi][yj + 1]);
        }
    }
    int ans = dp[h + w - 3][h - 1][h - 2] + a[h - 1][w - 1];
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 254336
#include <stdio.h>
#include <algorithm>
using namespace std;
int arr[200003];
int dp[200003];

int main()
{
    // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// freopen("input.in", "r", stdin);
	int n; scanf("%d", &n);
	int hit = 0;
	for(int i = 1; i <= n; i++)
		scanf("%d", &arr[i]);
	int res = 0;
	for(int i = 1; i <= n; i++)
	{
		dp[arr[i]] = dp[arr[i]-1]+1;
		res = max(res, dp[arr[i]]);
	}
	printf("%d\n", n-res);
}











Measured memory_bytes: 1792
import sys
sys.setrecursionlimit(10**7)

N = int(input())
color = [-1] * N
G = [[] for _ in range(N)]
for i in range(N-1):
  u, v, w = map(int, input().split())
  G[u-1].append((v-1, w))
  G[v-1].append((u-1, w))

def dfs(v, cur):
  color[v] = cur
  for next_v, w in G[v]:
    if color[next_v] != -1:
      continue
    if w % 2 == 0:
      dfs(next_v, cur)
    else:
      dfs(next_v, 1 - cur)
      
dfs(0, 0)
for i in range(N):
  print(color[i])

Measured memory_bytes: 79408
// May this submission get accepted!

#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define STEP(i, is, ie, step) for (long long i=(is), i##_end=(ie), i##_step = (step); i<=i##_end; i+=i##_step)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return true;} return false; }
template<class T> bool chmin(T &a, const T &b) {if (a > b) {a = b; return true;} return false; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) do { cerr << "[DEBUG] " #q ": ["; REP(i, (q).size()) { cerr << (q)[i] << (i == i_len-1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; } while (false)
template<class T> T gcd(T a, T b) { if (a < b) std::swap(a, b); while (b) std::swap(a %= b, b); return a; }
template<class T> T lcm(const T a, const T b) { return a / gcd(a, b) * b; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
#define DANCE_ long
#define ROBOT_ unsigned
#define HUMAN_ signed
#define CHOKUDAI_ const
using  ll = DANCE_ HUMAN_ DANCE_;
using ull = DANCE_ ROBOT_ DANCE_;
using cll = DANCE_ DANCE_ CHOKUDAI_;
using  ld = long double;
using namespace std;

// モジュール

// ランレングス圧縮 O(N)
template <class RandomAccessIterator>
vector<ll> run_length(RandomAccessIterator first, RandomAccessIterator last) {
    vector<ll> rl;
    for (RandomAccessIterator itr = first; itr != last; ) {
        RandomAccessIterator jtr = itr++;
        while ((itr != last && *itr == *(itr-1))) itr++;
        rl.push_back(itr - jtr);
    }
    return rl;
}

// 処理内容
int main() {
    
    // インタラクティブ問題では除去した方がいいかも
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s; cin >> s;
    ll n = s.size();

    vector<ll> srl = run_length(ALL_OF(s));
    ll ib = 0;

    ll ans = 0;

    if (s.front() == '>') {
        ans += srl.front() * (srl.front() + 1) / 2;
        ib = 1;
    }

    if (s.back() == '<') {
        ans += srl.back() * (srl.back() + 1) / 2;
        srl.pop_back();
    }
    
    RANGE(i, ib, (ll)srl.size()-1) {
        ll mi = min(srl[i], srl[i+1]);
        ll ma = max(srl[i], srl[i+1]);
        ans += ma * (ma + 1) / 2;
        ans += mi * (mi - 1) / 2;
        i++;
    }
    
    cout << ans << endl;
    
}

Measured memory_bytes: 3352
#[allow(unused_imports)]
use {
    itertools::Itertools,
    proconio::{fastout, input, marker::*},
    std::cmp::*,
    std::collections::*,
    std::io::Write,
    std::ops::*,
};

#[allow(unused_macros)]
macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; }

const N: usize = 35;

#[fastout]
fn main() {
    input! {
        n: usize,
        xy: [(i64, i64); n]
    }
    let m = (xy[0].0 + xy[0].1).rem_euclid(2);
    for &(x, y) in xy.iter() {
        if (x + y).rem_euclid(2) != m {
            println!("-1");
            return;
        }
    }
    let d = (0..N).map(|i| 1i64 << i).collect::<Vec<_>>();
    if m == 1 {
        println!("{}", N);
    } else {
        println!("{}", N + 1);
        print!("1 ");
    }
    println!("{}", d.iter().format(" "));
    for &(x, y) in xy.iter() {
        let mut u = x - y;
        let mut v = x + y;
        if m == 0 {
            u -= 1;
            v -= 1;
            print!("R");
        }
        let mut xs = vec![false; N];
        u += 1 << N;
        u -= 1;
        u /= 2;
        while u != 0 {
            xs[u.trailing_zeros() as usize] = true;
            u &= u - 1;
        }
        let mut ys = vec![false; N];
        v += 1 << N;
        v -= 1;
        v /= 2;
        while v != 0 {
            ys[v.trailing_zeros() as usize] = true;
            v &= v - 1;
        }
        println!(
            "{}",
            xs.iter()
                .zip(ys.iter())
                .map(|(&u, &v)| {
                    if u && v {
                        "R"
                    } else if !u && !v {
                        "L"
                    } else if u && !v {
                        "D"
                    } else {
                        "U"
                    }
                })
                .format("")
        );
    }
}


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

vector<int> costs;
vector< vector<int> > algo;

  int n, m, k;

int func(int x, vector<int> score, int cost = 0) {
  bool flag = true;
  for (int i= 0; i < m; i++) {
    if (score[i] < k) {
      flag = false;
      break;
    }
  }
  if (flag) {
    return cost;
  }
  else if (x >= n) {
    return INT_MAX;
  } 
  else {
    vector<int> score_i;
    score_i = score;
    for (int i = 0; i < m; i++) {
      score_i[i] += algo[x][i];
    }
    return min(func(x+1, score, cost), func(x+1, score_i, cost+costs[x]));
  }
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
  #endif

  int n;
  cin >> n;
  long long k;
  cin >> k;

  int a[n+1];
  for (int i = 1; i <= n; i++)
    cin >> a[i];


  int cycles[n+1] = {0};
  
  map<int, bool> visited;
  int node = 1;
  visited[1] = true;
  vector<int> path;
  path.push_back(1);
  int nodex = 1;
  while (true) {
    node = a[node];
    if (visited.count(node) == 0)
      visited[node] = true;
    else {
      nodex = node;
      break;
    }
    path.push_back(node);
  }

  // for (int i = 0; i < path.size(); i++) {
  //   cout << path[i] << " ";
  // }
  // cout << endl;

  int cycle_start = 0;
  for (int i = 0; i < path.size(); i++) {
    if (path[i] == nodex) {
      cycle_start = i;
      break;
    }
  }
  long long xk = k;
  if (xk >= cycle_start)
    xk -= cycle_start;
  else
    cycle_start = 0;
  // cout << xk << endl;
  xk = (xk%(path.size()-cycle_start));
  cout << path[cycle_start+xk] << endl;

  return 0;
}

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

int main() {
  int K;
  cin >> K;
  
  vector<int> V = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  
  cout << V.at(K-1) << endl;
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#include <string>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string S;
    int count = 0;
    cin >> S;
    if (S[0] == 'o') ++count;
    if (S[1] == 'o') ++count;
    if (S[2] == 'o') ++count;
    cout << (700 + 100 * count) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#define REP(i, a, n) for(int i = ((int) a); i < ((int) n); i++)
using namespace std;

struct state { int ly, lx, ry, rx; };

int W, H, SLY, SLX, SRY, SRX;
char S[2][50][50];
bool visited[50][50][50][50];
int dd[5] = { 0, 1, 0, -1, 0 };

bool isin(int y, int x) {
  return 0 <= y && y < H && 0 <= x && x < W;
}

int main(void) {
  while(cin >> W >> H, W || H) {
    REP(i, 0, H) {
      cin >> S[0][i];
      cin >> S[1][i];
      REP(j, 0, W) if(S[0][i][j] == 'L') SLY = i, SLX = j;
      REP(j, 0, W) if(S[1][i][j] == 'R') SRY = i, SRX = j;
    }

    REP(i, 0, 50) REP(j, 0, 50) REP(k, 0, 50) REP(l, 0, 50) visited[i][j][k][l] = false;

    queue<state> q;
    q.push((state) { SLY, SLX, SRY, SRX });

    int ans = -1;
    while(q.size()) {
      state c = q.front();
      q.pop();

      if(visited[c.ly][c.lx][c.ry][c.rx]) continue;
      visited[c.ly][c.lx][c.ry][c.rx] = true;

      bool f1 = S[0][c.ly][c.lx] == '%';
      bool f2 = S[1][c.ry][c.rx] == '%';
      if((!f1 && f2) || (f1 && !f2)) continue;
      if(f1 && f2) {
        ans = 0;
        break;
      }

      REP(i, 0, 4) {
        state n = (state) { c.ly + dd[i], c.lx + dd[i + 1], c.ry + dd[i], c.rx - dd[i + 1] };
        bool ok1 = isin(n.ly, n.lx) && S[0][n.ly][n.lx] != '#';
        bool ok2 = isin(n.ry, n.rx) && S[1][n.ry][n.rx] != '#';
        if(ok1 && ok2) q.push(n);
        if(ok1 && !ok2) q.push((state) { n.ly, n.lx, c.ry, c.rx });
        if(!ok1 && ok2) q.push((state) { c.ly, c.lx, n.ry, n.rx });
      }
    }

    if(ans == -1) cout << "No" << endl;
    else cout << "Yes" << endl;
  }
  return 0;
}

Measured memory_bytes: 12488
# # Make IO faster
# import sys
# input = sys.stdin.readline

# # get single (or) multiple str
# X = input()

# # get single int
# N = int(input())
# # get multiple int (e.g., 2)
# X, Y = map(int, input().split())
# # get multiple int (e.g., 2) for N lines
# XY = [list(map(int, input().split())) for _ in range(N)]

# from IPython import embed; embed(); exit();

# 全部入り
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
a = sorted(MAP())
print(a[-1] - a[0])


Measured memory_bytes: 27280
n=int(input())

a=0
w=0
t=0
r=0

for i in range(n):
  s=str(input())
  if s=="AC":
    a+=1
  elif s=="WA":
    w+=1
  elif s=="TLE":
    t+=1
  else:
    r+=1


print("AC x",a)
print("WA x",w)
print("TLE x",t)
print("RE x",r)

Measured memory_bytes: 69848
#include <bits/stdc++.h>
using namespace std;
int main(){
  string t;
  cin >> t;
  for (int i = 0; i < t.size(); i++) {
    if (t[i] == 'P') cout << "P";
    else cout << "D";
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 3752
#!/usr/bin/env python3
import sys


def solve(N: int, S: str):
    rest_r = []
    rest_g = []
    rest_b = []

    c_r = 0
    c_g = 0
    c_b = 0

    i_r = []
    i_g = []
    i_b = []

    for i in range(N-1, -1, -1):
        if S[i] == 'R':
            c_r+=1
            i_r.append(i)
        if S[i] == 'G':
            c_g+=1
            i_g.append(i)
        if S[i] == 'B':
            c_b+=1
            i_b.append(i)
        rest_r.append(c_r)
        rest_g.append(c_g)
        rest_b.append(c_b)

    rest_r.reverse()
    rest_g.reverse()
    rest_b.reverse()

    i_r.reverse()
    i_g.reverse()
    i_b.reverse()

    sum = 0

    # r, g, b
    for r in i_r:
        for g in i_g:
            i_max = max(r, g)
            sum += rest_b[i_max]
            i = i_max + abs(g - r)
            if i < N and S[i] == 'B':
                sum -= 1
    for r in i_r:
        for g in i_b:
            i_max = max(r, g)
            sum += rest_g[i_max]
            i = i_max + abs(g - r)
            if i < N and S[i] == 'G':
                sum -= 1

    for r in i_g:
        for g in i_b:
            i_max = max(r, g)
            sum += rest_r[i_max]
            i = i_max + abs(g - r)
            if i < N and S[i] == 'R':
                sum -= 1

    print(sum)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9528
def main():
    K, N = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    ans = K
    less = max(A[i+1] - A[i] for i in range(N-1))
    less = max(less, A[0] + K - A[-1])
    print(ans - less)


if __name__ == '__main__':
    main()


Measured memory_bytes: 78284
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
int main() {
  vector<vector<int>> grid(3, vector<int>(3));
  rep(i,3){
    rep(j,3) cin >> grid[i][j];
  }
  bool ok = true;
  if(grid[0][0]-grid[0][1]!=grid[1][0]-grid[1][1] || grid[1][0]-grid[1][1]!=grid[2][0]-grid[2][1]){
    ok = false;
  }
  if(grid[0][2]-grid[0][1]!=grid[1][2]-grid[1][1] || grid[1][2]-grid[1][1]!=grid[2][2]-grid[2][1]){
    ok = false;
  }
  if(ok) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
a,b,c,d,e,k=io.read("n","n","n","n","n","n","n")
t={a,b,c,d,e}
for i=1,#t-1 do
	for j=i+1,#t do
		if t[j]-t[i]>k then
			print(":(")
			return
		end
	end
end
print("Yay!")

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long N;
  cin >>N;
  long long ans=0;
  vector<int> C(N,0);
  for(int i=0; i<N; i++){
    int c;
    cin >>c;
    C[i]=c;
  }
  if(N==1){
    ans+=C[0];
    ans*=2;
    ans%=1000000007;
    cout <<ans <<endl;
    return 0;
  }
  sort(C.begin(), C.end());
  for(int i=0; i<N; i++){
    ans+=(N+1-i)*C[i];
    ans%=1000000007;    
  }
  for(int i=2; i<N; i++){
    ans*=2;
    ans%=1000000007;    
  }  
  for(int i=0; i<N; i++){
    ans*=2;
    ans%=1000000007;    
  }
  cout <<ans <<endl;
}


Measured memory_bytes: 1024
#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(){
    int N;
    cin>>N;
    bool ans=false;
    if(N%10==7)ans=true;
    N/=10;
    if(N%10==7)ans=true;
    N/=10;
    if(N%10==7)ans=true;
    cout<<(ans?"Yes":"No")<<endl;
}


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

long long n, a[200010], ans = 0;
int main() {
	scanf("%lld", &n);
	for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
	if(a[0]) return !printf("-1");
	a[n] = a[n-1];
	for(int i = 1; i <= n; i++) {
		if(a[i] - a[i-1] > 1) return !printf("-1");
		if(a[i] <= a[i-1]) ans += a[i-1];
	}
	printf("%lld", ans);
}

Measured memory_bytes: 1792
a, b, c, d = map(int, input().split())

while a or c > 0:
        aoki_hitpoint = c - b
        if aoki_hitpoint <= 0:
            c = 0
            print('Yes')
            exit()
        else:
            c = aoki_hitpoint

        takahash_hitpoint = a - d
        if takahash_hitpoint <= 0:
            a = 0
            print('No')
            exit()
        else:
            a = takahash_hitpoint


Measured memory_bytes: 9040
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
#define TO(x,t,f) ((x)?(t):(f))
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define FILV(x,a) fill(x.begin(),x.end(),a)
#define FILA(ar,N,a) fill(ar,ar+N,a)
#define NEXTP(x) next_permutation(x.begin(),x.end())
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define pb push_back
#define pri(aa) cout<<(aa)<<endl
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
const ll INF=1e9+7;
const ll N = 1002;

ll a,b;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>a>>b;
	ll ans=0;
	FOR(i,0,b-a){
		ans+=i;
	}
	ans-=a;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int M = 1000000;
bool prime[1000000+1];
void sieve(){
  for(int i=0;i<=M;i++){
    prime[i] = true;
  }
  prime[0] = false;
  prime[1] = false;
  for(int i=2;i<=M;i++){
    if(prime[i]){
      for(int j=2*i;j<=M;j+=i) prime[j] = false;
    }
  }
}

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

int main(){
    sieve();

  	ll A, B;
    cin >> A >> B;

    ll g = gcd(A, B);
    ll ans = 0;
    ll range = ll(sqrt(g));


    for(int i=2;i<=range;i++){
      if(prime[i] && g%i==0){
        ans++;
        while(g%i==0) g/=i;
      } 
    }
    if(g!=1) ans++;

    cout << ans+1 <<endl;
    
  	return 0;
}



Measured memory_bytes: 1280
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;
typedef complex<ld> com;
constexpr int inf = 1000000000;
constexpr ll INF = 1000000000000000000;
constexpr ld EPS = 1e-12;
constexpr ld PI = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }


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

	int n;
	cin >> n;
	vector<ll> a(n), b(n);
	rep(i, n) {
		cin >> a[i];
		b[i] = a[i] - i - 1;
	}
	sort(all(b));
	ll mid = b[n / 2];
	ll ans = 0;
	rep(i, n) ans += abs(b[i] - mid);
	cout << ans << '\n';
}

Measured memory_bytes: 3328
N = int(input())
A = list(map(int,input().split()))
A = A[::-1]
x = sum(A) - A[0]
y = A[0]
ans = abs(x - y)
for i in range(1,N - 1):
    y += A[i]
    x -= A[i]
    tmp_ans = abs(x - y)
    if tmp_ans < ans:
        ans = tmp_ans
print(ans)


Measured memory_bytes: 24832
h1,m1,h2,m2,k = map(int, input().split())
if m2-m1 < 0:
    h2 -= 1
    m2 += 60
    x = (h2-h1)*60+m2-m1
    print(x-k)
else:
    x = (h2-h1)*60+m2-m1
    print(x-k)

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

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define int long long
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;

signed main(){
    int x;
    cin >> x;
    if(x < 1200) cout << "ABC\n";
    else cout << "ARC\n";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)


int main(){
    int n,k;
    cin >> n >> k;
    if(n<=10){
        int m = 0;
        cout << m << endl;
        int cnt = 0;
        while(1){
            string s;
            
            for(int i=1;i<=n;i++){
                cout << i << endl;
                cin >> s;
                if(s=="Yes"){
                    cnt++;
                    if(cnt==k)break;
                }
            }
            if(cnt==k)break;
        }
    }else{
        vector<pair<int,int> > g;
        for(int i=10;i<=n;i++){
            int bit = i-10;
            for(int j=1;j<=9;j++){
                if((bit>>(j-1))&1){
                    g.push_back(MP(j,i));
                }
            }
        }
        cout << g.size() << endl;
        rep(i,g.size()){
            cout << g[i].first << " " << g[i].second << endl;
        }
        rep(zz,k){
            int ans = 10;
            string s;
            for(int i=1;i<=9;i++){
                cout << i << endl;
                cin >> s;
                if(s=="Yes"){
                    break;
                }else if(s=="Near"){
                    ans += 1<<(i-1);
                }
            }
            if(s=="Yes")continue;
            cout << ans << endl;
            cin >> s;
        }
    }


    return 0;
}


Measured memory_bytes: 3308
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

#define maxN 100011

int n, i;
char s[maxN];
int sum[maxN], best[maxN];

void check(char c) {
    int i;

    for (i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + (s[i] == c ? 1 : -1);
        best[i] = min(best[i - 1], sum[i]);

        if (i >= 2) {
            if (best[i - 2] < sum[i]) {

                for (int j = 0; j <= i - 2; j++) {
                    if (sum[j] < sum[i]) {
                        printf("%d %d", j + 1, i);
                        exit(0);
                    }
                }

            }
        }
    }
}

int main()
{
   // freopen("test.in","r",stdin);

    scanf("%s", s + 1);
    n = strlen(s + 1);

    for (char c = 'a'; c <= 'z'; c++)
        check(c);

    printf("-1 -1");


    return 0;
}


Measured memory_bytes: 1152
#include "bits/stdc++.h"
using namespace std;

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

    int cnt = 1;
    if (S == 1 || S == 2) {
        cout << 4 << endl;
    }
    else {
        while (true) {
            if (S == 4) {
                break;
            }
            if (S % 2 == 0) {
                S /= 2;
            }
            else {
                S = S * 3 + 1;
            }
            cnt++;
        }
        cout << cnt + 3 << endl;
    }
}

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

int main(){
    string s;
    cin>>s;
    ll ans=0;
    for(ll i=0;i<s.size();i++){
        if(s[i]=='+'){
            ans+=1;
        }else{
            ans-=1;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
cl1 = input().split()
cl2 = input().split()
n = int(cl1[0])
m = int(cl1[1])
cl1 = [int(s) for s in cl1]
cl2 = [int(s) for s in cl2]
sum= 0.0
for i in range(n):
    sum = cl2[i]+ sum
cl2 = sorted(cl2,reverse=True)
if(cl2[m-1] < sum/(4*m)):
    print("No")
else:
    print("Yes")

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

using namespace  std;

int main(){
    int N;
    int K;
    cin >> N >> K;
    vector<int> A(N);
    for(int i=0; i<N; i++){
        cin >> A[i];
    }

    for(int i=K+1; i<=N; i++){
        if(A[i-1-K] < A[i-1]){
            cout << "Yes\n";
        }else{
            cout << "No\n";
        }
    }
    return 0;   
}

Measured memory_bytes: 4004