akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main()
{
  string s;
  int k;
  cin >> s >> k;
  int n = s.size();
  long long len = 1LL * n * k, i = 0, op = 0;
  vector<long long> f(n, -1), id(n, -1);
  int found = 0;
  while (i + 1 < len)
  {
    if (!found && f[i % n] >= 0)
    {
      long long cycle = (i - id[i % n]) / n;
      long long repeat = (k - 1 - i / n) / cycle;
      op += (op - f[i % n]) * repeat;
      i += (i - id[i % n]) * repeat;
      found = 1;
      if (i + 1 >= len)
        break;
    }
    else
    {
      f[i % n] = op;
      id[i % n] = i;
    }

    if (s[i % n] == s[(i + 1) % n])
    {
      op++;
      i += 2;
    }
    else i++;
  }

  cout << op << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
 
int main(){
 int H,A;
 cin >> H >> A;
  vector<int> vec(A);
  int num=0;
 rep(i,A){
   cin >> vec[i];
   num+=vec[i];
 }
  if(num>=H){
  cout <<  "Yes" << endl;
  }
  else cout << "No" << endl;
}

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

int main(int argc, char** argv){
  int n, a;
  int max = 100;
  int min = -100;
  int sum = 0;
  int a_a = 0;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> a;
    sum += a;
    a_a += a*a;
  }
  for(int i = 0; i < 1000; i++){
    if(max*(max*n - 2*sum) <= min*(min*n - 2*sum)) {
      min = (max + min)/2;
    }
    else {
      max = (max + min) / 2;
    }
  }
  int large = max*max*n - 2*max*sum + a_a;
  int small = min*min*n - 2*min*sum + a_a;
  if (large<small) cout << large;
  else cout << small;
  return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
)

func main() {
	n := nextInt()
	v := nextInts(n)
	c := nextInts(n)
	// vx := make([]pair, n)
	// for i := 0; i < n; i++ {
	// 	vx[i].a = v[i]
	// 	vx[i].b = c[i]
	// }
	// sort.Sort(pairs(vx))
	var ans int
	for i := 0; i < pow(2, 20); i++ {
		var x, y int
		var j uint
		for j = 0; j < uint(n); j++ {
			if (1<<j)&i > 0 {
				x += v[j]
				y += c[j]
			}
		}
		// log.Println(x - y)
		ans = max(ans, x-y)
	}
	fmt.Println(ans)
}

var dy = []int{1, 0, -1, 0, 0}
var dx = []int{0, 1, 0, -1, 0}
var inf = int(1e9)

func pow(a, b int) int {
	return int(math.Pow(float64(a), float64(b)))
}

func lcm(a, b int) int {
	return a * b / gcd(a, b)
}
func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
func max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}
func min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}
func sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

type pair struct {
	a, b int
}

type pairs []pair

func (p pairs) Len() int {
	return len(p)
}
func (p pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

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

var nextReader func() []byte

func init() {
	nextReader = newScanner()
	log.SetFlags(log.Lshortfile)
}

func newScanner() func() []byte {
	r := bufio.NewScanner(os.Stdin)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)
	return func() []byte {
		r.Scan()
		return r.Bytes()
	}
}
func nextBytes() []byte {
	return nextReader()
}

func nextString() string {
	return string(nextReader())
}
func nextInt64() int64 {
	v, _ := strconv.ParseInt(string(nextReader()), 10, 64)
	return v
}
func nextInt() int {
	v, _ := strconv.Atoi(string(nextReader()))
	return v
}
func nextInts(n int) []int {
	r := make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}
func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(string(nextReader()), 64)
	return f
}


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<algorithm>
#include<utility>
#include<map>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const int INF = 1001001001;

ll pow_mod(ll p, ll n, ll m) {
	if (n == 0) return 1;
	else if (n == 1) return p % m;
	else if (n % 2 == 1) return p * pow_mod(p, n - 1, m) % m;
	else {
		ll tmp = pow_mod(p, n / 2, m);
		return (tmp * tmp) % m;
	}
}

ll gcd(ll x, ll y) {
	if (y == 0) {
		return x;
	}
	return gcd(y, x % y);
}

ll com_mod(ll n, ll k, ll m) {
	if (k == 0) return 1;
	else {
		ll x = 1;
		ll y = 1;
		for (ll i = 0; i < k; i++) {
			x = (x * (n - i)) % m;
			y = (y * (i + 1)) % m;
		}
		ll res = (x * pow_mod(y, m - 2, m)) % m;
		return res;
	}
}

int main() {
	int x, a, b; cin >> x >> a >> b;
	cout << (abs(x - a) < abs(x - b) ? 'A' : 'B') << endl;
	return 0;
}

Measured memory_bytes: 3584
import sys
if __name__ == '__main__':
    lines = sys.stdin.readlines()
    line = [a.strip('\n').split(' ') for a in lines]
    # print(line)
    right = []
    left = []
    count = 0

    for i,v in enumerate(line):
        if i == 0:
            st = v
        if i == 1:
            q = v
        if i >= 2:
            if len(v)==3:
                for j,k in enumerate(v):
                    if j == 1:
                        ichi = int(k)
                    if j==2:
                        alp = k
                if count%2 == 0:
                    if ichi == 1:
                        left.append(alp)
                        # print('left'+str(left))
                    if ichi == 2:
                        right.append(alp)
                        # print('right'+str(right))
                else:
                    if ichi == 1:
                        right.append(alp)
                        # print('right'+str(right))
                    if ichi == 2:
                        left.append(alp)
                        # print('left' + str(left))

            if len(v)==1:
                count += 1
    
    # print(left)
    # print(right)
    b = list(st[0])
    # print(list(st[0]))
    # print(b)
    # print(count)
    if count%2 == 0:
        d = list(reversed(left))+b+right
    if count%2 == 1:
        d = list(reversed(right))+list(reversed(b))+left
    print(''.join(d))

