akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<bitset>
#include<utility>
#include<sstream>
#include<iomanip>
using namespace std;

#define ll long long
#define MP make_pair

int main(void) {

    int n;
    while(1){
        cin>>n;
        if(n==0)break;
        ll a[1000]={},sa=100000000;

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

        for (int i = 1; i < n; i++) {
            sa = min(sa,a[i]-a[i-1]);
        }

        cout<<sa<<"\n";
    }
    
    
    return 0;
}


Measured memory_bytes: 3176
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int N,K;
int C[2000];int G[2000];
int gen[2000];
int mon[10][2001];
int dp[10][2001];
int main()
{
	scanf("%d%d",&N,&K);
	for(int i=0;i<N;i++){
		scanf("%d%d",&C[i],&G[i]);G[i]--;
	}
	int now,sum;
	for(int i=0;i<10;i++){
		now=0;sum=0;
		for(int j=0;j<N;j++){
			if(G[j]==i){
				gen[now]=C[j];
				now++;
			}
		}
		sort(gen,gen+now);
		reverse(gen,gen+now);
		for(int j=1;j<=now;j++){
			sum+=gen[j-1];
			mon[i][j]=sum+j*(j-1);
		}
	}/*
	for(int i=0;i<10;i++){
		printf("%d %d %d %d %d\n",mon[i][0],mon[i][1],mon[i][2],mon[i][3],mon[i][4]);
	}*/
	for(int j=0;j<=2000;j++)dp[0][j]=mon[0][j];
	for(int i=1;i<10;i++){
		for(int j=0;j<=2000;j++){
			for(int k=0;k<=2000-j;k++){
				dp[i][j+k]=max(dp[i][j+k],dp[i-1][j]+mon[i][k]);
			}
		}
	}
	printf("%d\n",dp[9][K]);
	return 0;
}

Measured memory_bytes: 1344
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let n: i64 = input();
    println!("{}", 800 * n - 200 * (n / 15));
}


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

