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

const int maxn=30;
int n;
char s[maxn];
int vis[maxn];

void solve(){
	for(int i=0;i<26;i++) if(!vis[i]){
		printf("%s", s+1); printf("%c", i+'a');
		return;
	}
}

int main(){

	scanf("%s", s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++) vis[ s[i]-'a' ]=i;
	if(n<26){ solve(); return 0; } 
	for(int i=n;i>=1;i--){
		int u=s[i]-'a';
		for(int j=u+1;j<26;j++){
			if(vis[j]>i){
				for(int k=1;k<i;k++) printf("%c", s[k]);
				printf("%c", j+'a');
				return 0;
			}
		}
	}
	puts("-1");
	return 0;
}


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

using namespace std;
using ll = long long int;
constexpr ll M = 1e9 + 7;
inline ll sum_1(const ll n) { return ((n * (n + 1)) / 2) % M; }
inline ll sum_2(const ll n) { return ((n * (n + 1) * (2 * n + 1)) / 6) % M; }
inline ll sum_3(const ll n) { return (((n * (n + 1)) / 2) % M * ((n * (n + 1)) / 2) % M) % M; }
inline ll sum_1(const ll i, const ll j) { return (sum_1(j) - sum_1(i - 1) + M) % M; }
inline ll sum_2(const ll i, const ll j) { return (sum_2(j) - sum_2(i - 1) + M) % M; }
inline ll sum_3(const ll i, const ll j) { return (sum_3(j) - sum_3(i - 1) + M) % M; }

ll pow_f(ll b, ll e) {
    ll ans = 1;
    b = b % M;
    while (e) {
        if (e&1) {
            ans = (ans * b) % M;
        }
        b = (b * b) % M;
        e >>= 1;
    }
    return ans;
}

ll nCr(ll n, ll r) {
    if (r > n || n < 0 || r < 0) { return 0; }
    if (n == r || r == 0) { return 1; }
    r = min(r, n-r);
    ll ans = 1;
    for (ll i = 1; i <= r; ++i) {
        ans = (ans * (n-i+1))/(i); 
    }
    return ans;
}

ll nCr(tuple<ll,ll> t) {
    auto n = get<0>(t);
    auto k = get<1>(t);
    return nCr(n+k-1, k);
}

template<typename T>
void print(const T &v) {
    cout << v << " ";
}

template<typename T>
void print(const vector<T> &v) {
    for (auto &i : v) {
        print(i);
    }
    cout << endl;
}

struct myHash {
    size_t operator()(const pair<ll,ll> &p) const {
        return p.first + p.second;
    }
};

unordered_map<pair<ll,ll>, ll, myHash> m;

ll dp(ll i, ll j, vector<ll> &A) {
    if (m.find({i, j}) != m.end()) {
        return m[{i, j}];
    }

    if (i == 0 && j == 0) {
        ll temp = A[0];
        m[{i, j}] = temp;
        return temp;
    } else if (j == 0) {
        ll temp = max(A[i], dp(i-1, j, A));
        m[{i, j}] = temp;
        return temp;
    } else if (j > i/2) {
        return LLONG_MIN;
    } else {
        ll temp = max(A[i] + dp(i-2, j-1, A), dp(i-1, j, A));
        m[{i, j}] = temp;
        return temp;
    }
}

void solve() {
    ll n;
    cin >> n;

    vector<ll> A(n);
    for (auto &i : A) {
        cin >> i;
    }

    ll num = n/2;
    cout << dp(n-1,num-1,A);
    /**
     * 
     * n elements with n/2 positions to fill
     * consider i'th element for j'th position
     * max sum with i-2'th element with j-1'th position or max i-1th as j'th
     * 
     * 1'st element cannot be at n/2 position
     * only at 1 or not
     * 
     * i/2'th position at max
     */ 
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifdef D_LOCAL
        freopen("in.in", "r", stdin);
        freopen("out.out", "w", stdout);
    #endif

    solve();

    return 0;
}

Measured memory_bytes: 32260
package main

import (
    "fmt"
    "sort"
)

type As [][]int

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

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

func (a As) Less(i, j int) bool {
    return a[i][0] < a[j][0]
}

func main() {
    var n, m int
    fmt.Scan(&n, &m)
    as := make(As, n)
    for i := 0; i < n; i++ {
        var a, b int
        fmt.Scan(&a, &b)
        as[i] = []int{a, b}
    }
    sort.Sort(as)

    rest := m
    var sum int
    for _, a := range as {
        price := a[0]
        num := a[1]
        if num >= rest {
            sum += rest * price
            break
        }
        sum += num * price
        rest -= num
    }

    fmt.Println(sum)
}


Measured memory_bytes: 6784
#include <stdio.h>

int main(){
	long N,M,n,m;
	scanf("%ld %ld",&N,&M);

	if(N >= 2) n = N-2;
		else n = 1;
	if(M >= 2) m = M-2;
		else m = 1;

	printf("%ld",n*m);

	return 0;
}

Measured memory_bytes: 128
#include <iostream>

using namespace std;

void bkt(int k);
void verif();

int n, m, nrsol, sol[15], a[15][15], p[15];

int main()
{
	int i, j;

	cin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		cin >> a[i][0];
		for (j = 1; j <= a[i][0]; j++)
			cin >> a[i][j];
	}
	for (i = 1; i <= m; i++)
		cin >> p[i];
	bkt(1);
	cout << nrsol << '\n';
	return 0;
}