Measured memory_bytes: 58952
#include <bits/stdc++.h>
 
using namespace std;
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i< (int) n; i++)
 
 
int main () {
    int N,T,A,H;
    
    cin >> N >> T >> A;

    int ans = 0;
    int cc = 1 << 30;

    repr(i,1,N+1){
        cin >> H;

        int d = abs((T*1000 - H*6)- A*1000);
        if(cc>d){
            cc = d;
            ans = i;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
from math import sqrt
from itertools import combinations

n = int(input())
if int(sqrt(2 * n)) * (int(sqrt(2 * n)) + 1) != 2 * n:
	print("No")
else:
	print("Yes")
	k = int(sqrt(2 * n)) + 1
	print(k)
	ans = [[] for _ in range(k)]
	num = 1
	for p in combinations(range(k), r=2):
		#print(p[0], p[1])
		ans[p[0]].append(num)
		ans[p[1]].append(num)
		num += 1
	for i in range(k):
		ans[i] = [k-1] + ans[i]
		print(*ans[i])


Measured memory_bytes: 9480
#include<bits/stdc++.h>
using namespace std;
int main(){
  int64_t n;
  cin>>n;
  int64_t p=26;
  int d=1;
  while(n>0){
    if(n<=p)
      break;
    n-=p;
    p*=26;
    d++;
  }
  n--;
  string s;
  for(int i=0;i<d;i++){
    s+=((char)(n%26)+'a');
    n/=26;
  }
  reverse(s.begin(),s.end());
  cout<<s<<endl;
}

Measured memory_bytes: 3624
#include <iostream>
#define SIZE 8

void threaten(int board[][SIZE], int x, int y)
{
	for (int i=0; i<SIZE; i++) {
		board[i][y]++; board[x][i]++;
	}
	for (int i=-x; i<SIZE-x; i++) {
		if (0 <= y+i && y+i < SIZE) board[x+i][y+i]++;
		if (0 <= y-i && y-i < SIZE) board[x+i][y-i]++;
	}
	board[x][y]+=100;
}

void unthreaten(int board[][SIZE], int x, int y)
{
	for (int i=0; i<SIZE; i++) {
		board[i][y]--; board[x][i]--;
	}
	for (int i=-x; i<SIZE-x; i++) {
		if (0 <= y+i && y+i < SIZE) board[x+i][y+i]--;
		if (0 <= y-i && y-i < SIZE) board[x+i][y-i]--;
	}
	board[x][y]-=100;
}

bool solve(int board[][SIZE], int rest)
{
	if (rest==0) return true;
	
	for (int i=0; i<SIZE; i++) {
		for (int j=0; j<SIZE; j++) {
			if (board[i][j]>0) continue;
			threaten(board, i, j);
			if (solve(board, rest-1)) return true;
			unthreaten(board, i, j);
		}
	}
	return false;
}

int main()
{
	int board[SIZE][SIZE];
	for (int i=0; i<SIZE; i++) {
		for (int j=0; j<SIZE; j++) board[i][j] = 0;
	}
	
	int k; std::cin >> k;
	for (int i=0; i<k; i++) {
		int x, y;
		std::cin >> x >> y;
		threaten(board, x, y);
	}
	
	solve(board, SIZE-k);
	
	for (int i=0; i<SIZE; i++) {
		for (int j=0; j<SIZE; j++) {
			if (board[i][j] < 100) std::cout << ".";
			else std::cout << "Q";
		}
		std::cout << std::endl;
	}
	
	return 0;
}



Measured memory_bytes: 3104
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define FOR(i,k,n) for(int(i)=(k);(i)<(n);++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v),end(v)
#define debug(x) std::cerr<<#x<<": "<<x<<"\n"
#define debug2(x,y) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<"\n"
#define debug3(x,y,z) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<", "<<#z<<": "<<z<<"\n"

using ll=long long;
using vi=std::vector<int>;
using vvi=std::vector<vi>;
using vll=std::vector<ll>;
using vvll=std::vector<vll>;
template<typename T> using vvec=std::vector<std::vector<T>>;
template<typename T>
auto make_v(size_t sz){return std::vector<T>(sz);}
template<typename T,typename... Ts>
auto make_v(size_t sz,Ts...ts){return std::vector<decltype(make_v<T>(ts...))>(sz,make_v<T>(ts...));}
template<typename T>
void fill_v(T&var,const T&x){var=x;}
template<typename V,typename T>
void fill_v(V&v,const T&x){for(auto&& w:v){fill_v(w,x);}}

template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<std::vector<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<std::deque<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s, const std::set<T>&v){
  s<<"\n";for(auto&& elm:v){s<<elm<<"\t";}s<<"\n";return s;}

inline void scan(int&a){scanf("%d",&a);}
inline void scan(ll&a){scanf("%lld",&a);}
inline void scan(char&a){scanf(" %c",&a);}
inline void scan(double&a){scanf("%lf",&a);}
inline void scan(std::string&s){char BUF[3000000];scanf(" %s",BUF);s=std::string(BUF);}
template<typename T>
inline void scan(std::vector<T>&v){for(auto&& sv:v){scan(sv);}}
template<typename First,typename...Args>
inline void scan(First&f,Args&...args){scan(f);scan(args...);}
inline void print(int a){printf("%d\n",a);}
inline void print(ll a){printf("%lld\n",a);}
inline void print(double a){printf("%.12f\n",a);}
inline void print(std::string s){std::cout<<s<<"\n";}

using namespace std;

int main() {
  string s;
  scan(s);
  sort(all(s));
  if (s[0] == s[1] && s[1] != s[2] && s[2] == s[3]) {
    print("Yes");
  } else {
    print("No");
  }
  return 0;
}


Measured memory_bytes: 888
import sys

lines = 1
inp = list()

for _ in range(lines):
    inp.append(sys.stdin.readline().strip())


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def lcm(x, y):
    return x * y // gcd(x, y)


lst = [int(i) for i in inp[0].split()]

a = lst[0]
b = lst[1]
c = lst[2]
d = lst[3]

# cを小さくする
if c > d:
    c, d = d, c

size = b - a + 1

c_size = b // c + (-a // c) + 1
d_size = b // d + (-a // d) + 1
cd_lcm = lcm(c, d)
cd_size = b // cd_lcm + (-a // cd_lcm) + 1

print(size - c_size - d_size + cd_size)


Measured memory_bytes: 3064
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <random>
#include <chrono>

#define _ << " " <<
#define all(v) v.begin(), v.end()
#define sp(n) fixed << setprecision(n)
#define ff first
#define ss second

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll mod = 1e9 + 7;
const double eps = DBL_EPSILON;

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		if (to_string(i).size() % 2) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
 
// Remove GCC optimizer for codechef
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
using namespace __gnu_pbds;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define endl "\n"
#define int long long
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
const int INF = 1e16;
const double PI = acos(-1);
const int N = 1e6 + 7;
int mod = 998244353;

int dp[102][100002];
vector<vector<int>> in;

int32_t main()
{
    IOS;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int n, W;
    cin >> n >> W;
    int sumv = 0;
    for(int i = 1; i <= n; i++)
    {
        int w, v;
        cin >> w >> v;
        in.pb({w, v});
        sumv += v;
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j <= sumv; j++)
            dp[i][j] = INF;
    for(int i = 0; i < n; i++)
        dp[i][0] = 0;
    for(int i = 1; i <= in[0][1]; i++)
        dp[0][i] = in[0][0];
    for(int i = 1; i < n; i++)
        for(int j = 0; j <= sumv; j++)
            dp[i][j] = min(dp[i-1][j], (j >= in[i][1] ? dp[i-1][j-in[i][1]] : 0) + in[i][0]);
    int ans;
    for(int i = sumv; i >= 0; i--)
        if(dp[n-1][i] <= W)
        {
            ans = i;
            break;
        }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 78336
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back
 
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<vector<int> > VVI;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<bool> VB;
 
int main() {
    int n;
    cin >> n;
    VI a(n,0);
    a[0] = 0;
    int k;
    rep(i,n-1) {
        cin >> k;
        a[k-1]++;
    }

    rep(i,n) {
        cout << a[i] << endl;
    }

}

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

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

    int x;
    cin >> x;

    if (x < 1200)
        cout << "ABC" << '\n';
    else
        cout << "ARC" << '\n';
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
struct node{
	char s[110];
	int x;
	int poi;
}a[110];
int n;
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%s%d",a[i].s,&a[i].x);
		a[i].poi=i+1;
	}
	for(int i=0;i<n-1;i++){
		for(int j=0;j<n-1-i;j++){
			if(strcmp(a[j].s,a[j+1].s)>0){
				struct node temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
			else if(strcmp(a[j].s,a[j+1].s)==0){
				if(a[j].x<a[j+1].x){
					struct node temp=a[j];
					a[j]=a[j+1];
					a[j+1]=temp;
				}
			}
		}
	}
	for(int i=0;i<n;i++)
		printf("%d\n",a[i].poi);	
}

Measured memory_bytes: 256
using System;

class Program{
    static bool solve(int remain, int[] A, int i){
        return remain==0 || (i<A.Length && (
            solve(remain-A[i], A, i+1) ||
            solve(remain, A, i+1)));
    }

    public static void Main(){
        var n=int.Parse(Console.ReadLine());
        var s=Console.ReadLine().Split(' ');
        var A=new int[n];
        for(var i=0; i<n; i++){
            A[i]=int.Parse(s[i]);
        }
        var q=int.Parse(Console.ReadLine());
        s=Console.ReadLine().Split(' ');
        for(var i=0; i<q; i++){
            var Mi=int.Parse(s[i]);
            if(solve(Mi, A, 0)){
                Console.WriteLine("yes");
            } else{
                Console.WriteLine("no");
            }
        }
    }
}

Measured memory_bytes: 9036
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	w,h,n = readline() |> split |> parseMap
	lx = 0
	rx = w
	ly = 0
	ry = h
	for i in 1:n
		x,y,a = readline() |> split |> parseMap
		if a==1
			lx = max(lx,x)
		elseif a==2
			rx = min(rx,x)
		elseif a==3
			ly = max(ly,y)
		else
			ry = min(ry,y)
		end
	end
	println(max(rx-lx,0)*max(ry-ly,0))
end

main()

Measured memory_bytes: 111780
def ans():
  H, W = map(int,input().split())
  HW = [input() for _ in range(H)]
  HW = ["".join(hw) for hw in zip(*HW) if hw.count("#") > 0]
  HW = ["".join(hw) for hw in zip(*HW) if hw.count("#") > 0]
  print("\n".join(HW))
ans()

Measured memory_bytes: 3060
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int N = 2005;
int a[N],d[N];
ll f[N][N];
bool cmp(int x,int y)
{
	return a[x] > a[y];
}
int main()
{
	int n;scanf("%d",&n);
	for(int i = 1;i <= n;++i)	scanf("%d",&a[i]),d[i] = i;
	sort(d+1,d+n+1,cmp);
	
	for(int l = 0;l <= n;++l)
	{
		for(int r = 0;l + r <= n;++r)
		{
			int k = l + r;
			if(l)	f[l][r] = max(f[l][r],f[l - 1][r] + a[d[k]] * abs(d[k] - l));
			if(r)   f[l][r] = max(f[l][r],f[l][r - 1] + a[d[k]] * abs(d[k] - n + r - 1));
		}
	}
	ll res = 0;
	for(int i = 0;i <= n;++i)
		res = max(res,f[i][n - i]);
	printf("%lld",res);
    return 0;
}


Measured memory_bytes: 25864
// https://atcoder.jp/contests/abc109/tasks/abc109_b
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <set>
#include <unordered_set>
#include <bitset>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define REP(i, n) for(size_t i = 0; i < (n); ++i)

int main()
{
    int N;
    cin >> N;
    map<string, int> dic;
    vector<string> vec(N);
    REP(i, N)
    {
        cin >> vec[i];
    }
    REP(i, N)
    {
        ++dic[vec[i]];
        if (dic[vec[i]] > 1)
        {
            cout << "No" << endl;
            return 0;
        }
    }
    for (int i = 1; i < N; ++i)
    {
        if (vec[i].front() != vec[i - 1].back())
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b){
  if(a%b==0) return b;
  return gcd(b, a%b);
}

int main(){
  int n, m;  cin >> n >> m;
  vector<ll> box(n, 1);
  vector<bool> place(n, false);
  place[0] = true;

  for(int i=0; i<m; i++){
    int x, y;  cin >> x >> y;
    x--; y--;
    box[x] -= 1;
    box[y] += 1;
    if(place[x]){
      place[y] = true;
      if(box[x]==0) place[x] = false;
    }
  }
  int cnt=0;
  for(int i=0; i<n; i++)
    if(place[i]) cnt += 1;
   cout << cnt << endl;
  
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define sz(c) (int)(c).size()
#define ALL(c) (c).begin(), (c).end()

void dfs (int x, int p, const vvi &g, vi &h, vvi &dp, int k)
{
    h[x] = 0;
    int sons = 0;

    for (int dest : g[x])
    if (dest != p)
    {
        dfs(dest, x, g, h, dp, k);
        h[x] = max(h[x], h[dest] + 1);
        sons++;
    }

    dp[x].resize(min(h[x] + 1, k + 1));
    dp[x][0] = 1;

    if (sons >= 1)
    {
        for (int dest : g[x])
        if (dest != p)
        {
            for (int h1 = 0; h1 < k && h1 < sz(dp[dest]); h1++)
                dp[x][h1 + 1] = max(dp[x][h1 + 1], dp[dest][h1] + 1);
        }

        for (int i = 1; i < sz(dp[x]); i++)
            dp[x][i] = max(dp[x][i], dp[x][i - 1]);

        if (sons == 1)
            return;
    }

    for (int h2 = 0; h2 < k; h2++)
    {
        int cur = 1;

        for (int dest : g[x])
        if (dest != p)
            cur += dp[dest][min(sz(dp[dest]) - 1, h2)];

        for (int who : g[x])
        if (who != p)
        for (int h1 = h2; h1 < sz(dp[who]) && h1 < k && h1 + h2 + 2 <= k; h1++)
        {
            cur -= dp[who][min(sz(dp[who]) - 1, h2)];
            cur += dp[who][min(sz(dp[who]) - 1, h1)];
            dp[x][h1 + 1] = max(dp[x][h1 + 1], cur);
            cur -= dp[who][min(sz(dp[who]) - 1, h1)];
            cur += dp[who][min(sz(dp[who]) - 1, h2)];
        }
    }

    for (int i = 1; i < sz(dp[x]); i++)
        dp[x][i] = max(dp[x][i], dp[x][i - 1]);

//    cerr << x << " : ";
//    for (int i = 0; i < sz(dp[x]); i++)
//        cerr << dp[x][i] << ' ';
//    cerr << endl;
}

void solve (int n)
{
    vvi g(n);
    int k;
    cin >> k;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].pb(b);
        g[b].pb(a);
    }

    vvi dp(n);
    vi h(n);
    dfs(0, -1, g, h, dp, k);

    int ans = 0;
    for (const vi &cur : dp)
        ans = max(ans, *max_element(ALL(cur)));
    cout << n - ans << endl;
}

int main()
{
    #ifndef ONLINE_JUDGE
 //   freopen("input.txt", "rt", stdin);
 //   freopen("output.txt", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    while (cin >> n)
        solve(n);
}


Measured memory_bytes: 5888
def solve():
    n, w = map(int, input().split())
    items = [list(map(int, input().split())) for _ in range(n)]
    
    dp = [[float("inf") if i != 0 else 0 for i in range(w+1)] for j in range(n+1)]
    for i in range(w+1):
        dp[0][i] = 0

    for j in range(1, n+1):
        for k in range(1, w+1):
            if k - items[j-1][1] >= 0:
                dp[j][k] = max(dp[j-1][k], dp[j-1][k-items[j-1][1]] + items[j-1][0], dp[j][k-items[j-1][1]] + items[j-1][0])
            else:
                dp[j][k] = dp[j-1][k]

    return dp[-1][-1]

print(solve())


Measured memory_bytes: 37952
N, M = [int(s) for s in input().split()]
S = []
for _ in range(M):
    l = [int(s) for s in input().split()]
    S.append(l[1:])
P = [int(s) for s in input().split()]

result = 0
for i in range(2 ** N):
    if all(sum(["{:0{N}b}".format(i, N=N)[t - 1] == '1' for t in s]) % 2 == P[j] for j, s in enumerate(S)):
        result += 1

print(result)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/






int N, T, A, H[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> T >> A;
    rep(i, 0, N) cin >> H[i];

    double dmin = 1e9, ans = -1;
    rep(i, 0, N) {
        double t = T - H[i] * 0.006;
        double d = abs(A - t);
        if (d < dmin) {
            dmin = d;
            ans = i;
        }
    }
    cout << (ans + 1) << endl;
}

Measured memory_bytes: 256
import java.io.*;
 
public class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        int x = Integer.parseInt(input);
        int h = x / 3600;
        int m = (x % 3600) / 60;
        int s = (x % 3600) % 60;
        System.out.println(h + ":" + m + ":" + s);
    }
}

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

