akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <string.h>

int main(void)
{
	char str[100][101], tmp[101];
	int N, L, i, j;
	
	scanf("%d %d", &N, &L);
	for(i = 0; i < N; i++) {
		scanf("%s", str[i]);
	}
	for(i = 0; i < N; i++) {
		for(j = i + 1; j < N; j++) {
			if(strcmp(str[i], str[j]) > 0) {
				strcpy(tmp, str[i]);
				strcpy(str[i], str[j]);
				strcpy(str[j], tmp);
			}
		}
		printf("%s", str[i]);
	}
	return 0;
}

Measured memory_bytes: 128
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    # import numpy as np
    # import math
    # import random
    input = stdin.readline

    n = int(input())
    aa = list(map(int, input().split()))

    left_leaves = sum(aa)
    ans = 0
    now = 1
    for i in range(n):
        ans += now
        num_of_node = now - aa[i]
        if num_of_node <= 0:
            print(-1)
            exit()
        max_next_node = num_of_node*2
        left_leaves -= aa[i]
        if max_next_node > left_leaves:
            now = left_leaves
        else:
            now = max_next_node
    ans += now
    if now-aa[-1] != 0:
        print(-1)
    else:
        print(ans)

    



Measured memory_bytes: 20120
/*
    ____        __
   / __ \____  / /_  ____ _____ ___
  / /_/ / __ \/ __ \/ __ `/ __ `__ \
 / _, _/ /_/ / / / / /_/ / / / / / /
/_/ |_|\____/_/ /_/\__,_/_/ /_/ /_/
*/
#include<bits/stdc++.h>

typedef long long ll ;

#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define vpii vector<pair<int , int>>
#define i_n   int i = 0 ; i< n ; i++
#define cn  int n ; cin>>n
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cina int a[n] ; for(int i = 0 ; i < n ; i++) cin>>a[i]
#define pb push_back
#define SZ(x) ll(x.size())

using namespace std;
const int maxn = 1000*100+5 ;

int main()
{
	migmig ;
	string s ; 
	cin>>s ; 
	int ans = 0 ; 
	 for(int i= 0 ; i < 4 ; i++)
	 {
	 	if(s[i] == '+') ans ++ ; 
	 	else ans-- ; 
	 }
	 cout<<ans ; 
}
//////
////////
///////////



Measured memory_bytes: 256
n = int(input())
A = [0] + list(map(int, input().split())) + [0]
b = [0]*(n+1)
d = [0]*(n+1)
c = 0
for i in range(n+1):
  t = A[i]-A[i+1]
  d[i] = abs(t)
  if t > 0:
    b[i] = 1
  elif t < 0:
    b[i] = -1
  else:
    b[i] = 0
  c += d[i]
for i in range(n):
  if b[i]*b[i+1] >= 0:
    print(c)
  else:
    print(c-2*min(d[i], d[i+1]))

Measured memory_bytes: 14172
{-# LANGUAGE BangPatterns #-}

import Control.Monad
import qualified Data.ByteString.Char8 as C
import Data.Int
import Data.List
import Data.Maybe
import qualified Data.Vector.Unboxed as V

main = sol <$> get >>= putStrLn

get = fmap (unfoldr (C.readInt . C.dropWhile (==' '))) . C.lines <$> C.getContents  

sol ([n,_]:es) = maybe "inf" (show . negate) $ bellman_ford n wes
  where
  wes = fmap (\[u,v,c] -> (u,v,fromIntegral (-c))) es :: [(Int, Int, Int64)]

bellman_ford n wes = if ok then Just $ d1 `V.unsafeIndex` n else Nothing
  where
  ev = V.fromList $ wes
  d0 = V.replicate (n+1) inf V.// [(1, 0)]
  d1 = iterate (f ev) d0 !! (n-1)
  d2 = iterate (f ev) d1 !! n
  ok = d1 `V.unsafeIndex` n == d2 `V.unsafeIndex` n

inf = 10^18 :: Int64

f ev !d = V.unsafeAccumulate min d $ V.map upd ev
  where
  upd (u, v, c) = (v, min dv $ du+c)
    where
    du = d `V.unsafeIndex` u
    dv = d `V.unsafeIndex` v

Measured memory_bytes: 4476
import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        while(true){
            int n=sc.nextInt();
            if(n==0){
                break;
            }
            int p[]=new int[10];
            for(int i=0;i<10;i++){
                p[i]=0;
            }
            for(int i=0;i<n;i++){
                int x=sc.nextInt();
                p[x]++;
            }
            for(int i=0;i<10;i++){
                if(p[i]==0){
                    System.out.println("-");
                }else{
                    for(int j=0;j<p[i];j++){
                        System.out.print("*");
                    }
                    System.out.println();
                }
            }
        }
    }
}


Measured memory_bytes: 61252
#include <bits/stdc++.h>
using namespace std;
using Graph=vector<vector<int>>;
typedef long long ll;

