akhauriyash/Code-Regression huggingface dataset:
package main

import (
	"bufio"
	"fmt"
	"os"
)

var sc = bufio.NewScanner(os.Stdin)

func ri() (n int) {
	sc.Scan()
	for _, v := range sc.Bytes() {
		n = n*10 + int(v-48)
	}
	return
}

func rb() []byte {
	sc.Scan()
	return sc.Bytes()
}

func smaller(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1e6), 1e6)
	n, s := ri(), rb()

	ctHash := 0
	for _, ss := range s {
		if ss == '#' {
			ctHash++
		}
	}
	ctDot := n - ctHash

	minCost := smaller(ctHash, ctDot)
	ctHash = 0
	for _, ss := range s {
		switch ss {
		case '#':
			ctHash++
		case '.':
			ctDot--
		}
		if cost := ctHash + ctDot; cost < minCost {
			minCost = cost
		}
	}
	fmt.Println(minCost)
}


Measured memory_bytes: 896
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num) vector<ll> name((num),0);
#define op(i) cout<<(i)<<endl;
#define opf(i) cout<<fixed<<setprecision(10)<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define opP cout<<"Possible"<<endl;
#define opI cout<<"Impossible"<<endl;
#define mat(name,fnum,snum); vector<vector<ll>> name((fnum),vector<ll>((snum),0));
#define matC(name,fnum,snum); vector<vector<char>> name((fnum),vector<char>((snum),0));
#define debugP int debug_point; cin>>debug_point;
#define FI first
#define SE second
const ll MOD= 1e9 + 7;


void solve(long long N, vector<char> S){
    rep(i,N){
        if(S[i]=='Y'){
            op("Four")
            return;
        }
    }
    op("Three")
    return;
}

// Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<char> S(N);
    for(int i = 0 ; i < N ; i++){
        std::cin >> S[i];
    }
    solve(N, S);
    return 0;
}


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

/***********************************************/
/* Dear online judge:
 * I've read the problem, and tried to solve it.
 * Even if you don't accept my solution, you should respect my effort.
 * I hope my code compiles and gets accepted.
 *  ___  __     _______    _______      
 * |\  \|\  \  |\  ___ \  |\  ___ \     
 * \ \  \/  /|_\ \   __/| \ \   __/|    
 *  \ \   ___  \\ \  \_|/__\ \  \_|/__  
 *   \ \  \\ \  \\ \  \_|\ \\ \  \_|\ \ 
 *    \ \__\\ \__\\ \_______\\ \_______\
 *     \|__| \|__| \|_______| \|_______|
 */
const long long mod = 1000000007;

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

	string s;
	cin>>s;
	cout<<s.substr(0,s.size()-8)<<'\n';
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
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 pi acos(-1.0)

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, c;
    cin >> a >> b >> c;
    cout << (b - a == c - b ? "YES" : "NO") << "\n";
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int ifcl(int p0[2],int p1[2],int p2[2],int p3[2]){
  long long x=p0[0],x0=p1[0]-x,x1=p2[0]-x,x2=p3[0]-x,x3=x2-x1,x4=x0-x1,x5=-x1;
  long long y=p0[1],y0=p1[1]-y,y1=p2[1]-y,y2=p3[1]-y,y3=y2-y1,y4=y0-y1,y5=-y1;
  long long x7=x2-x0,y7=y2-y0;  
  long long c1=(x0*y1-y0*x1)*(x0*y2-y0*x2),c2=(x3*y4-y3*x4)*(x3*y5-y3*x5);
  long long d1=x1*x4+y1*y4,d2=x2*x7+y2*y7,d3=x1*x2+y1*y2,d4=x4*x7+y4*y7;
  if(c1==0&&c2==0)return (d1<0&&d2>0&&d3>0&&d4<0)?0:1;
  return (c1<=0&&c2<=0)?1:0;
}
double dMIN(double a,double b){return a<b?a:b;}
double drpl(int p0[2],int p1[2],int p2[2]){
  int a=p0[1]-p1[1],b=p0[0]-p1[0],c=p0[0]*p1[1]-p1[0]*p0[1];
  int d=p2[1]-p1[1],e=p2[0]-p1[0];
  int f=p2[1]-p0[1],g=p2[0]-p0[0];
  if(a*d+b*e<0||a*f+b*g>0)return dMIN(hypot(d,e),hypot(f,g));
  return abs(p2[0]*a-p2[1]*b+c)/hypot(a,b);
}
double drll(int *p0,int *p1,int *p2,int *p3){
  double l=drpl(p2,p3,p0);
  l=dMIN(l,drpl(p2,p3,p1));
  l=dMIN(l,drpl(p0,p1,p2));
  l=dMIN(l,drpl(p0,p1,p3));
  if(ifcl(p0,p1,p2,p3))l=0;
  return l;
}
int main(){
  int p[4][2],n,i;
  scanf("%d",&n);
  while(n--){
    for(i=0;i<8;i++)scanf(" %d",&p[i/2][i%2]);
    printf("%.9f\n",drll(p[0],p[1],p[2],p[3]));
  }
  return 0;
}

Measured memory_bytes: 652
ans _ [] _ = []
ans i t w =
  let l = length w
      w'= take l t
      r = ans (i+1) (drop 1 t) w
  in
    if w == w'
    then i:r
    else r

main = do
  t <- getLine
  w <- getLine
  let o = ans 0 t w
  mapM_ print o

Measured memory_bytes: 4020
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
import collections


# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, Vi):
    V1 = Vi[::2]
    V2 = Vi[1::2]
    c_V1 = dict(collections.Counter(V1))
    c_V2 = dict(collections.Counter(V2))
    c_V1 = sorted(c_V1.items(), key=lambda x: x[1], reverse=True)
    c_V2 = sorted(c_V2.items(), key=lambda x: x[1], reverse=True)
    c_V1.append((-1, 0))
    c_V2.append((-1, 0))
    ans = 0
    if c_V1[0][0] == c_V2[0][0]:
        ans = min(len(V1) - c_V1[0][1] + len(V2) - c_V2[1][1],
                  len(V1) - c_V1[1][1] + len(V2) - c_V2[0][1])
    else:
        ans = len(V1) - c_V1[0][1] + len(V2) - c_V2[0][1]
    print(ans)


