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

using ll=long long;
const ll MOD=1e9+7;
int main(){
    int N,W;
    cin>>N>>W;
    vector<ll> w(N);
    for(int i=0;i<N;i++) cin>>w[i];
    sort(w.begin(),w.end(),greater<>());

    vector<vector<ll>> dp(N+1,vector<ll>(W+1,0));
    dp[0][0]=1;
    for(int i=0;i<N;i++){
        ll buf=0;
        for(int j=i+1;j<N;j++){
            buf+=w[j];
        }
        for(int j=0;j<=W;j++){
            if(j+w[i]<=W) (dp[i+1][j+w[i]]+=dp[i][j])%=MOD;
            if(j+buf+w[i]>W) (dp[i+1][j]+=dp[i][j])%=MOD;
        }
    }
    
    cout<<(accumulate(dp[N].begin(),dp[N].end(),0LL))%MOD<<endl;
    return 0;
}


Measured memory_bytes: 18556
#include<bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n ; i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) // decltypeで型取得、引数があればva_argsのところに入れる
using namespace std;
typedef long long ll; // long longをllでかけるようにした
const int INF = 1e9;

int main(void){
    while(true){
        int n; cin >> n;
        if(n == 0) return 0;
        else{
            vector<int> person(n);
            double ave = 0;
            REP(i, n){
                cin >> person[i];
                ave += person[i];
            }
            ave /= n;
            int count = 0;
            REP(i, n){
                if(ave >= person[i]) count++;
            }
            cout << count << endl;
        }       
    }
}


Measured memory_bytes: 3124
#include<iostream>
using namespace std;
double cross(double x1, double y1, double x2, double y2){
	return (x1 * y2) - (y1 * x2);
}
int main(){
	double x[3], y[3], px, py;
	while(cin >> x[0] >> y[0] >> x[1] >> y[1] >> x[2] >> y[2] >> px >> py){
		double ret[3];
		for(int i = 0; i < 3; ++i ){
			int n =( i+1 ) % 3;
			ret[i] = cross( px - x[i], py - y[i], x[n] - x[i], y[n] - y[i] );
		}
		if(ret[0] < 0 && ret[1] < 0 && ret[2] < 0 
		|| ret[0] > 0 && ret[1] > 0 && ret[2] > 0) 
			cout << "YES" << endl;
		else
		    cout << "NO" << endl;		
	}
}

Measured memory_bytes: 3072
using System;

namespace AtCoder.Question
{
    public class QuestionB
    {
        public static void Main(string[] args)
        {
            var inputs = Console.ReadLine().Split(' ');
            var a = int.Parse(inputs[0]);
            var b = int.Parse(inputs[1]);
            var c = int.Parse(inputs[2]);
            var k = int.Parse(inputs[3]);

            if (k <= a)
            {
                Console.WriteLine(k.ToString());
                return;
            }
            if (k <= (a + b))
            {
                Console.WriteLine(a.ToString());
                return;
            }
            Console.WriteLine((2 * a + b - k).ToString());
        }
    }
}


Measured memory_bytes: 27516
N, M = map(int, input().split(' '))

num = [0, ] * N

is_valid = True
for _ in range(M):
    s, c = map(int, input().split(' '))
    si = s - 1
    if (N > 1) and (s == 1) and (c == 0):
        is_valid = False
        break
    elif (num[si] != 0) and (c != num[si]):
        is_valid = False
        break
    else:
        num[si] = c

if not is_valid:
    print(-1)
else:
    if N == 1:
        print(num[0])
    else:
        if num[0] != 0:
            print(''.join(map(str, num)))
        else:
            num[0] = 1
            print(''.join(map(str, num)))

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

struct Dice{
    int s[6];
    void roll(char c){
    int b;
    if(c=='E'){
      b=s[0];
      s[0]=s[3];
      s[3]=s[5];
      s[5]=s[2];
      s[2]=b;
    }
    if(c=='W'){
      b=s[0];
      s[0]=s[2];
      s[2]=s[5];
      s[5]=s[3];
      s[3]=b;
    }
    if(c=='N'){
      b=s[0];
      s[0]=s[1];
      s[1]=s[5];
      s[5]=s[4];
      s[4]=b;
    }
    if(c=='S'){
      b=s[0];
      s[0]=s[4];
      s[4]=s[5];
      s[5]=s[1];
      s[1]=b;
    }
    if(c=='R'){
      b=s[1];
      s[1]=s[2];
      s[2]=s[4];
      s[4]=s[3];
      s[3]=b;
    }    
  }
  int top(){
      return s[0];
  }
  int right(){
      return s[2];
  }
  int left(){
      return s[3];
  }
  int front(){
      return s[1];
  }
};

int main(){
    Dice d;
    for (int i=0; i<6; i++) cin >> d.s[i];
    int n; cin >> n;
    while(n--){
        int a,b; cin >> a >> b;
        if(d.left() == a) d.roll('E');
        if(d.right() == a) d.roll('W');
        while(d.top() != a) d.roll('N');
        while(d.front() != b) d.roll('R');
        
        cout << d.right() << endl;
    }
    return 0;
}



Measured memory_bytes: 3088
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] arg) {

        try (Scanner scanner = new Scanner(System.in)){
            int[] input = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            double w = input[0];
            double h = input[1];
            double x = input[2];
            double y = input[3];

            System.out.println(String.format("%f %d", (w * h) / 2.0, w / 2.0 == x && h / 2.0 == y ? 1 : 0));
        }

    }
}


Measured memory_bytes: 30036
import Data.List
import qualified Data.Vector.Unboxed as V
import Control.Monad