void bkt(int k)
{
	int i;

	if (k == n + 1)
	{
		verif();
		return;
	}
	sol[k] = 0;
	bkt(k + 1);
	sol[k] = 1;
	bkt(k + 1);
}

void verif()
{
	int i, j, nr;

	for (i = 1; i <= m; i++)
	{
		nr = 0;
		for (j = 1; j <= a[i][0]; j++)
			nr += sol[a[i][j]];
		if (nr % 2 != p[i] % 2)
			return;
	}
	nrsol++;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] split = s.split(" ");
        int a = Integer.parseInt(split[0]);
        int b = Integer.parseInt(split[1]);

        if (a % 2 == 0 || b % 2 == 0) {
            System.out.print("Even");
        } else {
            System.out.print("Odd");
        }
    }
}


Measured memory_bytes: 20308
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
int mod=1e9+7;
int mod2=998244353;
const int INF=1e9;

signed main(){
  int a,b,x;
  cin>>a>>b>>x;
  if(x<a){
    cout<<x%mod<<endl;
    return 0;
  }
  int n=(x-a)/(a-b)+1;
  n%=mod;
  a%=mod;
  b%=mod;
  x%=mod;
  int ans=x+(n*b)%mod;
  cout<<ans%mod<<endl;
}


Measured memory_bytes: 3076
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    int a,b,c,s1,s2;
    cin>>a>>b>>c;
    if(a>b)
    {
        s1=b;
        if(a>c) s2=c;
        else s2=a;
    }
    else {
        s1=a;
        if(b>c) s2=c;
        else s2=b;
    }
    cout<<s1+s2;
    return 0;
}

Measured memory_bytes: 892
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = sorted(LI())
cnt = Counter(A)
ans = 0
for i in range(n - 1, -1, -1):
    a = A[i]
    if cnt[a]:
        cnt[a] -= 1
        b = 2 ** a.bit_length() - a
        if cnt[b]:
            ans += 1
            cnt[b] -= 1

print(ans)





Measured memory_bytes: 86568
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <memory.h>
#include <algorithm>
#include <iomanip>
#include <string>
#include <bitset>

#define F first
#define S second
#define MP make_pair

typedef long long ll;

using namespace std;

int const PI = acos(-1);
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };

long long gcd(long long a, long long b) {
	return b == 0 ? a : gcd(b, a % b);
}

long long lcm(long long a, long long b) {
	return a * (b / gcd(a, b));
}

int const N = 101;
long long n, w;
long long dp[N][10000];
vector<pair<long long, long long> > a;

long long calc(int index, long long sum) {
  if(index == n) return 0;
  if(dp[index][int(sum % 10000)] != -1) return dp[index][int(sum % 10000)];
  
  long long res1 = 0, res2 = 0;
  if(sum >= a[index].first) res1 = calc(index + 1, sum - a[index].first) + a[index].second;
  res2 = calc(index + 1, sum);
  return dp[index][int(sum % 10000)] = max(res1, res2);
}

int main() {
	scanf("%d%d", &n, &w);
	a.resize(n);
	for(int i = 0; i < n; ++i)
	  scanf("%d%d", &a[i].first, &a[i].second);
	
	memset(dp, -1, sizeof dp);
	cout << calc(0, w) << endl;

  return 0;
}

Measured memory_bytes: 8192
from collections import defaultdict
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n = ni()
ss = []
cs = []
for i in range(n):
    s, c = stdin.readline().split()
    ss.append(s)
    cs.append(int(c))

dp = defaultdict(lambda: 999999999999999)
rdp = defaultdict(lambda: 999999999999999)
p = 0
ved = set()
for s in ss:
    dp[s] = min(dp[s], cs[p])
    p += 1
    ved.add(s)

ans = 999999999999999

while True:
    dpp = defaultdict(lambda: 999999999999999)
    rdpp = defaultdict(lambda: 999999999999999)
    for k, v in dp.items():
        if k == k[::-1]:
            ans = min(ans, v)
        else:
            p = 0
            for s in ss:
                if k.startswith(s[::-1]):
                    ns = k[len(s):]
                    if v + cs[p] < dp.get(ns, 99999999999999):
                        dpp[ns] = min(dpp[ns], v + cs[p])
                elif s[::-1].startswith(k):
                    ns = s[::-1][len(k):]
                    if v + cs[p] < rdp.get(ns, 99999999999999):
                        rdpp[ns] = min(rdpp[ns], v + cs[p])
                p += 1
    for k, v in rdp.items():
        if k == k[::-1]:
            ans = min(ans, v)
        else:
            p = 0
            for s in ss:
                if k.startswith(s):
                    ns = k[len(s):]
                    if v + cs[p] < rdp.get(ns, 999999999999999):
                        rdpp[ns] = min(rdpp[ns], v + cs[p])
                elif s.startswith(k):
                    ns = s[len(k):]
                    if v + cs[p] < dp.get(ns, 999999999999999):
                        dpp[ns] = min(dpp[ns], v + cs[p])
                p += 1
    if len(dpp) + len(rdpp) == 0:
        break
    for k, v in dpp.items(): dp[k] = v
    for k, v in rdpp.items(): rdp[k] = v
print(ans if ans < 999999999999999 else -1)