const int MOD = 1e9 + 7;

inline void ModSum(int& x, int y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
    if (x < 0) {
        x += MOD;
    }
}

inline int GetModSum(int x, int y) {
    ModSum(x, y);
    return x;
}

inline void ModMul(int& x, int y) {
    x = (1LL * x * y) % MOD;
}

inline int GetModMul(int x, int y) {
    ModMul(x, y);
    return x;
}

int GetBinaryPow(int x, int pw) {
    int result = 1;
    while (pw > 0) {
        if (pw & 1) {
            ModMul(result, x);
        }
        ModMul(x, x);
        pw >>= 1;
    }
    return result;
}

int GetInv(int x) {
    return GetBinaryPow(x, MOD - 2);
}

#define LLD_SPEC "%lld"

const int BASE = 2e3;
const int COORD_COUNT = 2 * BASE + 1;

const int MAX_FACT = 4 * BASE + 1;

int fact[MAX_FACT];
int invFact[MAX_FACT];

void BuildFact() {
    fact[0] = 1;
    for (int i = 1; i < MAX_FACT; ++i) {
        fact[i] = fact[i - 1];
        ModMul(fact[i], i);
    }
    for (int i = 0; i < MAX_FACT; ++i) {
        invFact[i] = GetInv(fact[i]);
    }
}