int main()
{
  int N;cin>>N;
  vector<int> d(N);
  for (int i=0;i<N;i++)
  {
    cin>>d[i]; 
  }
  int sum=0;
  for (int i=0;i<N-1;i++)
  {
    for (int j=i+1;j<N;j++)
    {
       sum += d[i]*d[j];
    }
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#include <utility>
#include <functional>
using namespace std;
//orz jzm
#define ll long long
#define ull unsigned ll
const ll PR=19260817;
const int N=5005;
bool f[N];
int a[N];
int n, k;
bool check(int x) {
	if (a[x]>=k)
		return true;
	memset(f, false, sizeof(f));
	f[0]=1;
	for (int i=0; i<n; i++) {
		if (i==x)
			continue;
		for (int j=k-a[i]-1; j>=0; j--) {
			if (f[j])
				f[j+a[i]]=true;
		}
	}
	for (int i=k-a[x]; i<k; i++)
		if (f[i])
			return true;
	return false;
}
int main() {
	scanf("%d%d", &n, &k);
	for (int i=0; i<n; i++)
		scanf("%d", &a[i]);
	sort(a, a+n);
	int lo, hi;
	lo=0;hi=n;
	while (lo<hi) {
		int mid=(lo+hi)>>1;
		if (check(mid))
			hi=mid;
		else
			lo=mid+1;
	}
	printf("%d\n", hi);
	return 0;
}

Measured memory_bytes: 256
n, d = list(map(int, input().split()))

xs = []
for _ in range(n):
    xs.append(list(map(int, input().split())))
ans = 0
for i in range(n):
    xi = xs[i]
    for j in range(i+1, n):
        xj = xs[j]
        dist = sum([(xid - xjd)**2 for (xid, xjd) in zip(xi, xj)]) ** 0.5
        if dist.is_integer():
            ans += 1
print(ans)


Measured memory_bytes: 3060
#include <stdio.h>

int main(void){
  int n, a[1000], i, v, j, k;

  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }

  for ( i = 0; i < n; i++) {
    if ( i < n - 1) {
      printf("%d ", a[i]);
    }
    else if ( i == n - 1) {
      printf("%d\n", a[i]);
    }
  }

  for (i = 1; i < n; i++) {
    v = a[i];
    j = i - 1;
    while ( j >= 0 && a[j] > v) {
      a[j+1] = a[j];
      j--;
    }
    a[j+1] = v;

    for ( k = 0; k < n; k++) {
      if ( k < n - 1) {
        printf("%d ", a[k]);
      }
      else if ( k == n - 1) {
        printf("%d\n", a[k]);
      }
    }

  }

  return 0;
}


Measured memory_bytes: 2056
// https://beta.atcoder.jp/contests/abc063

#include <bits/stdc++.h>
using namespace std;

int s[100];
int N;

int main() {
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> s[i];

    sort(s, s + N);
    auto sum = accumulate(s, s + N, 0);
    if (sum % 10 != 0) {
        cout << sum << endl;
        exit(0);
    }

    int first_not_10x_index = 0;
    while (first_not_10x_index != N && s[first_not_10x_index] % 10 == 0) first_not_10x_index++;

    auto ans = (first_not_10x_index == N) ? 0 : sum - s[first_not_10x_index];
    cout << ans << endl;
    return 0;
}

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

int main(void){
	long long int p, i, j; cin >> p;
	vector<int> a(p);
	for(i = 0; i < p; i++) cin >> a[i];

	vector<long long int> ans(p);
	vector<long long int> gya(p);
	gya[0] = 1;

	for(i = 1; i < p; i++) {
		long long int now = 1;
		for(j = 0; j < p - 2; j++) {
            now *= i;
            now %= p;
        }
		gya[i] = now;
	}
	for(i = 0; i < p; i++) {
		ans[0] += a[i];
		long long int now = p - a[i];
		for(j = p - 1; j >= 0; j--){
			ans[j] += now;
            ans[j] %= p;
			now *= (p-i) * j * gya[p-j];
            now %= p;
		}
	}
	for(i = 0; i < p; i++){
        cout << ans[i] %p << " ";
    }
	cout << endl;

	return 0;
}


Measured memory_bytes: 384
def dfs(str):
    global AGC
    if len(str)==3:
        AGC.append(str)
    else:
        dfs(str+'A')
        dfs(str+'G')
        dfs(str+'C')
        dfs(str+'T')


moji=['A','G','C','T']
AGC=[]
dfs('')
ban=[]
for str in moji:
    ban.append(str+'AGC')
    ban.append(str+'ACG')
    ban.append(str+'GAC')
    ban.append('AGC'+str)
    ban.append('ACG'+str)
    ban.append('GAC'+str)
    ban.append('AG'+str+'C')
    ban.append('A'+str+'GC')

ban=list(set(ban))

N=int(input())
mod=10**9+7
dp=[{key:0 for key in AGC} for i in range(0,N+1)]
for key in AGC:
    if key!='AGC' and key!='ACG' and key!='GAC':
        dp[3][key]=1

for i in range(3,N):
    for key in AGC:
        ans=0
        for str in moji:
            if not key+str in ban:
                dp[i+1][key[1:]+str]+=dp[i][key]

print(sum(dp[N][key] for key in AGC)%mod)

Measured memory_bytes: 41200
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
#define INF 2e9
#define INFLL 4e18
using namespace std;
ll powmod(ll base,ll exponent,ll mod){ // with mod < 1e9
	ll ans=1;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int upperlimit = 1e6+1;
const int mod = 1e9+7;
int main() {
	bool c=false;
	string s;
	cin >> s;
	for(int i = 0; i < 3; i++) if(s[i]==s[i+1]) c=true;
	if(c) cout << "Bad";
	else cout << "Good";
	return 0;
}

Measured memory_bytes: 256
sx, sy, tx, ty=map(int,input().split())

hrz=tx-sx
vrt=ty-sy

a="U"*vrt
b="R"*hrz
c="D"*vrt
d="L"*hrz
ans1=a+b+c+d
a2=a+"U"
b2=b+"R"
c2=c+"D"
d2=d+"L"
ans2="L"+a2+b2+"DR"+c2+d2+"U"
print(ans1+ans2)

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

#define nax 100009
#define FOR(i,n,m) for(int i =(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define pb push_back

typedef long long ll;

int main(){
	ll dp[nax];
	int n,k;
	ll h[nax];
	cin>>n;
	k=2;
	REP(i,n) cin>>h[i];

	//dp: min costo para llegar a i
	REP(i,nax) dp[i] = 1000000000000LL;
	dp[0] = 0;
	REP(i,n){
		FOR(j,i+1,min(i+k+1,n)){
			if(dp[i]+abs(h[i]-h[j])<dp[j])
				dp[j] = dp[i]+abs(h[i]-h[j]);
		}
	}

	cout<<dp[n-1];

	return 0;
}

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

using namespace std;

int main(){
  string a, b, c;

  cin >> a >> b >> c;

  for (int i = 0; i < 3; i++){
    if (i == 0){
      cout << a.at(i);
    }
    if (i == 1){
      cout << b.at(i);
    }
    if (i == 2){
      cout << c.at(i) << endl;
    }
  }
}


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

int main(){
  string s, t;
  cin>>s >>t;
  
  int n = s.size(), ans = 0;
  
  for(int i=0;i<n;i++){
    if(s[i] != t[i]){
      ans++;
    }
  }
  
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3868
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

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

  int N=in(),M=in();
  vector<int> s(M,0);
  REP(i,N){
    int K=in();
    REP(j,K){
      int v=in();
      s[v-1]++;
    }
  }
  
  cout << count(ALL(s),N) << endl;
  return 0;
}


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

int main() {
  int h,w;
  cin >>h>>w;
  int count=0;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      char a;
      cin>>a;
      if(a=='#')count++;
    }
  }
  if(count==h+w-1){
    cout<<"Possible"<<endl;
  }else{
    cout<<"Impossible"<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, k, n) for(int i = (k); i < (n); i++)
#define FORr(i, k, n) for(int i = (k); i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORr(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;
using ll = long long;

const int INF = 1001001001;
const int mod = 1000000007;

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

  vector<int> h(n);
  REP(i, n) cin >> h[i];

  vector<int> dp(n, INF);
  dp[0] = 0;

  REP(i, n){
    FOR(j, 1, k+1){
      if(i+j >= n) break;
      chmin(dp[i+j], dp[i] + abs(h[i] - h[i+j]));
    }
  }
  cout << dp[n-1] << endl;
  return 0;
}

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