if __name__ == '__main__':
    N = int(input())
    Vi = [int(i) for i in input().split()]
    solve(N, Vi)

    # # test
    # from random import randint
    # from func import random_str



Measured memory_bytes: 27692
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 100010
ll n,m,h[N],ma[N];
//ma[i]计算的是i有连接的点的最大值 
int main(){
	cin>>n>>m;
	for(ll i=1;i<=n;i++) cin>>h[i];
	for(ll i=1;i<=m;i++){
		ll x,y;
		cin>>x>>y;
		ma[x]=max(ma[x],h[y]);
		ma[y]=max(ma[y],h[x]);
	}
	ll ans=0;
	for(ll i=1;i<=n;i++){
		ans+=h[i]>ma[i];
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 4732
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int MOD = 1000000007;
const int N = 6006;

double T[2][N], sum, p;
int act, prevv, i, j, n;

int main() {
scanf("%d", &n);
T[0][n] = 1.0;
for (i=1;i<=n;i++) {
	scanf("%lf", &p);
	act = i % 2;
	prevv = 1 - act;
	T[act][n - i] = T[prevv][n - i + 1] * p;
	for (j = n - i + 2;j <= n + i - 2; j++) T[act][j] = T[prevv][j + 1] * p + T[prevv][j - 1] * (1 - p);
	T[act][n + i] = T[prevv][n + i - 1] * (1 - p);
}
sum = 0.0;
for (j = 0;j<n;j+=2) sum += T[act][j];
printf("%.11lf\n", sum);
return 0;
}

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

int main(){
  int N;cin>>N;
  string s="";
  while(N!=0){
    if(N%2==0)
      s+='0';
    else{
      s+='1';
      N--;
    }
    N/=-2;
    
    //cout<<N<<endl;
  }
  reverse(s.begin(),s.end());
  if(s=="")
    cout<<0;
  else
    cout<<s<<endl;
}

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define ull unsigned long long
#define ld long double

template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) rep2(i, 0, n)
#define rep1(i, n) rep1(i, 1, n + 1)

// #define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
// #define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()  //

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

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

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << std::fixed << std::setprecision(15);
    //    cout << std::setfill('0') << std::setw(2);

    long long N;
    std::cin >> N;
    std::vector<long long> a(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
    }
    sort(all(a), greater<ll>());
    ll ans = 0;
    rep(i, N) {
        if (i % 2 == 0)
            ans += a[i];
        else
            ans -= a[i];
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<cmath>
#define ALL(v) (v).begin(), (v).end()
using namespace std;

void fuga(vector<vector<int> > *result, const vector<int> &a, int rest){
  if(rest == 0){
    (*result).push_back(a);
    return;
  }
  for(int i = a.size() == 0 ? rest : min(rest, a[a.size()-1]); i > 0; i--){
    vector<int> b;
    copy(ALL(a), back_inserter(b));
    b.push_back(i);
    fuga(result, b, rest-i);
  }
}

int main(){
  for(;;){
    int n;
    scanf("%d", &n);
    if(!n) break;
    vector<vector<int> > result;
    vector<int> v;
    fuga(&result, v, n);
    for(auto i : result){
      for(auto j = i.begin(); j < i.end(); j++){
	printf("%d", (*j));
	printf(j+1 == i.end() ? "\n" : " ");
      }
    }
  }
}

Measured memory_bytes: 1420
#include <bits/stdc++.h>
#define rep(i,n) for(long long int i = 0; i < n; i++)
#define _rep(i,m,n) for(long long int i = m; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
const int N = 1000000;
const ll mod = 1000000007;

int main(){
   ll x; cin >> x;
   ll ans = 0;
   while(x >= 500){
      x -= 500;
      ans += 1000;
   }
   while(x >= 5){
      x -= 5;
      ans += 5;
   }
   print(ans);
}

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

int main() {
  int W, H;
  int flg;
  cin >> H >> W;
   vector<vector<char>> A(H,vector<char>(W));
  vector<int> I(H,1);
  vector<int> J(W,1);
  
  for (int i = 0; i < H; i++) {
	for (int j = 0; j < W; j++) {
	  cin >> A.at(i).at(j);
    }
  }

  for (int j = 0; j < W; j++) {
	for (int i = 0; i < H; i++) {
      if (A.at(i).at(j) == '#') {
        J.at(j) = 0;
        break;
      }
    }
  }

  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (A.at(i).at(j) == '#') {
        I.at(i) = 0;
        break;
      }
    }
  }

  for (int i = 0; i < H; i++) {
    flg = 0;
	for (int j = 0; j < W; j++) {
 		if(I.at(i) == 0) {
          if(J.at(j) == 0) {
            cout << A.at(i).at(j);
            flg = 1;
          }
        }
        if (j == (W - 1)) {
          if (flg == 1) {
            cout << endl;
          }
        }
    }
  }
}

Measured memory_bytes: 256
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
            get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get!($($t),*)
        ).collect::<Vec<_>>()
    };
}

enum Res {
    No,
    Mid(i32),
    Res(usize, usize),
}

fn divide(i: usize, p: usize, n: usize, c: i32, t: &Vec<Vec<usize>>) -> Res {
    if i == n {
        return Res::Mid(c);
    }
    for &j in t[i].iter() {
        if j != p {
            match divide(j, i, n, c+1, t) {
                Res::No => (),
                Res::Res(x, y) => return Res::Res(x, y),
                Res::Mid(d) if d/2 == c => return Res::Res(i, j),
                Res::Mid(d) => return Res::Mid(d)
            }
        }
    }
    Res::No
}