int GetC(int n, int k) {
    if (k > n) {
        return 0;
    }
    int result = fact[n];
    ModMul(result, invFact[k]);
    ModMul(result, invFact[n - k]);
    return result;
}

int main() {
    BuildFact();

    int n;
    scanf("%d", &n);

    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &a[i].first, &a[i].second);
    }

    vector<vector<int>> sum(COORD_COUNT, vector<int>(COORD_COUNT, 0));
    for (int i = 0; i < n; ++i) {
        ++sum[BASE - a[i].first][BASE - a[i].second];
    }

    for (int j = 1; j < COORD_COUNT; ++j) {
        ModSum(sum[0][j], sum[0][j - 1]);
    }

    for (int i = 1; i < COORD_COUNT; ++i) {
        ModSum(sum[i][0], sum[i - 1][0]);
    }

    for (int i = 1; i < COORD_COUNT; ++i) {
        for (int j = 1; j < COORD_COUNT; ++j) {
            ModSum(sum[i][j], sum[i - 1][j]);
            ModSum(sum[i][j], sum[i][j - 1]);
        }
    }

    int result = 0;
    for (int i = 0; i < n; ++i) {
        ModSum(result, sum[a[i].first + BASE][a[i].second + BASE]);

        ModSum(result, -GetC(2 * (a[i].first + a[i].second), 2 * a[i].first));
    }

    ModMul(result, GetInv(2));

    printf("%d\n", result);

    return 0;
}