int main() {
    int n; cin >> n;
    
    vector<int> v(n, 0);
    vector<int> w(n, 0);

    for(int i = 0; i < n; ++i) {
        cin >> v[i];
        w[i] = v[i];
        v[i] -= i + 1;
    }

    sort(v.begin(), v.end());
    int b = v[n / 2];
        
    int64_t ans = 0;

    for(int i = 0; i < n; ++i) {
        ans += abs(w[i] - (b + i + 1));
    }

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

Measured memory_bytes: 1792
using System.Linq;
using System;
using System.IO;

class Program
{
  static void Main(string[] args) =>
    new Program().solve();

  private void solve()
  {
    var seq = Console.ReadLine().Split(' ')
      .Select(int.Parse).ToArray();
    var a = seq[0];
    var b = seq[1];
    
    var ans = Enumerable.Range(a, b - a + 1)
      .Aggregate(0, (acc, i) =>
        i == reverse(acc:0, n:i) ? acc + 1 : acc);

    Console.WriteLine(ans);
  }

  private int reverse(int acc, int n)
  {
    if(n == 0) return acc;
    else return reverse(acc * 10 + (n % 10), n / 10);
  }
}

Measured memory_bytes: 13396
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#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<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return vector<decltype(val)>(n, move(val));
}
const int INF = 1e9;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 200005;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int d,g,a,b,c,cnt,ok,m;
    cin >> d >> g;
    vector<int> s(d),p(d);
    rep(i,d){
        cin >> a >> b;
        p[i] = a;
        s[i] = (i+1)*100*a+b;
    }
    m = INF;
    rep(i,(1<<d)){
        c = 0;
        cnt = 0;
        ok = 0;
        rep(j,d){
            if (i&(1<<j)){
                c += s[j];
                cnt += p[j];
            }
        }
        c = g-c;
        if (c <= 0){
            chmin(m,cnt);
            continue;
        }
        for(int j = d-1;j >= 0;j--){
            if (!(i&(1<<j)) && c <= p[j]*100*(j+1)){
                chmin(m,cnt+(c-1)/((j+1)*100)+1);
                break;
            } 
        }
    }
    PRINT(m);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
int main()
{
	SPEED
	int a, b, ans = 0, current = 1;
	cin >> a >> b;
	while(current<b)
	{
		current--;
		current+=a;
		ans++;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#abc112_a

AGE_1 = 1
AGE_2 = 2

def main():
    a = int(input(""))
    if a == AGE_1:
        print ("Hello World")
    elif AGE_2:
        A = int(input(""))
        B = int(input(""))
        output = A + B
        print ("{}".format(str(output)))

if __name__ == "__main__": main()


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

using namespace std;
int pow(int a, int b)
{
 	int c=a;
  for(int i=1; i<b; i++)
  {
   	c*=a; 
  }
  return c;
}
int main()
{
 	int n;
  cin>>n;
  cout<<pow(n,3)<<endl;
  return 0;
}

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

using namespace std;
typedef long long ll;
#define debug(x) cerr << x << "\n"
#define all(x) (x).begin(),(x).end()
#define exist(s, e)((s).find(e) != (s).end())

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string a, b;
    size_t i;
    cin >> a >> b;
    if (a.size() < b.size()) cout << "LESS\n";
    else if (a.size() > b.size()) cout << "GREATER\n";
    else {
        for (i = 0;i<a.size() && a[i] == b[i];i++);
        if (i == a.size()) cout << "EQUAL\n";
        else if (a[i] < b[i]) cout << "LESS\n";
        else cout << "GREATER\n";
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<stack>
#include<cstdlib>
using namespace std;

int main(){
  string s;
  stack <int> t;
  int a,b;

  while(cin>>s){
    if(s=="+"){
      b=t.top();t.pop();
      a=t.top();t.pop();
      a=a+b;t.push(a);
   }
    else if(s=="-"){
      b=t.top();t.pop();
      a=t.top();t.pop();
      a=a-b;t.push(a);
  }
    else if(s=="*"){
      b=t.top();t.pop();
      a=t.top();t.pop();
      a=a*b;t.push(a);
    }
    else{
      t.push(atoi(s.c_str()));
    }
  }
  cout<<t.top()<<endl;
  return 0;
}

Measured memory_bytes: 1204
#include <vector>
#include <iostream>

using namespace std;

const int kSize = 200000;

struct Node {
    char c;
    int num;

    Node(char _c, int _num) {
        c = _c;
        num = _num;
    }

    Node(){

    };
};

void BubbleSort(Node A[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        for (int j = n - 1; j >= i + 1; --j) {
            if (A[j].num < A[j - 1].num) {
                swap(A[j], A[j - 1]);
            }
        }
    }
}

void SelectionSort(Node A[], int n) {
    for (int i = 0; i < n; ++i) {
        int min_index = i;
        for (int j = i; j < n; ++j) {
            {
                if (A[j].num < A[min_index].num) {
                    min_index = j;
                }
            }
        }

        swap(A[min_index], A[i]);
    }
}

void Print(Node A[], int n) {
    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            cout << " ";
        }
        cout << A[i].c << A[i].num;
    }

    cout << endl;
}

int main() {
    Node A[kSize];
    Node B[kSize];
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        char c;
        int num;
        cin >> c >> num;
        A[i].c = c;
        A[i].num = num;
        B[i].c = c;
        B[i].num = num;
    }

    BubbleSort(A, n);
    SelectionSort(B, n);
    Print(A, n);
    cout << "Stable" << endl;
    Print(B, n);
    for (int i = 0; i < n; ++i) {
        if (A[i].c != B[i].c) {
            cout << "Not stable" << endl;
            return 0;
        }
    }

    cout << "Stable" << endl;
    return 0;
}