int main() {
    int n;
    cin >> n;
    ll a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ll b = a[i];
        while (!(b % 2)) {
            ans++;
            b /= 2;
        }
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 384
use std::io::{self, BufRead};

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let k_x = lines.next().unwrap().unwrap();
    let mut k_x = k_x.split_whitespace();
    let k = k_x.next().unwrap().parse::<i32>().unwrap();
    let x = k_x.next().unwrap().parse::<i32>().unwrap();

    if 500 * k >= x {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
int a[maxn],n,m,c[3];
int b=0,tot=0;
int main()
{
    scanf("%d%d",&n,&m);
    c[0]=1;c[1]=m;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",a+i);
        if(~a[i]&1)continue;
        c[b++]=i;
        if(b>2){printf("Impossible\n");return 0;}
    }
    swap(a[1],a[c[0]]);swap(a[m],a[c[1]]);
    if(m==1&&a[1]==1){printf("1\n1\n1\n");return 0;}
    for(int i=1;i<=m;i++)printf("%d ",a[i]);
    if(m==1){printf("\n2\n%d 1\n",a[1]-1);return 0;}
    printf("\n%d\n%d ",a[m]>1?m:m-1,a[1]+1);
    for(int i=2;i<m;i++)printf("%d ",a[i]);
    if(a[m]>1) printf("%d\n",a[m]-1);
    return 0;
}

Measured memory_bytes: 256
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, h = list(map(int, input().rstrip('\n').split()))
    al = []
    bl = []
    for i in range(n):
        a, b = list(map(int, input().rstrip('\n').split()))
        al.append(a)
        bl.append(b)
    al.sort()
    bl.sort()
    al = collections.deque(al)
    bl = collections.deque(bl)
    k = al[-1]
    cnt = 0
    while True:
        if len(bl) != 0:
            p = bl.pop()
            if p > k and h != 0:
                h -= min(p, h)
                cnt += 1
            else:
                print(cnt + (h + k - 1) // k)
                exit()
        else:
            print(cnt + (h + k - 1) // k)
            exit()


if __name__ == '__main__':
    solve()


Measured memory_bytes: 57308
import fractions


def solve():
    a, b, c, d = map(int, input().split())
    lcm = c * d // fractions.gcd(c, d)
    div_c = b // c - (a - 1) // c
    div_d = b // d - (a - 1) // d
    div_cd = b // lcm - (a - 1) // lcm
    return (b - a + 1) - div_c - div_d + div_cd


if __name__ == "__main__":
    print(solve())


Measured memory_bytes: 5048
//#include <bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<cstring>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<iterator>
#include<algorithm>
#include<bitset>

#define Filein(N) freopen("N", "r", stdin);
#define Fileout(N) freopen("N", "w", stdout);
#define sci(x) scanf("%d", &x)
#define sci2(x,y) scanf("%d%d", &x,&y)
#define scll2(x,y) scanf("%lld%lld",&x,&y)
#define scll(x) scanf("%lld",&x)
#define scd(x) scanf("%lf", &x)
#define scstr(x) scanf("%s", x)
#define pfi(x) printf("%d", x)
#define pfll(x) printf("%lld", x)
#define pfd(x) printf("%f", x)
#define pfstr(x) printf("%s", x)
#define ps printf(" ")
#define pn printf("\n")
#define pfdt printf("..")

#define For(var,start,end) for(int var=start; var<=end;i++)
#define rFor(var,start,end) for(int var=start; var>=end; i--)
#define TestCase int testcase, cs=1; cin>>testcase;while(testcase--)

#define mkp make_pair
#define pb push_back
#define fi first
#define se second

#define px(x) cout<<"X -> "<<x<<endl;
#define py(x) cout<<"Y = "<<x<<endl;
#define pz(x) cout<<"Z >> "<<x<<endl;
#define pstr(x) printf("%s\n",x);

using namespace std;
using ll = long long;
using vi = vector <int>;
using mpii = map<int,int>;
using si = set<int>;
using sll = set<ll>;
using vll= vector<ll>;

#define INF 1000000000
#define LINF 4000000000000000000
#define pi  (2*acos(0))
#define Mod 1000000007

 int main(){
 char ch;
 scanf("%c",&ch);

 int d = ch;

 if(d>=65&&d<=90) printf("A\n");
 else printf("a\n");






    return 0;
}







Measured memory_bytes: 3756
N, K = map(int, input().split())
H = list(map(int, input().split()))
H = [H[0]] * K + H

# dp[i] := 足場iに来るのにかかる最小のコスト
INF = 10**18
dp = [INF] * (K + N)
dp[0] = 0
for i in range(K, N + K):
    h = H[i]
    # TLEするので内包表記にする
    costs = [x + abs(y - h) for x, y in zip(dp[i - K:i], H[i - K:i])]
    dp[i] = min(costs)
ans = dp[-1]
print(ans)


Measured memory_bytes: 13976
#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.setf(ios::fixed); cout.precision(20);
    int r; cin >> r;
    cout << r * r;
}


Measured memory_bytes: 256
# https://atcoder.jp/contests/abc086/tasks/abc086_a
n_music = int(input())
music_name = []
music_time = []
for i in range(n_music):
    si, ti = input().split()
    music_name.append(si)
    music_time.append(int(ti))

asleep_music = input()

for k in range(n_music):
    if music_name[k] == asleep_music:
        break

asleep_time = 0
for j in range(n_music):
    if j > k:
        asleep_time += music_time[j]

print(asleep_time)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
//#define num 1000000007
#define num 998244353
#define REP(i,a,n) for(ll i=a;i<n;i++)
#define inarr(i,a,n,A) for(ll i=a;i<n;i++) { cin>>A[i]; }
#define vll vector<long long>
#define pii pair <int,int>
#define pll pair<long long, long long>
#define vpii vector< pair <int,int>>
#define vpll vector< pair<long long, long long>>
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define max3(a,b,c) (a>b)?(a>c)?a:c:(b>c)?b:c
#define min3(a,b,c) (a<b)?(a<c)?a:c:(b<c)?b:c
#define avg(a,b) ((a)+(b))/2
#define push push_back
#define pop pop_back
#define mp make_pair
#define sf int flag=0     //Remember semicolon
#define assmin(a,b) if(b<=a) { a=b; }
#define assmax(a,b) if(b>=a) { a=b; }
#define f first
#define s second
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
typedef long long ll;

ll mod(ll a, ll b)
{
	if(a%b<0)
	{
		return a%b + b;
	}
	return a%b;
}
 
 
ll mod_exp(ll a, ll b, ll c)
{
	ll res=1;
	a=a%c;
	while(b>0)
	{
		if(b%2==1)
		{
			res=(res*a)%c;
		}
		b/=2;
		a=(a*a)%c;
	}
	return res;
}
ll gcd(ll a, ll b)
{
    if(b==0)
    {
        return a;
    }
    return gcd(b, a%b);
}
bool prime[3001];
void SieveOfEratosthenes() 
{ 
    memset(prime, true, sizeof(prime)); 
    prime[1]=false;
    for (int p=2; p*p<=3000; p++) 
    { 
        if (prime[p] == true) 
        { 
            for (int i=p*p; i<=3000; i += p) 
                prime[i] = false; 
        } 
    } 
}
ll powe[20];
void power()
{
	powe[0]=1;
	REP(i,1,20)
	{
		powe[i]=(powe[i-1]*10)%num;
        if(powe[i]<0)
        powe[i]+=num;
	}
}
ll A[300005],mx[300005],mn[300005],cur[300005];
void assign(ll n)
{
	REP(i,1,n)
	{
		A[i]=mx[i]=mn[i]=cur[i]=i;
	}
}
double dist(pll p1,pll p2)
{
	return (1.0)*(p1.f-p2.f)*(p1.f-p2.f)+(1.0)*(p1.s-p2.s)*(p1.s-p2.s);
}
bool isprime(ll x)
{
	if(x==1)
	return false;
	if(x==2)
	return true;
	REP(i,2,sqrt(x)+1)
	{
		if(x%i==0)
		{
			return false;
		}
	}
	return true;
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	ll x;
	cin>>x;
	while(true)
	{
		if(isprime(x))
		{
			cout<<x<<"\n";
			exit(0);
		}
		x++;
	}
	return 0;
}

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

using ll = long long;
using namespace std;

#define swap(a, b)    do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while(false)
#define repd(i, a, b) for(typeof(b) i = a; i < (b); ++i)
#define rep(i, n)     repd(i, 0, n)
#define dump(x)       cerr << #x << " = " << (x) << endl
#define debug(x)      cerr << "L" << __LINE__ << ": " << #x << " = " << (x) << endl
#define YN(x)         cout << ((x) ? "YES" : "NO") << endl
#define Yn(x)         cout << ((x) ? "Yes" : "No") << endl
#define yn(x)         cout << ((x) ? "yes" : "no") << endl
#define absi(x)       ( ((x) >= 0) ? (x) : (-(x)) )
#define debugvec(v)   rep(i, v.size()) cerr << "L" << __LINE__ << ": " << #v << "[" << i << "] = " << v[i] << endl;
#define debugvec2(v)  cerr << "L" << __LINE__ << ": " << #v << " = { "; rep(i, v.size()) cerr << v[i] << (i + 1 == v.size() ? "" : ", "); cerr << " }" << endl;

ll gcd(ll a, ll b) { return __gcd(a, b); }
ll lcm(ll a, ll b) { return (a == 0 || b == 0) ? 0 : (a / __gcd(a, b) * b); }

class unionfind {
public:
	std::vector<std::size_t> parent;
	std::vector<std::size_t> rank;
	std::vector<std::size_t> size;
	
	unionfind(const std::size_t n) {
		parent = std::vector<std::size_t>(n, 0);
		rank   = std::vector<std::size_t>(n, 0);
		size   = std::vector<std::size_t>(n, 1);
		for(std::size_t i = 0; i < n; ++i) {
			parent.at(i) = i;
		}
	}

	std::size_t root(const std::size_t i) {
		return (parent.at(i) == i) ? i : ( parent.at(i) = root(parent.at(i)) );
	}
	
	bool is_same(const std::size_t x, const std::size_t y) {
		return root(x) == root(y);
	}
	
	bool unite(std::size_t x, std::size_t y) {
		x = root(x);
		y = root(y);
		if(x == y) {
			return false;
		}

		if(rank.at(x) > rank.at(y)) {
			std::size_t oldx = x;
			x = y;
			y = oldx;
		}

		parent.at(x) = y;
		size.at(y) += size.at(x);
		if(rank.at(x) == rank.at(y)) {
			++rank.at(y);
		}
		return true;
	}


	std::size_t setsize(const std::size_t i) {
		return size.at(root(i));
	}
};

int main(int argc, const char* argv[]) {
	ll n, m;
	cin >> n >> m;

	vector<ll> a(m), b(m);
	unionfind uf(n);

	rep(i, m) {
		cin >> a.at(i) >> b.at(i);
		a.at(i) -= 1;
		b.at(i) -= 1;
	}

	vector<ll> ret(m, 0);
	ret.back() = n * (n-1) / 2;

	for(ll i = m-1; i > 0; --i) {
		ll size1 = uf.setsize(a.at(i));
		ll size2 = uf.setsize(b.at(i));

		if(uf.unite(a.at(i), b.at(i))) {
			ret.at(i-1) = ret.at(i) - size1 * size2;
		} else {
			ret.at(i-1) = ret.at(i);
		}
	}

	rep(i, m) {
		cout << ret.at(i) << endl;
	}
 
	return 0;
}


Measured memory_bytes: 6016
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int a[1000560];
int main()
{
        int n;
        while(~scanf("%d",&n))
        {
                int t;
                for(int i=1;i<=n;i++)
                        scanf("%d",&a[i]);
                if(n%2==1)
                {
                        for(int i=n;i>=1;i-=2)
                        printf("%d ",a[i]);
                        for(int i=2;i<=n-1;i+=2)
                        {
                                if(i==n-1)
                                        printf("%d",a[i]);
                                else
                                        printf("%d ",a[i]);
                        }
                }
                else if(n%2==0)
                {
                        for(int i=n;i>0;i-=2)
                                printf("%d ",a[i]);
                        for(int i=1;i<=n-1;i+=2)
                        {
                                if(i==n-1)
                                        printf("%d",a[i]);
                                else
                                        printf("%d ",a[i]);
                        }
                }
                printf("\n");
        }
        return 0;
}

Measured memory_bytes: 2816
N = int(input())
point = []
for i in range(2*N):
  x, y = map(int, input().split())
  point.append((x, y, i>=N))

point.sort()

ans = 0
Y = set()
for x, y, color in point:
  if color == 0:
    Y.add(y)
  else:
    t = -1
    for _y in Y:
      if t < _y < y:
        t = _y
    if t != -1:
      ans += 1
      Y.discard(t)

print(ans)

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

int main(){
	int N,M,P[100000], Y[100000];
	vector<int> yd[100001];
	cin >> N >> M;
	for(int i(0);i<M;++i){
		cin >> P[i] >> Y[i];
		yd[P[i]].push_back(Y[i]);
	}
	for(int i(1);i<=N;++i) sort(yd[i].begin(),yd[i].end());
	for(int i(0);i<M;++i){
		printf("%012lld\n", ll(P[i]) * 1000000 + int(lower_bound(yd[P[i]].begin(), yd[P[i]].end() ,Y[i])-yd[P[i]].begin())+1);
	}
	return 0;
}

Measured memory_bytes: 7808
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

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

const ll inf = 1ll << 60;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s) cout << fixed << setprecision(10) << s << endl;


int main()
{
	ll n;
	string s;
	cin >> n >> s;

	ll cnt = 0;
	for (ll i = 2; i < s.length(); i++)
	{
		if (s.substr(i - 2, 3) == "ABC")
		{
			cnt++;
		}
	}

	println(cnt);
}

Measured memory_bytes: 3652
import java.util.Scanner;

public class Main {

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

        int n, x;

        while (true) {
            n = sc.nextInt();
            x = sc.nextInt();

            if (n == 0 && x == 0) {
                break;
            }

            int count = 0;

            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    for (int k = 1; k <= n; k++) {
                        if (i < j && j < k) {
                            if ((i + j + k) == x) {
                                count++;
                            }
                        }
                    }
                }
            }
            System.out.println(count);
        }
    }
}

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