f :: String -> [Int]
f [] = []
f [_] = []
f (c:d:s) = if (c,d) == ('A','C') then 1 : (f (d:s)) else 0 : (f (d:s))

solve :: Int -> V.Vector Int -> Int -> IO ()
solve _ _ 0 = return ()
solve n cnts q = do
  [l,r] <- map read.words <$> getLine
  print $ (cnts V.! (r-1)) - (cnts V.!(l-1))
  solve n cnts (q-1)

main :: IO ()
main = do
  [n,q] <- map read.words <$> getLine
  s <- getLine
  let cnts = V.fromList $ scanl (+) 0 $ f s
  solve n cnts q


Measured memory_bytes: 8700
# author:  Taichicchi
# created: 15.09.2020 21:22:26

import sys

X, K, D = map(int, input().split())

X = abs(X)

if X >= K * D:
    print(X - (K * D))
else:
    k = K - X // D
    x = X - D * (X // D)

    if k % 2:
        print(abs(x - D))
    else:
        print(x)


Measured memory_bytes: 9104
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define f0(i,a,b) for(int i=a;i<b;i++)
#define f1(i,a,b) for(int i=a;i<=b;i++)
#define f2(i,a,b) for(int i=a;i>b;i--)
#define f3(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define int long long
#define fi first
#define se second
#define ncr(n,r) fact[n]*modInv(fact[r])*modInv(fact[n-r])
#define modInv(a) binExp(a,mod-2)
#define mod 1000000007
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define os_find(k) find_by_order(k)
#define os_order(k) order_of_key(k)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define make_graph(k) int x,y; f0(i,0,k){cin>>x>>y; adj[x].pb(y); adj[y].pb(x);}
#define test int t;cin>>t;while(t--)

signed main()
{
    fast

    string s;
    cin>>s;

    int cur = 0;
    int ans = 0;
    f0(i,0,s.length())
    {
        if(s[i]=='R')cur++;
        else cur = 0;
        ans = max(ans, cur);
    }
    cout<<ans;
}

Measured memory_bytes: 3648
import java.awt.*;
import java.awt.geom.*;
import java.io.*;

import java.util.*;
class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int min = Integer.MAX_VALUE;
		int[] list = new int[n];
		for(int i =0 ; i < n; i++) {
			list[i] = sc.nextInt();
			min = Math.min(list[i], min);
		}
		
		IN:for(int i = 1; i <= min; i++) {
			for(int j = 0; j < n; j++) {
				if(list[j] % i != 0) continue IN;
			}
			System.out.println(i);
		}
		
	}
}

Measured memory_bytes: 17164
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define lld double
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define all(v) v.begin(),v.end()
#define vc vector
#define rep1(it,v) for(it=v.begin();it!=v.end();it++)
#define ayush ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define input(v) for(auto &it:v)cin>>it
#define inf 100000000007
#define pb push_back

ll dp[100005]; ll v1[100005]; ll n,k; vc<ll> v2(105);

ll fun(ll start)
{
    if(start==n-1) return 0;
    
    if(dp[start]!=-1) return dp[start];
    
    ll ans=inf;
    rep(i,1,k) { if(start+i<n) { ans=min(ans,abs(v1[start+i]-v1[start])+fun(start+i)); } }
    return dp[start]=ans;
    
}

int main()
{
    cin>>n>>k; rep(i,0,n-1) cin>>v1[i];
    rep(i,0,n-1) dp[i]=-1;
    ll ans=fun(0);
    cout<<ans;
}


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

#define FORN(i, j, k) for(int i=j;i<k;i++)
#define FORR(i, j, k) for(int i=j;i>=k;i--)
#define REP(i, n) FORN(i, 0, n)
#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define endl '\n'

const int MODO = 1e+9 + 7;
const int MAX = 1e+5 + 5;

int n, m;
int dp[MAX];
vector<int> adj[MAX];
vector<bool> visit(MAX, false);

void dfs(int node){
	visit[node] = true;
	dp[node] = 0;
	for(int child:adj[node]){
		if(!visit[child]){
			dfs(child);
		}
		dp[node] = max(dp[node], dp[child]+1);
	}
}

void solve(){
	int x,y;
	REP(i,m){
		cin >> x >> y;
		adj[x].pb(y);
	}
	
	int res = 0;
	FORN(i,1,n+1){
		if(!visit[i]){
			dfs(i);
		}
	}
	
	FORN(i,1,n+1){
		res = max(res, dp[i]);
	}

	cout << res << endl;  
	return;
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	solve();
	return 0;
}