use std::ops::Add;

fn count(i: usize, p: usize, t: &Vec<Vec<usize>>) -> i32 {
    t[i].iter().map(|&j| if j == p { 0 } else { count(j, i, t) }).fold(1, Add::add)
}

fn main() {
    let n = get!(usize);
    let mut t = vec![Vec::new(); n];
    for _ in 1..n {
        let (a, b) = get!(usize, usize);
        t[a-1].push(b-1);
        t[b-1].push(a-1);
    }

    if let Res::Res(x, y) = divide(0, n, n-1, 0, &t) {
        if count(x, y, &t) > count(y, x, &t) {
            println!("Fennec");
        } else {
            println!("Snuke");
        }
    }
}

Measured memory_bytes: 21372
#素数列を得る(10007以下)

list = [2]
for j in 3..10007
list.each{|q|
if q*q > j then
list.push(j)
break
end
if (j % q) == 0 then
break
end
}
end

n = gets.to_i
count = 0

n.times{

sample = gets.to_i

list.each{|q|
if q*q > sample then
count += 1
break
end
if (sample % q) == 0 then
break
end
}

}

puts count



Measured memory_bytes: 6868
#include<bits/stdc++.h>
using namespace std;
//HERE NO 2 adjacent vertices should be black and not no 2 adjacent vertices of same color(note)
//so a white can have all the adjacent vertices white or some black,
// for white consider 1)if till that point all the children are white and current is black
//2) some black child has already been encountered,then u dont care what color of current child is i.e add both the possibilities
//3)or all are white
vector<int>v1[1000000];
int mod=1e9+7;
pair<int,int> dfs(int u,int p)
{pair<int,int>p1;long long s1=1,s2=0,s3=0,s4=0;
	for(int i=0;i<v1[u].size();i++)
	{if(v1[u][i]==p)continue;
	pair<int,int>p2=dfs(v1[u][i],u);
	long long y1=p2.first,y2=p2.second;
//	cout<<y1<<" y1_y2 "<<y2<<endl;
	s3=(s1*y2)%mod;
	s4=(s2*((y1+y2)))%mod;
	s2=((s1*y2)%mod+(s2*((y1+y2)))%mod)%mod;

	s1=(s1*y1)%mod;
	//s2=(s2+s1);
//	cout<<s2<<" s2 "<<endl;
	}
	p1.first=(s1+s2)%mod;
	p1.second=s1;
	//cout<<s1<<" pp "<<(s1+s2)<<endl;
//	cout<<p1.first<<" ll "<<p1.second<<" pp "<<u<<endl;
	return p1;
}
int main() {
	
	// your code goes here
	int n,a,b;
	cin>>n;
	for(int i=0;i<n;i++)
	v1[i].clear();
	for(int i=0;i<n-1;i++)
	{cin>>a>>b;
	a--;b--;
	v1[a].push_back(b);
	v1[b].push_back(a);
	}
	int ans=0;
	pair<int,int>p1=dfs(0,-1);
	ans=(p1.first+p1.second)%mod;
cout<<ans<<endl;
	return 0;
}

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

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln "\n"
#define show(x) cout << #x << " = " << x ln
#define dbg(x) cout<<#x"="<<x ln

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > mat;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

ll h, w, n, x, y, ans[10];
// 黒く塗った点の集合
map<pll,bool> m;
// 考慮すべき正方形の左上の座標全て
vector<pll> s;

int main() {
	cin >> h >> w >> n;
	rep(i,n) {
		cin >> y >> x;
		m[mp(x,y)] = true;
		// 点(x,y)を内側に含む正方形は最大9つ考えられる
		// 一番左上の正方形：(x,y)が正方形の右下になる位置
		// 一番右下の正方形：(x,y)が正方形の左上になる位置
		// 地図からはみ出すものは除外してそれぞれの正方形の左上の座標をsに追加しておく 最大9*10^5個
		rep(j,3) {
			rep(k,3) {
				ll xs = x-j, ys = y-k;
				if (1<=xs && xs+2<=w && 1<=ys && ys+2<=h) s.emplace_back(mp(xs, ys));
			}
		}
	}
	// 調べる必要がある正方形が↑で重複するので重複削除
	sort(all(s));
	s.erase(unique(all(s)), s.end());
	ans[0] = (h-2)*(w-2);
	// 上で追加した最大9*10^5個の正方形それぞれを構成している9マスを見ていく
	// その中で黒く塗られている点の数がjだったらans[0]を1個減らしてans[j]に持って来る
	rep(i,s.size()) {
		if (i!=0 && s[i]==s[i-1]) continue;
		int cnt = 0;
		rep(j,3) {
			rep(k,3) {
				if (m[mp(s[i].fi+j, s[i].se+k)]) cnt++;
			}
		}
		ans[0]--;
		ans[cnt]++;
	}
	
	rep(i,10) cout << ans[i] << ln;
}

Measured memory_bytes: 171236
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>


typedef long long ll;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBAC
/*map<Keyの型, Valueの型> 変数名;
queue<型> 変数名;
priority_queue<型> 変数名;
priority_queue<型, vector<型>, greater<型>> 変数名;*/
//copy(v1.begin(), v1.end(), back_inserter(v2));
using namespace std;

int gcd(int a, int b) {
	int c;
	if (a < b) {
		c = a; a = b; b = c;
	}
	while (b != 0) {
		c = a % b; a = b; b = c;
	}
	return a;
}

int sort_greater(int m,int n) {
	vector<int> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end(),greater<int>());
	for (int i = 0; i < n; i++) {
		cout << a[i];
	}
		return 0;
}