Measured memory_bytes: 3100
//I didn't solve this by my own
#include <iostream>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b){

	while(b>0){
	
		a%=b;
		ll c=a;
		a=b;
		b=c;
	}
	return a;
}
int main(){

	int k;
	cin>>k;
	if(k%7==0){
	
		k/=7;
	}
	if(gcd(k,10)!=1){
	
		cout<<-1<<"\n";
		return 0;
	}
	ll v=1%k;
	ll ans=1;
	while(v!=0){
	
		v=(v*10+1)%k;
		ans++;
	}
	cout<<ans<<"\n";
	return 0;
}


Measured memory_bytes: 3636
# define _CRT_SECUREj_NO_WARNINGS 1
# define _USE_MATH_DEFINES
# include <iostream>
# include <numeric>
# include <string>
# include <bitset>
# include <vector>
# include <algorithm>
# include <cstdlib>
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iomanip>
# include <queue>
# include <sstream>
# include <climits>
# include <cmath>
# include <list>
# include <functional>
# include <string>
# include <ctime>
# include <set>
# include <forward_list>
# include <map>
# include <stack>
using namespace std;
# define INF ((int)(1<<25))
# define REP(i,n) for(int i=0;i<(int)n;i++)
# define FOR(i,n) REP(i,n)
# define TORAD 2.0*M_PI/360.0
# define INT(x) int x;cin>>x;
# define ALL(x) (x).begin(),(x).end()
# define RALL(x) (x).rbegin(),(x).rend()
# define DEBUG(x) cout<<#x<<" :"<<x<<endl;
# define EPS 1e-12
template<class T> void debug(T a) { for (auto iiiiiiiiii : a)cout << iiiiiiiiii << endl; }
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
int dx[4] = { 0,1,0,-1 }, dy[4] = { -1,0,1,0 };

#define int long long
signed main()
{
	int d[] = { 0,6000,4000,3000,2000 };
	FOR(i, 4)
	{
		int t, n; cin >> t >> n;
		cout << d[t] * n << endl;;
	}
}