Measured memory_bytes: 12576
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define COUT(x) cout<<(x)<<"\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, n) for(int i=0;i<n;i++)
#define YES(x) cout<<(x?"YES":"NO")<<"\n"
#define Yes(x) cout<<(x?"Yes":"No")<<"\n"
#define dump(x) cout<<#x<<" = "<<(x)<<"\n"
#define endl "\n"
using G = vector<vector<int>>;
using M = map<int,int>;
using P = pair<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int,vector<int>,greater<int>>;
using V = vector<int>;
using ll = long long;
using edge = struct { int to; int cost; };
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; }
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  IOS;
  int n; cin >> n;
  vector<int> a(n+1);
  REP(i,n) cin >> a[i+1];

  vector<int> ans;
  vector<int> b(n+1);

  for (int i=n; i>0; i--) {
    int sum = 0;
    if (i == 1) {
      for(int j=2; j<=n; j++) {
        sum+=b[j];
      }
    } else {
      for(int j=i*2; j<=n; j+=i) {
        sum+=b[j];
      }
    }

    if (sum%2 != a[i]) {
      b[i]++;
      ans.push_back(i);
    }
  }
  COUT(ans.size());
  reverse(ALL(ans));
  for (int x: ans) {
    cout << x << " ";
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 5220
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define pii pair<ll,ll>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(ll i=a;i<=(ll)b;++i)
#define per(i,a,b) for(ll i=a;i>=(ll)b;--i)
#define ll long long
#define lowbit(x) ((x)&(-x))

const int maxn=2e5+5;
int a[maxn],cnt[maxn],used[maxn];
int main()
{
    IOS
    
    int n;cin>>n;
    rep(i,1,n){
        cin>>a[i];cnt[a[i]]++;
    }
    ll sum=0;
    rep(i,1,n){
        if(used[a[i]]) continue;
        used[a[i]]=1;
        sum+=1ll*cnt[a[i]]*(cnt[a[i]]-1)/2;
    }
    rep(i,1,n){
        ll tem=sum;
        tem-=1ll*cnt[a[i]]*(cnt[a[i]]-1)/2;
        ll x=cnt[a[i]]-1;
        if(x>=1) tem+=1ll*x*(x-1)/2;
        cout<<tem<<"\n";
    }
}


Measured memory_bytes: 3968
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int N = sc.nextInt();
		int L = sc.nextInt();
		
		sc.close();

		int truePi = (N*(1+N))/2  -N + N*L;
		
		int minMi = Integer.MAX_VALUE;
		int x = -1;
		for(int i=1;i<=N;i++) {
			int mi = L+i-1;
			if(minMi > Math.abs(mi)) {
				minMi = Math.abs(mi);
				x = i;
			}
		}
		
		out.println(truePi - (L+x-1));
		
		
	}

	public static void main(String[] args) {
		new Main()._main(args);
	}
	
	@SuppressWarnings("unused")
	private int[] nextIntArray(Scanner sc, int n) {
		int[] result = new int[n];
		for (int i = 0; i < n; i++) {
			result[i] = sc.nextInt();
		}
		return result;
	}

	@SuppressWarnings("unused")
	private int[] nextIntArray1origin(Scanner sc, int n) {
		int[] result = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			result[i] = sc.nextInt();
		}
		return result;
	}
}


Measured memory_bytes: 22996
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    if N == 1:
        print("Hello World")
    else:
        a = int(input())
        b = int(input())
        print(a+b)


if __name__ == '__main__':
    main()


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

int main(){
    int n,k;
    cin>>n>>k;
    const int INF = 1e9;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    

    vector<long long > dp(n);
    
    for(int i=0;i<n;i++)dp[i]=INF;
    dp[0]=0;
    dp[1]=abs(a[0]-a[1]);
    for (int i = 2; i < n; i++)
    {
        for(int j=1;j<=k;j++){
            if(i-j>=0)dp[i] = min(dp[i],dp[i-j]+abs(a[i]-a[i-j])); 
        }
        
    }
    cout << dp[n-1] << endl;
    return 0;
}

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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)

lli dd[60][60];
lli dp[60][60];

int main(){
    // cout << fixed << setprecision(5);

    lli h,w;
    cin>>h>>w;

    lli sum = 0;
    REP(i,0,h)REP(j,0,w){
        char tmp;
        cin>>tmp;
        if(tmp=='#'){
            dd[i][j]=1;
            sum++;
        }
    }

    REP(i,0,60)REP(j,0,60)dp[i][j]=INF;

    queue<pair<lli,lli>> q;
    q.push({0,0});
    dp[0][0]=1;

    while(q.size()){
        pair<lli,lli> top = q.front();
        q.pop();

        lli dx[4]={-1,0,1,0};
        lli dy[4]={0,1,0,-1};
        REP(i,0,4){
            lli ny = top.first+dy[i];
            lli nx = top.second+dx[i];
            if(nx<0 || nx >= w || ny<0 || ny>=h)continue;
            if(dd[ny][nx]==1)continue;
            if(dp[ny][nx]>dp[top.first][top.second]+1)
            {
                dp[ny][nx] = dp[top.first][top.second]+1;
                q.push({ny,nx});
            }
        }
    }

    //cout<<dp[h-1][w-1]<<endl;
    if(dp[h-1][w-1]==INF)cout<<-1<<endl;
    else cout<<(h*w)-dp[h-1][w-1]-sum<<endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

int n, k;
bool dp[5005][5005];

bool C(int mid, vector<int> v){
    if(mid >= n) return true;
    else if(mid < 0) return false;

    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;

    rep(i,n){
        for(int j = k; j >= 0; j--){
            dp[i + 1][j] |= dp[i][j];
            if(i != mid) dp[i + 1][min(k, j + v[i])] |= dp[i][j];
        }
    }

    range(i,max(0,k - v[mid]),k){
        if(dp[n][i]) return true;
    }
    return false;
}

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

    cin >> n >> k;

    vector<int> v(n);
    rep(i,n) cin >> v[i];
    sort(all(v));

    int right = n, left = -1;
    rep(i,20){
        int mid = (right + left ) / 2;
        if(C(mid,v)) right = mid;
        else left = mid;
    }
    if(left == n) cout << n << endl;
    else if(left == -1) cout << 0 << endl;
    else cout << left + 1 << endl;
}


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

