akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define pb push_back
#define pob pop_back
#define mp make_pair
#define ff first
#define ss second
#define pi 3.14159265
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <ll, ll> pll;
const ll M=1e9+7;
ll inf=1e18;
int d[1000001];
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
        d[a[i]]++;
    }
    int ans=0;
    for(int i=0;i<n;i++){
        int x=a[i];
        bool g=true;
        d[x]--;
        for(int j=1;j*j<=x;j++){
            if(x%j==0){
                if(d[x/j]>0 || d[j]>0)
                    g=false;
            }
        }
        d[x]++;
        if(g)
            ans++;
    }
    cout<<ans;
}


Measured memory_bytes: 8280
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <numeric>
#include <string>
#include <vector>
#include <utility>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int>p(n);
    for(auto & x : p){
        cin >> x;
    }
    sort(p.begin(),p.end(),greater<int>());
    auto ans = p[0]/2 + accumulate(p.begin() + 1,p.end(),0);
    cout << ans;
    return 0;
}



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

int main() {
    int n;
    cin >> n;
    vector<int> b(n-1);
    rep(i,n-1){
        int t;
        cin >> t;
        b[i]=t;
    }
    
    ll ans=0;
    rep(i,n){
        if (i==0){
            ans = ans + b[i];
            continue;
        }
        if (i==n-1){
            ans = ans + b[n-2];
            continue;
        }
        ans = ans + min(b[i-1],b[i]);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define _repargs(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _repargs(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    int N;
    cin >> N;
    vector<int> A(N + 1);
    rep(i, 1, 200) rep(j, 1, 200) rep(k, 1, 200) {
        if(i * i + j * j + k * k + i * j + i * k + j * k <= N) {
            A[i * i + j * j + k * k + i * j + i * k + j * k]++;
        }
    }
    rep(i, 1, N + 1) output(A[i]);
    
    return 0;
}


Measured memory_bytes: 3648
# from typing import NamedTuple

# class Burger(NamedTuple):
#     total: int
#     patty: int

from collections import namedtuple

def solve(n, x, burgers, total_eaten, patty_eaten):
    if n == 0:
        total_eaten += 1
        patty_eaten += 1
        return total_eaten, patty_eaten

    # try to eat the entire current level
    tmp_total = burgers[n].total
    tmp_patty = burgers[n].patty
    if total_eaten + tmp_total < x:
        return total_eaten + tmp_total, patty_eaten + tmp_patty

    # eat the lower bun
    total_eaten += 1
    if total_eaten == x:
        return total_eaten, patty_eaten

    # eat the lower n - 1 th burger
    total_eaten, patty_eaten = solve(n - 1, x, burgers, total_eaten, patty_eaten)
    if total_eaten == x:
        return total_eaten, patty_eaten

    # eat the middle patty
    total_eaten += 1
    patty_eaten += 1
    if total_eaten == x:
        return total_eaten, patty_eaten

    # eat the upper n - 1 th burger
    total_eaten, patty_eaten = solve(n - 1, x, burgers, total_eaten, patty_eaten)
    if total_eaten == x:
        return total_eaten, patty_eaten

    # eat the upper bun
    # the program should not reach the current line because this mean n th burger is eaten (= eat the entire current level)
    total_eaten += 1
    return total_eaten, patty_eaten

def main():
    N, X = map(int, input().split())
    Burger = namedtuple('Burger', ['total', 'patty'])
    burgers = [Burger(total=1, patty=1)]
    for i in range(N):
        total = burgers[i].total
        patty = burgers[i].patty
        burger = Burger(total=3 + total*2, patty=1 + 2*patty)
        burgers.append(burger)
    # print(burgers)
    total_eaten, patty_eaten = 0, 0
    total_eaten, patty_eaten = solve(N, X, burgers, total_eaten, patty_eaten)
    print(patty_eaten)

if __name__ == '__main__':
    main()


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

int main() {
  int k, s;
  cin >> k >> s;
  int answer = 0;
  
  for(int x = 0; x <= k; ++x) {
    for(int y = 0; y <= k; ++y) {
      if(s - x - y <= k && s - x - y >= 0) ++answer; 
    }
  }
  
  cout << answer << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>

// 11*100000
#define BUF_SIZE 1200000

int get_int(void) {
  int num;
#ifdef BUF_SIZE
  char line[BUF_SIZE];
  if(!fgets(line, BUF_SIZE, stdin)) return 0;
  sscanf(line, "%d", &num);
#else
#error
#endif
  return num;
}

// <arr[0]> <arr[1]> .. <arr[size-1]>
int fget_array(int *arr, int size) {
#ifdef BUF_SIZE
    char line[BUF_SIZE];
    char *tmpbuf = line;
    int i;
    if(!fgets(line, BUF_SIZE, stdin)) return -1;
    for(i = 0; i < size; i++) {
        char *tmp = strtok(tmpbuf, " ");
        arr[i] = strtol(tmp, NULL, 10);
        tmpbuf = NULL;
    }
#else
#error
#endif
    return 0;
}

#define PARTS_MAX 100000
#define PARTS_KINDS 3

int asc(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int get_combi(int *arr, int size, int query, int start) {
    int low = start-1;
    int high = size;

    while(low+1 < high) {
        int mid = (low + high)/2;
        // lower bound
        if(arr[mid] > query) {
            high = mid;
        } else {
            low = mid;
        }
    }
    return high;
}

int upper_bound(int *arr, int size, int key) {
    int low = -1;
    int high = size;

    while(low+1 < high) {
        int mid = (low+high)/2;
        if(arr[mid] < key) {
            low = mid;
        } else {
            high = mid;
        }
    }
    return low;
}

int lower_bound(int *arr, int size, int key) {
    int low = -1;
    int high = size;

    while(low+1 < high) {
        int mid = (low+high)/2;
        if(arr[mid] > key) {
            high = mid;
        } else {
            low = mid;
        }
    }
    return high;
}

int main(void) {
    int parts = get_int();
    int length[PARTS_KINDS][PARTS_MAX];
    int i;
    for(i = 0; i < PARTS_KINDS; i++) {
        fget_array(length[i], parts);
        qsort(length[i], parts, sizeof(int), asc);
    }

    uint64_t ans = 0;
    for(i = 0; i < parts; i++) {
        int pivot = length[1][i];
        int ans1 = upper_bound(length[0], parts, pivot)+1;
        int ans2 = parts - lower_bound(length[2], parts, pivot);
        ans += (uint64_t)ans1*ans2;
    }
    printf("%llu\n", ans);

    return 0;
}

Measured memory_bytes: 2676
#include <bits/stdc++.h>
using namespace std;
struct _ { ios_base::Init i; _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); } } _;

int main() {

	long long n;
	cin >> n;
	string code = "abcdefghijklmnopqrstuvwxyz";
	assert(code.length() == 26);
	string ans;

	while (n > 0) {
		n--;
		ans.push_back(code[n % 26]);
		n /= 26;
	}
	reverse(ans.begin(), ans.end());
	cout << ans;

	return 0;
}

Measured memory_bytes: 3664
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
 
#define ll long long 
#define fr(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define inf (1<<31)
 
using namespace std;
 
int main() {
	ios::sync_with_stdio(0);
	string s;
	cin>>s;
	s[5]=' ';
	s[13]=' ';
	cout<<s;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int, int> P;
typedef unsigned int ui;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
ll gcd(ll x,ll y) {
	if (x < y)swap(x, y);
	while (y > 0) {
		ll r = x % y; x = y; y = r;
	}
	return x;
}
int main() {
	int t; cin >> t;
	ll a, b, c, d;
	rep(i, t) {
		cin >> a >>b >> c >> d;
		if (b > d||a<b) {
			cout << "No" << endl;
			continue;
		}
		ll r = gcd(b, d);
		ll x = (b - a%b) % r;
		if (x == 0) {
			x += r;
		}
		x = b - x;
		if (c < x) {
			cout << "No" << endl;
		}
		else {
			cout << "Yes" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL << 60;

int main(){
  int n, k; cin >> n >> k;
  vector<int> l(n);
  rep(i, n) cin >> l[i];

  sort(rall(l));

  int sum = 0;
  rep(i, k){
    sum += l[i];
  }

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    string s, t;
    cin >> s >> t;
    ll ans = 0;
    rep(i, 3) {
        if(s[i] == t[i]) {
            ans++;
        }
    }
    out(ans);
    
    re0;
}

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

int main()
{
	int n, k;
	string s;
	cin >> n >> k >> s;

	vector<pair<int, int>> v;
	for (int i = 1, j = (s[0] == '0'); i < n; i++)
	{
		if (s[i] == '0')
		{
			j++;
		}
		else if (0 < j)
		{
			v.push_back({i - j, i});
			j = 0;
		}
		if (i == n - 1 && s[i] == '0')
		{
			v.push_back({n - j, n});
		}
	}

	if (v.empty())
	{
		cout << n << endl;
		return 0;
	}

	int ans = 0, l = 0;
	for (int i = 0; i < int(v.size()); i++)
	{
		if (int(v.size()) <= i + k)
		{
			ans = max(ans, n - l);
		}
		else
		{
			ans = max(ans, v[i + k].first - l);
		}
		l = v[i].second;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1020
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=200010;
char s[maxn];
int n;
int dp[maxn][2];
int main() {
	cin>>n;
	int ans=0;
	int flag=0;
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='.'){
			dp[i][0]=dp[i-1][0];
			dp[i][1]=min(dp[i-1][0],dp[i-1][1])+1;
		}else{
			dp[i][1]=min(dp[i-1][0],dp[i-1][1]);
			dp[i][0]=dp[i-1][0]+1;
		}
	}
	
	printf("%d\n",min(dp[n][0],dp[n][1]));
}


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

int main(){
    int a = 0;
    string b;
    cin >> b;

    for(int i=0; i< b.size() ; i++){
        if(b[i] == '+'){
            a ++;
        }else {
            a --;
        }
    }

    cout << a << endl;

    return 0;
}

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

using namespace std;

int main(){
	int X;
	cin >> X;

	int max = 0;
	for(int b=1;b <=X;b++){
		for(int p=2;p<=10;p++){
			int tmp = pow(b,p);
			if(tmp <= X){
				if(max < tmp){
					max = tmp;
				}
			}
		}
	}

	cout << max << endl;

	return 0;
}


Measured memory_bytes: 640
#include<iostream>
using namespace std;
#define MAX 100000
typedef long long llong;

int n, k;
llong T[MAX];

int check(llong p) {
	int i=0;
	for(int j = 0; j < k; j++ ) {
		llong sum = 0;
		while( sum + T[i] <= p) {
			sum += T[i];
			i++;
			if(i == n ) return n;
		}
	}
	return i;
}

int solve() {
	llong left = 0;
	llong right = 100000 * 10000 + 1;
	llong mid;
	while(left < right) {
		mid = (left + right) / 2;
		int v = check(mid);
		if(v == n) right = mid ;
		else left = mid + 1;
	}
	return right;
}

main() {
	cin >> n >> k;
	for( int i = 0; i < n; i++) cin >> T[i];
	llong ans = solve();
	cout << ans << endl;
}

Measured memory_bytes: 3872
#include<stdio.h>
int d[1000000];
int main(){
  int n,i,j,ans;
  while(scanf("%d",&n)!=EOF){
    for(i=2;i*i<=n;i++){
      if(d[i]==0){
	for(j=i+i;j<=n;j+=i){
	  d[j]=1;
	}
      }
    }
    ans=0;
    for(i=2;i<=n;i++){
      if(d[i]==0){
	ans++;
      }
    }
    printf("%d\n",ans);
  }
  return (0);
}

Measured memory_bytes: 4500
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n, k = li()
MOD = 10**9 + 7

dp = [[[0]*(n*n+1) for _ in range(n+1)] for _ in range(n+1)]

dp[0][0][0] = 1

for x in range(1, n+1):
    for y in range(n+1):
        for z in range(n*n+1):
            dp[x][y][z] = ((2*y + 1) * dp[x-1][y][z-2*y] if z-2*y >= 0 else 0)\
                            + ((y+1)**2 * dp[x-1][y+1][z-2*y] if (z-2*y >= 0 and y+1 <= n) else 0)\
                            + (dp[x-1][y-1][z-2*y] if (z-2*y >= 0 and y-1 >= 0) else 0)
            dp[x][y][z] %= MOD

print(dp[n][0][k])

Measured memory_bytes: 95580
cards = [[False for i in range(13)] for j in range(4)]
# 0: S, 1: H, 2: C, 3:D
pattern = ["S", "H", "C", "D"]
n = int(input())
for i in range(n):
    ch,rank = input().split()
    cards[pattern.index(ch)][int(rank)-1] = True
for i in range(4):
    for j in range(13):
                if cards[i][j] == False:
                    print(pattern[i], j+1)


Measured memory_bytes: 5600
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)

using namespace std;

double l;

int main(void)
{
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	
	cin >> l;
	double ans = l/3;
	ans = ans*ans*ans;
	printf("%.11f\n", ans);
	
	return 0;
}

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

for i in range(1000):
    stri = str(i)
    if len(stri) != N:
        continue
    for s, c in sc:
        if stri[s-1] != str(c):
            break
    else:
        print(i)
        exit()
print(-1)

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


int main() {

	int a[3][3], n, b[10];
	bool ab[3][3], ans = false;
	rep(i, 3) rep(j, 3) ab[i][j] = false;

	rep(i, 3) rep(j, 3) cin >> a[i][j];
	cin >> n;
	rep(i, n) cin >> b[i];

	rep(i, 3) rep(j, 3)rep(k, n) if (b[k] == a[i][j])ab[i][j] = true;




	rep(i, 3)if (ab[i][0] & ab[i][1] & ab[i][2]) ans = true;
	rep(j, 3)if (ab[0][j] & ab[1][j] & ab[2][j]) ans = true;

	if (ab[0][0] & ab[1][1] & ab[2][2]) ans = true;
	if (ab[0][2] & ab[1][1] & ab[2][0]) ans = true;


	if (ans == true)cout << "Yes" << endl;
	else cout << "No" << endl;
}

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

int main() {
  string N;
  cin >> N;
  if (N.at(0) == '7') cout << "Yes" << endl;
  else if (N.at(1) == '7') cout << "Yes" << endl;
  else if (N.at(2) == '7') cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3584
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::io::Read;
use std::io::{stdout, BufWriter, Write};
 
fn main() {
    let mut buf = String::new();
    
    let out = stdout();
    let mut out = BufWriter::new(out.lock());
 
    // 標準入力から全部bufに読み込む
    std::io::stdin().read_to_string(&mut buf).unwrap();
 
    // 読み込んだStringを空白で分解する
    let mut iter = buf.split_whitespace();
 
    
    let n: usize = iter.next().unwrap().parse().unwrap();
    
    let odd = n / 2;
    let even = (n + 1) / 2;
    
    let ans = (even as f64) / (n as f64);
    //println!("{:?}",colors);
    println!("{}", ans);
}

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

int main() {
  long long N;
  cin>>N;
  map<string,int>mp;
  int max=0;
  for(long long i=0;i<N;i++){
    string S;
    cin>>S;
    mp[S]++;
    if(max<mp[S]){
      max=mp[S];
    }
  }
  vector<string>ans;
  for(auto X:mp){
    if(X.second==max){
      ans.push_back(X.first);
    }
  }
  sort(ans.begin(),ans.end());
  for(int i=0;i<ans.size();i++){
    cout<<ans.at(i)<<endl;
  }
}

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

using namespace std;

const int N = 1234567;

char s[N];
int n;
int have[26];

int main() {
  scanf("%s", s);
  n = strlen(s);
  char last = 0;
  int cnt = 0;
  for (int i = 0; s[i]; i++) {
    have[s[i] - 'a']++;
  }
  long long ans = (long long) n * (n - 1) / 2 + 1;
  for (int i = 0; i < 26; i++) {
    ans -= (long long) have[i] * (have[i] - 1) / 2;
  }
  printf("%lld\n", ans);
  return 0;
}

Measured memory_bytes: 384
mod = 10**9 + 7
K = int(input())
S = input()
n = len(S)
tmp = pow(26, K, mod)
waru = pow(26, -1, mod)
ans = tmp
for i in range(1, K+1):
    tmp = (tmp * 25 * waru)%mod
    tmp = (tmp * (i + n -1) * pow(i, -1, mod))%mod
    ans = (ans+tmp)%mod
print(ans%mod)

Measured memory_bytes: 10892
misMatch :: String -> String -> Int
misMatch [] _ = 0
misMatch _ [] = 0
misMatch (s:ss) (t:ts) = if s == t then misMatch ss ts else 1 + misMatch ss ts

solve :: String -> String -> [Int]
solve ss ts
    | length ss <= length ts = [misMatch (take (length ts) ss) ts]
    | otherwise = misMatch (take (length ts) ss) ts : solve (tail ss) ts

main = do
    s <- getLine
    t <- getLine
    print $ minimum $ solve s t


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

int main() {
  int N, M;
  cin >> N >> M;
  
  vector<int> deg(N);
  
  for(int i=0; i<M; i++){
    int a,b; // a,b in [1,N] not [0,N)
  	cin >> a >> b;
    deg.at(a-1)++;
    deg.at(b-1)++;
  }
  
  for(int i=0; i<N; i++){
  	cout << deg.at(i) << endl;
  }
}

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

#define irep(i,n) for(int i = 0; i < (int)(n); i++)
#define irep2(i,a,n) for(int i = (int)(a); i <= (int)(n); i++)
#define irrep(i,n) for(int i = (int)(n-1); i > -1; i--)
#define irrep2(i,n,a) for(int i = (int)(n); i >= (int)(a); i--)

#define fi first
#define se second

using namespace std;

using ll = long long;
using v_int = vector<int>;
using v2_int = vector<v_int>;
using v_ll = vector<ll>;
using v2_ll = vector<v_ll>;
using v_string = vector<string>;
using v_bool = vector<bool>;
using v2_bool = vector<v_bool>;
using pii = pair<int, int>;
using mii = map<int, int>;

const double PI = 3.1415926535897932;
const int INF = (int)2e9;
const ll LINF = (ll)2e18;
const ll MOD = 1000000007;
const int dc[8] = {1, -1, 0,  0, 1, -1,  1, -1};
const int dr[8] = {0,  0, 1, -1, 1,  1, -1, -1};

template<typename T, typename U> inline
ostream& operator<<(ostream &o, pair<T,U> &p) {
    return o << "{" << p.first << "," << p.second << "}";
}
template<typename T> inline
istream& operator>>(istream &is, vector<T> &vec) {
    for(auto &v : vec) { is >> v; }
    return is;
}
template<typename T> inline
ostream& operator<<(ostream &os, vector<T> &vec) {
    for(auto &v : vec) { os << v << ",";}
    return os;
}
template<typename T> inline
ostream& operator<<(ostream &os, vector<vector<T> > &mat) {
    for(auto &row : mat) { os << row << endl; }
    return os;
}
template<typename T> inline
void chmin(T &a, T b) { a = min(a, b); }
template<typename T> inline
void chmax(T &a, T b) { a = max(a, b); }

int main(void)
{
    double n, k;
    cin >> n >> k;
    
    double ans;

    if(k <= n) {
        ans = (n-k+1)/n;
    } else {
        ans = 0.0;
    }
    
    for(int i = 1; i <= min(n, k-1); i++) {
        int j = i;
        double p = 1;
        while(j < k) {
            j *= 2;
            p /= 2.0;
        }
        ans += p/n;
    }
    printf("%.13f\n", ans);
    return 0;
} /*atcoder*/


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}

int main(void) {
  int64 n, m;
  cin >> n >> m;
  vector<int64> v(n+m);
  map<int64, int64> mp;

  REP(i, n) v[i] = n-i;
  REP(i, m) cin >> v[i+n];
  REP(i, n+m) {
    if (mp[v[n+m-i-1]] == 0) {
      cout << v[n+m-i-1] << endl;
      mp[v[n+m-i-1]] = 1;
    }
  }
}


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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

string S[2];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    REP(i, 2) {
        cin >> S[i];
    }

    ll index = 1;
    ll ans = 3;
    if (S[0][0] != S[1][0]) {
        index++;
        ans *= 2;
    }
    while (index < N) {
        if (S[0][index] == S[1][index]) {
            if (S[0][index - 1] == S[1][index - 1])
                ans *= 2;
        }
        else {
            if (S[0][index - 1] == S[1][index - 1])
                ans *= 2;
            else
                ans *= 3;
            index++;
        }
        ans %= MOD;
        index++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
#define MOD 1000000007LL
#define endl "\n"
#define fst first
#define snd second
const ll UNDEF = -1;
const int INF=1e9;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
const int mn=204;
int dp[mn][mn][mn];

int f(int a, int b, int c) {
	if (a==b&&b==c) return 0;
	if (a<mn&&b<mn&&c<mn) {
		int dpval=dp[a][b][c];
		if (dpval!=-1) return dpval;
		int ans=min({
			f(a+2,b,c),
			f(a,b+2,c),
			f(a,b,c+2),
			f(a+1,b+1,c),
			f(a+1,b,c+1),
			f(a,b+1,c+1)
			})+1;
		return dp[a][b][c]=ans;
	}
	else return INF;
}

void solve(long long A, long long B, long long C){
	memset(dp,-1,sizeof dp);
	int ans=f(A,B,C);
	printf("%d\n",ans);
}

int main(){	
	ios_base::sync_with_stdio(false); cin.tie(0);
	long long A;
	long long C;
	long long B;
	scanf("%lld",&A);
	scanf("%lld",&B);
	scanf("%lld",&C);
	solve(A, B, C);
	return 0;
}



Measured memory_bytes: 33536
#include <iostream>
 
using namespace std;
long long g(long long e, long long n, long long m)
{
    if (n == 0)
    {
        return 1;
    }
    long long x = g(e, n / 2, m);
  	x*=x;
    x%=m;
    if (n % 2 == 1)
    {
        x *= e;
    }
 
    return x % m;
}
long long comb(long long a, long long n)
{
    long long h = 1;
    long long w = 1;
    long long f = a;
    for (long long i = 0; i < f; i++)
    {
        h = (h % 1000000007) * (n % 1000000007);
        w = (w % 1000000007) * (a % 1000000007);
        n--;
        a--;
    }   
    h %= 1000000007;
    w %= 1000000007;
    long long W = g(w, 1000000005, 1000000007);
 
    return (h * W) % 1000000007;
}
 
int main()
{
    long long n;
    long long a;
    long long b;
    cin >> n >> a >> b;
    long long s = 1;
    s = g(2, n, 1000000007);
    s -= 1;
    long long t = comb(a, n);
    long long o = comb(b, n);
    if (s - t- o < -1000000007)
    {
        cout << s - t - o + 1000000007*2;
    }
    else if (s - t- o <0){
    	cout << s - t - o + 1000000007;
    }
    else
    {
        cout << s - t - o;
    }
}

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

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();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define EXIST(m,v) (m).find((v)) != (m).end()
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

void Main(){
    ll N; cin >> N;
    ll ans = N*(N+1)*(N+2)/6;
    REP(_,N-1){
        ll u,v; cin >> u >> v;
        if(u>v) swap(u,v);
        ans -= u*(N+1-v);
    }
    cout << ans << en;
    return;
}

int main(void){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15);
    int t=1; //cin>>t;
    REP(_,t) Main();
    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <limits>
#include <algorithm>
#include <array>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <unordered_map>
#include <random>
#include <cmath>
#include <complex>
// #include "utiltime.hpp"

using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef complex<double> cdouble;

const int INFL = (int)1e9;
const ll INFLL = (ll)1e18;
const double INFD = numeric_limits<double>::infinity();
const double PI = 3.14159265358979323846;
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loopll(i, n) for(ll i = 0; i < (ll)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopll1(i, n) for(ll i = 1; i <= (ll)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Looprll(i, n) for(ll i = (ll)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
#define Looprll1(i, n) for(ll i = (ll)n; i >= 1; i--)
#define Loopitr(itr, container) for(auto itr = container.begin(); itr != container.end(); itr++)
#define printv(vector) Loop(extra_i, vector.size()) { cout << vector[extra_i] << " "; } cout << endl;
#define printmx(matrix) Loop(extra_i, matrix.size()) { Loop(extra_j, matrix[extra_i].size()) { cout << matrix[extra_i][extra_j] << " "; } cout << endl; }
#define quickio() ios::sync_with_stdio(false); cin.tie(0);
#define readfile(filename) ifstream in(filename); cin.rdbuf(in.rdbuf());
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
bool nearlyeq(double x, double y) { return abs(x - y) < 1e-9; }
ll rndf(double x) { return (ll)(x + (x >= 0 ? 0.5 : -0.5)); }
ll floorsqrt(double x) { ll m = (ll)sqrt(x); return m + (m * m <= (ll)(x) ? 0 : -1); }
ll ceilsqrt(double x) { ll m = (ll)sqrt(x); return m + ((ll)x <= m * m ? 0 : 1); }
ll rnddiv(ll a, ll b) { return (a / b + (a % b * 2 >= b ? 1 : 0)); }
ll ceildiv(ll a, ll b) { return (a / b + (a % b == 0 ? 0 : 1)); }
ll gcd(ll m, ll n) { if (n == 0) return m; else return gcd(n, m % n); }

/*******************************************************/

int main() {
	quickio();
	int n; cin >> n;
	Loop1(i, 500) {
		if (i * (i - 1) / 2 == n) {
			cout << "Yes" << endl;
			cout << i << endl;
			vvi ans(i);
			int cnt = 1;
			Loop(j, i) {
				for (int k = j + 1; k < i; ++k) {
					ans[j].push_back(cnt);
					ans[k].push_back(cnt);
					cnt++;
				}
			}
			Loop(j, i) {
				cout << ans[j].size();
				Loop(k, ans[j].size()) {
					cout << " " << ans[j][k];
				}
				cout << endl;
			}
			return 0;
		}
	}
	cout << "No" << endl;
}

Measured memory_bytes: 2304
using System;

class Program
{
    static void Main(string[] args)
    {
        string Q = Console.ReadLine();
        string R = "CODEFESTIVAL2016";
        int i, ans;
        ans = 0;
        for (i = 0; i < 16; i++) {
            if (Q[i] != R[i]) ans++;
        }
        Console.WriteLine(ans);
    }
}

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

int n;
long long tw, dp[100005], ans;

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> tw;
	long long w[n], v[n];
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
	for (int i=0; i<n; i++) {
		cin >> w[i] >> v[i];
		for (int j=100004; j>=v[i]; j--) {
			dp[j] = min(dp[j], dp[j-v[i]] + w[i]);
		}
	}
	for (int i=100004; i>=0; i--) {
		if (dp[i] <= tw) {
			ans = i;
			break;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1024
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    d=make_divisors(m)
    l=m//n
    for v in d:
        if v<=l:
            print(v)
            break

def make_divisors(n):
    if n==1:
        divisors=[1]
        return divisors
    else:
        divisors=[]
        for i in range(1,n):
            if i*i>n:
                break
            if n%i==0:
                divisors.append(i)
                if i!=n//i:
                    divisors.append(n//i)

        divisors.sort(reverse=True)
        return divisors

if __name__=="__main__":
    main()

Measured memory_bytes: 3064
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <map>
#include <set>
#include <chrono>
#include <queue>
#include <string>
#include <cassert>
#include <bitset>
#include <stack> 

#define INFLL 2000000000000000000
#define INF 2000000000
#define MOD 998244353
#define BASE 77747
#define PI acos(-1.0)
#define MAXLEN 29

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;
typedef vector <ll> vll;

int dp[3000][3000];
pii par[3000][3000];
string s, t;


int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin >> s >> t;
	for (int i = 0; i < s.length(); i++) {
		for (int j = 0; j < t.length(); j++) {
			par[i][j] = make_pair(-1, -1);
			if (i == 0 && j == 0) {
				if (s[i] == t[j]) {
					dp[i][j] = 1;
					par[i][j] = make_pair(-1, -1);
				}
				continue;
			}
			if (s[i] == t[j]) {
				if (i > 0 && j > 0) {
					if (dp[i][j] < dp[i - 1][j - 1] + 1) {
						dp[i][j] = dp[i - 1][j - 1] + 1;
						par[i][j] = make_pair(i - 1, j - 1);
					}
				} else {
					if (dp[i][j] < 1) {
						dp[i][j] = 1;
						par[i][j] = make_pair(-1, -1);
					}
				}
			}
			if (i > 0 && dp[i][j] < dp[i - 1][j]) {
				dp[i][j] = dp[i - 1][j];
				par[i][j] = make_pair(i - 1, j);
			}
			if (j > 0 && dp[i][j] < dp[i][j - 1]) {
				dp[i][j] = dp[i][j - 1];
				par[i][j] = make_pair(i, j - 1);
			}
		}
	}
	int x = s.length() - 1;
	int y = t.length() - 1;
	vector <char> vec;
	while (x >= 0) {
		if (s[x] == t[y]) vec.push_back(s[x]);
		pii cur = par[x][y];
		x = cur.first;
		y = cur.second;
	}
	for (int i = vec.size() - 1; i >= 0; i--) cout << vec[i];
	cout << endl;
	return 0;
}

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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(13);
    for (int i = 0; i < n; i++) {
        int d;
        cin >> d;
        v[d]++;
    }

    if (v[0] > 0)cout << 0 << endl;
    else {
        vector<bool> exist(24);
        exist[0] = true;
        vector<int> alone;
        for (int i = 1; i <= 12; i++) {
            if (v[i] > 2) {
                cout << 0 << endl;
                return 0;
            } else if (v[i] == 2) {
                exist[i] = true, exist[24 - i] = true;
            } else if (v[i] == 1) {
                alone.push_back(i);
            }
        }

        int m = alone.size();
        int ret = 0;
        for (int i = 0; i < 1 << m; i++) {
            vector<bool> now = exist;
            for (int j = 0; j < m; j++) {
                if (i & (1 << j))now[alone[j]] = true;
                else now[24 - alone[j]] = true;
            }

            int nowres = 114514;
            for (int j = 0; j < 24; j++) {
                for (int k = j + 1; k < 24; k++) {
                    if (now[j] && now[k])nowres = min({nowres, k - j, 24 - (k - j)});
                }
            }
            ret = max(ret, nowres);
        }
        cout << ret << endl;
    }
    return 0;
}

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

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<char>> A(H, vector<char>(W));
    rep(i,H) {
        rep(j,W) {
            cin >> A.at(i).at(j);
        }
    }
    rep(i,H) {
        rep(j,W) {
            if ((i != 0 || j != 0 || i != H - 1 || j != W - 1)) {
                if (A.at(i).at(j) == '#') {
                    if ((i - 1 >= 0 && j - 1 >= 0 && A.at(i - 1).at(j) == A.at(i).at(j - 1))
                    || (i - 1 < 0 && j - 1 >= 0 && A.at(i).at(j - 1) == '.')
                    || (i - 1 >= 0 && j - 1 < 0 && A.at(i - 1).at(j) == '.')
                    || (i + 1 < H && j + 1 < W && A.at(i + 1).at(j) == A.at(i).at(j + 1))
                    || (i + 1 >= H && j + 1 < W && A.at(i).at(j + 1) == '.')
                    || (i + 1 < H && j + 1 >= W && A.at(i + 1).at(j) == '.')) {
                        cout << "Impossible" << endl;
                        return  0;
                    }
                }
            }
        }
    }
    cout << "Possible" << endl;
}


Measured memory_bytes: 3632
var a:array[0..100020] of int64;
var n,ans,x,y,num:int64;
var i:longint;
procedure qsort(l,r:int64);
var i,j,mid,t:int64;
begin
  i:=l;j:=r;mid:=a[(l+r)>>1];
  repeat
    while a[i]>mid do inc(i);
    while a[j]<mid do dec(j);
    if i<=j then
    begin
      t:=a[i];a[i]:=a[j];a[j]:=t;
      inc(i);dec(j);
    end;
  until i>j;
  if l<j then qsort(l,j);
  if i<r then qsort(i,r);
end;
begin
  read(n);
  for i:=1 to n do read(a[i]);qsort(1,n);
  i:=0;
  while i<n do
  begin
    num:=1;inc(i);while a[i]=a[i+1] do begin inc(i);inc(num);end;
    if num>1 then begin if x=0 then x:=a[i] else y:=a[i];end;
    if y>0 then break;
    if (num>=4) then begin y:=a[i];break;end;
  end;
  writeln(x*y);
end.

Measured memory_bytes: 896
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

const ll max_a = 1000000000;

struct BIT{
  ll M;
  std::vector<ll> bit;
  BIT(ll n){
    init(n);
  }
  void init(ll n){
    M = n;
    bit.resize(M+1);
    fill(bit.begin(),bit.end(),0);
  }
  ll sum(ll i){
    ll s = 0;
    while(i>0){
      s += bit[i];
      i -= i & -i;
    }
    return s;
  }
  void add(ll i, ll x){
    while(i<=M){
      bit[i] += x;
      i += i & -i;
    }
  }
};

int main(){
  ll n;
  cin >> n;
  ll a[n];
  ll a_sort[n];
  REP(i,n){
    cin >> a[i];
    a_sort[i] = a[i];
  }
  sort(a_sort,a_sort+n);
  ll lb = 0, ub = n;
  while(ub-lb>1){
    ll x = (lb + ub)/2;
    ll b[n];
    REP(i,n) b[i] = (a[i]<a_sort[x]) ? -1 : 1;
    ll s[n];
    REP(i,n){
      s[i] = (i==0) ? b[i] : s[i-1]+b[i];
    }
    ll cnt = 0;
    BIT bit(2*n+1);
    bit.add(n,1);
    REP(j,n){
      cnt += bit.sum(s[j]+n);
      bit.add(s[j]+n,1);
    }
    if(cnt>=ceil(n*(n+1)/2/2)){
      lb = x;
    }else{
      ub = x;
    }
  }
  cout << a_sort[lb] << endl;
  return 0;
}


Measured memory_bytes: 4968
import java.util.Scanner;

public class Main {

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

		for (int i = 0; i < N; i++) {
			a[i] = sc.nextInt();
		}

		int sum = 0;
		for (int i = 0; i < N; i++) {
			sum += a[i] - 1;
		}

		System.out.println(sum);
	}
}

Measured memory_bytes: 26064
def count_section_by_zero(data):
  count = 0
  flg = False
  start = 0
  for i, d in enumerate(data):
    if flg is False and d != 0:
      count += 1
      flg = True
      
    if d == 0:
      flg = False
  return count

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

def input_list_str():
  return list(map(str, input().split()))

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
  x = int(input())
  x_500 = 0
  x_5 = 0
  if x >= 500:
    x_500 = x//500
  x -= x_500 * 500
  if x >= 5:
    x_5 = x//5
  print(int(x_500*1000 + x_5 *5))
import math
import fractions
import collections
import itertools
from functools import reduce
main()

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

using namespace std;
typedef long long ll;
const ll INF = 1e9;
 
int main(void) {
    int N;
    cin >> N;
    double sum = 0.0;
    for (int i = 0; i < N; i++) {
        double a; cin >> a;
        sum += 1.0 / a;
    }
    sum = 1.0 / sum;
    cout << sum << endl;
}

Measured memory_bytes: 256
import std.stdio, std.string, std.conv;
import std.typecons;
import std.algorithm, std.array, std.range, std.container;
import std.math;

void main() {
	auto X = readln.split[0].to!long;
	long money = 100;
	foreach (i; 1 .. 4000) {
	    money = cast(long) floor(money * 1.01);
	    if (money >= X) { writeln(i); break; }
	}
}



Measured memory_bytes: 2760
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<list>
#include<vector>
#include<cmath>

using namespace std;

int main(){
    unsigned long long h, w;
    cin >> h >> w;

    if((h%3==0) || (w%3==0)){
        cout << 0 << endl;
        return 0;
    }

    unsigned long long s[3], tmp[3];

    unsigned long long ans = h*w;
    for(unsigned long long i=0;i<h;i++){
        s[0] = i*w;
        s[1] = ((h-i)/2)*w;
        s[2] = h*w-s[0]-s[1];
//cout << s[0] << ":" << s[1] << ":" << s[2] << "###";
        tmp[0] = s[0];
        tmp[1] = s[1];
        tmp[2] = s[2];
        sort(tmp, tmp+3);
        ans = min(ans,tmp[2]-tmp[0]);

        s[1] = (h-i)*(w/2);
        s[2] = h*w-s[0]-s[1];
//cout << s[0] << ":" << s[1] << ":" << s[2] << endl;
        sort(s, s+3);
        ans = min(ans,s[2]-s[0]);
    }

    h += w;
    w = h-w;
    h -= w;
    for(unsigned long long i=0;i<h;i++){
        s[0] = i*w;
        s[1] = ((h-i)/2)*w;
        s[2] = h*w-s[0]-s[1];
        tmp[0] = s[0];
        tmp[1] = s[1];
        tmp[2] = s[2];
        sort(tmp, tmp+3);
        ans = min(ans,tmp[2]-tmp[0]);

        s[1] = (h-i)*(w/2);
        s[2] = h*w-s[0]-s[1];
        sort(s, s+3);
        ans = min(ans,s[2]-s[0]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

usedall = set()
ans = 0

for j in range(h):
    for i in range(w):
        if (i, j) in usedall:
            continue

        used = {(i, j)}
        usedall.add((i, j))
        q = deque([(i, j)])

        while q:
            ii, jj = q.popleft()
            cur = s[jj][ii]

            for k in range(4):
                if not (0 <= ii + dx[k] < w):
                    continue
                if not (0 <= jj + dy[k] < h):
                    continue

                if s[jj + dy[k]][ii + dx[k]] == cur:
                    continue
                if (ii + dx[k], jj + dy[k]) in used:
                    continue

                used.add((ii + dx[k], jj + dy[k]))
                usedall.add((ii + dx[k], jj + dy[k]))
                q.append((ii + dx[k], jj + dy[k]))

        black = 0
        white = 0
        for m, n in used:
            if s[n][m] == "#":
                black += 1
            else:
                white += 1

        ans += black * white

print(ans)

Measured memory_bytes: 76508
import java.util.*;
import java.math.*;


public class Main {

public static void main(String[] args) {

   Scanner in = new Scanner(System.in);

   int N = in.nextInt();
   int A = 0;// 4で割り切れる数
   int B = 0;// 2で割り切れる数
   int C = 0;// 1
   int D = 0;// 上記以外

   for(int cnt = 0; cnt < N; cnt++){
       int num = in.nextInt();
       if(num % 4 == 0){
           A++;
       }
       else if(num % 2 == 0){
           B++;
           if(B % 2 == 0){
               B = B - 2;
               A++;
           }
       }
       else{
           C++;
       }
   }
   //2nが偶数個
   if(A >= N / 2){
       System.out.println("Yes");
   }
   else{
       System.out.println("No");
   }
   in.close();
}}

Measured memory_bytes: 46180
#include <bits/stdc++.h>
#define ll long long int
#define mp make_pair
#define pb push_back
#define ff first 
#define ss second
#define mod 1000000007
#define lim 100005
#define nfs_mw ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int main()
{
	nfs_mw;
	int i,d,j,k,n,a[401]; ll dp[401][401] = {}, part[401] = {};
	cin>>n;
	for(i=1; i<=n; i++) { cin>>a[i]; part[i] = part[i-1] + a[i]; }
	for(d=1; d<n; d++)
		for(i=1; i<=n-d; i++){
			j = i+d;
			dp[i][j] = 1e18;
			for(k=i; k<j; k++)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + part[j] - part[i-1]);
		}
	cout<<dp[1][n];
}

Measured memory_bytes: 1536
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"math/big"
	"os"
	"sort"
)

var scan *bufio.Scanner
var reader io.Reader
var writer io.Writer

func init() {
	scan = bufio.NewScanner(os.Stdin)
	reader = os.Stdin
	writer = os.Stdout
	scan.Split(bufio.ScanWords)
}

func main() {
	solve()
}

// Can is ...
type Can struct {
	num  int
	cost int
}

// Cans is ...
type Cans []Can

func (a Cans) Len() int {
	return len(a)
}

func (a Cans) Swap(i, j int) {
	a[i], a[j] = a[j], a[i]
}

func (a Cans) Less(i, j int) bool {
	return a[i].cost > a[j].cost
}

func solve() {
	var (
		n int
	)
	cin(&n)
	var a Cans
	//a := make([]Can, n)
	for i := 0; i < n; i++ {
		var cost int
		cin(&cost)
		a = append(a, Can{i + 1, cost})
	}

	sort.Sort(a)

	for i := 0; i < n; i++ {
		print(a[n-1-i].num, " ")
	}
}

func cin(a ...interface{}) {
	for i := 0; i < len(a); i++ {
		doScan(a[i])
	}
	return
}
func doScan(a interface{}) {
	switch a.(type) {
	case *[]int:
		s := *a.(*[]int)
		for i := 0; i < len(s); i++ {
			fmt.Fscan(reader, &s[i])
		}
	case *[]string:
		s := *a.(*[]string)
		for i := 0; i < len(s); i++ {
			fmt.Fscan(reader, &s[i])
		}
	default:
		fmt.Fscan(reader, a)
	}
	return
}

func print(a ...interface{}) {
	fmt.Fprint(writer, a...)
}

func println(a ...interface{}) {
	fmt.Fprintln(writer, a...)
}

func max(x int, y ...int) int {
	res := float64(x)
	for _, z := range y {
		res = math.Max(res, float64(z))
	}
	return int(res)
}

func min(x int, y ...int) int {
	res := float64(x)
	for _, z := range y {
		res = math.Min(res, float64(z))
	}
	return int(res)
}

func abs(x int) int {
	return int(math.Abs(float64(x)))
}

func sqrt(x int) int {
	return int(math.Sqrt(float64(x)))
}

func int2Int(x int) big.Int {
	var res big.Int
	res.SetInt64(int64(x))
	return res
}


Measured memory_bytes: 7696