Measured memory_bytes: 3120
use std::cmp;
use std::fmt::Debug;
use std::str::FromStr;
#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where
    T: FromStr,
    <T as FromStr>::Err: Debug,
{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim()
        .split_whitespace()
        .map(|c| T::from_str(c).unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_as_string() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main() {
    let n: usize = read_as_vec()[0];
    let mut uppers: Vec<usize> = vec![];
    let mut lowers: Vec<usize> = vec![];
    for _ in 0..n {
        let line = read_as_vec::<usize>();
        uppers.push(line[1]);
        lowers.push(line[0]);
    }

    uppers.sort();
    lowers.sort();
    dbg!(&uppers);
    if n % 2 == 1 {
        println!("{}", uppers[(n - 1) / 2] - lowers[(n - 1) / 2] + 1);
    } else {
        println!(
            "{}",
            uppers[(n - 1) / 2] + uppers[(n - 1) / 2 + 1]
                - (lowers[(n - 1) / 2] + lowers[(n - 1) / 2 + 1])
                + 1
        );
    }
}


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

#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
typedef pair<int,int> P;

//-----------------------------------------------------------------------

const int SZ=1005;
int l[SZ],r[SZ];
string name[SZ];

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

    int n,q;
    while(cin>>n>>q,n)
    {
        REP(i,n){
            int a;
            cin>>name[i]>>a>>r[i];
            l[i]=r[i]-a;
        }
        while(q--){
            int year; cin>>year;
            REP(i,n){
                if(l[i]<year && year<=r[i]){
                    cout<<name[i]<<" "<<year-l[i]<<endl;
                    goto g;
                }
            }
            cout<<"Unknown"<<endl;
        g:;
        }
    }       
} 


Measured memory_bytes: 3332
w,h,n = map(int,input().split())
arr = []
base_x = 0
base_y = 0
for i in range(n):
    arr.append(list(map(int,input().split())))
    x = arr[i][0]
    y = arr[i][1]
    num = arr[i][2]
    if num == 1:
        base_x = max(base_x,x)
    elif num == 2:
        w = min(w,x)
    elif num == 3:
        base_y = max(base_y,y)
    elif num == 4:
        h = min(h,y)
w2 = w - base_x
h2 = h - base_y
if base_x >= w or base_y >= h:
    print("0")
else:
    print(w2 * h2)

Measured memory_bytes: 3064
from collections import deque
def main():
  a,b=map(int,input().split())
  e=[[]for i in range(a)]

  for i in range(a-1):
    c1,c2=map(int,input().split())
    e[c1-1].append(c2-1)
    e[c2-1].append(c1-1)

  g=[[]for i in range(a)]
  f=deque()
  f.append((0,-1))
  ans=[0 for _ in range(a)]
  for i in range(b):
    ten,p=map(int,input().split())
    ans[ten-1]+=p
  i=0
  while len(f)!=0:
    i,fr=f.popleft()
    for j in e[i]:
      if j==fr:
        continue
      else:
        ans[j]+=ans[i]
        f.append([j,i]) 
  print(*ans)
  
main()
    
  

  
  


Measured memory_bytes: 79548
//In the Name of God
//Ya Ali

#include<bits/stdc++.h>

#define int long long

#define pb push_back
#define ld long double

#define err(A) cout<<#A<<" = "<<(A)<<endl

using namespace std;

const int maxn=131072;

int n;

int32_t main()
{
  ios::sync_with_stdio(0);cin.tie(0);
  
  cin>>n;

  int ans=0;
  while(cin>>n)
    (ans+=n)%=2;

  if(ans)
    cout<<"NO"<<endl;
  else
    cout<<"YES"<<endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
int inf=1000001000;
ll INF=100000000000000000;


int main() {
    while(true){
        int n;
        cin >> n;
        if (n==0) break;
        int m1;
        cin >> m1;
        int x1,y1;
        cin >> x1 >> y1;
        vector<pp> b(m1-1),bb(m1-1);
        int ty;
        vector<pp> z(m1-1);
        z[m1-2]=mk(x1,y1);
        int x3,y3;
        rep(i,m1-1){
            int x,y;
            cin >> x >> y;
            if (i==m1-2) {x3=x;y3=y;}
            else z[m1-3-i]=mk(x,y);
            x=x-x1;y=y-y1;
            if (i==0){
                if (x>0) ty=0;
                if (x<0) ty=1;
                if (y>0) ty=2;
                if (y<0) ty=3;
            }
            if (ty==1){
                x*=-1;
                y*=-1;
            }
            if (ty==2){
                swap(x,y);
                y*=-1;
            }
            if (ty==3){
                swap(x,y);
                x*=-1;
            }
            b[i]=mk(x,y);
        }
        rep(i,m1-1){
            int x,y;
            x=z[i].first-x3;y=z[i].second-y3;
            if (i==0){
                if (x>0) ty=0;
                if (x<0) ty=1;
                if (y>0) ty=2;
                if (y<0) ty=3;
            }
            if (ty==1){
                x*=-1;
                y*=-1;
            }
            if (ty==2){
                swap(x,y);
                y*=-1;
            }
            if (ty==3){
                swap(x,y);
                x*=-1;
            }
            bb[i]=mk(x,y);
        }
        rep(h,n){
        int m2;
        cin >> m2;
        bool t=true,tt=true;
        if (m2!=m1) {t=false;tt=false;}
        int x2,y2;
        cin >> x2 >> y2;
        int tyy;
        rep(i,m2-1){
            int x,y;
            cin >> x >> y;
            x=x-x2;y=y-y2;
            if (i==0){
                if (x>0) tyy=0;
                if (x<0) tyy=1;
                if (y>0) tyy=2;
                if (y<0) tyy=3;
            }
            if (tyy==1){
                x*=-1;
                y*=-1;
            }
            if (tyy==2){
                swap(x,y);
                y*=-1;
            }
            if (tyy==3){
                swap(x,y);
                x*=-1;
            }
            if (b[i]!=mk(x,y)) t=false;
            if (bb[i]!=mk(x,y)) tt=false;
        }
        if (t || tt) {cout << h+1 << endl;}
    }
    cout << "+++++" << endl;
}}




Measured memory_bytes: 3072
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;
 
signed main() {
    int N; cin >> N;
    cout << 180 * (N - 2) << endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
for i in range(1,100000):
  if n == i*(i+1)//2:
    k = i+1
    break
else:
  print("No")
  exit()
print("Yes")
print(k)
a = [[] for i in range(k)]
moto = list(range(1,n+1))
moto = moto[::-1]
for i in range(k):
  for j in range(i):
    a[i].append(a[j][i-1])
  while len(a[i]) != k-1:
    a[i].append(moto.pop())
for i in a:
  print(k-1,*i)

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

#define int long long
#define itn int
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL << (n))
constexpr int MOD = 1e9 + 7;

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = LLONG_MAX / 2;
using P = pair<int, int>;
using vec = vector<int>;
template <typename T>
using mat = vector<vector<T>>;

// clang-format off
template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) { return stream << p.first << " " << p.second; }
template <typename T>
void print(const vector<T> vec) { rep (i, vec.size() - 1) cout << vec[i] << ' '; cout << vec[vec.size() - 1] << '\n'; }
template <typename Arg>
void print(const Arg arg) { cout << arg << '\n'; }
template <typename Head, typename... Args>
void print(const Head head, const Args... args) { cout << head << " "; print(args...); }
template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) { rep (i, v.size()) cin >> v[i] >> w[i]; }
template <typename T>
void init(vector<T>& v) { rep (i, v.size()) cin >> v[i]; }
template <typename T>
T sum_(vector<T> vec, T init = 0) { return std::accumulate(all(vec), T(init)); }
template<typename T>
bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template<typename T>
bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <typename T>
int index(const T& vec, const typename T::iterator it) { return distance(vec.begin(), it); }
template <typename T = int>
mat<T> mmat(int n, int m=0) { return mat<T>(n, vector<T>(m)); }
template <typename T = int>
vector<T> ivec(int n) { vector<T> v(n); init(v); return v; }
// clang-format on

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// -------------------------------------------------------------------
// sort 1 2 3 4
// pqr 1 2 3 must impl >

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    int thre = (n - 1) * (n - 2) / 2;
    if (k > thre) {
        print(-1);
        return 0;
    }
    vector<P> buf;
    For(i, 2, n) buf.pb({1, i});
    int time = thre - k;

    For(i, 2, n) {
        bool out = false;
        For(j, i + 1, n) {
            if (time == 0) {
                out = true;
                break;
            }
            buf.pb({i, j});
            time--;
        }
        if (time == 0) out = true;
        if (out) break;
    }
    print(buf.size());
    repall (e, buf)
        print(e);

    return 0;
}