int main() {
  int N, A, B;
  scanf("%d %d %d",&N,&A,&B);
  int ans=0;
  for (int i=1; i<=N; i++) {
    int x=0;
    int num=i;
    while (num) {
      int sum=num%10;
      x+=sum;
      num/=10;
    }
    if (A<=x && x<=B) {
      ans+=i;
    }
  }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 256
// #include <stdio.h>
// #include <string.h>
//#include <iostream>
#include <math.h>
#include <iostream>
#include <utility>
#include <cstdio>
#include <stack>
#include <queue>
#include <algorithm>
#include <map>
#include <string>
#include <set>


using namespace std;
typedef pair<int, int> XY;// Pair型変数の宣言
typedef long long ll;
const ll MOD = (ll)1e9 + 7;
    

int main()
{
  	int Nmax = 100000;
    ll H[Nmax];
    ll dH[Nmax]; // 微分値
//    char String[Nmax];
    int N;
    int i,j,k;

/*   
    // int型スタック
    stack<int> stack;   
    stack.push(777);
    stack.push(778);
    stack.push(779);
  
	int tmpsl = stack.top();  // LAST要素の参照
 // 	int tpmsf = stack.back(); // FIRST要素の参照
 //	printf("%d %d \n",tmpsl,tmpsf);
    stack.pop();// LAST要素の削除（取出しではない）
 // 	if( stack.empty() == true) printf("empty stack\n");
     
    // int型キュー
    queue<int> que;
  	que.push(999);
  	que.push(998);   
  	que.push(997);    
  	int tmpqs = que.front(); // FIRST要素の参照
  	int tmpqe = que.back();  // LAST要素の参照
 //	printf("%d %d \n",tmpqs,tmpqe);
  	que.pop();  // FIRST要素の削除（取出しではない）
  //	if( que.empty() == true) printf("empty que\n");
    
    // ２次元座標を扱うキュー
    queue<XY> xyque; // ２次元座標型変数のキュー
  	XY p; 
  	xyque.pop();	// FIRST要素の削除。キューが空のときは削除が予約されて次のPOPが即削除される
  	xyque.push( XY(5,5) );
    xyque.push( XY(5,5) );
   	p = xyque.front();  // FIRST要素からのコピー
 // 	printf("%d %d\n", p.first, p.second);
  	
    
  que.back();
  //  sort(&(que.front()), &(que.back()));
        
  */ 
      
    // 入力読込
    // 文字列
 //   scanf("%s", String);   
    
    // 数列
    scanf("%d ", &N);
//    scanf("%lld", &K);
    for(i=1;i<=N;i++){
        scanf("%lld ",&H[i]);
    }
    
    // 文字列の長さをチェック
    // 文字列は配列の0からlen-1に格納されてる
//    len = strlen( String );
//  	printf("%d\n",len);
    
    
    
    ll count = 0;
    ll count_max =0;
    for(i = 1; i <= N ; i++){
        count =0;
        for(j= i ; j < N ; j++){
            if(H[j] >= H[j+1]){
                count++;
                if( count > count_max) {
                    count_max = count;
                    i =j; // スキップ
                }
            }
            else
                j = N;
        }
    }

    
    
    // 結果出力
  	cout << count_max  << endl;
   
  
  return 0;
   
}

Measured memory_bytes: 1024
from itertools import permutations


def main():
    N = int(input())
    P = list(map(int, input().split()))
    Q = list(map(int, input().split()))
    dic = list(permutations(range(1, N+1), N))
    print(abs(dic.index(tuple(P)) - dic.index(tuple(Q))))


if __name__ == "__main__":
    main()


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

using namespace std;

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

const int MAX = 510000;
const ll MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit()
{
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++)
	{
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k)
{
	if (n < k)
		return 0;
	if (n < 0 || k < 0)
		return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

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

	COMinit();

	ll ans = 0;
	for(ll i=k; i<=n+1; i++){
		ll max = (n-i+1+n)*i/2;
		ll min = (0+i-1)*i/2;
		ans += max-min+1;
		ans %= MOD;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 15564
#include<bits/stdc++.h>
using namespace std;
int main(){
string S;
  cin>>S;
  int N=S.size();
  if(S.substr(0,(N-1)/2)==S.substr((N+3)/2-1,(N-1)/2)){
  
  cout<<"Yes"<<endl;
  }
   else{
   cout<<"No"<<endl;
   }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 1e9 + 7;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
#define rep(i, n) for(int i = 0; i < n; i++)
const int inf9 = 1e9; const lint inf18 = 1e18;
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint P(int n, int r){ if(r < 0 || n < r) return 0; return (fact[n] * inv[n - r] % mod); } lint C(int p, int q){ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }
template<class itr, class itr2> bool next_sequence2(itr first, itr last, itr2 first2, itr2 last2){ itr now = last; itr2 now2 = last2; while(now != first){ now--, now2--; (*now)++; if((*now) == (*now2)){ (*now) = 0; }else{ return true; } } return false; }
inline int at(lint i, int j){ return (i >> j) & 1; }

int main(){
    string S, T;
    cin >> S >> T;
    cout << T << S << endl;
}



Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	long long int a[100][100] = { 0 };
	long long int b[100][100] = { 0 };
	long long int c[100][100] = { 0 };

	int n, m, l;
	int i, j, k;

	scanf("%d %d %d", &n, &m, &l);

	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			scanf("%lld", &a[i][j]);

	for (j = 0; j < m; j++)
		for (k = 0; k < l; k++)
			scanf("%lld", &b[j][k]);

	for (i = 0; i < n; i++)
		for (k = 0; k < l; k++)
			for (j = 0; j < m; j++)
				c[i][k] += a[i][j] * b[j][k];

	for (i = 0; i < n; i++)
		for (k = 0; k < l; k++) {
			printf("%lld", c[i][k]);

			if (k == l - 1)
				printf("\n");
			else
				printf(" ");
		}

	return 0;
}

Measured memory_bytes: 848
from sys import stdin

readline = stdin.readline
def main():
    _, *keys = map(lambda s: ''.join(sorted(s.rstrip())), open(0))
    # _, *keys = map(lambda s: tuple(sorted(s)), open(0))
    primes = {}
    res = 0
    for key in keys:
        if key in primes:
            res += primes[key]
            primes[key] += 1
        else:
            primes[key] = 1
    print(res)


if __name__ == "__main__":
    main()


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


int main(){
    string s;
    cin >> s;
    int ans = 0;
    rep(i,s.length()){
        if(s[i]=='+') ans++;
        else ans--;
    }
   cout << ans << endl;
}

Measured memory_bytes: 256
S,K=input().split()
K=int(K)
K=min(K,300)
mod=998244353
a=[]
val=0
for i in range(len(S)):
    if S[i]=="0":
        a.append(val)
        val=0
    else:
        val+=1

if val!=0:
    a.append(val)
m=len(a)
K=min(sum(a),K)

b=[a[i] for i in range(m)]
c=[a[i] for i in range(m)]
for i in range(1,m):
    b[i]+=b[i-1]
b=[0]+b
for i in range(m-2,-1,-1):
    c[i]+=c[i+1]

dp=[[0 for i in range(K+1)] for j in range(K+1)]
plus=[[0 for j in range(K+1)] for k in range(K+1)]
minus=[[0 for j in range(K+1)] for k in range(K+1)]

for j in range(K+1):
    dp[j][j]=1
    plus[j][j]=1
    minus[j][j]=1

for k in range(K+1):
    for j in range(1,K+1):
        plus[j][k]+=plus[j-1][k]

for j in range(K+1):
    for k in range(1,K+1):
        minus[j][k]+=minus[j][k-1]

for i in range(m-1,-1,-1):
    ndp=[[0 for j in range(K+1)] for k in range(K+1)]
    for k in range(min(b[i],K)+1):
        for j in range(min(K,k+c[i])+1):
            M=max(k-j,-a[i])
            if max(0,M)+j==0:
                ndp[j][k]+=plus[K][k]
            else:
                ndp[j][k]+=plus[K][k]-plus[(max(0,M))+j-1][k]
            if min(K-k,-M)>0:
                ndp[j][k]+=minus[j][k+min(K-k,-M)]-minus[j][k]
            ndp[j][k]%=mod
    dp=ndp
    for j in range(K+1):
        for k in range(K+1):
            plus[j][k]=ndp[j][k]
            minus[j][k]=ndp[j][k]

    for k in range(K+1):
        for j in range(1,K+1):
            plus[j][k]=(plus[j][k]+plus[j-1][k])%mod

    for j in range(K+1):
        for k in range(1,K+1):
            minus[j][k]=(minus[j][k]+minus[j][k-1])%mod


print(dp[0][0])

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

#define ll long long
#define mod 1000000007
#define pb push_back
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector< pi > 
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL)
const int N=100002,M=11;
int a[N],h[N];
vi v[N];
int main()
{
	ll x;
	cin>>x;
	for(ll i=-3981;i<=3981;i++)
	{
		for(ll j=-3981;j<=3981;j++)
		{
			if(i*i*i*i*i-j*j*j*j*j==x)
				return cout<<i<<" "<<j,0;
		}
	}
	return 0;
}

Measured memory_bytes: 5940
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def bfs(N):
    q = deque(["a"])

    res = []
    while q:
        s = q.popleft()
        if len(s) == N:
            res.append(s)
            continue

        n = len(set(list(s)))
        for i in range(n + 1):
            c = chr(ord("a") + i)
            q.append(s + c)

    return res


def main():
    N = int(input())
    ans = bfs(N)
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()


Measured memory_bytes: 15664
#include<bits/stdc++.h> 
// #define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define forn(i,o,n) for(int i=o;i<n;i++)
#define int long long
// #define endl "\n"
#define MOD 1000000007
#define double double
#define pb push_back
#define swap(x,y) (x^=y^=x^=y)
using namespace std;


int32_t main(){
     #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout); 
    #endif
        int n,k;
          cin>>n>>k;
          int a[n+1];
          for (int i=1;i<=n;i++)
               cin>>a[i];
          int  dp[n+1][k+1];
          int pre[n+1][k+1];
          for (int i=0;i<=n;i++)
               for (int j=0;j<=k;j++)
                    dp[i][j]=0;
          for (int i=0;i<=n;i++)
               dp[i][0]=1;
          pre[0][0]=dp[0][0];

          for (int i=1;i<=k;i++)
                pre[0][i]=(pre[0][i-1]+dp[0][i]);
          for (int i=1;i<=n;i++)
          {
               for (int j=0;j<=k;j++)
               {
                    int x=max(j-a[i],0);
                    if (x>0)
                      dp[i][j]=pre[i-1][j]-pre[i-1][x-1];
                    else
                      dp[i][j]=pre[i-1][j];

                 // dp[i][j]%=MOD;
               }
               pre[i][0]=dp[i][0];
               for (int j=1;j<=k;j++)
                  pre[i][j]=(pre[i][j-1]+dp[i][j])%MOD;
          }
         cout<<(dp[n][k]%MOD + MOD)%MOD<<"\n";

}

Measured memory_bytes: 161408
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
 
int main(){
    int n;
    int flag = 0;
    string ans[] = {"APPROVED", "DENIED"};
	cin>>n;
    int x[n];
    for (int i = 0; i < n; i++){
        cin>>x[i];
    }
    for (int i = 0; i < n; i++){
        if ((x[i]%2 == 0)&&((x[i]%3 != 0)&&(x[i]%5 != 0))){
                flag = 1;
        }
    }
	cout<<ans[flag]<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

    vector <string> a(H);
    for (int i = 0; i < H; i++){
        cin >> a[i];
    }

    int counth, countv;
    vector <int> h(0), v(0);
    for (int i = 0; i < H; i++){
        for (int j = 0; j < W; j++){
            if (a[i][j] == '#'){
                counth ++;
            }
        }
        if (counth > 0){
            h.push_back(i);
        }
        counth = 0;
    }
    for (int i = 0; i < W; i++){
        for (int j = 0; j < H; j++){
            if (a[j][i] == '#'){
                countv ++;
            }
        }
        if (countv > 0){
            v.push_back(i);
        }
        countv = 0;
    }

    
    for (int i = 0; i < h.size(); i++){
        for (int j = 0; j < v.size(); j++){
            cout << a[h[i]][v[j]];
        }
        cout << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cmath>

bool cmp(std::tuple<long, long, long>l,
         std::tuple<long, long, long>r) {
  long sum_l =
    std::get<0>(l) + std::get<1>(l) + std::get<2>(l);
  long sum_r =
    std::get<0>(r) + std::get<1>(r) + std::get<2>(r);

  return sum_l < sum_r;
}

long
sum(std::vector<std::tuple<long, long, long>> const& v,
    size_t m) {
  long x=0;
  long y=0;
  long z=0;
  for (size_t i=0; i<m; i++) {
    x+=std::get<0>(v[i]);
    y+=std::get<1>(v[i]);
    z+=std::get<2>(v[i]);
  }

  return std::abs(x) + std::abs(y) + std::abs(z);
}

int main() {
  size_t N, M;

  std::cin >> N;
  std::cin >> M;

  std::vector<std::tuple<long, long, long>> ppp(N);
  std::vector<std::tuple<long, long, long>> ppm(N);
  std::vector<std::tuple<long, long, long>> pmp(N);
  std::vector<std::tuple<long, long, long>> pmm(N);
  std::vector<std::tuple<long, long, long>> mpp(N);
  std::vector<std::tuple<long, long, long>> mpm(N);
  std::vector<std::tuple<long, long, long>> mmp(N);
  std::vector<std::tuple<long, long, long>> mmm(N);

  for (size_t i=0; i<N; i++) {
    long x, y, z;
    std::cin >> x;
    std::cin >> y;
    std::cin >> z;

    ppp[i] = std::make_tuple( x,  y,  z);
    ppm[i] = std::make_tuple( x,  y, -z);
    pmp[i] = std::make_tuple( x, -y,  z);
    pmm[i] = std::make_tuple( x, -y, -z);
    mpp[i] = std::make_tuple(-x,  y,  z);
    mpm[i] = std::make_tuple(-x,  y, -z);
    mmp[i] = std::make_tuple(-x, -y,  z);
    mmm[i] = std::make_tuple(-x, -y, -z);
  }

  std::sort(ppp.begin(), ppp.end(), cmp);
  std::sort(ppm.begin(), ppm.end(), cmp);
  std::sort(pmp.begin(), pmp.end(), cmp);
  std::sort(pmm.begin(), pmm.end(), cmp);
  std::sort(mpp.begin(), mpp.end(), cmp);
  std::sort(mpm.begin(), mpm.end(), cmp);
  std::sort(mmp.begin(), mmp.end(), cmp);
  std::sort(mmm.begin(), mmm.end(), cmp);

  long ans =
    std::max({sum(ppp, M),
          sum(ppm, M),
          sum(pmp, M),
          sum(pmm, M),
          sum(mpp, M),
          sum(mpm, M),
          sum(mmp, M),
          sum(mmm, M)});

  std::cout << ans << std::endl;

  return 0;
}


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


vector<bool> hurui(int n){
    vector<bool> A(n + 1, true);
    A[0] = A[1] = false;
    for (int i = 1; i * i <= n; i++){
        if (!A[i])
            continue;
        for (int j = 2 * i; j <= n; j += i)
            A[j] = false;
    }
    return A;
}

signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
    cout << fixed << setprecision(20);
    int n;
    cin >> n;
    auto A = hurui(n + 2);
    int ans = 0;
    for (int i = 0; i <= n; i++){
        if (!A[i])
            continue;
        if (A[2 + i])
            ans += 2;
    }
    cout << ans << endl;
}


Measured memory_bytes: 4132
#B=FLIP
n,m,k=map(int,input().split())
flag=False
for i in range(n+1):
    for j in range(m+1):
        if m*i+n*j-2*i*j==k:
            flag=True
            break
if flag:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 2940
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>
#include <map>

using namespace std;
using lli = long long int;
using ll = long long;

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

    for(int i = 0 ; i < S.length() ; i++) {
        int x = S[i] - 'A';
        x = (x + N) % 26;
        S[i] = x + 'A';
    }
    cout << S << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define ld long double
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;

ll n, a, b;

int main() {	
	scanf("%lld %lld %lld", &n, &a, &b);
	if((b - a) % 2 == 0) {
		printf("%lld", (b - a) / 2);
	}
	else {
		ll lewo = a - 1 + 1 + (b - a - 1) / 2;
		ll prawo = (n - b) + 1 + (n - (a + (n - b + 1))) / 2;
		lewo = min(lewo, b - 1);
		prawo = min(prawo, n - a);
		printf("%lld\n", min(lewo, prawo)); 
	}
	
	return 0;
}



Measured memory_bytes: 256
while true
  n = gets.strip.to_i
  break if n == 0

  walls = []
  n.times.each do
    x, y, r = gets.strip.split(" ").map{|s| s.to_i}
    walls.push [x, y, r]
  end

  m = gets.strip.to_i

  m.times.each do
    tx, ty, sx, sy = gets.strip.split(" ").map{|s| s.to_i}
    danger = true

    for w in walls
      td2 = (w[0] - tx) ** 2 + (w[1] - ty) ** 2
      sd2 = (w[0] - sx) ** 2 + (w[1] - sy) ** 2
      r2 = w[2] ** 2

      if td2 < r2 && sd2 > r2 || td2 > r2 && sd2 < r2
        danger = false
        break
      end

      if td2 > r2 && sd2 > r2
        vx = tx - sx
        vy = ty - sy
        v2 = vx ** 2 + vy ** 2
        t = ((w[0] - sx) * vx + (w[1] - sy) * vy).to_f / v2
        px = t * vx + sx
        py = t * vy + sy
        if t > 0 && t < 1 && (px - w[0]) ** 2 + (py - w[1]) ** 2 <= r2
          danger = false
          break
        end
      end
    end

    puts danger ? "Danger" : "Safe"
  end
end

Measured memory_bytes: 6172
import java.util.*;
import java.util.Arrays;
public 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];
      for(int i= 0;i<n;i++){
        a[i] = sc.nextInt();
      }
      Arrays.sort(a);
      int sum  =0;
      for(int i=0;i<k;i++){
        sum += a[i];
      }
      System.out.println(sum);
      
      

     
    }
   
    
       
    
}