int main() {
  string S;
  cin >> S;
  int a[26] = {};
  for(int i = 0; i < S.size(); ++i) {
    a[S[i] - 'a'] += 1;
  }
  for(int i = 0; i < 26; ++i) {
    if(a[i] == 0) {
      cout << char(i + 'a') << endl;
      break;
    }
    if(i == 25) {
      cout << "None" << endl;
    }
  }
}

Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>
#define N 10000
int main(){
  int *A,*B,C[N+1],a=0,n,i,j;

  scanf("%d",&n);

  A=malloc(sizeof(int)*n+1);
  B=malloc(sizeof(int)*n+1);
  for(i=0;i<n;i++){
    scanf("%d",&A[i+1]);
  }

  for(i=0;i<=N;i++){
    C[i]=0;
  }

  for(j=0;j<n;j++){
    C[A[j+1]]=C[A[j+1]]+1;
  }
  for(i=1;i<=N;i++){
    C[i]=C[i]+C[i-1];
  }
  
  for(j=n;j>=1;j--){
    B[C[A[j]]]=A[j];
    C[A[j]]=C[A[j]]-1;
    
  }

  for(i=1;i<n;i++){
  printf("%d ",B[i]);
  }
  printf("%d\n",B[n]);
  return 0;
}

Measured memory_bytes: 16268
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T, class U> inline bool chmax(T& a,U b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class U> inline bool chmin(T& a,U b) { if (a > b) { a = b; return 1; } return 0; }
constexpr int MAX = 100000;
constexpr int geta = 50000;
constexpr int R = 4000;

inline bool match (const char &c1, const char &c2) {
    return (c1 == '?' || c2 == '?' || c1 == c2);
}

int main() {
    string a, b, c;
    cin >> a >> b >> c;
    int la = a.size(), lb = b.size(), lc = c.size();
    // ab[i] : a を基準にした時、a[i] から b を一致させられるかどうか
    vector<bool> ab(MAX, true), ac(MAX, true), bc(MAX, true);
    
    for (int i = 0; i < la; i++) {
        for (int j = 0; j < lb; j++) {
            if (!match(a[i], b[j])) ab[i-j+geta] = false;
        }
    }
    for (int i = 0; i < la; i++) {
        for (int j = 0; j < lc; j++) {
            if (!match(a[i], c[j])) ac[i-j+geta] = false;
        }
    }
    for (int i = 0; i < lb; i++) {
        for (int j = 0; j < lc; j++) {
            if (!match(b[i], c[j])) bc[i-j+geta] = false;
        }
    }
    
    int ans = la + lb + lc;
    for (int i = -R; i <= R; i++) {
        for (int j = -R; j <= R; j++) {
            if (!ab[i+geta] || !ac[j+geta] || !bc[j-i+geta]) continue;
            int l = min({0, i, j});
            int r = max({la, i+lb, j+lc});
            int len = r - l;
            chmin(ans, len);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main()
{
        double a,b;
        cin>>a>>b;
        if(a>b)
        {
            cout<<"GREATER";
        }
        else if(a<b)
        {
            cout<<"LESS";
        }
        else{
            cout<<"EQUAL";
        }
}


Measured memory_bytes: 3656
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define endl '\n'
const int INF = (1 << 30);
using namespace std;
typedef long long int ll;

bool solve(){
    int n, p;
    cin >> n >> p;
    if(!n && !p) return false;

    vector<int> hand(n,0);
    int i=-1, wan=p;
    do{
        i = (i+1)%n;
        if(wan-- == 0) { wan = hand[i]; hand[i] = 0; }
        else{ hand[i]++; }
    }while(hand[i] != p);
    cout << i << endl;
    return true;
}

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

    while(solve());
}

Measured memory_bytes: 2996
#[allow(unused_imports)]
use std::mem::swap;
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{VecDeque, HashSet, BTreeSet, BinaryHeap, HashMap};
#[allow(unused_imports)]
use std::io::{stdin, stdout, Write, BufReader, BufWriter};
#[allow(unused_imports)]
use std::io::prelude::BufRead;


fn main() {
    let n = read::<usize>();
    if n == 1 {
        println!("Hello World");
        return;
    }
    let a = read::<usize>();
    let b = read::<usize>();
    println!("{}", a + b);
}

#[allow(dead_code)]
fn read<T>() -> T where T: std::str::FromStr, T::Err: std::fmt::Debug {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    return buf
        .trim()
        .parse()
        .unwrap();
}

#[allow(dead_code)]
fn read_vector<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug {
    let mut buf = String::with_capacity(100);
    stdin().read_line(&mut buf).unwrap();
    return buf
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();
}

#[allow(dead_code)]
fn read_matrix<T>() -> Vec<Vec<T>> where T: std::str::FromStr, T::Err: std::fmt::Debug {
    use std::io::prelude::*;
    let stdin = stdin();
    let mut reader = BufReader::with_capacity(100 * 1024, stdin);
    let mut line = String::with_capacity(100);
    let mut matrix: Vec<Vec<T>> = Vec::new();

    while reader.read_line(&mut line).unwrap() > 0 {
        matrix.push(line
            .trim()
            .split_whitespace()
            .map(|s| s.parse().unwrap())
            .collect());
        line.clear();
    }

    return matrix;
}

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

int main(){
	int a,b;
	cin>>a>>b;
	int ans = 0;
	int anko = 1;
	while(anko<b){
		--anko;
		anko += a;
		++ans;
	}
	cout << ans << endl;
	return 0;		
}

Measured memory_bytes: 256
import java.util.Scanner;

/**
 * Created by khrom on 2017/06/14.
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = scanner.nextInt();
        int cnt = 0;
        for (int i = a; i <= b; i++)
            if (c % i == 0) cnt++;
        System.out.println(cnt);
    }
}

Measured memory_bytes: 26220
#include <stdio.h>
int main(void){
    // Your code here!
    int A,B;
    scanf("%d %d",&A,&B);
    if(A>B)
        printf("%d\n",2*A-1);
    else if(B>A)
        printf("%d\n",2*B-1);
    else
        printf("%d\n",A+B);
}


Measured memory_bytes: 128
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <memory.h>
#include <list>
#include <numeric>
#include <functional>
#include <complex>
#include <cassert>
#include <regex>
#include <random>

#define ll long long
#define ld long double
#define ull unsigned ll
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pii pair<int,int> 
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vector<int>>
#define forn(it,from,to) for(int (it)=from; (it)<to; (it)++)
const int  Inf = 2 * 1000 * 1000 * 1000;
ll LINF = (ll)4e18;
using namespace std;
#define M_PI       3.14159265358979323846   // pi


int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	//freopen("sum.in", "r", stdin);
	//freopen("sum.out", "w", stdout);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int a, b;
	cin >> a >> b;
	cout << max({ a + a - 1, b + b - 1, a + b });
 	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
char s[3],t[3];
int ans;
int main(){
  for(int i=0;i<3;i++){
    cin>>s[i];
  }
  for(int i=0;i<3;i++){
    cin>>t[i];
    if (s[i]==t[i]){
      ans++;
    }
  }
  cout<<ans<<endl;
}

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

using namespace std;

int main(void)
{
	int n; cin>>n;
	int t[n]; for(int i = 0; i < n; i++) cin>>t[i];
	int m; cin>>m;
	int p[m],x[m]; for(int i = 0; i < m; i++) cin>>p[i]>>x[i];
	
	long long ans = 0; for(int i = 0; i < n; i++) ans+= t[i];
	
	for(int  i = 0; i < m; i++){
		long long w = ans;
		w -= t[p[i]-1];
		w += x[i];
		//cout<<"i = "<<i<<", w = "<<w<<", p[i] = "<<p[i]<<", x[i] = "<<x[i]<<endl;
		cout<<w<<endl;
	}
	/*
	for(int i = 0; i < m; i++){
		cout<<w[i]<<endl;
	}
	*/
	return 0;
}



Measured memory_bytes: 256
S = [list(map(int, input().split())) for _ in range(3)]
s = []
for i in range(3):
    for j in range(3):
        s.append(S[i][j])
n = int(input())
a = [int(input()) for i in range(n)]
if (s[0]in a and s[1] in a and s[2] in a)or(s[3]in a and s[4] in a and s[5] in a)or(s[6]in a and s[7] in a and s[8] in a)or(s[0]in a and s[3] in a and s[6] in a)or(s[4]in a and s[1] in a and s[7] in a)or(s[2]in a and s[5] in a and s[8] in a)or(s[0]in a and s[4] in a and s[8] in a)or(s[2]in a and s[4] in a and s[6] in a):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
#include<stdio.h>

int main(void)
{
 int n;
 while(scanf("%d",&n)!=EOF)
 {
     int a,b,c,d,cnt=0,max=9;
     for(a = 0; a <= max; ++a)
     for(b = 0; b <= max; ++b)
     for(c = 0; c <= max; ++c)
     for(d = 0; d <= max; ++d)
     if(a+b+c+d == n) 
       ++cnt;
     printf("%d\n",cnt);
 }
 return 0;
}

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

int main(){
  ll dp[3100][3100];
  ll mod=998244353;
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  dp[a][b]=1;
  for(int i=a;i<=c;i++){
    for(int j=b;j<=d;j++){
      if(i==a&&j==b){
        continue;
      }
      if(i-a>0&&j-b>0){
        dp[i][j]=(dp[i-1][j]*j)%mod+(dp[i][j-1]*i)%mod;
        dp[i][j]%=mod;
        dp[i][j]-=((dp[i-1][j-1]*(i-1))%mod*(j-1))%mod;
        while(dp[i][j]<0){
          dp[i][j]+=mod;
        }
        dp[i][j]+=mod;
        dp[i][j]%=mod;
        continue;
      }
      if(i-a==0){
        dp[i][j]=dp[i][j-1]*i;
        dp[i][j]%=mod;
      }
      if(j-b==0){
        dp[i][j]=dp[i-1][j]*j;
        dp[i][j]%=mod;
      }
    }
  }
  cout<<dp[c][d]<<endl;
}

Measured memory_bytes: 76056
#pragma region
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std; 
  
typedef long long LL; 
typedef pair<int, int> pii; 
typedef pair<LL, LL> pll; 
typedef pair<string, string> pss; 
typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef vector<pii> vii; 
typedef vector<LL> vl; 
typedef vector<vl> vvl; 
typedef map<int,int> mii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  

double EPS = 1e-9; 
int INF = 1000000005; 
long long INFF = 1000000000000000005LL; 
double PI = acos(-1); 
int mod = 1e9+7;
  
  
#define FOR(a, b, c) for (int(a) = (int)(b); (a) < (int)(c); ++(a)) 
#define FORD(a, b, c) for (int(a) = (int)(b); (a) >= (int)(c); --(a)) 
#define F first 
#define S second 
#define mp make_pair 
#define pb push_back 
#define pqb priority_queue<int>
#define pqs priority_queue<int,vi,greater<int>>
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define ps(x,y) fixed<<setprecision(y)<<x
#define ALL(v) v.begin(), v.end() 
#define SIZE(v) (int)v.size() 
#define SORT(v) sort(ALL(v)) 
#define SORTC(v, c) sort(ALL(v), c)
#define REVERSE(v) reverse(ALL(v)) 
#define SORTA(arr, sz) sort(ALLA(arr, sz)) 
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz)) 
#define test(x) int x; cin>>x; while(x--)
#define endl '\n'