Measured memory_bytes: 74576
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define MOD 1000000007
#define ll long long int
#define pair <ll, ll> pi
#define vector <ll> vi
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define SQ(a) (a) * (a)
#define ordered_set tree<ll, null_type, greater_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> //greater_equal<ll> or less<ll>
// find_by_key()   order_of_key()
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
/*bool comp(string a, string b) {
if (a.size() != b.size()) return a.size() < b.size();
return a < b;
}*/

/*void printNcR(ll n, ll r) 
{ 
 long long p = 1, k = 1; 
    if (n - r < r) 
        r = n - r; 
    if (r != 0) { 
        while (r) { 
            p *= n; 
            k *= r; 
            long long m = __gcd(p, k); 
            p /= m; 
           k /= m; 
            n--; 
            r--; 
        } 
    } 
    else
        p = 1; 
    cout << p << endl; 
} */
// priority_queue <int, vector<int>, greater<int> >  min priority_queue
 //std:: set<ll> :: iterator it;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen('input.txt', 'r', stdin);
    //freopen('output.txt', 'w', stdout);
    ll i, j, k, n, m, b, d, t, ans = 0,a,x,y;
    double D,F;
    cin>>n>>D;
    while(n--){
        cin>>x>>y;
        F=sqrt(x*x+y*y);
        if(F<=D){
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3756
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define max0(a,b,c) max(max(a,b),c)
#define min0(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
using Graph = vector<vector<int>>;
typedef long long lint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldouble;
typedef vector<int> vec;
typedef vector<ll> lvec;
typedef vector<ull> ulvec;
typedef vector<double> dvec;
typedef vector<pair<int,int>> pvec;
typedef vector<pair<ll,ll>> plvec;
typedef vector<tuple<ll,ll,ll>> tvec;
typedef vector<string> svec;

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

int main(){
    ll n;
    cin>>n;
    lvec a;
    for(int i=2;i<=100003;i++){
        if(is_prime(i)) a.push_back(i);
    }
    sort(all(a));
    ll m=lower_bound(all(a),n)-a.begin();
    cout<<a[m]<<endl;
}

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

int main()
{
    int a, b, c, cnt = 0;
    cin >> a >> b >> c;
    for (int i = a; i <= b; ++i)
    {
        if (c % i == 0)
        {
            ++cnt;
        }
    }
    cout << cnt << endl;
    return 0;
}



Measured memory_bytes: 3108
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    return S[:3]


def main():
    S = read_str()
    print(slv(S))


if __name__ == '__main__':
    main()


Measured memory_bytes: 76788
import collections
q=collections.deque()
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append('#')
for i in range(h):
  arr[i+1].append('#')
  for j in input():
    arr[i+1].append(j)
  arr[i+1].append('#')
for i in range(w+2):
  arr[h+1].append('#')
dx=[-1,0,1,0]
dy=[0,-1,0,1]
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]=='#':
      q.append([i,j,0])
while 1:
  y,x,cnt=q.popleft()
  for i in range(4):
    if arr[y+dy[i]][x+dx[i]]=='.':
      q.append([y+dy[i],x+dx[i],cnt+1])
      arr[y+dy[i]][x+dx[i]]='#'
  if len(q)==0:
    print(cnt)
    break


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

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

  ll s, t ,x;
  vector<tuple<ll, ll, bool>> events;
  for (ll i = 0; i < n; i ++) {
    cin >> s >> t >> x;
    events.push_back(make_tuple(s - x, x, true));
    events.push_back(make_tuple(t - x, x, false));
  }
  sort(events.begin(), events.end());

  vector<ll> d(q);
  for (ll i = 0; i < q; i ++) {
    cin >> d[i];
  }

  set<ll> xs;
  ll i = 0;

  for (auto di : d) {
    // cout << "d : " << di << endl;
    while (i < 2*n && get<0>(events[i]) <= di) {
      auto x = get<1>(events[i]);
      auto begin = get<2>(events[i]);

      if (begin) {
        // cout << "begin : " << x << endl;
        xs.insert(x);
      } else {
        // cout << "end : " << x << endl;
        xs.erase(x);
      }

      i++;
    }
    if (xs.size()) {
      cout << *xs.begin() << endl;
    } else {
      cout << -1 << endl;
    }
  }
}


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

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<int> a(2 * m);
    for (int i = 0; i < 2 * m; i++) {
        cin >> a[i];
    }
    
    for (int j = 1; j <= n; j++) {
        int count = 0;
        for (int i = 0; i < 2 * m; i++) {
            if (a[i] == j) count++;
        }
        cout << count << endl;
    }
}

Measured memory_bytes: 3460
#include <iostream>

using namespace std;

int main (){
    int a, b, i;
    for(i=0; i<3000; i++){
    cin>>a>>b;
    if(a==0&&b==0){
    return 0;
    }
    else if(b>=a){
    cout<<a<<" "<<b<<endl;
    }
    else{
    cout<<b<<" "<<a<<endl;
    }
    }
    cout<<endl;
}


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