Measured memory_bytes: 64512
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)                                                         

using namespace std;
#define ll long long

int main(){
  int A, B, C, X;
  cin >> A >> B >> C >> X;
  int ret = 0;
  for(int i=0; i<=A; i++){
    for(int j=0; j<=B; j++){
      int tmp = X - 500 * i - 100 * j;
      if(tmp >= 0 && tmp % 50 == 0 && tmp / 50 <= C)
        ret++;
    }
  }
  cout << ret << endl;
  return 0;
}


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

using namespace std;

stack<char> st[3];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    string a, b, c;
    cin >> a >> b >> c;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    reverse(c.begin(), c.end());
    for(auto x : a){
        st[0].push(x);
    }
    for(auto x : b){
        st[1].push(x);
    }
    for(auto x : c){
        st[2].push(x);
    }
    int ptr = 0;
    int winner = 0;
    while(!st[0].empty() || !st[1].empty() || !st[2].empty()){
        if(st[ptr].empty()){
            winner = ptr;
            break;
        } else {
            char to = st[ptr].top();
            st[ptr].pop();
            ptr = to - 'a';
        }
    }
    if(winner == 0){
        cout << "A\n";
    } else if(winner == 1){
        cout << "B\n";
    } else {
        cout << "C\n";
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string str;
  cin >> str;
  
  int count = 0;
  
  for(int i = 0; i < str.size(); ++i){
    if(str[i] == str[i + 1]){
      if(str[i + 1] == '1') {
        str[i + 1] = '0';
      }
      else{
        str[i + 1] = '1';
      }
      
      count++;
    }
  }
  
  cout << count << endl;
}

Measured memory_bytes: 512
N = int(input())
K = int(input())

Nstr = str(N)

l = len(Nstr)

DP = [[[0]*2 for j in range(K+1)] for i in range(l+1)]

DP[0][0][1] = 1

for i in range(l):
    if int(Nstr[i])==0:
        for j in range(K+1):
            DP[i+1][j][0] += DP[i][j][0]
            DP[i+1][j][1] += DP[i][j][1]
            if j>0:
                DP[i+1][j][0] += 9*DP[i][j-1][0]
    else:
        for j in range(K+1):
            DP[i+1][j][0] += DP[i][j][0]+DP[i][j][1]
            if j>0:
                DP[i+1][j][0] += (int(Nstr[i])-1)*DP[i][j-1][1]+9*DP[i][j-1][0]
                DP[i+1][j][1] += DP[i][j-1][1]

print(DP[l][K][0] + DP[l][K][1])        

Measured memory_bytes: 38384
H, W, K = map(int, input().split())
s = []
INF = (H - 1) + (W - 1)
ans = INF

def add(col: int):
    for i in range(g):
        now[i] += c[i][col]
    for i in range(g):
        if now[i] > K:
            return False
    return True

for _ in range(H):
    s.append(list(input()))