void redir()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

void showv(const vector<int> &v){for(auto &i:v) cout << i << " "; cout << endl;}
void showv2(const vector<vector<int>> &v1){for(auto &v:v1) showv(v);}
#pragma endregion

//like
int main() 
{ 
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    redir();

    int n;
    cin >> n;
    
    vl arr(n);
    FOR(i,0,n) cin >> arr[i];

    auto prefix = arr;
    for(int i = n-2; i >= 0; i--)
    {
        prefix[i] = (prefix[i] + prefix[i+1])%mod;
    }

    long long ans = 0;
    FOR(i,0,n-1)
    {
        ans = (ans + (arr[i]*prefix[i+1])%mod)%mod;
    }
    cout << ans << endl;
    return 0; 
} 

Measured memory_bytes: 6352
#include <iostream>

using namespace std;

int main() {
    int a, b, c, d, e;
    cin >> a >> b >> c >> d;
    e = 100;
    while(e>0){
        e--;
        c = c-b;
        if(c<=0){
            cout << "Yes" << endl;
            break;
        }
        a = a-d;
        if(a<=0){
            cout << "No" << endl;
            break;
        }
    }
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  ll n, q;
  cin >> n >> q;
  vector<ll> a(n), x(q);
  REP(i, n) cin >> a[i];
  REP(i, q) cin >> x[i];
  REP(i, q) {
    ll ans = 0;
    ll r = 0;
    ll sum = 0;
    for (ll l = 0; l < n; ++l) {
      while (r < n && sum + a[r] <= x[i]) {
        sum += a[r];
        r++;
      }
      ans += r - l;
      if (l == r)
        ++r;
      else
        sum -= a[l];
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 3552
use std::io::prelude::*;
use std::str::FromStr;
pub struct Scanner<R: Read>(R);
impl<R: Read> Scanner<R> {
    pub fn new(reader: R) -> Self {
        Self(reader)
    }
    pub fn read<T: FromStr>(&mut self) -> T {
        let token = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| (b as char).is_whitespace())
            .take_while(|&b| !(b as char).is_whitespace())
            .collect::<Vec<u8>>();
        unsafe { std::str::from_utf8_unchecked(token.as_slice()) }
            .parse()
            .ok()
            .expect("Can't parse it.")
    }
    pub fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}
fn main() {
    let (stdin, stdout) = (std::io::stdin(), std::io::stdout());
    let mut sc = Scanner::new(stdin.lock());
    let mut out = std::io::BufWriter::new(stdout.lock());
    solve(&mut sc, &mut out);
    out.flush().ok().unwrap();
}
fn solve(sc: &mut Scanner<std::io::StdinLock>, out: &mut std::io::BufWriter<std::io::StdoutLock>) {
    let n: usize = sc.read();
    let mut plan = vec![(0, 0, 0)];
    for _ in 0..n {
        plan.push((sc.read(), sc.read(), sc.read()));
    }

    let ans = plan.windows(2).all(|w| {
        let (t, x, y) = w[0];
        let (nt, nx, ny) = w[1];

        let dist = (nx - x as i32).abs() + (ny - y as i32).abs();
        let time = nt - t;

        dist <= time && (time - dist) & 1 == 0
    });

    println!("{}", if ans { "Yes" } else { "No" });
}


Measured memory_bytes: 3176
#include<stdio.h>

long int calc_lcm(long int a, long int b){
    long int temp = 0;
    long int x;
    if(a < b){
        temp = a;
        a = b;
        b = temp;
    }
    x = a * b;
    temp = a % b;
    while(temp != 0){
        a = b;
        b = temp;
        temp = a % b;
    }
    return x / b;
}

int main(void){
    long int a, b;
    scanf("%ld""%ld", &a, &b);
    printf("%ld\n", calc_lcm(a, b));
    return 0;

}

Measured memory_bytes: 128
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;

enum inf3 = 1_001_001_001;
enum inf6 = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;

alias Edge = Tuple!(int, "u", int, "v");

void main() {
    int n;
    scan(n);

    Edge[] ans;
    int s = n % 2 ? n : n + 1;

    foreach (i ; 1 .. n + 1) {
        foreach (j ; i + 1 .. n + 1) {
            if (i + j == s) continue;
            ans ~= Edge(i, j);
        }
    }

    writeln(ans.length);
    foreach (ansi ; ans) {
        writefln("%s %s", ansi.u, ansi.v);
    }
}


























int[][] readGraph(int n, int m, bool isUndirected = true, bool is1indexed = true) {
    auto adj = new int[][](n, 0);

    foreach (i; 0 .. m) {
        int u, v;
        scan(u, v);
        if (is1indexed) {
            u--, v--;
        }
        adj[u] ~= v;
        if (isUndirected) {
            adj[v] ~= u;
        }
    }

    return adj;
}

//alias Edge = Tuple!(int, "to", int, "cost");

Edge[][] readWeightedGraph(int n, int m, bool isUndirected = true, bool is1indexed = true) {
    auto adj = new Edge[][](n, 0);

    foreach (i; 0 .. m) {
        int u, v, c;
        scan(u, v, c);
        if (is1indexed) {
            u--, v--;
        }
        adj[u] ~= Edge(v, c);
        if (isUndirected) {
            adj[v] ~= Edge(u, c);
        }
    }

    return adj;
}

void yes(bool b) {
    writeln(b ? "Yes" : "No");
}

void YES(bool b) {
    writeln(b ? "YES" : "NO");
}

T[] readArr(T)() {
    return readln.split.to!(T[]);
}

T[] readArrByLines(T)(int n) {
    return iota(n).map!(i => readln.chomp.to!T).array;
}

void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}


Measured memory_bytes: 380
from fractions import gcd
a, b, c, d = map(int, input().split())
e = c * d // gcd(c, d)
tmp = []
for i in (c, d, e):
    if not a % i:
        l = a
    else:
        l = a + (i - (a % i))
    r = b - b % i
    tmp.append((r - l) // i + 1)

print((b-a+1) - tmp[0] - tmp[1] + tmp[2])

Measured memory_bytes: 5052
n,q = map(int,input().split())
s = input()
t_list = [0]*n
for i in range(len(s)-1):
    if (s[i] == 'A') and (s[i+1] == 'C'):
        t_list[i+1] = 1+t_list[i]
    else:
        t_list[i+1] = t_list[i]
        
for i in range(q):
    l,r =  map(int,input().split())
    print(t_list[r-1] - t_list[l-1])

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

"""
・ダイクストラ(優先度付きキュー)
"""

from heapq import heappop, heappush
from collections import deque

# 今回はダイクストラするので、データの持ち方は隣接リスト
N = int(input())
nodes = [deque() for _ in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    # nodes[出発ノード](到着ノード, コスト))
    nodes[a].append((b, c))
    nodes[b].append((a, c))

def dijkstra(nodes, start):
    # 最短距離メモ
    memo = [float('inf')] * (len(nodes))
    # 訪問済メモ
    visited = [False] * (len(nodes))
    # スタート位置
    que = [(0, start)]
    memo[start] = 0
    # キューが空になるまで
    while len(que) != 0:
        # startからの距離, 現在のノード
        dist, cur = heappop(que)
        # 訪問済にする
        visited[cur] = True
        # 出発ノードcurの到着ノードでループ
        while len(nodes[cur]) != 0:
            nxt, cost = nodes[cur].popleft()
            # 訪問済ではない時だけ
            if not visited[nxt]:
                memo[nxt] = min(memo[cur] + cost, memo[nxt])
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (memo[nxt], nxt))
    # ノードstartからの最短距離リストを返却
    return memo

Q, K = map(int, input().split())
# 引数：(ノードの隣接リスト, 出発ノード)
memo = dijkstra(nodes, K)

for i in range(Q):
    x, y = map(int, input().split())
    print(memo[x] + memo[y])


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

int main(){
    string S;
    cin >> S;
    bool A = true;

    if(S.size()%2!=0){
        A=false;
    }

    for(int i=0; i< S.size();i++){
        if(i%2==0 && S.at(i) !='h'){
            A = false;
        }
        if(i%2!=0 && S.at(i) !='i'){
            A = false;
        }
    }

    if(A==true){
        cout << "Yes" <<endl;

    }
    if(A==false){
        cout << "No" <<endl;
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
static const double EPS = 1e-5;

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

int main(void){
  int sum;
  while(cin>>sum){
    if(sum==0) break;
    REP(i,9){
      int tmp;
      cin>>tmp;
      sum-=tmp;
    }
    cout<<sum<<endl;
  }
  return 0;
}

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

using namespace std;

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

int main() {
    int n, m, l;
    cin >> n >> m >> l;
    ll a[n][m] = {};
    ll b[m][l] = {};
    ll c[n][l] = {};

    REP(i, n) {
        REP(j, m) cin >> a[i][j];
    }

    REP(i, m) {
        REP(j, l) cin >> b[i][j];
    }

    REP(i, n) {
        REP(j, l) {
            REP(k, m) c[i][j] += a[i][k] * b[k][j];
        }
    }

    REP(i, n) {
        REP(j, l) {
            if (j) cout << " ";
            cout << c[i][j];
        }
        cout << endl;
    }

}

Measured memory_bytes: 3308
#include <bits/stdc++.h>
using namespace std;
#define N_PRIME 1000000007
#define ll int64_t

int64_t aabs(int64_t n){
    if( n < 0 )
        return -n;
    else
        return n;
}

int main(void){
    int64_t x,y;
    cin >> x >> y;
    int64_t count = 0;
    int64_t ax,ay;
    
    ax = aabs(x);
    ay = aabs(y);
    
    if( ax > ay ){
        if( x > 0 ){
            count++;
            x *= -1;
        }
        count += aabs(ax - ay);
        x = -aabs(y);
    }else if( ax < ay ){
        if( x < 0 ){
            count++;
            x *= -1;
        }
        count += aabs(ay - ax);
        x = aabs(y);
    }
    
    if( x * y < 0 )
        count++;
    
    cout << count << endl;
    
    
    
    
    return 0;
}

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

using namespace std;

typedef long long int ll;

const ll mod = 1e9 + 7;

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

  ll n;
  cin >> n;
  vector < ll > a(n + 1), b(n + 1), c(n + 1);
  vector < vector < ll > > dp(n + 1, vector < ll > (3, 0));
  for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];

  for(int i = 1; i <= n; i++){
    dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i];
    dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b[i];
    dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + c[i];
  }

  cout << max({dp[n][0], dp[n][1], dp[n][2]}) << '\n';
}


Measured memory_bytes: 8064
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int inf=0x3f3f3f3f;
int f[1003],g[2][5010],n,first[1003],tot,v[1003];
struct edge{
	int v,from;
}e[1003];
inline void insert(int u,int v){
	e[++tot].v=v;  e[tot].from=first[u];  first[u]=tot;
}
inline int min(int a,int b){
	return a<b?a:b;
}
void dfs(int x){
    for(int i=first[x];i;i=e[i].from){
    	dfs(e[i].v);
	}
    memset(g[0],0x3f,sizeof(g[0]));
    int X=0;
    g[X][0]=0;
    for(int i=first[x];i;i=e[i].from){
        int y=e[i].v;
        X=1-X;
        memset(g[X],0x3f,sizeof(g[X]));
        for(int j=0;j<=v[x];j++){
            if(j-v[y]>=0)g[X][j]=min(g[X][j],g[1-X][j-v[y]]+f[y]);
            if(j-f[y]>=0)g[X][j]=min(g[X][j],g[1-X][j-f[y]]+v[y]);
        }
    }
    for(int i=0;i<=v[x];i++){
    	f[x]=min(f[x],g[X][i]);
	}
}
int main(){
	cin>>n;
    for(int i=2;i<=n;i++){
        int p;
        cin>>p;
        insert(p,i);
    }
    for(int i=1;i<=n;i++){
    	cin>>v[i];
	}
    memset(f,0x3f,sizeof(f));
    dfs(1);
    if(f[1]<inf)printf("POSSIBLE");
	else printf("IMPOSSIBLE");
    return 0;
}

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

int n,m,fa[202000],d[202000];

int GF(int x){
  if (fa[fa[x]]==fa[x]) return fa[x];
  int orgfa=fa[x];
  fa[x]=GF(fa[x]);
  d[x]+=d[orgfa];
  return fa[x];
}
int dis(int x){
  return fa[x]==x? 0: d[x]+dis(fa[x]);
}

void onion(int x,int y,int v){
  int fx=GF(x), dx=dis(x), fy=GF(y), dy=dis(y), las;
  las=-dx+dy+v;
  if (fx==fy){
    if (las){
      puts("No");
      exit(0);
    }
  }else{
    fa[fx]=fy;
    d[fx]=las;
  }
}

int main(){
  cin>>n>>m;
  for (int i=1;i<=n;++i)
    fa[i]=i, d[i]=0;
  int l,r,x;
  for (;m--;){
    scanf("%d%d%d",&l,&r,&x);
    onion(r,l,x);
  }
  puts("Yes");
}


Measured memory_bytes: 1024
import java.util.*;
import java.lang.Math;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] x = new int[N];
        int[] y = new int[N];
        for(int i = 0; i < N; i++){
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        double result = 0;
        int n = 1;
        for(int i = 0; i < N; i++){
            n *= (i + 1);
            for(int j = 0; j < N; j++){
                result += Math.sqrt((x[i] - x[j])*(x[i]-x[j])+(y[i] - y[j])*(y[i] - y[j]));
            }
        }
        System.out.println(result / (double)n * (n / N));
    }
}