int main(){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  
  if( (max(a,b)-min(a,b) <= d) && (max(b,c)-min(b,c) <= d)){
    cout << "Yes" << endl;
  }
  else if(max(a,c)-min(a,c) <=d){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
A=int(input())
B=int(input())
C=int(input())
D=int(input())
E=int(input())
a=-(-A//10)*10
b=-(-B//10)*10
c=-(-C//10)*10
d=-(-D//10)*10
e=-(-E//10)*10
print(a+b+c+d+e-max(a-A,b-B,c-C,d-D,e-E))



Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <iomanip>
#include <math.h>
#include <fstream>

using namespace std;

class pqComp
{
public:
    bool operator()(pair<int, int> &a, pair<int, int> &b)
    {
        return a.second < b.second;
    }
};

bool sorting(pair<int, int> a, pair<int, int> b)
{
    return a.second < b.second;
}

int main()
{
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cin.tie();
    cout.tie();
    // ifstream cin("in.txt");
    // ofstream cout("out.txt");
    
    
    // int t;
    // cin >> t;
    // for (int qwe = 0; qwe < t; qwe++)
    // {
    //     cout << "Case #" << qwe + 1 << ": ";
    // }


    int k;
    string s;
    cin >> k >> s;
    if (s.size() <= k)
    {
        cout << s << '\n';
    }
    else
    {
        cout << s.substr(0, k) << "...\n";
    }


    return 0;
}


Measured memory_bytes: 3104
H, W, A, B = map(int, input().split())
MOD = 10 ** 9 + 7

i = H - A - 1
j = B


# 階乗とその逆元を事前計算する (O(N))
# finv[0] := 0の階乗の逆元
def factorial_and_inv(n, mod=10 ** 9 + 7):
    f = [1]
    for n in range(1, n):
        f.append(f[n - 1] * n % mod)
    finv = [0] * n
    finv[n - 1] = pow(f[n - 1], mod - 2, mod)
    for n in range(n - 2, -1, -1):
        finv[n] = finv[n + 1] * (n + 1) % mod
    return f, finv


f, finv = factorial_and_inv(W + H + 2, MOD)
ans = 0
while i >= 0 and W > j:
    path1 = f[i + j] * finv[i] % MOD * finv[j] % MOD
    path2 = f[(H - i - 1) + (W - j - 1)] * finv[H - i - 1] % MOD * finv[W - j - 1] % MOD
    ans += path1 * path2 % MOD
    i -= 1
    j += 1
print(ans % MOD)


Measured memory_bytes: 54128
#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
 
 
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N;
 
    cin >> N;
 
    vector<int> temp;
 
    for(int i = 1 ; i <= N ; i++)temp.push_back(i);
 
    vector<int> v1, v2;
 
	for(int i = 0 ; i < N ; i++)
	{
		int n;
		cin >> n;
		v1.push_back(n);
	}
 
	for(int i = 0 ; i < N ; i++)
	{
		int n;
		cin >> n;
		v2.push_back(n);
	}
 
	int a = -1, b = -1;
 
	int cont = 0;
 
	do
	{
		cont++;
		if(v1 == temp)a = cont;
		if(v2 == temp)b = cont;
	}
	while(next_permutation(temp.begin(),temp.end()));
 
	cout << abs(b-a) << '\n';
 
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;

const double EPS = 1e-12;

int p, q, a, n, c;
double d;

void solve(int s, int t, double sum, int m){
	if(m==n) return;
	for(int i=s;;i++){
		if(t*i>a) break;
		if(abs(d - (sum + 1.0/i)) < EPS) c++;
		if(d - (sum + 1.0/i) > EPS) solve(i,i*t,sum+1.0/i,m+1);
	}
}

int main(){
	while(cin >> p >> q >> a >> n){
		if(!p) break;
		d = (double)p/q;
		c = 0;
		solve(1,1,0.0,0);
		cout << c << endl;
	}
}

Measured memory_bytes: 864
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> p(N);
    rep(i, N) cin >> p[i];

    double e = 0;
    rep(i, K) e += (1 + p[i]) / 2.0;
    double ans = e;
    rep(i, K, N) {
        e -= (1 + p[i - K]) / 2.0;
        e += (1 + p[i]) / 2.0;
        ans = max(ans, e);
    }
    write(ans);
}

Measured memory_bytes: 1024
n,m=map(int,input().split())
x=[0]*m
for i in range(0,n):
  lis=list(map(int,input().split()))
  k=lis[0]
  for j in range(1,k+1):
    a=lis[j]-1
    x[a]+=1

ans=0
for y in x:
  if y==n:
    ans+=1
print(ans)

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


int main(){
  long long n,a,b,c,d,e;
  cin >> n >> a >> b >> c >> d >> e;
  long long mi;
  mi=min(a,b);
  mi=min(mi,c);
  mi=min(mi,d);
  mi=min(mi,e);
  long long ans;
  if(n%mi==0){
    ans=n/mi+4;
  }else{
    ans=n/mi+5;
  }
  cout << ans << endl;
  return 0;

}


Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<map>
#include<string>

int n;
std::map<std::string, int> hash;

int main()
{
	while( std::cin >> n, n )
	{
		hash.clear();

		for( int i = 0; i != n; ++i )
		{
			std::string s;
			int p;
			std::cin >> s >> p;
			hash.insert( std::make_pair( s, p ) );
		}

		int m;
		std::cin >> m;
		for( int i = 0; i != m; ++i )
		{
			std::string o;
			int k;
			std::cin >> o >> k;
			
			int p = 0;
			for( int j = 0; j != k; ++j )
			{
				std::string q;
				std::cin >> q;
				p += hash[q];
			}

			hash[o] = std::min( hash[o], p );
		}

		std::string item;
		std::cin >> item;
		std::cout << hash[item] << std::endl;
	}

	return 0;
}

Measured memory_bytes: 1224
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  ll N, M; cin >> N >> M;
  vector<ll> dp(N + 1, 0);
  dp[0] = 1;
  ll a, cnt = 0;
  cin >> a;
  for(ll i = 1; i < N + 1; i++) {
    if(i == a && cnt < M) {
      cin >> a;
      cnt++;
      continue;
    }
    dp.at(i) += dp.at(i - 1) % 1000000007;
    if(i > 1) dp.at(i) += dp.at(i - 2) % 1000000007;
    dp.at(i) %= 1000000007;
  }
  cout << dp.at(N) << endl;
}

Measured memory_bytes: 1024
N, K = gets.split(' ').map(&:to_i)
A = gets.split(' ').map(&:to_i)
sum = A.inject(:+)

root = sum ** 0.5
k = 1
divisor = []
while k <= root
	if sum % k == 0
		divisor.push(k)
		divisor.push(sum / k)
	end
	k += 1
end
cand = []
divisor.each do |d|
	b = A.collect{|n| n % d}.sort.reverse
	modsum = b.inject(:+)
	op = 0
	pos = 0
	while pos < modsum / d
		op += (d - b[pos])
		pos += 1
	end
	cand.push(d) if op <= K
end
puts cand.max

Measured memory_bytes: 11128
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
main(){
	cin>>n;
	for(int i=0;((int)1<<i)<n;i++){
		if(!(((int)1<<i)&n)){
			cout<<((int)1<<i)<<endl;
			return 0;
		}
	}
	cout<<n+1<<endl;
}

Measured memory_bytes: 3100
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
#include <unordered_map>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;

int main()
{
    ll N;
    scanf("%lld", &N);

    string s, t;
    cin >> s >> t;

    ll ans = 0;
    for (ll i = 0; i < s.length(); i++)
    {
        if (s[i] != t[i])
            ans++;
    }
    printf("%lld\n", ans);
}


Measured memory_bytes: 3944
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define all(a) a.begin(),a.end()
#define endl '\n'
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ull unsigned long long
#define int long long
#define iter set<int>::iterator
using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<class T>
using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd1(chrono::steady_clock::now().time_since_epoch().count());

//find_by_order
//order_of_key

const int N=2e5+7;
const int inf=1e18+5;
const int mod=1e9+7;

int dp[N][2];

main ()
{
    ios;
    string s;
    cin>>s;
    s='#'+s;
    for (int i=1;i<s.size();++i){
        if (s[i]!=s[i-1]){
            dp[i][0]=max(dp[i][0],dp[i-1][0]+1);
        }
        dp[i][0]=max(dp[i][0],dp[i-1][1]+1);
        if (i>1){
            dp[i][1]=max(dp[i][1],dp[i-2][0]+1);
            string p="";
            p+=s[i-3];
            p+=s[i-2];
            string p1="";
            p1+=s[i-1];
            p1+=s[i];
            if (p!=p1){
                dp[i][1]=max(dp[i][1],dp[i-2][1]+1);
            }
        }
    }
    int pos=s.size()-1;
    int ans=max(dp[pos][0],dp[pos][1]);
    cout<<ans<<endl;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100005
ll n;

const ll mod=1e9+7;
ll mypow(ll a,ll p){
	ll ret=1;
    while(p>0){
		if(p%2)ret=(ret*a)%mod;
		a=(a*a)%mod;
		p>>=1;
	}
	return ret;
}
ll fac[N],a[N];
ll comb(ll n,ll m){
	int tmp=(fac[m]*fac[n-m])%mod;
	return mypow(tmp,mod-2)*fac[n]%mod;
}

int	main()
{
	cin>>n;
	fac[0]=fac[1]=1;
	for (ll i = 2; i <=n+1; i++) {
		fac[i]=(fac[i-1]*i)%mod;
	}
	ll l=0;
	for (ll i = 0; i < n+1; i++) {
		ll t;
		cin>>t;
		if(a[t]==0){
		a[t]=i+1;
		}
		else l=1+n-(i+2-a[t]);
	}
	for(ll i=1;i<=n+1;i++){
		int ret=comb(n+1,i);
		if(l>=i-1)ret=(ret+mod-comb(l,i-1))%mod;
		cout<<ret<<endl;
	}
	return 0;
}


Measured memory_bytes: 2816
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
signed main()
{
	int N, M;
	cin >> N >> M;
	if (M <= N)
	{
		cout << 0;
		return 0;
	}
	vector<int>X(M);
	priority_queue<int>q;
	rep(i, M)
	{
		cin >> X[i];
	}
	sort(X.begin(), X.end());
	rep(i, M - 1)
	{
		q.push(X[i + 1] - X[i]);
	}
	int ans = X[M - 1] - X[0];
	rep(i, N - 1)
	{
		ans -= q.top();
		q.pop();
	}
	cout << ans;
}

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

#define int long long int
#define ff first
#define ss second
#define pb push_back

#define N 1010

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

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

	sort(a, a + n, greater<int>());

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


	int l = 0, r = 1e12;
	int cnt = 0, ret = 0;
	while(r - l > 1)
	{
		int mid = l + r >> 1;
		cnt = 0, ret = 0;
		for (int i = 0; i < n; ++i)
		{
			int k = mid - a[i];
			int l1 = 0, r1 = n - 1;
		
			while(l1 < r1)
			{
				int mid1 = l1 + r1 + 1 >> 1;
				if(a[mid1] < k)
					r1 = mid1 - 1;
				else
					l1 = mid1; 
			}
			if(a[l1] >= k)
			{
				// cout << l1 << "   ";
				cnt += l1 + 1;
				ret += cum[l1] + (l1 + 1) * a[i];
			}
		}

		// cout << " :" << l << " " << mid << " " << r << " " << cnt << "\n";
		if(cnt < m)
			r = mid;
		else
			l = mid;
	}	
	cout << ret - (cnt - m) * l;
	return 0;
}



Measured memory_bytes: 1792
/*                         _
                        _ooOoo_
                       o8888888o
                       88" . "88
                       (| -_- |)
                       O\  =  /O
                    ____/`---'\____
                  .'  \\|     |//  `.
                 /  \\|||  :  |||//  \
                /  _||||| -:- |||||_  \
                |   | \\\  -  /'| |   |
                | \_|  `\`---'//  |_/ |
                \  .-\__ `-. -'__/-.  /
              ___`. .'  /--.--\  `. .'___
           ."" '<  `.___\_<|>_/___.' _> \"".
          | | :  `- \`. ;`. _/; .'/ /  .' ; |
          \  \ `-.   \_\_`. _.'_/_/  -' _.' /
===========`-.`___`-.__\ \___  /__.-'_.'_.-'================

                  Please give me AC.
*/

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

using namespace std;

using int64 = long long;
using uint64 = unsigned long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;

int n;
int64 a[100100];
int64 b[100100];
int64 sub[100100];

int main(){
    cout << fixed << setprecision(15);

    cin >> n;
    rep(i, n) {
        cin >> a[i];
    }
    rep(i, n) {
        cin >> b[i];
    }

    int64 suma = accumulate(begin(a), begin(a) + n, 0LL);
    int64 sumb = accumulate(begin(b), begin(b) + n, 0LL);

    if(suma < sumb) {
        cout << "-1\n";
        return 0;
    }

    rep(i, n) {
        sub[i] = a[i] - b[i];
    }

    sort(begin(sub), begin(sub) + n);

    int64 ans = 0;
    int64 m = 0;
    rep(i, n) {
        if (sub[i] >= 0)
            break;
        m -= sub[i];
        ans++;
    }

    for (int i = n - 1; i >= 0 && m > 0; i--) {
        m -= sub[i];
        ans++;
    }

    cout << ans << '\n';

    return 0;
}



Measured memory_bytes: 2560
n = gets.to_i
sticks = gets.split.map(&:to_i)

answer = 0

sticks.combination(3).each do |a, b, c|
  next if [a, b, c].uniq.size != 3

  answer += 1 if (a + b) > c && (b + c) > a && (c + a) > b
end

puts answer


Measured memory_bytes: 14432
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i < n; i ++)
#define rep1(i, n) for (int i=1; i <= n; i ++)
#define _min(x, y) x = min(x, y)
#define _max(x, y) x = max(x, y)
using namespace std;


const int MOD = 1000000007;

// a^n mod を計算する
long long modpow(long long a, long long n) {
  long long res = 1;
  while (n > 0) {
    if (n & 1) {
      res = res * a % MOD;
    }
    a = a * a % MOD;
    n >>= 1;
  }
  return res;
}

long long modinv(long long a) {
  return modpow(a, MOD - 2);
}


int main() {
  int X, Y; cin >> X >> Y;
  if (X > Y) {
    int tmp = Y;
    Y = X;
    X = tmp;
  }
  int cnt = 0;
  while (X * 2 != Y && X > 0 && Y > 0 && X != Y * 2) {
    X -= 1;
    Y -= 2;
    cnt ++;
  }
  if (X > Y) {
    int tmp = Y;
    Y = X;
    X = tmp;
  }
  if (X * 2 != Y) {
    cout << 0 << endl;
    return 0;
  }
  long long ans = 1;
  rep1(i, X + cnt) {
    ans = ans * i % MOD;
  }
  rep1(i, X) {
    ans = ans * modinv(i) % MOD ;
  }
  rep1(i, cnt) {
    ans = ans * modinv(i) % MOD;
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>)
{
    val n = readInt()
    val d = readNInts().sorted()

    val lbound = d[n/2 - 1]
    val ubound = d[n/2]

    println(if (lbound == ubound) 0 else (ubound - lbound))
}


// Read an integer
// Usage: val a = readInt()
private fun readInt() = readLine()!!.toInt()

// Read N integers separated by " "
// Usage: val (a, b, c) = readNInts()
private fun readNInts() = readLine()!!.split(" ").map(String::toInt)

// Read a string
// Usage: val a = readString()
private fun readString() = readLine()!!


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


void solve(long long S, long long W){
    string status;
    if(S > W) status = "safe";
    else status = "unsafe";
    cout << status << endl;
    return;
}

int main(){
    long long S;
    scanf("%lld",&S);
    long long W;
    scanf("%lld",&W);
    solve(S, W);
    return 0;
}


Measured memory_bytes: 3696
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = (s); i < (n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==v.size()-1?']':','); return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

const int mod = 1000000007;
//const int mod = 998244353;
struct mint {
    ll x;
    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++() { return *this += mint(1); }
    mint& operator-=(const mint& a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; }
    mint& operator--() { return *this -= mint(1); }
    mint& operator*=(const mint& a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint& a) const { mint res(*this); return res+=a; }
    mint operator-(const mint& a) const { mint res(*this); return res-=a; }
    mint operator*(const mint& a) const { mint res(*this); return res*=a; }
    mint pow(ll t) const {
        mint res = mint(1),a(*this);
        while(t > 0) {
            if(t&1) res *= a;
            t >>= 1;
            a *= a;
        }
        return res;
    }
    // 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 { mint res(*this); return res/=a; }
};
ostream& operator<<(ostream& os,const mint& m) { return os << m.x; }

mint dp[25][1<<21];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    vvi a(n,vi(n));
    cin >> a;
    dp[0][0] = 1;
    rep(i,n) rep(bit,1<<n) {
        if(__builtin_popcount(bit) != i) continue;
        rep(j,n) {
            if(bit>>j&1) continue;
            if(!a[i][j]) continue;
            dp[i+1][bit|1<<j] += dp[i][bit];
        }
    }
    cout << dp[n][(1<<n)-1] << endl;
}


Measured memory_bytes: 409856
/*
    Problem 56
    https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_A
*/
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int V, E, st;
    cin >> V >> E >> st;

    vector<vector<pii>> G(V, vector<pii>());
    for (int i = 0; i < E; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(pii(v, w));
    }

    vector<int> p(V, -1), d(V, INF);
    d[st] = 0;
    // pq : pair<int, int> = first : -距離, second : 頂点
    priority_queue<pii> PQ;
    PQ.push(pii(0, st));
    while (!PQ.empty()) {
        pii f = PQ.top(); PQ.pop();
        int dist = (-1) * f.first;
        int v = f.second;

        if (d[v] < dist) continue;

        for (pii edge : G[v]) {
            int u = edge.first;
            int w = edge.second;
            if (d[u] > d[v] + w) {
                d[u] = d[v] + w;
                p[u] = v;
                PQ.push(pii((-1) * d[u], u));
            }
        }
    }

    for (int i = 0; i < V; i++) {
        if (d[i] == INF) cout << "INF";
        else cout << d[i];
        cout << '\n';
    }
}


Measured memory_bytes: 13424
#include <iostream>

using namespace std;

int main() {
    int n, t1, t2;

    cin >> n;

    t1 = n % 10;
    t2 = n / 10;

    if (t1 == 9 || t2 == 9) {
        cout << "Yes"
             << "\n";
    } else {
        cout << "No"
             << "\n";
    }
}

Measured memory_bytes: 256
N = int(input())
S = list(input())

c_b = 0
c_w = S.count('.')
sum = []

for i in S:
	if i == '.':
		c_w = c_w - 1
	sum.extend([c_b+c_w])
	if i == '#':
		c_b = c_b + 1

print(min(sum))


Measured memory_bytes: 12836
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

namespace Competitive
{
    internal class Solution
    {
        public int N, K;
        public long MOD = 1000000007;

        public void Run()
        {
            var line = Input.ReadIntArray();
            N = line[0];
            K = line[1];

            double ret = 0;

            for (int i = 1; i <= N; i++)
            {
                int x = i;
                double prob = 1.0 / N;

                while (x < K)
                {
                    x *= 2;
                    prob /= 2;
                }

                ret += prob;
            }

            Console.WriteLine(ret);
        }
    }

    // libs ----------
    

    // common ----------

    internal static class Input
    {
        public static string ReadString()
        {
            string line = Console.ReadLine();
            return line;
        }

        public static int ReadInt()
        {
            string line = Console.ReadLine();
            return int.Parse(line);
        }

        public static int[] ReadIntArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(int.Parse).ToArray();            
        }

        public static long ReadLong()
        {
            string line = Console.ReadLine();
            return long.Parse(line);
        }

        public static long[] ReadLongArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(long.Parse).ToArray();
        }

        public static double[] ReadDoubleArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(double.Parse).ToArray();
        }
    }
    
    internal class Program
    {
        public static void Main(string[] args)
        {
            var s = new Solution();
            s.Run();
        }
    }
}