for div in range(1 << (H - 1)):
    g = 0
    id = [0] * H
    for i in range(H):
        id[i] = g
        if div >> i & 1:
            g += 1
    g += 1
    
    now = [0] * g
    num = g - 1
    c = [[0 for _ in range(W)] for _ in range(H)]

    for i in range(H):
        for j in range(W):
            c[id[i]][j] += int(s[i][j])

    for j in range(W):
        if not add(j):
            num += 1
            now = [0] * g

            if not add(j):
                num = INF
                break

    ans = min(ans, num)
    
print(ans)

Measured memory_bytes: 64860
#include<bits/stdc++.h>
#define ll long long
#define all(a) a.begin(),a.end()
#define sz(a) a.size()
#define re return 
#define MP make_pair
#define pb push_back
using namespace std;

signed main(){
	ios_base::sync_with_stdio(0);
	int x;
	cin>>x;
	if(x<600) cout<<8;
	else if(x>=600&&x<800) cout<<7;
	else if(x>=800&&x<1000) cout<<6;
	else if(x>=1000&&x<1200) cout<<5;
	else if(x>=1200&&x<1400) cout<<4;
	else if(x>=1400&&x<1600) cout<<3;
	else if(x>=1600&&x<1800) cout<<2;
	else cout<<1;
	re 0;
}


Measured memory_bytes: 3604
main :-
	read_num(N),
	read_n_num_list(N, L),
	more_than_three_same(L, 0),
	write('Yes'),
	nl,
	halt.
main :- write('No'),
	nl,
	halt.

more_than_three_same(_, N) :-
        N >= 3,
        !.
more_than_three_same([], _) :-
        false.
more_than_three_same([[HA, HB]|T], _) :-
        HA =\= HB,
        !,
        more_than_three_same(T, 0).
more_than_three_same([[HA, HB]|T], N) :-
        HA =:= HB,
        NewN is N + 1,
        !,
        more_than_three_same(T, NewN).


read_n_num_list(Num, List) :-
	read_n_num_list_aux(Num, [], List),
	!.
read_n_num_list_aux(0, List, List).
read_n_num_list_aux(Num, Old, Accum) :-
	read_num(NewItem1),
        read_num(NewItem2),
	NewNum is Num - 1,
	append(Old, [[NewItem1, NewItem2]], NewList),
	read_n_num_list_aux(NewNum, NewList, Accum).
	

read_str(S) :-
        read_string(current_input, ' \n', '', _, S).

read_num(N) :-
	read_str(S),
	number_string(N, S).



Measured memory_bytes: 8112
import copy
h, w, K = map(int, input().split())

C = []

for i in range(h):
    c = list(input())
    # print(c)
    C.append(c)
# print(C)
ans = 0
for i in reversed(range(2 ** (h + w))):
    d = copy.deepcopy(C)
    x = []
    for j in reversed(range(h + w)):
        if ((i >> j) & 1):
            x.append(j)
            if j < h:
                del d[j]
            if h <= j:
                m = j - h
                for k in range(len(d)):
                    del d[k][m]
    # print(x)
    count = 0
    for n in d:
        count += n.count('#')
    if count == K:
        ans += 1
print(ans)




Measured memory_bytes: 9312
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] A = new int[N+1];
        int[] rec = new int[N+1];
        HashSet<Integer> dic = new HashSet<>();
        for(int i=1;i<=N;i++){
            A[i] = sc.nextInt();
            dic.add(A[i]);
            rec[A[i]]++;
        }
        int ans = 0;
        if(dic.size()<=K){
            System.out.println(ans);
            System.exit(0);
        }
        Arrays.sort(rec);
        int i=0;
        while(rec[i]==0) i++;
        for(int j=i;j<i+(dic.size()-K);j++){
            ans += rec[j];
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 104344
X = int(input())

if X == 2:
        print(X)
        exit()
elif X %2 == 0:
        X += 1

while True:
        flag = 1
        for i in range(3, round(X**(1/2)), 2):
                if X % i == 0:
                        flag = 0
                        break
        if flag == 1:
                print(X)
                exit()
        X += 2

Measured memory_bytes: 38384
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;
int main(){
	string s,t;
	cin>>s>>t;
	sort(s.begin(),s.end());
	sort(t.begin(),t.end(),greater<int>());
	if(t>s) puts("Yes");
	else puts("No");
	return 0;
}

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

using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); ++i)
double const PI = 3.1415926535897932384626433;
using P = pair<int, int>;

int main() {
    int a, b;
    cin >> a >> b;
    if (a <= 8 && b <= 8)
        cout << "Yay!" << endl;
    else
        cout << ":(" << endl;
    return 0;
}

Measured memory_bytes: 3584
//https://atcoder.jp/contests/abc118/tasks/abc118_a
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main()
{
    int A, B;
    cin >> A >> B;
    
    vector<int> v;
    for( int i = 1; i <= B; i++ )
    {
        if( B % i == 0 )
        {
	       v.emplace_back( i );
        }
    }
    cout << ( find( ALL( v ), A ) != v.end() ? A + B : B - A ) << endl;
    return 0;
}

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

using namespace std;

int main(void){
    int N;
    cin >> N;
    vector<int> A; // ..N
    A.push_back(0);
    for(int i=0;i<N;i++){
        int x;
        cin >> x;
        A.push_back(x);
    }
    vector<int> p(N+2); // ..N+1
    p[0] = 0;
    for(int i=1;i<=N;i++){
        p[i] = p[i-1] + abs(A[i]-A[i-1]);
    }
    p[N+1] = p[N] + abs(A[N]-A[0]);

    for(int i=1;i<=N-1;i++){
        cout << p[i-1]+(p[N+1]-p[i+1])+abs(A[i-1]-A[i+1]) << endl;
    }

    cout << p[N-1] + abs(A[N-1]-A[0])<< endl;

    return 0;
}

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