Measured memory_bytes: 512
N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [min(i/2,(T-i)/2) for i in range(T+1)]
ts = 0
te = 0
for i in range(N):
    te += t[i]*2
    for j in range(T+1):
        vt[j] = min(vt[j],v[i]+max(0,-(j-ts)/2,(j-te)/2))
    ts = te
print(sum(vt)/2)

Measured memory_bytes: 51420
import numpy as np
n, y = np.array(list(input().split()), dtype=int)

vals = np.array([10000, 5000, 1000])

table = []
for c in range(n + 1):
    part = np.zeros((n + 1 - c, 3), dtype=int)
    part[:, 0] = c
    part[:, 1] = np.arange(n + 1 - c)
    table += [part]
table = np.concatenate(table)
table[:, 2] = n - table[:, 0:2].sum(axis=1)

accum = (table * vals).sum(axis=1)
flags = np.where(accum == y)[0]

if len(flags) == 0:
    print("-1 -1 -1")
else:
    nums = table[flags[0]]
    print("{} {} {}".format(*nums))

Measured memory_bytes: 152616
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

int n, m, c, s, g;
int G1[25][105][105];
int p[25], q[25][55], r[25][55];
int G2[105][105];

void init() {
  rep(i, 25) rep(j, 105) rep(k, 105) G1[i][j][k] = inf;
  rep(i, 25) rep(j, 105) G1[i][j][j] = 0;
  memset(p, 0, sizeof(p));
  memset(q, 0, sizeof(q));
  memset(r, 0, sizeof(r));
  rep(i, 105) rep(j, 105) G2[i][j] = inf;
  rep(i, 105) G2[i][i] = 0;
}

void solve() {
  rep(l, c) {
    rep(k, n) {
      rep(i, n) {
        rep(j, n) {
          chmin(G1[l][i][j], G1[l][i][k] + G1[l][k][j]);
        }
      }
    }
    vector<int> cost(40001, 0);
    int res = 0, idx = 0;
    FOR(i, 1, 40001) {
      res += r[l][idx];
      cost[i] = res;
      if (i == q[l][idx + 1]) idx++;
    }
    rep(i, n) {
      rep(j, n) {
        if (G1[l][i][j] == inf) continue;
        chmin(G2[i][j], cost[G1[l][i][j]]);
      }
    }
  }
  rep(k, n) {
    rep(i, n) {
      rep(j, n) {
        chmin(G2[i][j], G2[i][k] + G2[k][j]);
      }
    }
  }
  cout << (G2[s][g] == inf ? -1 : G2[s][g]) << '\n';
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(25);

  while (cin >> n >> m >> c >> s >> g, n || m || c || s || g) {
    init();
    s--, g--;
    rep(i, m) {
      int x, y, d, c;
      cin >> x >> y >> d >> c;
      x--, y--, c--;
      chmin(G1[c][x][y], d);
      chmin(G1[c][y][x], d);
    }
    rep(i, c) cin >> p[i];
    rep(i, c) {
      FOR(j, 1, p[i]) cin >> q[i][j];
      rep(j, p[i]) cin >> r[i][j];
    }
    solve();
  }

  




  
  return 0;
}


Measured memory_bytes: 4420
#!/usr/bin/env python3

s = str(int(input()))
k = int(input())


for i in range(k):
    if s[i] != "1":
        print(s[i])
        exit()

print(s[i])

# if s[0] == "1":
#     if k == 1:
#         print(1)
#     else:
#         print(s[1])
# else:
#     print(s[0])


Measured memory_bytes: 9108
N = int(input())
l = {}
for i in range(N):
  s = input()
  s = ''.join(sorted(s))
  if s in l:
    l[s] += 1
  else:
    l[s] = 0
ans = 0
value_l = [1]
for value in l.values():
  if value == 0:
    continue
  if len(value_l) >= value:
    tmp = value_l[value - 1]
  else:
    l_val = len(value_l)
    for i in range(l_val, value):
      value_l.append(value_l[i-1] + i + 1)
    tmp = value_l[value - 1]
  ans += tmp

print(ans)


Measured memory_bytes: 17808
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define MOD 1000000007

map<pair<long long, long long>, long long> dp;
long long func(long long S, long long X){
    if(dp.count(make_pair(S, X))) return dp[make_pair(S, X)];
    long long &r = dp[make_pair(S, X)];
    if(S == 0){
        r = 1;
        return 1;
    }
    if(X == 0){
        int i = 0;
        while(S != 0){
            S >>= 1;
            i++;
        }
        r = i;
        return i;
    }

    long long d = func(S/2, X/2);
    if(S>=1&&X>=1)
        d = (d+func((S-1)/2, (X-1)/2))%MOD;
    if(S>=2)
        d = (d+func((S-2)/2, X/2))%MOD;
    r = d;
    return d;
}

int main(){
    long long N;
    cin >> N;
    cout << func(N, N) << endl;
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#include <map>

using namespace std;

#define MOD 1000000007
#define INF 2147483647
#define ll long long

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

	int res = 0;
	for (int i = 0; i < n; i++) {
		int l, r;
		cin >> l >>  r;
		res += r - l + 1;
	}
	cout << res << endl;

	return (0);
}

Measured memory_bytes: 256
N = int(input())
s = input()
t = input()
l = 2*N
kouho = []