Measured memory_bytes: 13268
#76b
N = int(input()) #
K = int(input()) #

#電光掲示板に整数 1 が表示されているのを見ました。
#彼は、電光掲示板に対して、以下の操作 A, 操作 B をすることができます。
#操作 A： 電光掲示板に表示する整数を「今の電光掲示板の整数を 2倍にしたもの」に変える。
#操作 B： 電光掲示板に表示する整数を「今の電光掲示板の整数に Kを足したもの」に変える。
#操作 A, 操作 B 合計で N回 行わなければなりません。 
#そのとき、N 回の操作後の、電光掲示板に書かれている整数として考えられる最小の値を求めなさい。
ans = 1

for i in range(N):
    if ans*2 <= ans+K:
        ans = ans*2
    else:
        ans += K
        
print(ans)

Measured memory_bytes: 2940
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#define int long long
#define ggr getchar();getchar();return 0;
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
int a[114514];
signed main() {
	int n, k;
	cin >> n >> k;
	rep(i, n)cin >> a[i];
	if ((n - k) % (k - 1) == 0)cout << 1 + (n - k) / (k - 1) << endl;
	else cout << 2 + (n - k) / (k - 1) << endl;
	ggr
}

Measured memory_bytes: 1024
import java.util.Scanner;

class Main{