Measured memory_bytes: 30208
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <cstdio>
#include <climits>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
struct Edge {
    int to, cost;
    Edge(int to, int cost): to(to), cost(cost) {}
};

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<Edge>> AdjList;
AdjList graph;

const int INF = 100000000;



int GCD(int a, int b){
    if(a < b) swap(a, b);
    if(b == 0) return a;
    return GCD(b, a%b);
}

ll a[100010];

bool cmp(const pair<int, int> &a, const pair<int, int> &b){
    if(a.first == b.first) return a.second == b.second;
    return a.first < b.first;
}
vector<pair<int, int>> vp;
int main() {
    //cout << fixed << setprecision(15);

    int N; cin >> N;

    for(int i=0; i<N; ++i){
        int A = readInt(), B = readInt();
        vp.push_back({B, A});
    }
    sort(all(vp), cmp);
    ll t=0;
    bool c = true;
    
    for(int i=0; i<N; ++i){
        t += vp[i].second;
        if(t > vp[i].first){
            c = false;
        }
    }
    if(c){
        cout << "Yes" << endl;

    }else cout << "No" << endl;


    return 0;
}

Measured memory_bytes: 2420
#include <stdio.h>

int main(void){
	int n, x, y, h, w, i, j, s, asum;
	while(1){
		scanf("%d",&n);
		if(!n) break;
		s = 0;
		for(i = 0;i < n;i++){
			scanf("%d%d%d%d",&x,&y,&h,&w);
			asum = x + y + h;
			if(asum <= 60 && w <= 2)
				s += 600;
			else if(asum <= 80 && w <= 5)
				s += 800;
			else if(asum <= 100 && w <= 10)
				s += 1000;
			else if(asum <= 120 && w <= 15)
				s += 1200;
			else if(asum <= 140 && w <= 20)
				s += 1400;
			else if(asum <= 160 && w <= 25)
				s += 1600;
		}
		printf("%d\n",s);
	}
	return 0;
}