Measured memory_bytes: 21844
x,y=map(int,input().split())
if x==0:
  a=abs(y-x)
  if y<0:
    print(a+1)
  else:
    print(a)
  exit()
if y==0:
  a=abs(x-y)
  if x<=0:
    print(a)
  else:
    print(a+1)
  exit()
if x>0:
  if abs(y)>=x:
    a=abs(y)-x
    if y<0:
      print(a+1)
    else:
      print(a)
  else:
    a=x-abs(y)
    if y<0:
      print(a+1)
    else:
      print(a+2)
  exit()
#x<0
if abs(y)>abs(x):
  a=abs(y)-abs(x)
  if y>0:
    print(a+1)
  else:
    print(a+2)
else:
  a=abs(abs(y)-abs(x))
  if y<0:
    print(a)
  else:
    print(a+1)

Measured memory_bytes: 9220
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int GetNumberOfKind(string str1, string str2);
vector<char> SortAndErase(string str);

int main()
{
    int N;
    string S;
    int max = 0;
   
    cin >> N >> S;
    
    for (int i = 0; i < N; i++) {
        string X = S.substr(0, i);
        string Y = S.substr(i, N-i);
        if (max < GetNumberOfKind(X, Y)) max = GetNumberOfKind(X, Y) ; 
        
    }
    
    cout << max << endl;
  
    return 0;
}