	public static void main(String[] args) {


		Scanner scan = new Scanner(System.in);
		String N = scan.next();
		long M = scan.nextLong();

		int count = 0;
		int numone=0;
		while(count < N.length()){
			String first = N.substring(count,count+1);
			if(first.equals("1")){
				numone++;
			}else{
				break;
			}
			
			count++;
		}
		
		if(M <= numone){
			System.out.println("1");
		}	
		else{
			System.out.println(N.substring(count,count+1));
		}




	}



}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define pi (double)acos(-1)
using namespace std;
set<long long> s;
vector<int> v;

void solve()
{
    int n,k;
    cin>>n>>k;
    double p=0;
    for(int i=1;i<=n;++i)
    {
        if(i<=k-1)
            p+=pow(0.5,ceil(log(k*1.0/i)/log(2)));
        else
            p+=1;
    }
    cout<<fixed<<setprecision(15)<<p/n;

    return;
}
int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t=1;
	//cin>>t;
	while(t--) {solve();}
	return 0;
}


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

int main(void){
	int n;
	int *tokuten;
	int maxi=0,mini=1000;
	int goukei=0,cnt=0;
	int *heikin=new int[100];
	while(1){
		cin>>n;
		int i=0;
		if(n==0)
			break;

		tokuten=new int[n];
		maxi=0;
		mini=1000;
		for(i=0;i<n;i++){
			cin>>tokuten[i];
			maxi=max(maxi,tokuten[i]);
			mini=min(mini,tokuten[i]);
			goukei+=tokuten[i];
		}
		
		
		goukei=goukei-(mini+maxi);
		goukei=goukei/(n-2);
		heikin[cnt]=goukei;
		goukei=0;
		cnt++;
		delete[] tokuten;
		
	}
	for(int j=0;j<cnt;j++)
		cout<<heikin[j]<<endl;
	delete[] heikin;
	
	return 0;
}

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

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

    x=ceil(c/(b*1.0)) ;
    y=ceil(a/(d*1.0));

    if(x>y)
        cout<<"No"<<endl ;
    else
        cout<<"Yes"<<endl ;