Measured memory_bytes: 1028
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>
#include <set>
#include <unordered_set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <complex>
#include <regex>
#include <locale>
#include <random>
#include <type_traits>
#include <chrono>

using namespace std;

#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

using LL = long long;

int main() {

    int N;
    cin >> N;

    int ans = 0;
    for (int i = 1; i <= N; i++) {
        int cnt = 0;
        int d = i;
        while(d){
            d /= 10;
            cnt++;
        }
        if(cnt % 2)ans++;
    }

    cout << ans << endl;

}





































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

const int maxn=8;
bool graph[maxn][maxn];


int main(){
  int n,m;
  cin >> n >> m;
  for (int i=0;i<m;i++){
    int a,b;
    cin >> a >> b;
    graph[a-1][b-1]=graph[b-1][a-1]=true;
  }
  vector<int> v(n-1);
  for (int i=0;i<n-1;i++){
    v.at(i)=i+1;
  }
  bool flag=1;
  int count=0;
  do {
    flag=1;
    for (int j=0;j<n-2;j++){
      if(graph[0][v.at(0)]){
        if(graph[v.at(j)][v.at(j+1)]==0){
          flag=0;
        }
      }
      else{
        flag=0;
      }
    }
    if (flag){
        count++;
    }
  }
  while (next_permutation(v.begin(), v.end()));
  
  cout << count << endl;
  
}

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