int GetNumberOfKind(string str1, string str2) {
    vector<char> s1 = SortAndErase(str1);
    vector<char> s2 = SortAndErase(str2);

    int count = 0;
    //一致する文字の数を調べる
    for (int i = 0; i < s1.size(); i++) {
        for (int j = 0; j < s2.size(); j++) {
            if (s1[i] == s2[j]) count++;    
        }
    }
    
    return count;

}

vector<char> SortAndErase(string str) {
    vector<char> s;
    
    for (int i = 0; i < str.size(); i++) {
        s.push_back(str[i]);
    }
    
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    
    return s;

}

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

using namespace std;

#define lli long long 
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define rep0(i,j) for(lli i=0;i<j;i++)
#define rep1(i,j) for(lli i=1;i<=j;i++)
#define rep0d(i,j) for(lli i=j-1;i>=0;i--)
#define MAX 1000000007
bool cmpf(const pair<lli, lli> left, const pair<lli, lli> right) {
          return left.first < right.first;
}
bool cmps(const pair<double, double> left, const pair<double, double> right) {
          return left.second < right.second;
}


int main(){
int n,k;
  cin >> n >> k;
  int num=0;
  while(n>0){
	n/=k;
    num++;
  }
  cout << num;
}


Measured memory_bytes: 256
from collections import defaultdict as dd
n=int(input())
a=[int(i) for i in input().split()]
d=dd(int)
for i in a:
    d[i]+=1