for i in range(N):
    ns = s[i:]
    res = 0
    for j, k in zip(ns, t):
        if j == k:
            res += 1
        else:
            break
    kouho.append(res)

print(l - max(kouho))


Measured memory_bytes: 38640
#include <cmath>
#include <cstdio>
#include <iostream>
int main(){
	double x0,y0,x1,y1,x, y, s = 0;
	char c;
	std::cin >> x0 >> c >> y0;
	x1 = x0; y1 = y0;
	while(std::cin>>x>>c>>y){
		s += x1*y - y1*x;
		x1 = x;
		y1 = y;
	}
	s += x1*y0 - y1*x0;
		printf("%.6f\n", fabs(s / 2));

}

Measured memory_bytes: 1240
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    int w,a,b,a2,b2,s;
    while(scanf("%d%d%d",&w,&a,&b)!=EOF)
    {
        a2=a+w;
        b2=b+w;
        if (b>a2) s=b-a2;
        else if (b<=a2&&b>=a) s=0;
        else if (b2<=a2&&b2>=a) s=0;
        else if (b2<a) s=a-b2;
        printf("%d\n",s);
    }
    return 0;
}

Measured memory_bytes: 128
use std::io;
fn main() {
    let mut bufs = String::new();
    let mut buft = String::new();
    io::stdin().read_line(&mut bufs).unwrap();
    io::stdin().read_line(&mut buft).unwrap();
    let mut iter1 = bufs.char_indices();
    let mut iter2 = buft.char_indices();
    let mut ans = 0i32;
    while let Some(v) = iter1.next() {
        if let Some(k) = iter2.next() {
            if k == v {
                ans += 1;
            }
        }
    }
    ans -=1;
    println!("{}", ans)
}


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

int main(){
    string root;
    int sx, sy, tx, ty;
    int dx, dy;
    int i, j;

    cin >> sx >> sy >> tx >> ty;

    dx = tx - sx;
    dy = ty - sy;

    //root = NULL;
    //root = '\0';

    root = 'R';

    for (i=1; i<dx; i++){
        root = root + 'R';
    }
    for (i=0; i<dy; i++) {
        root = root + 'U';
    }
    for (i=0; i<dx; i++){
        root = root + 'L';
    }
    for (i=0; i<dy; i++) {
        root = root + 'D';
    }

    root = root +'L';
    for (i=0; i<dy+1; i++) {
        root = root + 'U';
    }
    for (i=0; i<dx+1; i++){
        root = root + 'R';
    }
    root = root +'D';

    root = root +'R';
    for (i=0; i<dy+1; i++) {
        root = root + 'D';
    }
    for (i=0; i<dx+1; i++){
        root = root + 'L';
    }
    root = root +'U';


    
    cout << root << endl;

}

Measured memory_bytes: 3748
#include<cstdio>
#include<algorithm>

using namespace std;

int n;
long long k;
long long a[200005];

long long rndup(long long x, long long y) { // y != 0
  if (x % y == 0) {
    return x / y;
  } else if (x < 0 && y < 0) {
    return -x / -y + 1;
  } else if (x > 0 && y > 0) {
    return x / y + 1;
  } else if (x > 0 && y < 0) {
    return -(x / -y);
  } else {
    return -(-x / y);
  }
}

long long rnddown(long long x, long long y) { // y != 0
  if (x % y == 0) {
    return x / y;
  } else if (x < 0 && y < 0) {
    return -x / -y;
  } else if (x > 0 && y > 0) {
    return x / y;
  } else if (x > 0 && y < 0) {
    return -(x / -y) - 1;
  } else {
    return -(-x / y) - 1;
  }
}

long long cnt(long long x) {
  long long y = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] > 0) {
      y += lower_bound(a, a + i, rndup(x, a[i])) - a;
    } else if (a[i] < 0) {
      y += a + i - upper_bound(a, a + i, rnddown(x, a[i]));
    } else {
      if (x <= 0) {
        y += 0;
      } else {
        y += i;
      }
    }
  }
  return y;
}

#ifdef DEBUG
long long cnt2(long long x, vector<long long>& wtf) {
  long long y = 0;
  for (auto ha: wtf) {
    if (ha < x) {
      y++;
    }
  }
  return y;
}
#endif

int main() {
  scanf("%d %lld", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%lld", &a[i]);
  }
  sort(a, a + n);
  long long lo = -2e18;
  long long hi = 2e18;
  while (lo + 1 < hi) {
    long long mi = (lo + hi) / 2;
    if (cnt(mi) >= k) {
      hi = mi;
    } else {
      lo = mi;
    }
  }
  printf("%lld\n", lo);
}


Measured memory_bytes: 1664
fun main(args: Array<String>) {
    val (a, b, m) = readIntegerList()
    val aList = readIntegerList()
    val bList = readIntegerList()
    val couponArray = Array(m) { readIntegerList() }

    val minA = aList.min()!!
    val minB = bList.min()!!
    val minNoC = minA + minB

    var min = Int.MAX_VALUE
    for (c in couponArray) {
        val tmp = aList[c[0] - 1] + bList[c[1] - 1] - c[2]
        min = Math.min(tmp, min)
    }

    println(Math.min(min, minNoC))
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)


Measured memory_bytes: 108768
#include <stdio.h>

int main(void)
{
	int N,x=0,max=0,i;
	scanf("%d",&N);
	char S[N];
	scanf("%s",S);

	for(i=0;i<N;i++)
		if(S[i]=='I'){
			x++;
			if(x>max)
				max=x;
		}else
			x--;

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

	return 0;
}

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