return 0 ;
}


Measured memory_bytes: 3656
#include <vector>
#include <iostream>
#include <string>
using namespace std;
#define REP(i,x) for(int i=0;i<(int)(x);i++)
string n;

main(){
	while(cin >> n, n!="0"){
		int dp[2][11]={0};
		dp[1][0] = 1;
		int ans = 0, sum = 0;
		REP(i, n.size()){
			sum = (sum * 10 + n[i]-'0') % 11;
			ans += dp[i&1][(110-10*sum)%11];
			REP(j, 11) dp[i&1][(j*10)%11] = dp[1&i^1][j];
			if(i<n.size()-1 && n[i+1] != '0') dp[i&1][sum] ++;
		}
		cout << ans << endl;
	}
	return 0;
}

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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

template <typename T>
using V = std::vector<T>;
template <typename T>
using VV = V<V<T>>;

using namespace std;

int main() {
  in(ll, n);
  V<ll> a(n);
  rep(i, n) cin >> a[i];
  rep(i, n) a[i] -= i + 1;
  sort(all(a));
  ll ans = 0;
  rep(i, n) ans += abs(a[i] - a[n / 2]);
  if (n % 2 == 0) {
    ll sum = 0;
    rep(i, n) sum += abs(a[i] - a[n / 2 - 1]);
    ans = min(ans, sum);
  }
  out(ans);
}

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