int bubblesort(int a[], int n) {
	int sw = 0;
	bool flag = 1;
	for (int i = 0; flag; i++) {
		flag = 0;
		for (int j = n - 1; j >= i + 1; j--) {
			if (a[j] < a[j - 1]) {
				swap(a[j], a[j - 1]);
				flag = 1;
				sw += 1;
			}
		}
	}
	return sw;
}

int a_z()
{
	for (int i = 0; i <= ('Z' - 'A'); i++) {
		cout << (char)('A' + i);
	}
	return 0;
}

int selecttionsort(int a[], int n) {
	int t,sw = 0, minj;
	for (int i = 0; i < n - 1; i++) {
		minj = i;
		for (int j = 0; j < n - 1; j++) {
			if (a[j] < a[minj]) {
				minj = j;
			}
		}
		t = a[i]; a[i] = a[minj]; a[minj] = t;
		if (i != minj) sw += 1;

	}
	return sw;
}

bool is_prime(int x) {
	if (x <= 1) return false;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) return false;
	}
	return true;
}

map<string, int> memo;

using P=pair<int, int>;

struct Clock {
	int hour, minute, second;
	void set(int h, int m, int s) {
		hour = h; minute = m; second = s;
	}
	string to_str() {
		string h, m, s;
		h = to_string(hour);
		m= to_string(minute);
		s= to_string(second);
		if (h.size() < 2) h = "0" + h;
		if (m.size() < 2) m = "0" + m;
		if (s.size() < 2) s = "0" + s;
		return h + ":" + m + ":" + s;
	}
	void shift(int diff_second) {
		int h, m;
		h = diff_second / 3600;
		m = diff_second / 60;
		diff_second %= 60;
		second += diff_second;
		
	}
};


/*void dfs(int v, int p = -1) {
	for (int u : to[v]) {
		if (u == p) continue;
		ans[u] += ans[v];
		dfs(u, v);
	}
}*/
int main() {
	//sort(a.begin(),a.end());
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (to_string(i).size() % 2 == 1) ans++;
	}
	cout << ans;
	return 0;
}









Measured memory_bytes: 256
num = int(input())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
z = list(map(int,input().split()))
val = 0
 
for i in range(num):
    val += y[x[i]-1]
    if 1<=i and x[i]-x[i-1] == 1:
        val += z[x[i]-2]
 
print(val)