int main(){

    int n;
    int ans=1;
    string s;
    cin>>n>>s;

    for(int i=0;i<n-1;i++){
        if(s[i]!=s[i+1]) ans++;
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 512
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction


def get_max(a, b, theta):
    kari = b * math.tan(math.radians(90 - theta))
    if kari > a:
        S = (a * b) - (a * (a * math.tan(math.radians(theta))) / 2)
    else:
        S = (kari * b) / 2
    max_water = S * a
    return max_water




def main():
    a, b, x = map(int, input().split())
    left, right = 0, 90

    for i in range(10000):
        half = (left + right) / 2
        max_water = get_max(a, b, half)
        if max_water >=x:
            left = half
        else:
            right = half

    print(left)





if __name__ == '__main__':
    main()



Measured memory_bytes: 63084
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N; cin >> N;
    string S; cin >> S;
    vector<vector<int>> G(N);
    for (int i = 0; i < N - 1; i++) {
        int a, b; cin >> a >> b; a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    vector<int> ns(N), mas(N), mis(N);
    auto recur = [&](auto& recur, int node, int prev) -> void {
        int n = 0, ma = 0, mi = 0;
        for (int next : G[node]) if (next != prev) {
            recur(recur, next, node);
            n += ns[next];
            ma += mas[next];
        }
        for (int next : G[node]) if (next != prev) {
            int ans = mis[next] + ns[next] - (ma + n - mas[next] - ns[next]);
            mi = max(mi, ans);
        }
        ma += n;
        mas[node] = ma;
        mis[node] = max(ma % 2, mi);
        ns[node] = n + (S[node] == '1');
    };
    int ans = 1e9;
    for (int root = 0; root < N; root++) {
        recur(recur, root, -1);
        if (mis[root] == 0) {
            ans = min(ans, mas[root] / 2);
        }
    }
    cout << (ans == 1e9 ? -1 : ans) << endl;
    return 0;
}


Measured memory_bytes: 512
#include <stdio.h>

int cnt=0;
int m=0;
int G[1000000]={};

void insertion(int N,int a[],int g){
    int i,j,v;
    
    for(i=g; i<N; i++){
        v = a[i];
        j=i-g;
         
        while(j>=0 && a[j]>v){
            a[j+g]=a[j];
            j-=g;
            cnt++;
            a[j+g]=v;
        }
    }
}


void shell(int N,int a[]){
    int i;
    
    G[0]=1;
    
    for(m=1;m<15;m++){
        G[m]=G[m-1]*3+1;
        if(G[m]>N)break;
    }
    
    for(i=m-1;i>=0;i--){
        insertion(N,a,G[i]);
    }
    
}

int main(void){
    int i,N,a[1000000]={};
    
    scanf("%d",&N);
    for(i=0;i<N;i++){
        scanf("%d",&a[i]);
    }
    
    shell(N,a);
    
    printf("%d\n",m);
    for(i=m-1;i>=0;i--){
        printf("%d",G[i]);
        if(i==0)puts("");
        else printf(" ");
    }
    printf("%d\n",cnt);
    
    for(i=0;i<N;i++){
        printf("%d\n",a[i]);
    }
    
    return 0;
}




Measured memory_bytes: 5764
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M=mi()
    A=list(mi())

    sum_vote = sum(A)
    count = 0
    for a in A:
        if a >= sum_vote / (4*M):
            count +=1 
    
    print("Yes" if count >= M else "No")



if __name__ == "__main__":
    main()

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

using namespace std;

int main(void) {
	string str;
	while (cin >> str, str != "0") {
		int res = 0;
		for (int i = 0; i < str.length(); ++i) {
			res += str[i] - '0';
		}
		cout << res << endl;
	}
	return 0;
}



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

int main() {
  vector<char> n(4);
  for(int i=0;i<4;i++){
    cin >> n.at(i);
  }
  int check =0;
  if(((n.at(0)=='0')&&(n.at(1)!='0'))||((n.at(0)=='1')&&((n.at(1)=='0')||((n.at(1)=='1')||(n.at(1)=='2'))))){
   check+=2; 
  }
  if(((n.at(2)=='0')&&(n.at(3)!='0'))||((n.at(2)=='1')&&((n.at(3)=='0')||((n.at(3)=='1')||(n.at(3)=='2'))))){
   check+=1; 
  }
  
  if(check==0){
   cout << "NA"<<endl; 
  }
    if(check==1){
   cout << "YYMM"<<endl; 
  }
    if(check==2){
   cout << "MMYY"<<endl; 
  }
    if(check==3){
   cout << "AMBIGUOUS"<<endl; 
  }
  
  
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
	int a, b;
	cin >> a >> b;
	if (a<b) {
		cout << "a < b" << endl;
	} else if (a>b) {
		cout << "a > b" << endl;
	} else if (a==b) {
		cout << "a == b" << endl;
	}
	return 0;
}


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

int main()
{
    char c;
    cin >> c;
    if ((c == 'a') or (c == 'i') or (c == 'u') or (c == 'e') or (c == 'o')){
        cout << "vowel" << endl;
    } else{
        cout << "consonant" << endl;
    }
}

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

int main()
{
  string S, T;
  cin >> S >> T;
  vector<string> ans;
  if (T.size() > S.size())
    cout << "UNRESTORABLE" << endl;
  else
  {
    for (int i = 0; i <= S.size() - T.size(); i++)
    {
      bool ok = true;
      for (int j = 0; j < T.size(); j++)
      {
        if (S[i + j] != '?' and S[i + j] != T[j])
          ok = false;
      }
      if (ok)
      {
        string tmp;
        for (int j = 0; j < S.size(); j++)
          tmp += S[j];
        for (int j = 0; j < T.size(); j++)
          tmp[i + j] = T[j];
        for (int j = 0; j < S.size(); j++)
        {
          if (tmp[j] == '?')
            tmp[j] = 'a';
        }
        ans.push_back(tmp);
      }
    }
    sort(ans.begin(), ans.end());
    if (ans.size() == 0)
      cout << "UNRESTORABLE" << endl;
    else
      cout << ans[0] << endl;
  }
}

// 「Tを配置できる最も後ろの位置に配置して残りをaで埋める」だと嘘で、すべて試して最小を取る必要がある。


Measured memory_bytes: 256