int main() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    if (a>=k) {
        cout << k << endl;
        return 0;
    }
    else if (a+b>=k) {
        cout << a << endl;
        return 0;
    }
    else if (a+b+c>=k) {
        cout << a - (k - (a+b)) << endl;
    }

}

Measured memory_bytes: 3644
import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    h, w = ns()
    mat = [list(sys.stdin.readline()) for _ in range(h)]

    def bfs(x, y):
        arrived_mat = [[False for i in range(w)] for j in range(h)]

        que = queue.Queue()
        que.put((x, y, 1))
        arrived_mat[y][x] = True
        res = 0

        direc = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        while que.qsize() > 0:
            xi, yi, cnt = que.get()

            for dx, dy in direc:
                next_x = xi + dx
                next_y = yi + dy
                if -1 < next_x < w and -1 < next_y < h:
                    if mat[next_y][next_x] == "." and arrived_mat[next_y][next_x] != True:
                        que.put((next_x, next_y, cnt + 1))
                        arrived_mat[next_y][next_x] = True                        
                        res = max(res, cnt + 1)

        return res

    ans = 0
    for y in range(h):
        for x in range(w):
            if mat[y][x] == ".":
                ans = max(ans, bfs(x, y) - 1)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 51428
n = int(input())
a = sorted(map(int,input().split()))

c = [0] * 9
for num in a:
    if num < 400:
        c[0] += 1
    elif num < 800:
        c[1] += 1
    elif num < 1200:
        c[2] += 1
    elif num < 1600:
        c[3] += 1
    elif num < 2000:
        c[4] += 1
    elif num < 2400:
        c[5] += 1
    elif num < 2800:
        c[6] += 1
    elif num < 3200:
        c[7] += 1
    else:
        c[8] += 1
mi = 0
ma = 0
for i in range(8):
    if c[i] >= 1:
        mi += 1
        ma += 1
ma += c[8]
if mi == 0:
    if c[8] >= 1:
        mi += 1
print(str(mi) + " " + str(ma))



Measured memory_bytes: 9236