//#define int long long
//using ll = boost::multiprecision::cpp_int;
using ll = long long;
//constexpr int INF = 1e9;//INT_MAX=(1<<31)-1=2147483647
constexpr ll INF = (ll)1e18;//(1LL<<63)-1=9223372036854775807
constexpr ll MOD = (ll)1e9 + 7;
constexpr double EPS = 1e-9;
constexpr int dx[4]={1,0,-1,0};
constexpr int dy[4]={0,1,0,-1};
#ifdef LOCAL_ENV
	#define debug(var) std::cout<<#var" = "<<var<<std::endl
#else
	#define debug(var)
#endif
#define p(var) std::cout<<var<<std::endl
#define rep(i, n)   for(ll i=0, i##_length=(n); i< i##_length; ++i)
#define repeq(i, n) for(ll i=1, i##_length=(n); i<=i##_length; ++i)
#define all(a) (a).begin(), (a).end()
#define PI (acos(-1))
template<typename T> inline T power(T x, T n){ return n ? power(x*x%MOD,n/2)*(n%2?x:1)%MOD : 1; }
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b,a%b) : a; }
template<typename T> inline T lcm(T a, T b) { return a / gcd(a,  b) * b; }
template<typename T1, typename T2>inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2>inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	for (int i = 0, len = v.size(); i < len; ++i){
		s << v[i]; if (i < len - 1) s << "\t";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
	for (int i = 0, len = vv.size(); i < len; ++i){
		s << vv[i] << endl;
	}
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const map<T1, T2>& m) {
	s << "{" << endl;
	for (typeof(m.begin()) itr = m.begin(); itr != m.end(); ++itr){
		s << "\t" << (*itr).first << " : " << (*itr).second << endl;
	}
	s << "}" << endl;
	return s;
}