int main()
{
    int N;
    cin >> N;
    int Alice=0,Bob=0;
    vector <int> a(N);
    for (int i=0;i<N;i++)
    {
        cin >> a[i];
    }
    sort(a.begin(),a.end(),greater<int>());
    for (int i=0;i<N;i++)
    {
        if (i%2==0)
        {
            Alice+=a[i];
        }
        else
        {
            Bob+=a[i];
        }
    }
    cout << Alice-Bob << endl;
return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main{
	
	static long mod=(long)1e9+7;
	
	public static void main(String[] args) throws IOException {
		Writer out=new Writer(System.out);
		Reader in=new Reader(System.in);
		int ts=1;
		
		outer: while(ts-->0) {	
			int n=in.nextInt();
			int a[]=in.readArray(n);
			if(n<3) {
				out.println(0);
				continue outer;
			}
			int count=0;
			for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) for(int k=j+1; k<n; k++) {
				if(a[i]!=a[j] && a[j]!=a[k] && a[i]!=a[k]) {
					if(tri(a[i],a[j],a[k]) || tri(a[j],a[k],a[i]) || tri(a[i],a[k],a[j])) count++;
				}
			}
			out.println(count);
		}
		out.close();		
		
	}

	static boolean tri(int a, int b, int c) {
		if(c<a+b && c>abs(a-b)) return true;
		return false;
	}
	
	
/*********************************** UTILITY CODE BELOW **************************************/	
		
	static int abs(int a) {
		return a>0 ? a : -a;
	}
	
	static int max(int a, int b) {
		return a>b ? a : b;
	}
	
	static int pow(int n, int m) {
		if(m==0) return 1;
		int temp=pow(n,m/2);
		long res=(((long)temp*temp)%mod);
		if(m%2==0) return (int)res;
		return (int)((res*n)%mod);
	}
	
	static class Pair{
		int u, v;
		
		Pair(int u, int v){this.u=u; this.v=v;}
		
		static void sort(Pair [] coll) {		
			List<Pair> al=new ArrayList<>(Arrays.asList(coll));
			Collections.sort(al,new Comparator<Pair>() {
				public int compare(Pair p1, Pair p2) {
					return p1.u-p2.u;
				}	
			});
			for(int i=0; i<al.size(); i++) {
				coll[i]=al.get(i);
			}
		}
		
	}
	
	static void sort(int[] a) {
		ArrayList<Integer> list=new ArrayList<>();
		for (int i:a) list.add(i);
		Collections.sort(list);
		for (int i=0; i<a.length; i++) a[i]=list.get(i);
	}
	
	static int [] array(int n, int value) {	
		int a[]=new int[n];
		for(int i=0; i<n; i++) a[i]=value;
		return a;
	}
	
	static class Reader{
		
		BufferedReader br;
		StringTokenizer to;
		
		Reader(InputStream stream){
			br=new BufferedReader(new InputStreamReader(stream));
			to=new StringTokenizer("");
		}
		
		String next() {
			while(!to.hasMoreTokens()) {
				try {
					to=new StringTokenizer(br.readLine());	
				}catch(IOException e) {}
				
			}
			return to.nextToken();
			
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		
		long nextLong() {
			return Long.parseLong(next());
		}
		
		int [] readArray(int n) {
			int a[]=new int[n];
			for(int i=0; i<n ;i++) a[i]=nextInt();
			return a;
		}
		long [] readLongArray(int n) {
			long a[]=new long[n];
			for(int i=0; i<n ;i++) a[i]=nextLong();
			return a;
		}
		
	}
	
	static class Writer extends PrintWriter{
		Writer(OutputStream stream){
			super(stream);
		}
		void println(int [] array) {
			for(int i=0; i<array.length; i++) {
				print(array[i]+" ");
			}
			println();
		}
		void println(long [] array) {
			for(int i=0; i<array.length; i++) {
				print(array[i]+" ");
			}
			println();
		}
	}
	
}

Measured memory_bytes: 34068
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define debug(...) cerr<<__LINE__<<" ["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec)
{ for (auto v : vec) os << v << ' '; os << '\n'; return os; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa)
{ os << '(' << pa.first << ',' << pa.second << ')'; return os; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T)
{ cerr << " " << H; debug_out(T...); }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

void solve() {
    int n;
    cin >> n;
    int ans = 0;
    REP(i, 1, n) {
        if (to_string(i).size() % 2 == 1) ans++;
    }
    cout << ans << endl;
}

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


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

int main(){
	int i,n;
	ll sum=0;
	cin>>n;
	rep(i,1,n+1)
		if(i%3!=0&&i%5!=0)
			sum+=i;
	cout<<sum;

	return 0;
}


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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    map<int32,int64> mp;
    int32 cur = 0;
    mp[0]++;
    int32 ten = 1;
    FORR(i,s.size()-1,0){
        cur += (s[i] - '0') * ten;
        cur %= 2019;
        ten = ten * 10 % 2019;
        mp[cur]++;
        // cout << cur << endl;
    }
    int64 ans = 0;
    for(auto p : mp){
        // cout << p.first << " " << p.second << endl;
        ans += p.second * (p.second - 1) / 2;
    }
    ANS(ans);
    return 0;
}

Measured memory_bytes: 3772
n = int(input())
a = list(map(int, input().split()))

result = 0
i = 0
x = 0
for j in range(n):
    while x < n and (i & a[x]) == 0:
        i += a[x]
        x += 1
    result += x-j
    i -= a[j]
print(result)

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

using namespace std;