Measured memory_bytes: 9084
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

    int H, W, M;
    cin >> H >> W >> M;
    vector<int> cntH(H), cntW(W);
    vector<int> h(M), w(M);
    set<P> st;
    REP(i, M) {
        cin >> h[i] >> w[i];
        h[i]--;
        w[i]--;
        cntH[h[i]]++;
        cntW[w[i]]++;
        st.emplace(h[i], w[i]);
    }
    int maxH = 0, maxW = 0;
    REP(i, H) {
        maxH = max(maxH, cntH[i]);
    }
    REP(j, W) {
        maxW = max(maxW, cntW[j]);
    }
    set<int> vh, vw;
    int res = 0;
    REP(i, H) {
        if (cntH[i] == maxH) {
            vh.emplace(i);
        }
    }
    REP(j, W) {
        if (cntW[j] == maxW) {
            vw.emplace(j);
        }
    }
    vector<vector<int>> existW(H);
    REP(i, M) {
        existW[h[i]].emplace_back(w[i]);
    }
    res = 0;
    for (auto &a : vh) {
        int cnt = 0;
        for (auto &b : existW[a]) {
            cnt += vw.count(b);
        }
        res = max(res, maxH + maxW - (cnt == vw.size()));
    }
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 66560
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int dis(int x,int y)
{
	if(x>=y) return x-y;
	else return y-x;
}
int main()
{
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	if(dis(a,c)<=d||(dis(a,b)<=d&&dis(b,c)<=d)) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int N;
    cin >> N;
    map<int,int>Map;
    for(int i = 2; i*i <= N; i++) {
        while(N%i == 0) {
            N/=i;
            Map[i]++;
        }
    }
    if(N != 1) {
        Map[N]++;
    }
    int ans = 0;
    for(pair<int,int> P:Map) {
        for(int i = 1; i <= P.second; i++) {
            ans++;
            P.second-=i;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAX_N = 110;

int judge_num;
int score[MAX_N];

//---------------------//                                                                                            
int main()
{
        while (cin >> judge_num) {

                if (judge_num == 0) break;

                for(int i = 0; i < judge_num; ++i) {
                        cin >> score[i];
                }

                sort(score, score + judge_num);

                int ave;
                double sum_temp = 0;

                for (int i  = 1; i < judge_num - 1; ++i) {
                        sum_temp += score[i];
                }

                ave = (int)( floor( sum_temp / (judge_num - 2) ) );

                cout << ave << endl;
        }

        return 0;
}

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

int main()
{
  int N;
  cin >> N; 
  vector<int> V(N);
  for (int i = 0; i < N; ++i) 
    cin >> V[i];
  long long s = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = i+1; j < N; ++j) {
      s += V[i]*V[j];
    }
  }
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 256
def call(n):
    i = 1
    while i <= n:
        if i % 3 == 0:
            print(' %d' % i, end='')
        else:
            x = i
            while x > 0:
                if x % 10 == 3:
                    print(' %d' % i, end='')
                    break
                x = int(x/10)
        i += 1
    print('')

line = input()
n = int(line)

call(n)

Measured memory_bytes: 7924
function Main(input) {
    const args = input.split(' ');
	const k = parseInt(args[0], 10);
    const x = parseInt(args[1], 10);
    
    var min = Math.max(-1000000,x-k+1);
    var max = Math.min(1000000,x+k-1);
    var str = "";

    for(var i = min; i <= max; i++){
        if(i == max){
            str += i;
        }else{
            str += i + " ";
        }
    }

    console.log(str);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    int S, W;
    cin >> S >> W;
    if (S > W)
    {
        cout << "safe" << endl;
    }
    else
    {
        cout << "unsafe" << endl;
    }
    return 0;
}

Measured memory_bytes: 3624
from itertools import product
from collections import deque

H, W = [int(i) for i in input().split()]
grid = [list(input()) for _ in range(H)]
reached = [[0] * W for _ in range(H)]

queue = deque()
for y, x in product(range(H), range(W)):
    if grid[y][x] == "#":
        queue.append((y, x, 0))

if len(queue) == H * W:
    print(0)
    exit()

while queue:
    y, x, steps = queue.popleft()
    for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        ny, nx = y + dy, x + dx
        if not (0 <= ny < H and 0 <= nx < W):
            continue
        if reached[ny][nx]:
            continue
        reached[ny][nx] = 1
        queue.append((ny, nx, steps+1))
print(steps)


Measured memory_bytes: 197548
use std::cmp;

fn main() {
    let mut n_1 = String::new();
    std::io::stdin().read_line(&mut n_1).unwrap();
    let _n: i32 = n_1.trim().parse().unwrap();
    
    let mut a_numbers = String::new();
    std::io::stdin().read_line(&mut a_numbers).unwrap();
    let a_vec: Vec<i32> = a_numbers.trim().split_whitespace()
        .map(|x| x.parse().unwrap()).collect();
    
    let mut small: i32 = 1000000001;
    let mut big: i32 = 0;

    for a in a_vec {
        small = cmp::min(small, a);
        big = cmp::max(big, a);
    }
    
    println!("{}", big - small);
}


Measured memory_bytes: 4352
n, m = gets.chomp.split(" ").map(&:to_i)
min = 0
max = n
m.times do |i|
    l, r = gets.chomp.split(" ").map(&:to_i)
    min = [min,l].max
    max = [max,r].min
end
puts [max - min + 1,0].max

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

#define FastRead        ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl            "\n"
#define NUM             100005

const int INF = 1e9+5;

typedef long long ll;

int dp[NUM];

int main()
{
    ll n,k;

    cin>>n>>k;

    int a[n];

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

    for(ll i=0;i<n;i++)
        dp[i] = INF;

    dp[0] = 0;

    for(ll i=0;i<n;++i)
    {
        for(ll j=i+1;j<=i+k;++j)
        {
            if(j<n)
            {
                dp[j] = min(dp[j],dp[i]+abs(a[i]-a[j]));
            }
        }
    }

    cout<<dp[n-1];
}


Measured memory_bytes: 1152
using System;
using System.Linq;
 
namespace workspace{
  class Program{
    static void Main(){
      var S = Console.ReadLine();
      var T = Console.ReadLine();
      var cnt = 0;

      for(int i=0; i<S.Length; i++){
          if(S[i] != T[i]){
              cnt++;
          }
      }
      Console.WriteLine(cnt);
    }
  }
}

Measured memory_bytes: 27524
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstdint>
#include <unordered_set>
#include <ctime>
#include <numeric>
#include <cstdint>

typedef long long int llint;

void solve(){

  int x, y;
  std::cin >> x >> y;

  if(2*x<=y && y<=4*x && y%2==0) std::cout << "Yes" << std::endl;
  else                           std::cout << "No" << std::endl;
  return;
  
}

int main(void){

  solve();
  
  return 0;
}


Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main(void) {
    int X;
    cin >> X;
    if(X >= 30) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


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

int main()
{
  int x, y;
  cin>>x>>y;
  if(y%2==0 && y>= x*2 && y<=x*4) {
    cout<<"Yes\n";
  }
  else
    cout<<"No\n";
  return 0;
}


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

int main()
{
    int a, b, x;
    cin >> a >> b >> x;
    if((a <= x) && (x <= a + b)){
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
    return 0;
}

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

int main() {
  int a,b,c,d;
  cin>>a>>b>>c>>d;

  if (a+b==c+d) cout<<"Balanced"<<endl;
  else if (a+b<c+d) cout<<"Right"<<endl;
  else cout<<"Left"<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int max(int a, int b){return a > b ? a : b;}

int main(void){
	int a, b, c;
	int sum = 0;
	scanf("%d %d %d", &a, &b, &c);
	printf("%d\n", max(a * 10 + b + c, max(b * 10 + a + c, c * 10 + a + b)));
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 100005

using namespace std;

int n,ans;
char s[MAX_N];

int main()
{
	scanf("%s",s+1);
	n=ans=strlen(s+1);
	for(int i=1;i<n;i++) if(s[i]!=s[i+1]) ans=min(ans,max(i,n-i));
	printf("%d\n",ans);
}


Measured memory_bytes: 384
#include <stdio.h>

#define N 2000
#define Q 200

int solve(int, int, int *, int);

int main(){
  int A[N], n, q, i, B[Q];

  scanf("%d", &n);
  for(i = 0; i < n; i++){
    scanf("%d", &A[i]);
  }

  scanf("%d", &q);
  for(i = 0; i < q; i++){
    scanf("%d", &B[i]);
  }

  for(i = 0; i < q; i++){
    if(solve(0, B[i], A, n) == 1) printf("yes\n");
    else printf("no\n");
  }
  return 0;
}

int solve(int i, int m, int *A, int n){
  int res;

  if(m == 0){
    return 1;
  }

  if(i >= n){
    return 0;
  }

  res = solve(i + 1, m, A, n) || solve(i + 1, m - A[i], A, n);

  return res;
}

Measured memory_bytes: 588
// A - Two Rectangles

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

int main() {
	int A, B, C, D;
	cin >> A >> B >> C >> D;

	int ans = max(A * B, C * D);

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define loop(n) for (int ngtkana_is_genius = 0; ngtkana_is_genius < int(n); ngtkana_is_genius++)
#define rep(i, begin, end) for(int i = int(begin); i < int(end); i++)
#define all(v) v.begin(), v.end()
#define lint long long
auto cmn = [](auto& a, auto b){if (a > b) {a = b; return true;} return false;};
auto cmx = [](auto& a, auto b){if (a < b) {a = b; return true;} return false;};
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail){
  std::cerr << " " << head;
  debug_impl(tail...);
}
#define debug(...)\
  std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
  debug_impl(__VA_ARGS__);\
  std::cerr << std::noboolalpha;

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  lint n, k; std::cin >> n >> k;
  if (n == 1) {
    std::cout << 1 << std::endl;
    return 0;
  }
  auto cookie = [&] (lint x, lint y) {
    auto q = y / x;
    auto r = y % x;
    assert(2 <= q);
    auto ret = 1LL;
    loop(r) {
      if (ret > 3 * n / q) return n;
      ret *= q + 1;
    }
    loop(x - r) {
      if (ret > 3 *  n / q) return n;
      ret *= q;
      if (ret > n) return n;
    }
    return ret;
  };
  auto cost = [&] (lint x, lint y)
    { return (x - 1) * k + y; };
  auto check = [&] (lint x, lint y)
    { return n <= cookie(x, y); };
  auto cal = [&] (lint x) {
    lint ok = n;
    lint ng = 2 * x - 1;
    lint y;
    assert(ng <= ok);
    while (ok - ng > 1LL) {
      y = (ok + ng) >> 1;
      if (check(x, y)) ok = y;
      else ng = y;
    }
    y = ok;
    // debug(x, y, cost(x, y));
    return cost(x, y);
  };
  auto ret = 1LL << 60;
  auto x = 1LL, p = 2LL;
  while (p <= n) {
    cmn(ret, cal(x));
    x++, p *= 2;
  }
  std::cout << ret << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
using namespace std;
typedef long long int ll;
static const int MAX_N = 400;
static const int MAX_C = 400;
static const int MAX_B = 400;
static const ll MOD = 1000000007LL;

int N, C;
int A[MAX_N + 1], B[MAX_N + 1];
ll memo[MAX_N + 1][MAX_C + 1], memo2[MAX_C + 1][MAX_B + 1];

int main(){
	scanf("%d %d", &N, &C);
	for(int i = 0; i <= C; i++){
		for(int j = 0; j <= MAX_B; j++){
			if(j == 0) memo2[i][j] = 0;
			else if(i == 0) memo2[i][j] = 1LL;
			else memo2[i][j] = memo2[i - 1][j] * (ll)j;
			memo2[i][j] %= MOD;
		}
	}
	for(int i = 0; i <= C; i++){
		for(int j = 1; j <= MAX_B; j++){
			memo2[i][j] += memo2[i][j - 1];
			memo2[i][j] %= MOD;
		}
	}
	for(int i = 1; i < N + 1; i++) scanf("%d", &A[i]);
	for(int i = 1; i < N + 1; i++) scanf("%d", &B[i]);
	for(int i = 0; i < N + 1; i++){
		for(int j = 0; j < C + 1; j++){
			if(i == 0 && j == 0) memo[i][j] = 1LL;
			else if(i > 0){
				for(int k = j; k >= 0; k--){
					memo[i][j] += (memo[i - 1][k] * (memo2[j - k][B[i]] - memo2[j - k][A[i] - 1])) % MOD;
					memo[i][j] %= MOD;
					if(memo[i][j] < 0) memo[i][j] += MOD;
				}
			}
		}
	}
	printf("%lld\n", memo[N][C]);
	return 0;
}

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

#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)


using namespace std;
using ll = long long;

void solve() {
    int k;
    cin >> k;
    int ans = 0;
    for (int i = 1; i < k + 1; ++i) {
        for (int j = 1; j < k + 1; ++j) {
            for (int l = 1; l < k + 1; ++l) {
                ans += gcd(i, gcd(j, l));
            }
        }
    }
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);

    solve();
    return 0;
}


Measured memory_bytes: 3636
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 inf = 1_001_001_001;
enum inf6 = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;

void main() {
    string s;
    scan(s);
    auto n = s.length.to!int;
    writeln(repeat("x", n).joiner);
}










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: 256
#include<iostream>
#include<vector>
#include<string>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= (int)end; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return 0;}
template<typename T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return 0;}

const int MOD = 998244353;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, X;
    cin >> N >> X;
    vector<vector<int>> prev(X + 1, vector<int>(1 << 9, 0));
    vector<vector<int>> dp(X + 1, vector<int>(1 << 9, 0));
    prev[0][0] = 1;
    rep(i, 1, N + 1) {
        rep(k, 0, 1 << 9) {
            int cumsum = 0;
            rep(j, 0, X + 1) {
                cumsum = (cumsum + prev[j][k]) % MOD;
                dp[j][k ^ j] = (dp[j][k ^ j] + cumsum) % MOD;
            }
        }
        prev = dp;
        rep(j, 0, X + 1) rep(k, 0, 1 << 9) {
            dp[j][k] = 0;
        }
    }
    int ans = 0;
    rep(i, 0, X + 1) {
        ans = (ans + prev[i][X]) % MOD;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5000
import sys

input = sys.stdin.readline

def main():
    ans = 0
    n, d = map(int, input().split())
    for i in range(n):
        x,y = map(int, input().split())
        if (x**2+y**2)**0.5 <= d:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 9644
/*
g++ -std=c++14 -o2 -Wall ABC120B.cpp -o .\out\ABC120B.out
.\out\ABC120B.out
*/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
//  freopen("./input/input.txt", "r", stdin);
  ios::sync_with_stdio(0);
  cin.tie(0);
  int a, b, k;
  cin >> a >> b >> k;
  int cnt = 0;
  for (int i = 100; i >= 1; --i) {
    if (a % i == 0 && b % i == 0) ++cnt;
    if (cnt == k) {
      cout << i << "\n";
      return 0;
    }
  }
}


Measured memory_bytes: 256
/* 2029 = 
	1 ツつェツ鳴ウツつ「ツづつォツ閉・ツつヲツづ按つ「 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
#include <set>
#include <cstring>
using namespace std;

typedef pair<int,int> NODE;
#define sum first
#define depth second

int main(){
	int n;
	int count=0;
	unsigned int memo[50001];
	while(cin >> n, n){
		cout << "Case #" << ++count << ": ";
		bool cant = true;
		vector<int> data(n);
		int maxPrice = 0;
		for(int i=0;i<n;i++){
			cin >> data[i];
			maxPrice += data[i];
			if(data[i]==1)cant=false;
		}
		if(cant){
			cout << "Cannot pay some amount" << endl;
			continue;
		}
		sort(data.begin(),data.end(),greater<int>());

		queue<NODE> Q;
		memset(memo,-1,50001*4);
		memo[0] = 0;
		
		NODE p = make_pair(0,0);
		Q.push(p);
		
		while(Q.size()){
			NODE q = Q.front();Q.pop();
			
			for(int i=0;i<n;i++){
				NODE next;
				next.sum = q.sum + data[i];
				next.depth = q.depth + 1;
				if(next.sum > 50000)continue;
				//if(next.depth >= r )continue;
				if((unsigned)next.depth >= memo[next.sum])continue;
				Q.push(next);
				memo[next.sum] = next.depth;
			}
		}
		
		for(int price=1;price<=maxPrice;price++){
			int t = price,r=0;
			for(int i=0;i<n;){
				if(t >= data[i]){
					t-=data[i];
					r++;
				}else{	
					i++;
				}
			}
			if(r>memo[price])cant = true;
		}
		cout << (cant?"Cannot use greedy algorithm":"OK") << endl;
		
	}
}

Measured memory_bytes: 1124
N,K = map(int, input().split())
XY = [tuple(map(int, input().split())) for _ in range(N)]

Xs = set()
Ys = set()
for x,y in XY:
    Xs.add(x)
    Ys.add(y)


Xs = list(Xs)
Xs.sort()

Ys = list(Ys)
Ys.sort()

LX = len(Xs)
LY = len(Ys)
ans = 10**20

for i in range(LX):
    for j in range(i+1, LX):
        for k in range(LY):
            for l in range(k+1, LY):
                cnt = 0
                for x,y in XY:
                    if Xs[i] <= x <= Xs[j] and Ys[k] <= y <= Ys[l]:
                        cnt += 1

                if cnt >= K:
                    ans = min(ans, (Xs[j] - Xs[i])*(Ys[l] - Ys[k]))


print(ans)

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

int main(){
    long MOD = 1000000007;
    int N;
    cin >> N;
    long long yakusuu[N+1] = {0};
    for(int j=1;j<N+1;j++){
        int M = j;
        while(M > 1){
            for(int i=2;i<M+1;i++){
                if(M%i == 0){
                    yakusuu[i]++;
                    M = M/i;
                    break;
                }
            }
        }
    }
    long long ans = 1;
    for(int i=0;i<N+1;i++){
        ans = (ans*(yakusuu[i]+1))%MOD;
        //cout << yakusuu[i] << " " << ans << endl;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
n = gets.to_i

max = 0

smaller = []

gets.split.each{|x|
    color = x.to_i / 400
    if color >= 8 then
        max += 1
    else
        smaller.push(color)
    end
}

min = smaller.sort.uniq.length
max += min

min = 1 if min == 0

printf("%d %d\n", min, max)

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[]) {
  int a[100],N,cnt=0;
  bool flg=1;
  int i=0;
  cin>>N;
  for (int i = 0; i < N; i++) {
    cin>>a[i];
  }
  while (flg) {
    flg=0;
    for(int j=N-1;j>=i+1;j--){
      if(a[j]<a[j-1]){
        swap(a[j],a[j-1]);
        flg=1;
        cnt++;
      }
    }
    i++;
  }
  for (int i = 0; i < N; i++) {
    if(i!=N-1)  cout << a[i] << ' ';
    else  cout << a[i];
  }
  cout <<'\n'<< cnt << '\n';
  return 0;
}



Measured memory_bytes: 3088
#include<bits/stdc++.h>
#define N 100005
#define MO 1000000007
using namespace std;
int n,m,K;
vector<int>P[N];
int dfs(int p,int lastt,int lt){
	int k=P[p].size();
	if(lastt!=0)k--;
	int res=1;
	for(int i=1;i<=k;i++)res=1LL*res*(K-lt-i)%MO;
	for(int i=0;i<P[p].size();i++){
		int y=P[p][i];
		if(y==lastt)continue;
		res=(1LL*res*dfs(y,p,1)%MO);
	}
	return res;
}
void solve(){
	scanf("%d %d",&n,&K);
	for(int a,b,i=1;i<n;i++){
		scanf("%d %d",&a,&b);
		P[a].push_back(b);
		P[b].push_back(a);
	}
	int ans=1LL*dfs(1,0,0)*K%MO;
	printf("%d\n",ans);
}
int main(){
	solve();
	return 0;
}

Measured memory_bytes: 11520
#include <iostream>
#include <math.h>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;
#define n_max 1000

int main()
{
    string str;
    
    cin >> str;
    
    int A = str.find("A");
    int Z = str.rfind("Z");

    cout << Z - A + 1<< endl;

    return 0;
}


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

#define F first
#define S second
#define pb push_back
#define ll long long
//#define int long long 

using namespace std ;

const int MAXN =8001 ; 


int ask(int x , int y )
{
	if(x==y)
		return 1 ;
	cout << "? " << x << ' ' << y << endl ;
	string ans ; 
	cin >> ans ; 
	return ans=="Y" ; 
}

int mark[MAXN]  , n  ; 

void Solve(int x)
{
	for(int i = 0 ; i < n ; i ++ ) 
		mark[i] = ask(x,i);
	cout << "! " ; 
	for(int i = 0 ; i < n ; i ++ ) 
		cout << mark[i] ; 
	cout << endl ; 
}

void solve(vector<int> v , int a , int b)
{
	int N = n; 
	if(!b)
	{
		cout << "! " ;
		for(auto u : v )
			mark[u] = 1 ;
		for(int i = 0 ; i < n ; i ++ ) 
			cout << mark[i] ; 
		cout << endl ; 
	}
	random_shuffle(v.begin(),v.end()) ; 
	
	vector<int> V; 
	
	for(auto u : v)
	{
		if(!V.size())
		{
			V.pb(u) ; 
			continue ; 
		}
		int x = V.back() ; 
		if(!ask(x,u))
		{
			V.pop_back(); 
			continue ; 
		}
		V.pb(u) ;
	}
	Solve(V.back()) ; 
}

int32_t main()
{
	ios::sync_with_stdio(0) ; cin.tie(0) ; 
	int a , b ; 
	cin >> a >> b ;
	n = a + b; 
	if(a<=b)
		return cout << "Impossible" << endl , 0 ; 
	int n = a + b ; 
	vector<int> v ; 
	for(int i = 0 ; i < n ; i ++ ) v.pb(i) ; 
	solve(v,a,b) ; 

}

Measured memory_bytes: 852
#include <set>
#include <map>
#include <unordered_map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double EPS = 1e-9;
const double INF = 2147483647;
#define rep(i, n) REP(i, 0, n)
#define rep2(i, n) REP(i, 1, n+1)
#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rrep(i, n) RREP(i, 0, n)
#define RREP(i, x, n) for(int i = (int)(n) - 1 - (int)(x); i >= 0; i--)

template<class T>
void printv(vector<T> v) {
    for(auto it = v.begin(); it != v.end(); it++){
        cout << *it << ",";
    }
    cout << endl;
}


int main() {
    int N;
    ll res = 1;
    cin>>N;
    vector<ll> v(N);
    rep(i,N) cin>>v[i];
    sort(v.begin(),v.end());
    rep(i,N){
        if (v[i] != 0 && res >= std::numeric_limits<ll>::max()/v[i]) {
            cout << -1;
            return 0;
        }
        res *= v[i];
        // cout << res << endl;
        // cout << 1000000000000000000 << endl;
        if (res > 1000000000000000000) {
            cout << -1;
            return 0;
        }
        //cout << res << endl;
    }
    cout << res;
    
    return 0;
}

Measured memory_bytes: 4052
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N, M, X;
  cin >> N >> M >> X;
  vector<int> A(M);
  for (int i = 0; i < M; i++)
    cin >> A[i];
  int low = lower_bound(A.begin(), A.end(), X) - A.begin();
  int high = M - low;
  cout << min(low, high) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

int main(){
     int n;
     int num;
     cin >> n;
     int MAX=0,MIN=1001;
     for (int i=1;i<=n;i++){
          cin >> num;
          MAX = max(num,MAX);
          MIN  = min(num,MIN);
     }
     cout << MAX-MIN;
     return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    int n; scanf("%d", &n);
    int arr[50] = {0};
    for(int i=1; i<=n; i++)
        scanf("%d", &arr[i]);
    int count=0;
    for(int i=2; i<=n-1; i++)
    {
        if((arr[i]<arr[i-1] && arr[i]>arr[i+1]) || (arr[i]>arr[i-1] && arr[i]<arr[i+1]))
            count++;
    }
    printf("%d\n", count);
    return 0;
}

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

int main() {
  int x, y, a, b, c; cin >> x >> y >> a >> b >> c;
  vector<long long> p(a), q(b), r(c);
  for(int i = 0; i < a; i++) cin >> p.at(i);
  for(int i = 0; i < b; i++) cin >> q.at(i);
  for(int i = 0; i < c; i++) cin >> r.at(i);
  sort(p.rbegin(), p.rend());
  sort(q.rbegin(), q.rend());
  sort(r.rbegin(), r.rend());
  int i = 0, j = 0, k = 0, l = 0;
  long long out = 0;
  while(l < x + y){
    long long tmp;
    int ind;
    if(i >= x){
      tmp = q.at(j);
      ind = 2;
    }else if(j >= y){
      tmp = p.at(i);
      ind = 1;
    }else if(p.at(i) > q.at(j)){
      tmp = p.at(i);
      ind = 1;
    }else{
      tmp = q.at(j);
      ind = 2;
    }
    if(k < c){
    if(tmp < r.at(k)){
      out += r.at(k);
      k++;
    }else{
      out += tmp;
      if(ind == 1){
        i++;
      }else{
        j++;
      }
    }
    }else{
      out += tmp;
      if(ind == 1){
        i++;
      }else{
        j++;
      }
    }
    l++;
  }
  cout << out;
}

Measured memory_bytes: 2560
MOD = 998244353
n, k = map(int, input().split())
l, r = [0]*k, [0]*k
for i in range(k):
    _l, _r = map(int, input().split())
    l[i], r[i] = _l, _r
dp, dpsum = [0]*(n+1), [0]*(n+1)
dp[1], dpsum[1] = 1, 1
for i in range(2, n+1):
    for j in range(k):
        li = i - r[j]
        ri = i - l[j]
        if ri<0: continue
        li = max(li, 1)
        dp[i] += dpsum[ri] - dpsum[li-1]
        dp[i] %= MOD
    dpsum[i] = dpsum[i-1] + dp[i]
print(dp[n])


Measured memory_bytes: 27892
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) (v.begin(),v.end())
#define ff first
#define ss second
const ll maxn=2e5+10;
const ll mod=1e9+7;


int main() {
  	fast;
  	ll n,m,i,j,k;
  	cin>>n>>m;
  	ll a[m];
  	ll s=0;
  	for(i=0;i<m;i++)
	{
		cin>>a[i];
		s+=a[i];
	}
	if(s>n)
		cout<<"-1";
	else
		cout<<(n-s);
}

Measured memory_bytes: 3724