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

using namespace std;
typedef long long ll;
#define mp make_pair

const int N = 200;
int a[N];

int main() {
	//	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);	
	int n;
	cin >> n;
	int sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	if (sum % 10 != 0) {
		cout << sum << endl;
		return 0;
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		if (a[i] % 10 != 0) {
			cout << sum - a[i] << endl;
			return 0;
		}
	}
	cout << "0" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<int>>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

int main() {
    int X, Y;
    cin >> X >> Y;
    if(X > Y)
        swap(X, Y);
    if((X + Y) % 3 != 0) {
        cout << 0 << endl;
        return 0;
    }

    int d = (X + Y) / 3;
    X -= d;
    if(X < 0) {
        cout << 0 << endl;
        return 0;
    }

    vector<ll> fac(d + 5), finv(d + 5), inv(d + 5);
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i <= d; ++i) {
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        fac[i] = fac[i - 1] * i % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }

    cout << fac[d] * (finv[d - X] * finv[X] % MOD) % MOD << endl;
    return 0;
}


Measured memory_bytes: 15872
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    # X 以上の素数のうち、最小のもの
    X = int(input())
    PrimeList = defaultdict(int)
    while True:
        # X を増やし続ける
        i = 2
        a = X
        flag = True
        while i * i <= a:
            if a % i == 0:
                X += 1
                # 素因数があったら駄目です
                flag = False
                break
            else:
                i += 1
        if flag:
            print(X)
            exit()

if __name__ == '__main__':
  main()


Measured memory_bytes: 5788
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <numeric>
#include <string>
#include <bitset>
#include <functional>

using ld = long double;
using vld = std::vector<ld>;
using vvld = std::vector<vld>;
using vvvld = std::vector<vvld>;
using ll = long long;
using vll = std::vector<ll>;
using vvll = std::vector<vll>;
using vvvll = std::vector<vvll>;
using pll = std::pair<ll, ll>;
using vpll = std::vector<pll>;
using str = std::string;
using vstr = std::vector<str>;

template<typename T> bool chmin(T a, T &b) { return a < b ? b = a, true : false; }
template<typename T> bool chmax(T a, T &b) { return a > b ? b = a, true : false; }

constexpr ld PI = 3.141592653589793L;
constexpr ld EPS = std::numeric_limits<ld>::epsilon();

ll gcd(ll n, ll m) { return m ? gcd(m, n % m) : n; }
ll lcm(ll n, ll m) { return n / gcd(n, m) * m; }
bool is_prime(ll n) {
    if (n == 1) return false;
    for (ll i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}
ll rpow(ll x, ll n) {
    if (n == 0) return 1;
    ll k = 1;
    for (; n > 1; n /= 2) {
        if (n & 1) k *= x;
        x *= x;
    }
    return k * x;
}
ll modpow(ll x, ll n, ll mod) {
    if (n == 0) return 1;
    ll k = 1;
    for (; n > 1; n /= 2) {
        if (n & 1) (k *= x) %= mod;
        (x *= x) %= mod;
    }
    return k * x % mod;
}
ll modcomb(ll n, ll r, ll mod) {
    if (r < 0 || n < r) return 0;
    chmin(n - r, r);
    ll mul = 1, div = 1;
    for (ll i = 0; i < r; i++) {
        (mul *= n - i) %= mod;
        (div *= i + 1) %= mod;
    }
    return mul * modpow(div, mod - 2, mod) % mod;
}

/*------------------------------------------------------------------------*/

void solve();

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

    solve();
}
void solve() {
    ll a, b, c, x;
    std::cin >> a >> b >> c >> x;

    ll ans = 0;
    for (ll i = 0; i <= a; i++) for (ll j = 0; j <= b; j++) for (ll k = 0; k <= c; k++)
        ans += 500 * i + 100 * j + 50 * k == x;

    std::cout << ans << '\n';
}


Measured memory_bytes: 3592
N = gets.to_i
A = gets.split.map(&:to_i)

ans = 1000
k = 0

(N - 1).times do |i|
  if A[i] <= A[i + 1]
    tp = ans / A[i]
    k += tp
    ans -= tp * A[i]
  else
    ans = ans + A[i] * k
    k = 0
  end
end

ans += A[N - 1] * k

puts ans


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

using namespace std;

int main() {
  vector<int> a(5);
  cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];

  sort(a.begin(), a.end(), [](const int& a, const int& b) {
    if((a % 10) == 0 && (b % 10) == 0) return false;
    else if((a % 10) == 0) return true;
    else if((b % 10) == 0) return false;
    else return 10 - (a % 10) < 10 - (b % 10);
  });

  int ans =0;
  for(int i=0; i<4; i++) {
    int t = a[i]%10;
    ans += (t==0) ? a[i] : a[i] + (10 - t);
  }
  ans += a[4];

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include<algorithm>
#include <cmath>
using namespace std;
int main(){
	while(1){
	double a,b,c;
	scanf("%lf %lf %lf",&a,&b,&c);
	if(a+b+c==0) break;
	int ans=0,u,w;
	for(int i=2;i<=(int)sqrt(a);i++){
		bool d=false;
			for(int k=2;k*k<=i;k++){
				if(i%k==0){
					d=true;
					break;
				}
			}
			if(d) continue;
		for(int j=max((int)(ans/i),2);j<=min(a/i,(int)i*c/b);j++){
			bool r=false;
			for(int k=2;k*k<=j;k++){
				if(j%k==0){
					r=true;
					break;
				}
			}
			if(r) continue;
			if(i*j<=a && ans<i*j){
				ans=i*j;
				u=i;
				w=j;
			}
		}
	}
	printf("%d %d\n",u,w);
	}
}