ans=0
for i in d.keys():
    if(d[i]>=i):
        ans+=(abs(d[i]-i))
    else:
        ans+=d[i]
print(ans)


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

int main() {
    int d,t,s;
    cin >> d >> t >> s;
    if((double)d/s > t) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3572
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;

const int MAX_N = 100 + 9;
const int MAX_M = 1e7;

int N, x, cnt, match[MAX_N * 2 + 9];//, V;
bool is_prime[MAX_M + 9], rev[MAX_M + 9], used[MAX_N * 2 + 9];
vector<int> primes, v1, v2, G[MAX_N * 2 + 9];

void sieve() {
	memset(is_prime, 1, sizeof(is_prime));
	is_prime[0] = is_prime[1] = 0;
	for (int i = 2; i <= MAX_M; i++) {
		if (is_prime[i]) primes.push_back(i);
		for (int j : primes) {
			if (1LL * i * j > MAX_M) break;
			is_prime[i * j] = false;
			if (i % j == 0) break;
		}
	}
}

bool dfs(int v) {
	for (int u : G[v]) {
		if (!used[u]) {
			used[u] = true;
			if (match[u] < 0 || dfs(match[u])) {
				match[u] = v;
				return true;
			}
		}
	}
	return false;
}

void bipartite_matching() {
	memset(match, -1, sizeof(match));
	for (int v = 0; v < v1.size(); v++) {
		memset(used, 0, sizeof(used));
		if (dfs(v)) cnt++;
	}
}

int main() {
	sieve();
	scanf("%d", &N); 
	for (int i = 1; i <= N; i++) scanf("%d", &x), rev[x] ^= true;
	for (int i = 1; i <= MAX_M + 1; i++) {
		if (rev[i] != rev[i - 1]) {
			if (i & 1) v1.push_back(i);
			else v2.push_back(i);
		}
	}
	for (int i = 0; i < v1.size(); i++) {
		for (int j = 0; j < v2.size(); j++) {
			int m = abs(v1[i] - v2[j]);
			if (is_prime[m]) G[i].push_back(j);
		}
	}
//	V = v1.size() + v2.size();
	bipartite_matching();
	printf("%d", cnt + (v1.size() - cnt >> 1 << 1) + (v2.size() - cnt >> 1 << 1) + ((v1.size() - cnt) & 1) * 3);
	return 0;
}

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

string s ;
int s_size ;

int f( int p ){
	if( s[p] == 'O' && s[p+1] == 'I' ) return 1 ;
	return 0 ;
}

int main(){
	
	while( cin >> s ){
		if( cin.eof() ) break ;
		s_size = s.size() ;
		
		int ans[2] = {} ;
		for( int i=0 ; i<s_size ; i++ ){
			if( s[i] == 'J' ) ans[0] += f(i+1) ;
			if( s[i] == 'I' ) ans[1] += f(i+1) ;
		}
		
		cout << ans[0] << endl ;
		cout << ans[1] << endl ;
		
	}
	
return 0 ;
}

Measured memory_bytes: 1196
def resolve():
    '''
    code here
    '''
    import collections
    N = int(input())
    reds = [[int(item) for item in input().split()] for _ in range(N)]
    blues = [[int(item) for item in input().split()] for _ in range(N)]

    reds = sorted(reds, key=lambda x:x[1], reverse=True)
    blues.sort()

    que = collections.deque(blues)
    cnt = 0

    while que:

        bx, by = que.popleft()

        for rx, ry in reds[:]:
            if rx <= bx and ry <= by:
                cnt += 1
                reds.remove([rx, ry])
                break
    print(cnt)


if __name__ == "__main__":
    resolve()




Measured memory_bytes: 9476
#include <bits/stdc++.h>
// #include <math.h>
#include <cmath>
// #include <unordered_map>
using namespace std;
typedef long long int lli;
#define M_PI_H  3.14159265358979323846/2  /* pi by two*/



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

	cin>>s;

	int l = s.length();
	for(int i=0; i<l; i++){
		if(s[i]=='?'){
			s[i] = 'D';
		}
	}

	cout<<s;	
    return 0;
}

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

int main(void) {
    int N;cin>>N;
    int result = 0;
    for (int i = 1;i <= N; i++) {
        int l,r;cin>>l>>r;
        result += r - l + 1;
    }
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 888