/*-----8<-----8<-----*/

constexpr ll N_MAX = 2000;
constexpr ll Y_MAX = 2;

ll N, Y;

void input() {
	scanf("%lld%lld", &N, &Y);
}

void solve() {
	ll ans = 0;
	rep(i,N+1){
		rep(j,N+1-i){
			ll okane=10000*i+5000*j+1000*(N-i-j);
			if(Y==okane){
				printf("%lld %lld %lld\n", i, j, N-i-j);
				return;
			}
		}
	}


	printf("-1 -1 -1\n");
}

signed main() {
	input();
	solve();
	return 0;
}


Measured memory_bytes: 256
n, m = map(int,input().split())
x = sorted(list(map(int, input().split())))
if n >= m:
    print(0)
    exit()
xd = []
for i in range(m-1):
    xd.append(x[i+1]-x[i])
xd.sort()
print(sum(xd[:m-n]))

Measured memory_bytes: 13960
#include<iostream>
#include<numeric>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<map>
#include<utility>
#include<cmath>
#include<tuple>
#include<string>
#include<bitset>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
using namespace std;
typedef long long ll;

int main(){
    int a;
    cin>>a;
    cout<<a+a*a+a*a*a<<endl;
}

Measured memory_bytes: 3628
import java.util.*
fun main(args: Array<String>){
	val cin = Scanner(System.`in`)
    val n = cin.nextInt()
    val m = cin.nextInt()
    var lmax = 1
    var rmin = n
    for (i in 1..m) {
        val l = cin.nextInt()
        val r = cin.nextInt()
        if (l > lmax) {
            lmax = l
        }
        if (rmin > r) {
            rmin = r
        }
    }

    val ans = rmin - lmax + 1
    if (ans >= 0) {
        println(ans)
    } else {
        println(0)
    }
}

Measured memory_bytes: 67184
#include<stdio.h>
int main()
{
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	if(a==b&&b==c)
	{
		printf("No");
		return 0;
	}
	if(a!=b&&b!=c&&a!=c) printf("No");
	else printf("Yes");
	return 0;
}

Measured memory_bytes: 128
import sys

input=sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


def LI(): return list(map(int,input().split()))


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))


# rstrip().decode('utf-8')
import numpy as np

def main():
	n,k=MI()
	s=set()
	for _ in range(k):
		d=II()
		A=set(LI())
		s|=(A)
	print(n-len(s))
	
	









if __name__=="__main__":
	main()


Measured memory_bytes: 27064
#include <stdio.h>

int main() {
	int n, cnt = 0;
	char a[100], b[100], c[100];
	scanf("%d",&n);
	scanf("%s",a);
	scanf("%s",b);
	scanf("%s",c);
	
	for(int i=0;i<n;i++) {
		if (a[i]==b[i] && a[i]==c[i]) continue;
		if (a[i]==b[i] && a[i]!=c[i]) {cnt++;continue;}
		if (a[i]!=b[i] && a[i]==c[i]) {cnt++;continue;}
		if (a[i]!=b[i] && b[i]==c[i]) {cnt++;continue;}
		cnt+=2;
	}
	
	printf("%d\n",cnt);
	return 0;
}


Measured memory_bytes: 888
#include <iostream>

using namespace std;

int main()
{
    long long value;
    while(cin >> value){
        int divisor = 0;
            int temp = value;
            while(temp!=0){
                divisor += temp%10;
                temp /=10;
            }
            if(value%divisor == 0){
                cout << "Yes" << endl;
            }
            else
                cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

ll a, b, c;

ll sol1(ll x, ll y, ll z){
	ll ret = x - (x & 1);
	x &= 1;
	
	if(x && y && z) ret += 3, y--, z--;
	ret += y + z - (y & 1) - (z & 1);
	
	return ret;
}

ll sol2(ll x, ll y, ll z){
	ll ret = y + z - (y & 1) - (z & 1);
	y &= 1, z &= 1;
	
	if(x && y && z) ret += 3, x--;
	ret += x - (x & 1);
	
	return ret;
}

ll sol3(ll x, ll y, ll z){
	ll ret = min({x, y, z});
	x -= ret, y -= ret, z -= ret;
	ret *= 3;
	
	ret += x + y + z - (x & 1) - (y & 1) - (z & 1);
	
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	ll ret;
	
	cin >> a >> ret >> b >> b >> c;
	
	ret += max({sol1(a, b, c), sol2(a, b, c), sol3(a, b, c)});
	
	cout << ret << endl;

	return 0;
}

Measured memory_bytes: 3636