Measured memory_bytes: 1056
#include<iostream>
using namespace std;
long L,A,B,M;
long ten[99],sten[99],iten[99];
long n;
long cnt[18],SUM[18];
long pre,tmpten,ans,ll,rr,mm,k,X,Y,p,g;
main()
{
	cin>>L>>A>>B>>M;
	pre=-1,tmpten=1;
	for(n=1;n<=18;n++)
	{
		cnt[n-1]=1;
		ll=pre,rr=L;
		tmpten*=10;
		while(rr-ll>1)
		{
			mm=(ll+rr)/2;
			if(A+B*mm<tmpten)ll=mm;
			else rr=mm;
		}
		k=ll-pre;
		if(k<0)
		{
			continue;
		}
		pre=ll;
		ten[0]=tmpten%M;
		sten[0]=1;
		iten[0]=0;
		if(k&1)cnt[n-1]=tmpten%M;
		for(int i=1;i<61;i++)
		{
			ten[i]=ten[i-1]*ten[i-1]%M;
			sten[i]=(ten[i-1]+1)%M*sten[i-1]%M;
			iten[i]=((ten[i-1]+1)%M*iten[i-1]+(1LL<<i-1)%M*sten[i-1]%M*ten[i-1])%M;
			if(k>>i&1)cnt[n-1]=cnt[n-1]*ten[i]%M;
		}
		X=0,p=1,Y=0,g=0;
		for(int i=61;i--;)
		{
			if(k>>i&1)
			{
				(X+=sten[i]*p)%=M;
				(Y+=(iten[i]+sten[i]*g)%M*p)%=M;
				p=p*ten[i]%M;
				g=(g+(1LL<<i))%M;
			}
		}
		SUM[n-1]=(((A+B*ll)%M*X-B%M*Y)%M+M)%M;
	}
	p=1;
	for(int i=18;i--;)
	{
		ans=(ans+SUM[i]*p)%M;
		p=p*cnt[i]%M;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long       ll;
#define PI                acos(-1)
#define pb                push_back
#define mp                make_pair
#define mt                make_tuple
#define all(a)            (a).begin(), (a).end()
#define clr(a,h)          memset(a, (h), sizeof(a))
#define F first
#define S second
#define fore(i,b,e)		  for(int i=(int)b;i<(int)e;++i)
#define forr(i,b,e)		  for(int i=(int)b;i<(int)e;++i)
#define deb(x)			  cerr << "# " << (#x) << " = " << (x) << endl;
#define sz(x)             (int)x.size()
int faster_in(){int r=0,c;for(c=getchar();c<=32;c=getchar());if(c=='-') return -faster_in();for(;c>32;r=(r<<1)+(r<<3)+c-'0',c=getchar());return r;}

using namespace std;

typedef pair<int, int>  ii;
typedef vector<int>     vi;
typedef vector<ii>      vii;
typedef vector<ll>      vll;
const int INF = 1234567890;

int main()
{
    std::ios::sync_with_stdio(false); cin.tie(0);
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    string s;
    cin >> s;
    if (s.back() == 's') s += "es";
    else s += "s";
    cout << s << '\n';
    return 0;
}
// Dinosaurs are cool!

Measured memory_bytes: 3636
D = int(input())
C = list(map(int, input().split()))
S = []
for _ in range(D):
    s_row = list(map(int, input().split()))
    S.append(s_row)

results = []

# Cを無視して最大値をとる
# for d in range(D):
#     s_row = S[d]
#     max_value = max(s_row)
#     max_index = s_row.index(max_value)
#     results.append(max_index+1)

# 26種類順番にやる
# for d in range(D):
#     results.append((d % 26) + 1)
#     results.append(max_index+1)

# 次の日に減る分も考慮して選ぶ
last = [0 for i in range(26)]
next_costs = [0 for i in range(26)]

for d in range(D):

    for i in range(26):
        next_costs[i] = C[i] * (d-last[i])

    result = -100000
    next_costs_sum = sum(next_costs)
    result_idx = -1
    for i in range(26):
        tmp_result = - (next_costs_sum - C[i] * (d-last[i]))
        if tmp_result > result:
            result = tmp_result
            result_idx = i
    last[result_idx] = d
    results.append(result_idx + 1)

for result in results:
    print(result)


Measured memory_bytes: 68392
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()
N = len(S)
a = S[:(N - 1) // 2]
b =  S[(N + 1) // 2 :]
# print(a, b)
# print(a[::-1], b[::-1])
if S == S[::-1] and a == a[::-1] and b == b[::-1]:
    print("Yes")
    exit()
print("No")

    




Measured memory_bytes: 5392
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,t,sum=0;
	cin>>n>>t;
	for(int i=0;i<t;i++){
		int x;
		cin>>x;
		sum+=x;
	}
	printf("%s\n",sum>=n?"Yes":"No");
	return 0;
} 

Measured memory_bytes: 256
N,K = map(int,input().split())
h = list(map(int,input().split()))
ans = [0]*N
ans[1] = abs(h[1] - h[0])
for i in range(N - 2):
  j = i + 2
  step = min(K , j)
  height = h[j]
  p = [ans[j - s - 1] + abs(h[j-s-1] - height)
       for s in range(step)]
  ans[j] = min(p)
print(ans[N - 1])  

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

using namespace std;

// Repetitions
#define FOR(i,a,n) for(ll i = ((ll) a); i < ((ll) n); ++i)
#define FORR(i, s, g) for(ll i = ((ll)s - 1); i >= ((ll) g); --i)
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) FORR(i, n, 0)

// Container Utils
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define SORTALL(v) sort(ALL(v))
#define SZ(a) int((a).size())
#define CLR(a) memset((a), 0 ,sizeof(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())

// For Debug
#define DMP(x)  cerr << #x << " = " << (x) << endl
#define DBG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

// Aliases
#define PB push_back
#define MP make_pair
typedef long long ll;
typedef string str;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

// I/O Asynchronizing
struct aaa{
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
    };
}aaaaaaa;

int main() {
    int sum = 0;
    REP(i, 4) {
        int t;
        cin >> t;
        sum += t;
    }

    cout << sum / 60 << "\n" << sum % 60 << "\n";

    return 0;
}



Measured memory_bytes: 3156
#include <stdio.h>
int main()
{
	int n, m;
	while(scanf("%d %d", &n, &m))
	{
		bool ok = true, go = false;
		
		if(n == 0 && m == 0)
		{
			break;
		}
		
		for(int i = 0; i < n ; i++)
		{
			if(ok)
			{
				go = true;
				for(int j = 0; j < m ; j++)
				{
					if(go)
					{
						printf("#");
						go = false;
					}
					else 
					{
						printf(".");
						go = true;
					}
					
				}
				printf("\n");
				ok = false;	
			}
			else
			{
				go = true;
				for(int j = 0; j < m ; j++)
				{
					if(go)
					{
						printf(".");
						go = false;
					}
					else 
					{
						printf("#");
						go = true;
					}
					
				}
				printf("\n");
				ok = true;	
			}
		}
		printf("\n");
		
	}
	return 0;
}


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

int main() {
	int t[4], sum=0, m, s;
	for(int i=0; i<4; i++){
		cin >> t[i];
		sum += t[i];
	}
	s = sum%60;
	m = sum/60;
	cout << m << endl;
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 3100
/*
 It's better to sleep happy and tired rather than disappointed and frustrated
 There's only 1 thing that's impossible and that is defeating a man who doesn't give up
*/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mx2 102
#define mx3 1003
#define mx4 10004
#define mx5 100005
#define mx6 1000006
#define mod 1000000007
#define PI 3.14159265
#define deb(x) cout << #x << " " << x << endl;
#define fo(i,n) for(int i=0 ; i<n ; i++)
#define Fo(i,k,n) for(int i=k ; i<n ; i++)
 
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pair<int,int>,int> piii;

const int inf=0x3f3f3f3f;
int n,m , ans , sum , a , b ,arr[mx3][mx3],dp[mx3][mx3];
string str;

int solve(int i , int j )
{
	if(i>=n || j>=m)
	{
		return 0;
	}
	if(i==n-1 && j==m-1)
	{
		return 1;
	}
	
	if(arr[i][j]==1)
	{
		return 0;
	}
	if(dp[i][j]!=-1)
	{
		return dp[i][j];
	}
	dp[i][j]=(solve(i+1,j)+solve(i,j+1))%mod;
	return dp[i][j];
}
 
int main() {
	ios::sync_with_stdio(false);
	//int t;cin>>t;while(t--)
	{
		cin>>n>>m;
		fo(i,n)
		{
			cin>>str;
			fo(j,str.length())
			{
				if(str[j]!='.')arr[i][j]=1;
			}
		}
		memset(dp,-1,sizeof(dp));
		cout<<solve(0,0);
	}
	return 0;
}


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

int main() {
    int N, X, c;
    int ans = 1;
    int h = 0;
    cin >> N >> X;
    for(int i=0; i < N; i++) {
        cin >> c;
        h += c;
        if (h <= X) {
            ans += 1;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
h = []
for i in range(N):
  h.append(int(input()))
h.sort()
h.reverse()

min = 10 ** 20

for i in range(N):
  if i+K > N:
    break
  diff = h[i] - h[i+K-1]
  if diff < min:
    min = diff

print(min)

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

#define HAS_TEST_CASE 0

namespace rG{

typedef long long ll;

const int N=5e5;

int n,m,k,a[N+10];
char s[N+10];
int f[N+10];

int getRt(int u){return f[u]==u?u:f[u]=getRt(f[u]);}
void merge(int u,int v){f[getRt(u)]=getRt(v);}

inline void main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		merge(u,v);
	}
	memset(a,-1,sizeof(a));
	for(int i=1;i<=n;i++){
		if(a[getRt(i)]==-1)a[getRt(i)]=0;
		a[getRt(i)]++;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(a[i]!=-1)
			ans=std::max(ans,a[i]);
	printf("%d\n",ans);
}

} // namespace rG

int main(){
#if defined(LOCAL)&&HAS_TEST_CASE
	freopen("tmp.out","w",stdout);
#endif
#if HAS_TEST_CASE
	int T;
	scanf("%d",&T);
	while(T--)rG::main();
#else
	rG::main();
#endif
	return 0;
}


Measured memory_bytes: 12744
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let a: u32 = read();
    let b: u32 = read();

    let ans = if a >= 13 {
        b
    } else if a >= 6 {
        b / 2
    } else {
        0
    };

    println!("{}", ans);
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


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

int main(void) {
    int N,M,X,Y;cin>>N>>M>>X>>Y;
    vector<int> x(N),y(M);
    for (int i = 0; i < N; i++) cin>>x[i];
    for (int i = 0; i < M; i++) cin>>y[i];
    if (X >= Y) {
        cout << "War" << endl;
        return 0;
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    if (x[N - 1] < y[0] && x[N - 1] < Y && y[0] > X) cout << "No War" << endl;
    else cout << "War" << endl;   
    return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpl;
typedef vector<vll> vvll;

#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define no cout<<"No"<<endl
#define NO cout<<"NO"<<endl
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

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

  ll l,r,d;
  cin>>l>>r>>d;
  ll ans=0;
  for(ll i=l; i<=r; i++){
    if(i%d==0)
      ans++;
  }

  cout<<ans<<endl;
}



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


def solve(S: str, K: int):
    S = list(map(lambda c:int(c), S))
    for i in range(len(S)):
        #print("i = {}".format(i))
        if S[i] == 1 and i+1 == K:
            print(1)
            break
        elif S[i] != 1:
            print(S[i])
            break
    return


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

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
import itertools
n,m = map(int,input().split())
a = []
c = 0
for _ in [0]*m:
  a += [list(map(int,input().split()))]
for x in list(itertools.permutations(range(2,n+1))):
  y = [1] + list(x)
  f = True
  for i in range(1,n):
    if (not [y[i-1],y[i]] in a) and (not [y[i],y[i-1]] in a):
      f = False
      break
  if f:
    c += 1
print(c)

Measured memory_bytes: 3700
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>
#include <random>
#include <complex>
#include <functional>
#include <tuple>

using namespace std;

#define Rep(i,a,b) for(ll i = a; i < b; ++i)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")

using ll = long long;

constexpr int inf = 1e9 + 7;
constexpr ll infll = 1ll << 60ll;
constexpr ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

namespace {
    template<typename T> void chmax(T& a, T b) { a = std::max(a, b); }
    template<typename T> void chmin(T& a, T b) { a = std::min(a, b); }
    template<typename T> void chadd(T& a, T b) { a = a + b; }

    void Cout(long long x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const T& x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const std::vector<T>& x, const char* sep = " ", const char* end = "\n") { for (std::size_t i = 0, sz = x.size(); i < sz; i++) { std::cout << x[i] << (i == sz - 1 ? end : sep); } }

    // 標準入出力
    struct inp {
        std::size_t sz;
        inp(std::size_t _sz = 1) : sz(_sz) {}
        template <typename T> operator T () const { T a; std::cin >> a; return a; }
        template <typename T> operator std::vector<T>() const { vector<T> a(sz); for (std::size_t i = 0; i < sz; i++) std::cin >> a[i]; return a; }
        template <typename T, typename U> operator std::pair<T, U>() const { T f; U s; std::cin >> f >> s; return std::pair<T, U>(f, s); }
    };

    inp inp1; // input one
}

int main() {

    int n, k;
    cin >> n >> k;
    vector<int> p = inp(n);

    vector<int> sum(n + 1, 0);
    rep(i, n) {
        sum[i + 1] = sum[i] + p[i];
    }

    int ma = 0;
    int ti = 0;
    rep(i, n - k + 1) {
        int tmp = sum[i + k] - sum[i];
        if (ma < tmp) {
            ma = tmp;
            ti = i;
        }
    }

    double ans = 0.0;

    Rep(i, ti, ti + k) {
        ans += (p[i] + 1) / 2.0;
    }

    cout << fixed << setprecision(7) << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
from itertools import accumulate
N, C = map(int, input().split())

X, V = [], []
for i in range(N):
    x, v = map(int, input().split())
    X.append(x)
    V.append(v)


# 右向き・左向きに進み、i番目の寿司までたどり着いた時点のコストを無視したエネルギー
R_v = list(accumulate(V))
L_v = list(accumulate(V[::-1]))

# 右向き・左向きに進み、i番目の寿司までたどり着いた時点のエネルギー
R_xv, L_xv = [], []
for i in range(N):
    R_xv.append(R_v[i] - X[i])
    L_xv.append(L_v[i] - (C - X[N - i - 1]))

# 右向き・左向きに進み、i番目の寿司までたどり着いた時点のエネルギーのmax累積和
R_xv_max = list(accumulate(R_xv, func=max))
L_xv_max = list(accumulate(L_xv, func=max))

ans = 0
for i in range(N):
    ans = max(ans, R_xv[i], L_xv[i])
    if i < N - 1:
        ans = max(ans,
                  R_xv[i] - X[i] + L_xv_max[N - i - 2],
                  L_xv[i] - (C - X[N - i - 1]) + R_xv_max[N - i - 2]
                  )

print(ans)


Measured memory_bytes: 30776
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
int main(void){
    ll N;
    cin>>N;
    ll V[N],C[N];
    rep(0,i,N)cin>>V[i];
    rep(0,i,N)cin>>C[i];
    ll ans=0;
    rep(0,i,N){
        if(V[i]-C[i]>0)ans+=V[i]-C[i];
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 384
from collections import defaultdict
import io
import math

data = input()
counter = 0
for o in range(1 << (len(data) - 1)):
    array = data[0]
    for i in range(len(data) - 1):
        if o & 1 << i:
            array += '+'
        array += data[i + 1]
    counter += eval(array)
print(counter)

Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#define int long long
signed main() {
	int n;cin>>n;
	vector<vector<int>>cnt1(3);
	for(int k=0;k<3;k++){
		for(int i=0;i<n;i++){
			int a;cin>>a;
			if(k)cnt1[k].push_back(a);
			else cnt1[k].push_back(1e9-a);
		}
		sort(cnt1[k].begin(), cnt1[k].end());
	}
	
	int ans = 0;
	int pre=-1;
	int a,b;
	for(int i=0;i<n;i++){
		if(cnt1[1][i]==pre){
			ans += a*b;
			continue;	
		}
		a = distance(upper_bound(cnt1[0].begin(), cnt1[0].end(), 1e9-cnt1[1][i]), cnt1[0].end());
		b = distance(upper_bound(cnt1[2].begin(), cnt1[2].end(), cnt1[1][i]), cnt1[2].end());
		
		ans += a*b;
		pre = cnt1[1][i];
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 3444
//#define _GLIBCXX_DEBUG
#include <iostream>
#include <bits/stdc++.h>


using namespace std;
#define ll long long
#define ld long double
#define  P pair<ll,ll>
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define FORr(i,m,n) for(ll i=n; i>=(ll)m; i--)
#define FORm(i,m) for(auto i=m.begin();i!=m.end();i++)
#define sortAl(v) sort(v.begin(),v.end())
#define sortAlr(v) sort(v.begin(),v.end()); reverse(v.begin(),v.end())
#define cout(n) cout<<fixed<<setprecision(n)

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

    ll sum=0;
    FOR(i,1,1e6){
      if((n-i)%i == 0 && (n-i)/i>i){
        sum+=(n-i)/i;
      }
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
typedef long long ll;

int main()
{
  int R0, W0, C, R;
  while(cin>>R0>>W0>>C>>R) {
    if(R0 == 0) return 0;
    // cout << (W0 * C - R0 + R - 1) / R << endl;
    FOR(i,0,10000000) {
      if(R0+i*R>=W0*C) {
        cout << i << endl;
        break;
      }
    }
  }
  return 0;
}

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

int main() {
  int N, M, A, B, cnt=0;
  long long Sum=0;
  cin >> N >> M;
  vector<pair<int, int>> P(N);
  rep(i, N){
    cin >> A >> B;
    P[i]=make_pair(A, B);
  }
  sort(P.begin(), P.end());
  rep(i, N){
    rep(j, P[i].second){
      Sum+=P[i].first;
      cnt++;
      if(cnt==M) break;
    }
    if(cnt==M) break;
  }
  cout << Sum << endl;
}

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


class Dice{
	int dn[6];
	int ori[6];
	int up, front;
	string qu;

public:
	Dice(int d1, int d2, int d3, int d4, int d5, int d6){
		dn[0] = d1;
		dn[1] = d2;
		dn[2] = d3;
		dn[3] = d4;
		dn[4] = d5;
		dn[5] = d6;

		ori[0] = d1;
		ori[1] = d2;
		ori[2] = d3;
		ori[3] = d4;
		ori[4] = d5;
		ori[5] = d6;
	}

	void Result(string m){
		int w;
		qu = m;
		for (int i = 0; i < 6; i++){
			dn[i] = ori[i];
		}

		for (int i = 0; i < qu.size(); i++){
			switch (qu[i]){
			case 'E':
				w = dn[0];
				dn[0] = dn[3];
				dn[3] = dn[5];
				dn[5] = dn[2];
				dn[2] = w;
				break;

			case 'N':
				w = dn[5];
				dn[5] = dn[4];
				dn[4] = dn[0];
				dn[0] = dn[1];
				dn[1] = w;
				break;

			case 'S':
				w = dn[0];
				dn[0] = dn[4];
				dn[4] = dn[5];
				dn[5] = dn[1];
				dn[1] = w;
				break;

			case 'W':
				w = dn[0];
				dn[0] = dn[2];
				dn[2] = dn[5];
				dn[5] = dn[3];
				dn[3] = w;
				break;
			}
		}
	}

	int get0(){
		return dn[0];
	}
	int get1(){
		return dn[1];
	}
	int get2(){
		return dn[2];
	}
	int get3(){
		return dn[3];
	}
	int get4(){
		return dn[4];
	}
	int get5(){
		return dn[5];
	}
};

int main()
{
	int n;
	int count = 0;
	int ndice[100][6];
	string flag = "Yes";
	string quu[23] = { "WSE", "ESW", "WSSE", "SWW", "EN", "WN", "N", "SW", "W", "SSW",
		"NW", "SE", "E", "SSE", "NE", "S", "WS", "ES", "WWS", "WW", "SWS", "SES", "SS" };

	cin >> n;
	for (int i = 0; i < n; i++){          // n個のサイコロの入力
		for (int j = 0; j < 6; j++){
			cin >> ndice[i][j];
		}	
	}

	for (int i = 0; i < n; i++){                // サイコロを比べる
		for (int j = i + 1; j < n; j++){                      // Dice a()にサイコロを登録し、順次比較していく
			Dice a(ndice[j][0], ndice[j][1], ndice[j][2], 
				ndice[j][3], ndice[j][4], ndice[j][5]);

			for (int k = 0; k < 6; k++){            // 転がすこともなく同じサイコロかどうか
				if (ndice[i][k] == ndice[j][k]){
					count = count + 1;
				}
			}
			if (count == 6){     // 6面全てが一致すれば、同じサイコロ
				flag = "No";
			}
			count = 0;

			for (int l = 0; l < 23; l++){     // サイコロが取り得る全ての可能性(面の上下左右)を比較していく
				a.Result(quu[l]);

				ndice[j][0] = a.get0();
				ndice[j][1] = a.get1();
				ndice[j][2] = a.get2();
				ndice[j][3] = a.get3();
				ndice[j][4] = a.get4();
				ndice[j][5] = a.get5();

				for (int k = 0; k < 6; k++){               // 6面全てが一致すれば、同じサイコロ
					if (ndice[i][k] == ndice[j][k]){
						count = count + 1;
					}
				}
				if (count == 6){
					flag = "No";
				}
				count = 0;
			}
		}
	}
	cout << flag << endl;
	
	return 0;
}


Measured memory_bytes: 3228
N,M = map(int,input().split())
pys = []
for i in range(M):
    pys.append(tuple(map(int,input().split())))

year_of_p_dict = {}
for py in pys:
    p,y = py
    if not p in year_of_p_dict:
        year_of_p_dict[p] = []
    year_of_p_dict[p].append(y)

for p,ys in year_of_p_dict.items():
    ys.sort()
    ys_idx_dict = {}
    for i,y in enumerate(ys):
        ys_idx_dict[y] = i+1
    year_of_p_dict[p] = ys_idx_dict

for py in pys:
    p,y = py
    ans = str(p).zfill(6) + str(year_of_p_dict[p][y]).zfill(6)
    print(ans)

Measured memory_bytes: 107732
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAX=100005;
vector<pii> conn[MAX];
deque<pii> dijk;
int n,dist[MAX];
int main(){
    scanf("%d",&n);
    for(ll i=1;i<n;i++){
        conn[i].push_back(make_pair((i+1)%n,1));
        conn[i].push_back(make_pair((10*i)%n,0));
    }
    dijk.push_back(make_pair(1,1));
    while(!dijk.empty()){
        pii tmp=dijk.front();
        dijk.pop_front();
        if(dist[tmp.first]==0){
            dist[tmp.first]=tmp.second;
            for(int i=0;i<conn[tmp.first].size();i++) {
                if(conn[tmp.first][i].second==0) dijk.push_front(make_pair(conn[tmp.first][i].first,tmp.second));
                else dijk.push_back(make_pair(conn[tmp.first][i].first,tmp.second+1));
            }
        }
    }
    printf("%d\n",dist[0]);
}


Measured memory_bytes: 6912
from collections import defaultdict
class UnionFind:
    def __init__(self,nodes):
        self.parents = {node : node for node in nodes}
    def root(self,x):
        if x == self.parents[x]:
            return x
        else:
            rt = self.root(self.parents[x])
            self.parents[x] = rt
            return rt
    def find(self,x,y):
        return self.root(x) == self.root(y)
    def union(self,x,y):
        self.parents[self.root(x)] = self.root(y)
    def get_sets(self):
        res = defaultdict(list)
        for node, parent in self.parents.items():
            res[self.root(node)].append(node)
        # return [*res.values()]
        return list(res.values())

N,M = map(int,input().split(' '))
p = list(map(int,input().split(' ')))

uf = UnionFind(range(1,N+1))

for i in [0]*M:
    x, y = map(int,input().split(' '))
    uf.union(x,y)

ans = 0
for n in range(1,N+1):
    if uf.find(n,p[n-1]):
        ans += 1
print(ans)





Measured memory_bytes: 20952
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

//

fn run() {
    input! {
        h: usize,
        w: usize,
        k: usize,
        s: [chars; h],
    }
    let mut ans = h + w;
    for bit in 0usize..(1 << (h - 1)) {
        let mut hash = vec![0; h];
        for j in 1..h {
            if bit >> (j - 1) & 1 == 1 {
                hash[j] = 1;
            }
        }
        for j in 1..h {
            hash[j] += hash[j - 1];
        }
        let mut cut = bit.count_ones() as usize;
        let mut cnt = vec![0; h];
        for j in 0..w {
            let mut t = cnt.clone();
            for i in 0..h {
                if s[i][j] == '1' {
                    t[hash[i]] += 1;
                }
            }
            if t.iter().all(|p| *p <= k) {
                cnt = t;
            } else {
                cut += 1;
                cnt = vec![0; h];
                for i in 0..h {
                    if s[i][j] == '1' {
                        cnt[hash[i]] += 1;
                    }
                }
                if cnt.iter().any(|c| *c > k) {
                    cut = h + w;
                }
            }
        }
        ans = std::cmp::min(ans, cut);
    }
    println!("{}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 4352
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    A[i] -= i + 1
A.sort()
if N % 2:
    median = A[N // 2]
    print(sum(abs(a - median) for a in A))
else:
    median1 = A[N // 2 - 1]
    median2 = A[N // 2]
    print(min(sum(abs(a - median1) for a in A), sum(abs(a - median2) for a in A)))


Measured memory_bytes: 31128
#include <stdio.h>

#define INF 100000000

#define MAX_N_NODE 100
int nodes_c[MAX_N_NODE][MAX_N_NODE];
int nodes_t[MAX_N_NODE][MAX_N_NODE];
int n_nodes;
int min_cost[MAX_N_NODE];
int is_used[MAX_N_NODE];

void init_nodes(void)
{
    int i,j;
    for(i=0;i<MAX_N_NODE;i++){
        for(j=0;j<MAX_N_NODE;j++){
            nodes_c[i][j]=-1;
            nodes_t[i][j]=-1;
        }
    }
}

//warning: a,b starts from one
void set_node(int a,int b,int c,int t)
{
    a--; b--;
    nodes_c[a][b]=nodes_c[b][a]=c;
    nodes_t[a][b]=nodes_t[b][a]=t;
}

//warning: p,q starts from one
int dijkstra_c(int p,int q)
{
    int start=p-1,goal=q-1;

    int i;
    for(i=0;i<n_nodes;i++){
        min_cost[i]=INF;
        is_used[i]=0;
    }
    min_cost[goal]=0;

    while(1){
        // the unused node with minimum cost become used
        int min_val=INF, min_node;
        int n_unused=0;
        for(i=0;i<n_nodes;i++){
            if(is_used[i]){ continue; }
            if(min_val>=min_cost[i]){
                min_val=min_cost[i];
                min_node=i;
            }
            n_unused++;
        }
        //no unused node, then exit
        if(n_unused==0){ return min_cost[start]; }
        //become used
        is_used[min_node]=1;
        //updated cost of node connected new used node
        for(i=0;i<n_nodes;i++){
            if(nodes_c[min_node][i]<0){ continue; }
            if(min_cost[i]>min_cost[min_node]+nodes_c[min_node][i]){
                min_cost[i]=min_cost[min_node]+nodes_c[min_node][i];
            }
        }
    }
}
int dijkstra_t(int p,int q)
{
    int start=p-1,goal=q-1;

    int i;
    for(i=0;i<n_nodes;i++){
        min_cost[i]=INF;
        is_used[i]=0;
    }
    min_cost[goal]=0;

    while(1){
        int min_val=INF, min_node, n_unused=0;
        for(i=0;i<n_nodes;i++){
            if(is_used[i]){ continue; }
            if(min_val>=min_cost[i]){
                min_val=min_cost[i]; 
                min_node=i;
            }
            n_unused++;
        }
        if(n_unused==0){ return min_cost[start]; }
        is_used[min_node]=1;

        for(i=0;i<n_nodes;i++){
            if(nodes_t[min_node][i]<0){ continue; }
            if(min_cost[i]>min_cost[min_node]+nodes_t[min_node][i]){
                min_cost[i]=min_cost[min_node]+nodes_t[min_node][i];
            }
        }
    }
}

//#define DEBUG
int main(void)
{
    FILE *fpin;
#ifdef DEBUG
    fpin=fopen("input.txt","r");
#else
    fpin=stdin;
#endif

    while(1){
        int n,m; //num of lines and station
        fscanf(fpin,"%d %d\n",&n,&m);
        if(n==0 && m==0){ break; } //exit case

        init_nodes();
        n_nodes=m;
        int i;
        for(i=0;i<n;i++){
            int a,b,c,t; //start, goal, cost, time
            fscanf(fpin,"%d %d %d %d\n",&a,&b,&c,&t);
            set_node(a,b,c,t); 
        }

        int k; //num of access
        fscanf(fpin,"%d\n",&k);
        for(i=0;i<k;i++){
            int p,q,r;
            fscanf(fpin,"%d %d %d\n",&p,&q,&r);
            printf("%d\n",
                    (r==0)?
                    dijkstra_c(p,q):
                    dijkstra_t(p,q));
        }

    }
    return 0;
}

Measured memory_bytes: 488
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

const long MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;

int main(){
    int N, K;
    cin >> N >> K;

    int mx = min(K, N);

    int V[N];
    for(int i=0; i<N; i++) cin >> V[i];

    ll ans = 0;
    //  取る個数
    for(int i=1; i<=mx; i++){
        // 左からl個、右からr個
        for(int l=0; l<=i; l++){
            int r = i-l;

            vector<int> s;
            for(int i=0; i<l; i++) s.push_back(V[i]);
            for(int i=0; i<r; i++) s.push_back(V[N-1-i]);

            sort(s.begin(), s.end());

            int ret = K - i;
            int cnt = 0;
            ll ta = 0;
            // cout << "---------" << endl;
            // cout << i << " " << l << " " << r << " " << ret << endl;
            for(int i=0; i<s.size(); i++){
                // cout << s[i] << endl;
                if(cnt < ret && s[i] < 0){
                    cnt++;
                    continue;
                }
                ta = ta + s[i];
            }
            ans = max(ta, ans);
        }
    }
    
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n;
int minx, maxx;
int a[122];
int res[122];
bool flg[122];

int main() {
	while(~scanf("%d", &n)) {
		memset(flg, 0, sizeof(flg));
		memset(a, 0, sizeof(a));
		memset(res, 0, sizeof(res));
		int cnt = 0;
		for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
		for(int i = 1; i <= n; i++) {
			if(a[i] >= 1 && a[i] <= 399) res[i] = 1;
			else if(a[i] >= 400 && a[i] <= 799) res[i] = 2;
			else if(a[i] >= 800 && a[i] <= 1199) res[i] = 3;
			else if(a[i] >= 1200 && a[i] <= 1599) res[i] = 4;
			else if(a[i] >= 1600 && a[i] <= 1999) res[i] = 5;
			else if(a[i] >= 2000 && a[i] <= 2399) res[i] = 6;
			else if(a[i] >= 2400 && a[i] <= 2799) res[i] = 7;
			else if(a[i] >= 2800 && a[i] <= 3199) res[i] = 8;
			else res[i]= 9;
		}
		for(int i = 1; i <= n; i++) {
			if(res[i] != 9 && flg[res[i]] == 0) {
				flg[res[i]] = 1;
				cnt++;
			}
		}
		int c = 0;
		for(int i = 1; i <= n; i++) {
			if(res[i] == 9) c++;
		}
		if(c == n) minx = 1;
		else minx = cnt;
		int t = 0;
		for(int i = 1; i <= n; i++){
			if(res[i] == 9) t++;
		}
		maxx = cnt + t;
		printf("%d %d\n", minx, maxx);
	}
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define mod 1000000007
#define fr first
#define se second
#define ll long long
#define PI 3.1415926535 
#define pb push_back
#define mpr make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define senky_bansal ios_base::sync_with_stdio(false);
#define IIIT_ALLAHABAD    cin.tie(NULL);cout.tie(NULL);
using namespace std;
ll power(ll a,ll b)
{
    ll res =1;
    while(b)
    {
        if(b&1) res = (res%mod*a%mod)%mod;
        b/=2;
        a = (a%mod*a%mod)%mod;
    }
    return res;
}
ll sieve[1000005];
void pre()
{
    sieve[0]=1;
    sieve[1]=1;
    for(int i=2;i<1000005;i++)
    {
        if(sieve[i]==0)
        for(int j=2*i;j<1000005;j+=i)
        {
            sieve[j]=1;
        }
    }
}
ll ch(ll p)
{
    ll sum=0;
    while(p)
    {
        sum++;
        p/=10;
    }
    if(sum%2!=0)
    return 1;
    else
    return 0;
}
signed main()
{
    
    senky_bansal
    IIIT_ALLAHABAD
      
    ll n;
    cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        if(ch(i))
        ans++;
    }
    cout<<ans<<endl;
    
    
    
    
    
    
}








Measured memory_bytes: 256
N = int(input())
T = list(map(int, input().split()))
M = int(input())
PX = [list(map(int, input().split())) for _ in range(M)]

point = []
for i in range(M):
  a = sum(T) - T[PX[i][0] - 1] + PX[i][1]
  point.append(a)

for j in point:
  print(j)

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

// 問題名："The Most Powerful Spell"
// https://onlinejudge.u-aizu.ac.jp/problems/1169
// 所要時間… 考察：30分程度 実装：20分程度

/*
***方針***
Bellman-Ford法を使いたくなるが、スタート（空文字列）から後ろに文字列を追加していくのはうまく行かない（「a<bならばa+c<b+c」が成り立たないため e.g. a="a", b="aa", c="b"）。なので、逆にゴールから先頭に文字を付け加えていく（「a<bならばc+a<c+b」は成り立つ）。
各点で、「そこからゴールまでの最強呪文（暫定）」を保持。はじめはinf="zzzzz.....zzzz（十分長い）"にしておく。
負閉路のようなもの、すなわち一周たどると辞書順が短くなる閉路が発生しない場合は、通常のBellman-Ford法のようにn回のループで最強呪文が確定する。ただし、通常のように負閉路検出時は"NO"というわけにはいかない（例えば、"bc"<"bbc"<"bbbc"<"bbbbc"<...という負のループが発生していても、これが"a"より小さくなることはない。
ループに入った文字列は明らかに答えにならないから、答えの文字列は最大でも6*n文字であるので、十分大きい回数（ループに入ってしまった文字列は6*n文字を超えるまで）Bellman-Ford法のループを行って、スタート地点における文字列がinf、または6*n文字より長ければ"NO"。それ未満ならその文字列を出力する。

***学んだこと***
dfsするのは簡単だが、その結果から復元するのは案外難しい（というよりむしろ、「ドアの数」と「接続先との相対位置」と順番という微妙な情報だけで復元できるのが面白い）。
*/

int main() {
  // 変数、infを定義
  int n, a, s, g;
  const string inf = string(100000, 'z');

  // テストケースが終わるまでループ
  while (cin >> n >> a >> s >> g, n != 0) {
    vector<string> dist(n, inf);  // 各点からゴールまでの暫定最強呪文
    dist[g] = "";  // 後ろから構築
    vector<tuple<int, int, string>> edge(a);  // 辺の情報を保持するvector（始点、終点、文字列）

    string lab;
    for (int i = 0; i < a; i++) {
      cin >> get<0>(edge[i]) >> get<1>(edge[i]) >> get<2>(edge[i]);
    }
    for (int i = 0; i < 6 * n + 10; i++) {
      for (tuple<int, int, string> e : edge) {
        if (dist[get<1>(e)] == inf) continue;
        dist[get<0>(e)] = min(dist[get<0>(e)], get<2>(e) + dist[get<1>(e)]);
      }
    }

    string ret = dist[s];

    if (dist[s].length() > 6 * n)
      cout << "NO" << endl;
    else
      cout << dist[s] << endl;
  }
}


Measured memory_bytes: 3512
import itertools
import math

N = int(input())
crd_list = []
for _ in range(N):
    crd_list.append([int(xy) for xy in input().split()])

cost_list = []
for way in itertools.permutations([n for n in range(N)]):
    cost = 0
    for index in range(1, N):
        cost += ((crd_list[way[index]][0]-crd_list[way[index-1]][0])**2 + (crd_list[way[index]][1]-crd_list[way[index-1]][1])**2)**0.5
    cost_list.append(cost)

print(sum(cost_list)/math.factorial(N))

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

using namespace std;

int ans, n, a[(int)1e5], ls[(int)1e5], rs[(int)1e5];

int main(){
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> a[i];
	
	ls[0] = a[0], rs[n-1] = a[n-1];
	for(int i = 1; i < n; ++i){
		ls[i] = __gcd(ls[i-1], a[i]);
		rs[n-i-1] = __gcd(a[n-i-1], rs[n-i]);
	}
	for(int i = 0; i < n; ++i){
		if(i == 0){
			ans = max(ans, rs[i+1]);
		}else if(i == n - 1){
			ans = max(ans, ls[i-1]);
		}else{
			ans = max(ans, __gcd(ls[i-1], rs[i+1]));
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1408
#include <stdio.h>
int main() {int A=0,B=0,AB=0,O=0,i;char Tex[5];while (scanf("%d,%s",&i,&Tex)!=EOF) {if (Tex[0]=='A' && Tex[1]=='B') AB++; else if (Tex[0]=='O') O++; else if (Tex[0]=='A') A++; else B++;} printf("%d\n%d\n%d\n%d\n",A,B,AB,O);return 0;}

Measured memory_bytes: 0
def main():
    l, r, d = map(int, input().split())
    n = 100//d
    count = 0
    for i in range(n):
        i_ = i + 1
        a = d * i_
        if a>=l and a<=r:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String ans = "";
        for(int i=0; i<3; i++) {
            String s = br.readLine().trim();
            ans += s.charAt(i);
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 22996
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

"""
・「必要」とは～～が存在
・x を含まない、[K-x,K) 内の総和が存在
・集合を指定すると、ある値段より上側
・全体としても単調性がある
"""

N,K,*A = map(int,read().split())

A = [x if x <= K else K + 1 for x in A]
A.sort()

mask = (1 << K) - 1

def test(x):
    # x番目は必要
    if A[x] > K:
        return True
    dp = 1
    for a in itertools.chain(A[:x], A[x+1:]):
        dp |= (dp << a)
        dp &= mask
    dp >>= (K - A[x])
    return (dp > 0)

left = -1 # 必要
right = N # 不要
while left + 1 < right:
    x = (left + right) // 2
    if test(x):
        right = x
    else:
        left = x

answer = left + 1
print(answer)

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

int main() {
	int A,B,C,X;
  	cin >> A >> B >> C >> X;
  
  	int num = 0;
  
  	for(int i = 0; i < A + 1; i++) {
     for(int j = 0; j < B + 1; j++) {
      for(int k = 0; k < C + 1; k++) {
    	int sum = 500 * i + 100 * j + 50 * k;
        if (sum == X) {
        num++;
        }
        
      }
     }
    }
  
  cout << num << endl;
}


Measured memory_bytes: 256
/*
g++ --std=c++17 D.cpp
*/

#include <iostream>
#include <iomanip> //! for setprecision(20)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <limits.h>

using namespace std;

typedef long long ll;

#define rep(i,n) for (int i = 0; i < int(n); ++i)
template<class T> inline bool chmax(T& a, T b) { bool ret = (a < b); if (ret) { a = b; } return ret; }
template<class T> inline bool chmin(T& a, T b) { bool ret = (b < a); if (ret) { a = b; } return ret; }
#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define dumpMap(m) { for (auto it: m) cout << it.first << "=>" << it.second << ' '; }

const int INF = 1000000000;

const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct BIT {
  int n;
  vector<mint> d;
  BIT(int n=0):n(n),d(n+1) {}
  void add(int i, mint x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  mint sum(int i) {
    mint x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  mint sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};

struct BIT2 {
  BIT2(int n) : bit(n+1) {}
  void add(int l, int r, mint x=1) {
    bit.add(l, x);
    bit.add(r+1, -x);
  }
  mint val(int i) {
    return bit.sum(i);
  }
private:
  BIT bit;
};

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

  int n, k;
  cin >> n >> k;
  int l[10];
  int r[10];
  rep(i, k) cin >> l[i] >> r[i];

  BIT2 bit (410000);
  bit.add(1, 1);
  for (int base = 1; base < n; ++base) {
    rep(i, k) {
      int x = base+l[i];
      int y = base+r[i];
      if (x <= n) {
        bit.add(x, y, bit.val(base));
      }
    }
  }
  cout << bit.val(n).x << endl;

  return 0;
}


Measured memory_bytes: 6356