#define rep(i, x)   for (__typeof(x) i = 0; i < x; i++)
#define mp             make_pair
#define pb             push_back
#define fi             first
#define se             second
#define sz(x)          (int)((x).size())
#define all(x)         (x).begin(), (x).end()
#define sci(x)         int x;       scanf("%d", &x);
#define scii(x, y)     int x, y;    scanf("%d %d", &x, &y);
#define sciii(x, y, z) int x, y, z; scanf("%d %d %d", &x, &y, &z);
#define TC(x)          sci(x); while(x --)
#define eprintf(...)   fprintf(stderr, __VA_ARGS__)
#define debug(x)       { cerr << #x << " = " << x << endl; }
#define repi(i, x)  for (__typeof(x) i = x-1; i >= 0; i --)
#define fore(itr, x)   for (__typeof(x.begin()) itr = x.begin(); itr != x.end(); itr ++)
#define forei(itr, x)  for (__typeof(x.end()) itr = x.end() - 1; itr != x.begin() - 1; itr --)
typedef long long      ll;
typedef pair<int, int> ii;
typedef pair<ii, int>  iii;
typedef vector<int>    vi;
typedef vector<ii>     vii;
typedef vector<iii>    viii;
typedef vector<vector<int> > vvi;
const   int            infi = numeric_limits<int>::max();
const   double         eps = 0;
const   int            ms  = 0;



struct Sushi{
    ll val;
    ll t;
    int idx;
    Sushi(){}
    Sushi(ll val_, ll t_, int idx_) : val(val_), t(t_), idx(idx_){}// underbar wasure
	
	bool operator <(const Sushi& sushi) const
	{
		return val < sushi.val;
	}
};


int main()
{
    ios::sync_with_stdio(false);//endl->"\n"
    cin.tie(0);
    ll ds=0, ans = 0;
    ll N, K;
    cin >> N >> K;
    vector<ll> T(N), D(N);
    vector<Sushi> sv;
    rep(i, N){
        cin >> T[i] >> D[i];

        Sushi s(D[i], T[i], i);
        sv.pb(s);
    } 
    

    sort(all(sv));
   
    priority_queue<Sushi> spq;
    unordered_set<ll> tset;
    reverse(all(sv));
    rep(i, K){
        auto s = sv[i];
        s.val = -s.val;
        if(tset.count(s.t))spq.push(s);

        ds -= s.val;
        tset.insert(s.t);
    }
    ll tlen = tset.size();
    ans = ds+tlen*tlen;

    for(ll i = K; i < N; i++){
        if (spq.empty()) break;

        Sushi s = sv[i];
        if (tset.count(s.t)) continue;
        //spq.push(s);

        auto mins = spq.top(); spq.pop();
        ds -= -mins.val;
        

        ds += s.val;
        
        tset.insert(s.t);
        tlen = tset.size();
        ans = max(ans, ds + tlen*tlen);
        
    }

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

Measured memory_bytes: 9584
#pragma once
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
typedef long long ll;
using namespace std;

int t[100010];
ll d[100010];
void init(int n) {
	for (size_t i = 0; i < n; i++)
	{
		t[i] = i;
	}
}
int parent(int x) {
	if (t[x] == x) {
		return x;
	}
	int tp = t[x];
	int p = parent(t[x]);
	if (tp != p) {
		d[x] += d[tp];
	}
	return t[x] = p;
}
bool unite(int x,int y,ll _d) {
	int xp = parent(x);
	int yp = parent(y);

	if (xp == y) return false;

	if (xp == yp) {
		if (d[x] + _d != d[y]) {
			return false;
		}
	}
	else {
		int dx = d[x];
		int dy = d[y];
		if ((dx + _d) > dy) {
			t[yp] = xp;
			d[yp] = dx + _d - dy;
		}
		else {
			t[xp] = yp;
			d[xp] = dy - (dx + _d);
		}
	}
	return true;
}
void PeopleOnaline() {
	int N,M;
	cin >> N >> M;
	init(N + 1);
	
	for (size_t i = 0; i < M; i++)
	{
		int L, R, D;
		cin >> L >> R >> D;
		if (!unite(L, R, D)) {
			cout << "No" << endl;
			return;
		}
	}
	cout << "Yes" << endl;
}
int main() {
	PeopleOnaline();
	return 0;
}

Measured memory_bytes: 1408
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60

typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-9, pi = acos(-1.0);
namespace std {
    bool operator<(const Point &lhs, const Point &rhs) {
        if (lhs.real() < rhs.real() - eps) return true;
        if (lhs.real() > rhs.real() + eps) return false;
        return lhs.imag() < rhs.imag();
    }
}
Point input_point() {ld x, y; cin >> x >> y; return Point(x, y);} // ????????\???
bool eq(ld a, ld b) {return (abs(a - b) < eps);} // ????????????????????????
ld dot(Point a, Point b) {return real(conj(a) * b);} // ??????
ld cross(Point a, Point b) {return imag(conj(a) * b);} // ??????

// ??´????????????
class Line {
public:
    Point a, b;
    Line() : a(Point(0, 0)), b(Point(0, 0)) {}
    Line(Point a, Point b) : a(a), b(b) {}
    Point operator[](const int _num) {
        if (_num == 0)return a;
        else if (_num == 1)return b;
        else assert(false);
    }
};

// ????????????
class Circle {
public:
    Point p;
    ld r;
    Circle() : p(Point(0, 0)), r(0) {}
    Circle(Point p, ld r) : p(p), r(r) {}
};

// ??????????¶?
Point proj(Line l, Point p) {
    ld t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
    return l.a + t * (l.a - l.b);
}

int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    //    Point p1 = input_point(),p2 = input_point(); Line l(p1,p2);
    Line l(input_point(),input_point());
    int q; cin >> q;
    for(int i = 0; i < q;i++){
        Point p = input_point();
        Point p3 = proj(l,p);
        
        Point vec_px = (ld)2 * (p3 - p);
        
        Point x = p + vec_px;
        cout << fixed << setprecision(10) << x.real() << " " << x.imag() << endl;
    }
    return 0;
}

Measured memory_bytes: 3364