akhauriyash/Code-Regression huggingface dataset:
from math import sqrt, ceil, pow

class SieveOfAtkin:
    """ ??¢???????????????
    https://github.com/mccricardo/sieve_of_atkin/blob/master/sieve_of_atkin.py
    """
    def __init__(self, limit):
        self.limit = limit
        self.primes = []
        self.sieve = [False] * (self.limit + 1)

    def flip(self, prime):
        try:
            self.sieve[prime] = True if self.sieve[prime] == False else False
        except KeyError:
            pass

    def invalidate(self, prime):
        try:
            if self.sieve[prime] == True: self.sieve[prime] = False
        except KeyError:
            pass

    def isPrime(self, prime):
        try:
            return self.sieve[prime]
        except KeyError:
            return False

    def getPrimes(self):
        testingLimit = int(ceil(sqrt(self.limit)))

        for i in range(testingLimit):
            for j in range(testingLimit):
                # n = 4*i^2 + j^2
                n = 4 * int(pow(i, 2)) + int(pow(j, 2))
                if n <= self.limit and (n % 12 == 1 or n % 12 == 5):
                    self.flip(n)

                # n = 3*i^2 + j^2
                n = 3 * int(pow(i, 2)) + int(pow(j, 2))
                if n <= self.limit and n % 12 == 7:
                    self.flip(n)

                # n = 3*i^2 - j^2
                n = 3 * int(pow(i, 2)) - int(pow(j, 2))
                if n <= self.limit and i > j and n % 12 == 11:
                    self.flip(n)

        for i in range(5, testingLimit):
            if self.isPrime(i):
                k = int(pow(i, 2))
                for j in range(k, self.limit, k):
                    self.invalidate(j)

        self.primes = [2, 3] + [x for x in range(len(self.sieve)) if self.isPrime(x) and x >= 5]
        return self.primes




if __name__ == '__main__':
    A = SieveOfAtkin(110000)
    A.getPrimes()
    # ??????????????\???
    while True:
        data = int(input())
        if data == 0:
            break

        # ????????¨???????????¨???
        result = A.primes[:data]
        print(sum(result))

Measured memory_bytes: 9124
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <math.h>

using namespace std;

int main(void) {
	int k, t;
	
	cin >> k >> t ;
	vector<int>a(t);

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

	sort(a.begin(), a.end(), greater<int>());

	int ret = 0;

	for (int i = 0; i < 1; i++)
	{
		if (a[i] > k / 2)
			ret += a[i] * 2 - k - 1;
		k = a[i] - k / 2;
	}
	cout << ret << endl;

	return 0;
}

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

R = 0
G = 0
B = 0

for i in range(N):
	if S[i] == 'R':
		R += 1
	elif S[i] == 'G':
		G += 1
	else:
		B += 1
ans = R*G*B
for i in range(N-2):
	for j in range(i+1, N-1):
		k = j+(j-i)
		if k >= N:
			break
		if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
			ans -= 1
print(ans)

Measured memory_bytes: 9108
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

S = input()
if all(c != 'R' for c in S[1::2]) and all(c != 'L' for c in S[::2]):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 38256
S = input()
cnt = 0
cntOld = 0
for n in range(len(S)):
    if S[n] == 'A' or  S[n] == 'C' or S[n] == 'G' or S[n] == 'T':
        cnt += 1
    else:
        if cntOld < cnt:
            cntOld = cnt
            cnt = 0
if cntOld < cnt:
    cntOld = cnt
print(cntOld)

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

long long cnt;
int l,n;
int A[1000010];
vector<int> G;

void insertionSort(int A[], int n, int g) {
    for(int i=g; i<n; i++) {
        int j=i-g;
        int k=A[i];
        while(j>=0&&A[j]>k) {
            A[j+g]=A[j];
            j-=g;
            cnt++;
        }
        A[j+g]=k;
    }
}
void shellSort(int A[], int n) {
    int h=1;
    while(h<=n) {
        G.push_back(h);
        h = 3*h + 1;
    }

    for(int i = G.size()-1; i>=0; i--) {
        insertionSort(A,n,G[i]);
    }


}
int main() {
    cin>>n;
    for(int i=0; i<n; i++)scanf("%d",&A[i]);
    cnt = 0;

    shellSort(A,n);

    cout<<G.size()<<endl;
    for(int i=G.size()-1; i>0; i--)cout<<G[i]<<' ';
    cout<<G[0]<<endl;

    cout<<cnt<<endl;

    for(int i=0; i<n; i++)cout<<A[i]<<endl;

    return 0;
}



Measured memory_bytes: 7104
/**
*	  Name: Ajay
*	  Institute: IIITH 
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <string.h>
#define ll long long
#define inf 0x7fffffff
#define mod 1000000007
#define pb push_back
#define ppi pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vii vector<ppi>
#define vll vector<ll>
#define mp make_pair
#define fi first
#define se second
using namespace std;

void fastio()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
void input()
{
  #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  #endif
}

int main()
{      
  fastio();
  	int x;
    cin>>x;
    int ans=(x/500)*1000;
    x=x%500;
    ans+=(x/5)*5;
    cout<<ans;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

        Scanner sc = new Scanner(System.in);

        int num = Integer.parseInt(sc.nextLine());

        int result = 0;

        for (int i = 0; i < num; i++) {
            int target = Integer.parseInt(sc.nextLine());

            if (target == 1) { continue; }

            boolean flgPrime = true;
            for(int j = 2; j <= (int)Math.sqrt(target); j++) {
                if (target % j == 0) {
                    flgPrime = false;
                    break;
                }
            }

            if (flgPrime) {
                result++;
            }
        }

        System.out.println(result);
    }
}


Measured memory_bytes: 61056
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl "\n"
#define ll long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF 2147483647
#define LLINF 9223372036854775807LL
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ALL(a) (a).begin(), (a).end()
#define BIT(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
constexpr ll MOD = 1e9 + 7;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;
ll ans = 0;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec)
        is >> x;
    return is;
}

signed main() {
    cin >> N >> S;
    int l = 0, r = 0;
    REP(i, N) {
        if (S[i] == '(') {
            r++;
        } else {
            if (r > 0)
                r--;
            else
                l++;
        }
    }
    REP(i, l)
    S = '(' + S;
    REP(i, r)
    S = S + ')';
    cout << S << endl;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
inline int D()
{
    int t;
    scanf("%d",&t);
    return t;
}
inline ll llD()
{
    ll t;
    scanf("%lld",&t);
    return t;
}

const int Max=1e6+9;
const int OO=-1e6;
int st[4]= {1,0,0,-1};
int nt[4]= {0,1,-1,0};
int n,m;
bool valid(int x,int y)
{
    return x>-1 && y>-1 && x<n && y<m;
}
ll mem[Max];
void init()
{
    memset(mem,-1,sizeof mem);
}
//////////////////////////////////////////////////////////

ll a[Max];

ll solve (int i )
{
    if(i==n-1)return 0;
    if(i>=n)
        return Max;

    ll &ret=mem[i];
    if(~ret)return ret;
    ret=1e9;
    for(int j=0;j<=m;j++)
    ret=min(ret,(solve(i+j)+abs(a[i]-a[i+j])));

     return mem[i]=ret;
}

void Fast()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cerr.tie(0);
}
int main()
{
   init();
   n =D();
m =D();
   for(int i=0; i<n;i++)
   {
       a[i]=llD();
   }
   printf("%lld",solve(0));

}


Measured memory_bytes: 18608
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define VSUM(V) accumulate(ALL(V), 0)
#define MID(a,b,c) (a) < (b) && (b) < (c)
#define MIDe(a,b,c) (a) <= (b) && (b) <= (c)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define IN4(a,b,c,d) cin >> a >> b >> c >> d
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define Vd vector<double>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b != 0 ? gcd(b, a % b) : a;} //最大公約数
int lcm(int a, int b){return a * b / gcd(a, b);}
string toStrUp(string str){char diff = 'A'-'a';REP(i,str.size()) str[i] += diff;return str;}
string gCh(string str, int key){return str.substr(key,1);}

signed main() {
  RAPID;
  // デフォルト変数定義
  int n=0,m=0,a=0,b=0,c=0,d=0,x=0,y=0,z=0;
  string s="",t="";
  //

  // ここから
  IN2(n,s);
  FOR(j,1,n-1){
    set<char> D1;
    set<char> D2;
    set<char> RST;
    REP(i,j){
      D1.insert(s[i]);
    }
    FOR(i,j,n){
      D2.insert(s[i]);
    }
    set_intersection(D1.begin(), D1.end(),
                     D2.begin(), D2.end(),
                     std::inserter(RST, RST.end()));
    c = max(c, (int)RST.size());
  }
  OUT(c);
}

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

#define int long long int
#define pb push_back
#define mp make_pair

#define fr(i,a,b) for(i=a;i<=b;i++)

vector <int> v[503];

int32_t main()
{
     
     int n,m,q,i,x,y;     
     
   cin>>n>>m>>q;
   
   for(i=1;i<=m;i++)
   {
        cin>>x>>y;
        v[x].pb(y);
   }
   
   for(i=1;i<=n;i++)
   {
        if(v[i].size()!=0)
        {
             sort(v[i].begin(),v[i].end());
        }
   }
   
   while(q--)
   {
        int a,b,ans=0;
        
        cin>>a>>b;
        
        for(i=a;i<=b;i++)
        {
             ans+=(upper_bound(v[i].begin(),v[i].end(),b)-v[i].begin());
        }
        
        cout<<ans<<endl;
        
   }
   return 0;
}

Measured memory_bytes: 5248
#include <iostream>
#include <string.h>
using namespace std;
int dx[]={-1,0,1,0,0};
int dy[]={0,-1,0,1,0};

int main() {
	int n ; cin >> n ;
	while(n--){
		int field[10][10];
		for(int i=0;i<10;i++) for(int j=0;j<10;j++) cin >> field[i][j];
		int tmp_ans[10][10]={0};
		int tmp_field[10][10];
		for(int i=0;i<1<<10;i++){
			bool failed=false;
			memset(tmp_ans,0,sizeof(tmp_ans));
			memcpy(tmp_field,field,sizeof(field));
			for(int j=0;j<10;j++) tmp_ans[0][10-1-j]= i>>j & 1;
			for(int j=0;j<10;j++){
				if(tmp_ans[0][j]){
					for(int m=0;m<=4;m++)
						if(0<=j+dx[m] && j+dx[m]<10 && 0<=dy[m] ) (tmp_field[dy[m]][j+dx[m]])^=1;
				}
			}
			for(int l=1;l<10;l++){
				for(int k=0;k<10;k++){
					if(tmp_field[l-1][k]){
						tmp_ans[l][k]=true;
						for(int m=0;m<=4;m++)
							if(0<=k+dx[m] && k+dx[m]<10 && 0<=l+dy[m] && l+dy[m]<10) tmp_field[l+dy[m]][k+dx[m]]^=1;
					}
				}
			}
			for(int j=0;j<10;j++) if(tmp_field[9][j]) failed=true;
			if(!failed) break;
		}
		for(int i=0;i<10;i++){
			for(int j=0;j<10;j++) {if(j) cout << ' ' ; cout << tmp_ans[i][j] ;}
			cout << '\n' ;	
		}
	}
}

Measured memory_bytes: 1160
#include <iostream>
#include <string>
#define llint long long

using namespace std;

string s;
llint k;

int main(void)
{
	cin >> s;
	cin >> k;
	
	int p = s.size() + 100;
	for(int i = 0; i < s.size(); i++){
		if(s[i] != '1'){
			p = i;
			break;
		}
	}
	k--;
	if(k < p) cout << 1 << endl;
	else cout << s[p] << endl;
	return 0;
}

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

int main() {

  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  int ans, cnt;
  ans = -1;
  cnt = 1;
  for (int i = 0; i < N; i++) {
    if (A.at(i) == cnt) {
      cnt++;
    }
  }
  cnt -= 1;
  if (cnt != 0) {
    cout << N - cnt << endl;
  }
  else {
    cout << ans << endl;
  }
  
      
    
}


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

template <
    typename TYPE,
    std::size_t SIZE>
std::size_t a_len(const TYPE (&array)[SIZE])
{
    return SIZE;
}

using namespace std;
using ll = long long int;
using vi = vector<ll>;

#define REPS(a, i, n) for (ll(i) = a; (i) < (n); ++(i))
#define REP(i, n) REPS(0, i, n)
#define ALL(x) (x).begin(), (x).end()

const ll INF = 912345678;

string s;

int main()
{
    cin >> s;
    int ans = 0;
    for (auto c : s)
    {
        if (c == '1')
        {
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <list>
#include <math.h>
#include <iomanip>
#include <map>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;

long A,B;

long res(long in){
  long ans = 0;
  if(in == 1) return 1;
  if(in % 2 == 0){
    if( (in/2)%2 == 0){
      ans = in^0;
    }else{
      ans = in^1;
    }
  }else{
    if( ((in+1)/2)%2 == 0){
      ans = 0;
    }else{
      ans = 1;
    }
  }
  return ans;
}

int main(){
  cin>>A>>B;
  //cout<<res(A-1)<<endl;
  //cout<<res(B)<<endl;
  if(A == 0){
    cout<<res(B)<<endl;
  }else{
    cout<< (res(A-1)^res(B)) << endl;
  }

}

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

int main() {

  long long A, B, N;
  cin >> A >> B >> N;

  long long x;

  if (N < B - 1) {
    x = N;
  } else {
    x = B - 1;
  }

  x %= B;
  A *= x;

  long long answer = (A - A % B) / B;

  cout << answer << endl;

  return 0;
}

Measured memory_bytes: 3640
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<numeric>
#include<utility>
#include<unordered_map> //hash map

#define rep(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define rrep(i,a,n) for(int (i)=(a);(i)>=(n);(i)--)

#define INF 1000000000
#define MOD 1000000007

typedef  long long ll;

using namespace std;

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

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

double euclid_distance(double a,double b){
    return sqrt(a*a+b*b);
}

ll gcd(ll  a,ll b){
    ll r;
    if(a < b){
        ll tmp;
        tmp = a;
        a = b;
        b = tmp;
    }
    while(r = a % b){
        a = b;
        b = r;
    }
    return b;
}
/*
ll Integer_factorization(ll n){
    ll num = 0;
    ll ndash = n;
    if(n == 1) return 1;
    ll a = 2;
    while(ndash >= a*a){
        if(n % a  == 0){
            count++;
            n/=a;

        if(count % b == 0){
            ans *= a;
        }
        }else{a++;count = 0;}
    }

    return num;
}
*/

ll r_fuct[2000];
ll fuct[2000];

//MOD逆元
void conb(ll n,ll k){
    fuct[0] = 1;
    for(int i = 1;i < k+1;i++){
        fuct[i] *= fuct[i-1]%MOD;
        
        ll b = MOD, u = 1, v = 0;
        ll value = fuct[i];
        while (b) {
            ll t = value / b;
            value -= t * b;
            swap(value, b);
            u -= t * v;
            swap(u, v);
        }
        u %= MOD;
        if (u < 0) u += MOD;
        r_fuct[i] = u;
    }
}

ll factrial(ll n){
    if(n == 0) return 1;
    ll p = factrial(n-1)*n%MOD;
    return p;
}

//MOD逆元
ll farmat(ll n,ll p){    
    if(p == 0) return 1;
    else if(p == 1) return n%MOD;
    ll d = farmat(n,p/2);
    if(p%2 == 0){
        return (d*d)%MOD;
    }else{
        return ((n*d)%MOD*d)%MOD;
    }
}

ll conbination(ll n,ll k){
    ll a = factrial(n);
    ll b = factrial(k);
    ll c = factrial(n-k);
    return (a*farmat(b,MOD-2)%MOD*farmat(c,MOD-2))%MOD;
}

int memo[10000000];

int fib(int i){
    if(i <= 1) return i;
    if(memo[i] != 0) return memo[i];
    return memo[i] = fib(i-1)+fib(i-2);
}

ll dig(ll n){
    ll d = 0;
    while(n != 0){
        n/=10;
        d++;
    }
    return d;
}

void solve() {
    int a,b,c;
    cin >> a >> b >> c;
    cout << min(a*b,c) << endl;
    
/*
  ll n,k;
  cin >> n >> k;
  vector<ll> x(n+1);
  vector<ll> sub(n);
  for(int i = 0;i < n;i++){
      cin >> x[i];
  }
  if(n == 1){
      cout << abs(x[0]) << endl;
      return;
  } 
  x[n] = 0;
  sort(x.begin(),x.end());
  for(int i = 0;i < n;i++){
      sub[i] = x[i+1]-x[i];
  }
  vector<ll> right(n);
  right[0] = sub[0];
  for(int i = 1;i < n;i++){
      right[i] = right[i-1]+sub[i];
  }

  ll ans = right[k-1];
  for(int i = 0;i < n-k;i++){
      ans = min(ans,right[i+k]-right[i]);
  }
  cout << ans << endl;
  */
}




int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
 
const double pi = 3.141592653589793238462643383279;
 
 
using namespace std;
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
 
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
 
//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
 
 
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const double EPS = 1E-10;
 
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)


//ここから編集

int arr[62];
ll pows[43];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int N;
  ll K; cin >> N >> K;
  vector<ll> A(N);
  REP(i,N) cin >> A[i];

  pows[0] = 1;
  for(int i=1; i<43; i++){
    pows[i] = 2*pows[i-1];
  }
  REP(i,N){
    ll tmp = A[i];
    for(int j=0; j<60; j++){
      if(tmp%2 == 1){
        arr[j]++;
      }
      tmp /= 2;
    }
  }
  //for(int i=0; i<20; i++) cout << arr[i] << endl;

  ll ans = 0;
  for(int i=43; i>=0; i--){
    
    // 0を取った時
    ll s1 = arr[i] * pows[i];

    // 1を取ったとき
    ll s2 = (N - arr[i]) * pows[i];
    //cout << arr[i] << endl;
    if(K >= pows[i]){
      if(s1 >= s2){
        ans += s1;
      }else{
        ans += s2;
        K -= pows[i];
      }
    }else{
      ans += s1;
    }
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
  int K, S;
  cin >> K >> S;
  int ans = 0;

  for(int x = 0; x <= K; x++) {
    for (int y = 0; y <= K; y++) {
      int z = S - x - y;
      if (0 <= z && z <= K) ++ans;
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3532
#include<stdio.h>

int linear(int *,int,int);
int main(){
	int i,j,n,q[100000],sum=0,s,t;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&q[i]);
	}
	scanf("%d",&s);
	for(i=0;i<s;i++){
		scanf("%d",&t);
		sum+=linear(q,n,t);
	}
	printf("%d\n",sum);
	return 0;
}

int linear(int *q,int n,int t){
	int j=0;
	q[n]=t;
	while(q[j]!=t){
		j++;
	}
	if(j==n)return 0;
	return 1;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
#include<string.h>
#define ll long long 
#include<vector>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int main(){
	IOS;
	ll x;
	cin>>x;
	int ans=0;
	if(x>=500)
	ans+=x/500*1000;
	x%=500;
	if(x>=5)
	ans+=x/5*5;
	cout<<ans;
	
	}

Measured memory_bytes: 3652
#include <algorithm>
#include <iostream> //入出力
#include <stdio.h>
#include <map>
#include <set>
#include <string>
#include <math.h> //算術演算子
#include <vector>
#include <cstdlib>
#include <queue>
#include <stack>
#include <list>
#include <iomanip> //小数点以下を表示させる(setprecision())
//#include <bits/stdc++.h>
using namespace std;
typedef long long ll; //64bit型

#define debug(x) cerr << x << " " \
                      << "(L:" << __LINE__ << ")" << '\n'
#define PRINT(V)                                   \
        {                                          \
                for (int i = 0; i < V.size(); i++) \
                {                                  \
                        cout << V[i] << " ";       \
                }                                  \
                cout << endl;                      \
        }

int gcd(int a, int b)
{
        return b ? gcd(b, a % b) : a;
}

int main()
{
        //input->compute->output//
        int D, N;
        cin >> D >> N;
        if (N != 100)
        {
                if (D == 0)
                {
                        cout << N << endl;
                }
                else if (D == 1)
                {
                        cout << N * 100 << endl;
                }
                else if (D == 2)
                {
                        cout << N * 100 * 100 << endl;
                }
        }
        else
        {
                if (D == 0)
                {
                        cout << N+1 << endl;
                }
                else if (D == 1)
                {
                        cout << (N + 1) * 100 << endl;
                }
                else if (D == 2)
                {
                        cout << (N + 1) * 100 * 100 << endl;
                }
        }

        return 0;
}


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

int a[9];

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

  int n; cin >> n;
  for(int i = 0; i < n; i++){
    int c; cin >> c;
    a[min(8LL,c/400)]++;
  }

  int sum = 0;
  for(int i = 0; i < 8; i++){
    if(a[i]) sum++;
  }
  cout << max(sum,1LL) << " " << sum+a[8] << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define x real()
#define y imag()
#define EPS 0.0000001
using namespace std;
typedef complex<double> point;

double dot(point a,point b){return a.x*b.x+a.y*b.y;}
double cross(point a,point b){return a.x*b.y-a.y*b.x;}
int ccw(point a,point b,point c){
  point d = b-a,e = c-a;
  if(cross(d,e)>0) return 1;//"COUNTER_CLOCKWISE"
  if(cross(d,e)<0) return -1;//"CLOCKWISE"
  if(dot(d,e)<0) return 2;//"ONLINE_BACK"
  if(abs(d) < abs(e)) return -2;//"ONLINE_FRONT"
  return 0;//"ON_SEGMENT"
}

point crosspoint(point a,point b,point c,point d){
  a-=d;b-=d;c-=d;
  return d+a+(b-a)*imag(a/c)/imag(a/c-b/c);
}

vector<point> ConvexCut(vector<point> &polygon,point a,point b){
  vector <point> res;
  for(int i=0;i<polygon.size();i++){
    point A=polygon[i],B=polygon[(i+1)%polygon.size()];
    if(ccw(a,b,A)!=-1)res.push_back(A);
    if(ccw(a,b,A)*ccw(a,b,B)==-1)res.push_back(crosspoint(a,b,A,B));
  }
  return res;
}

double get_area(vector <point> &polygon){
  if(polygon.size()<3)return 0;
  double res=0;
  for(int i=0;i<polygon.size();i++)
    res+=cross(polygon[i],polygon[(i+1)%polygon.size()])/2;
  return res;
}

int main(){
  while(1){
    int v,n,d;
    vector <point> pl;
    cin>>n>>d>>v;
    if(!n&&!d&&!v) break;
    for(int i=0,a,b;i<n;i++) cin>>a>>b,pl.push_back(point(a,b));
    
    double V=min(get_area(pl)*d,(double)v),ans=0;

    for(int i=0;i<n;i++){
      double L=0,M,R=2010;
      int I=1000;
      while(I--){
	M=(L+R)/2;
	point h=pl[(i+1)%n]-pl[i],b=h;
	h=(point(0,M)*h/abs(h))+pl[i];

	if(ccw(pl[(i+1)%n],pl[i],h)*ccw(pl[(i+1)%n],pl[i],h+b)<=0)assert(0);
	vector<point> a=ConvexCut(pl,h+b,h);
	double res=get_area(a);
	assert(res>0);
	if(res*d>=V)R=M;
	else L=M+0.000000001;
      }
      ans=max(ans,L);
    }
    assert(ans<2001&&ans>0.0001);
    printf("%.8f\n",ans);
  }
  return 0;
}

Measured memory_bytes: 1252
#include<bits/stdc++.h>
using namespace std;
char a[55][55];
int main()
{
	int n,m;
	int i,j,ans=0;
	cin>>n>>m;
	for(i=0;i<n;i++)
	for(j=0;j<m;j++)
	cin>>a[j][i];
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			if(a[j][i]=='#')
			{
				cout<<"#";
			
			}
			else
			{
				if(a[j+1][i]=='#')ans++;
				if(a[j-1][i]=='#')ans++;
				if(a[j+1][i+1]=='#')ans++;
				if(a[j-1][i-1]=='#')ans++;
				if(a[j+1][i-1]=='#')ans++;
				if(a[j-1][i+1]=='#')ans++;
				if(a[j][i+1]=='#')ans++;
				if(a[j][i-1]=='#')ans++;
				cout<<ans;
			}
		ans=0;
		}	cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
def inpl(): return [int(i) for i in input().split()]
import bisect
N = int(input())
A = sorted(inpl())
B = inpl()
C = sorted(inpl())
ans = 0
for b in B:
    ans += bisect.bisect_left(A,b)*(N-bisect.bisect_right(C,b))
print(ans)

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

int beki(int n,int m){
  int k=1;
  for(int i=0;i<m;i++){
    k*=n;
  }
  return k;
}

int heihou(int n){
  int count=0;
  for(int i=1;i<=40;i++){
    for(int j=2;j<=10;j++){
      if(n==beki(i,j)){
        count++;
      }
    }
  }
  if(count!=0){
    return 1;
  }
  else{
    return 0;
  }
}  

int main(){
  int n;
  cin >> n;
  for(int i=n;;i--){
    if(heihou(i)==1){
      cout << i << endl;
      break;
    }
  }
}


Measured memory_bytes: 256
x=input()
n=len(x)

for i in range(n):
    if x[i]=='S':
        left=i
        break
else:
    print(n)
    exit(0)

right=left+1
ans=n

while True:

    while right<n and x[right]=='S':
        right+=1
    
    if right>=n:
        break

    ans-=2
    right+=1
    left+=1
    while left<n and x[left]=='T':
        left+=1
    
    if left>=n:
        break

    right=max(left+1,right)


print(ans)


Measured memory_bytes: 73124
// AOJ 0521
#include<cstdio>
#define rep(i,a) for( int i = 0; i != (a); ++i )

const int C[6] = { 500, 100, 50, 10, 5, 1 };

int main()
{
	int p;
	while( scanf( "%d", &p ), p )
	{
		p = 1000-p;

		int ans = 0;
		rep( i, 6 )
			ans += p/C[i], p %= C[i];

		printf( "%d\n", ans );
	}

	return 0;
}

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

int main() {
    ll n, a[87] = {0}; cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    ll money = 1000;
    ll cnt = 0;
    for(int i=0; i<n; i++) {
        if(a[i] < a[i + 1]) {
            ll num = money / a[i];
            cnt += num;
            money -= a[i] * num;
        }
        else {
            money += cnt * a[i];
            cnt = 0;
        }
    }
    cout << money << endl;
}

Measured memory_bytes: 3616
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <deque>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define print(x) cout<<(x)<<endl
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n)-1; i >= 0; --i)
#define INF10 1001001001 
#define INF5 100000
#define EPS 1e-10


int main() {
	ll n; cin >> n;
	vector<ll>traf(5);
	ll mn = 1000100100100100;
	int ky = 0;
	REP(i, 5) {
		cin >> traf[i];
		if (traf[i] <= mn) {
			ky = i;
			mn = traf[i];
		}
	}
	ll cost = 0;
	cost += 4 + (n + mn - 1) / mn ;

	print(cost);






	return 0;
}


Measured memory_bytes: 256
import collections
s = map(int,list(raw_input()))
qa = collections.deque([0])
qb = collections.deque([1])
for i in range(len(s)):
	qa.append(min(qa[0] + s[i], qb[0] + 10 - s[i]))
	qb.append(min(qa[0] + s[i] + 1, qb[0] + 10 - s[i] - 1))
	qa.popleft()
	qb.popleft()

print qa[-1]





Measured memory_bytes: 106056
n = int(input())
lst = [int(i) for i in input().split()]
mod = pow(10, 9) + 7
ans = 0
summ = 0
for i in range(1, n):
  summ += lst[i]
  summ %= mod
for i in range(n - 1):
  ans += lst[i] * summ
  ans %= mod
  summ -= lst[i + 1]
  summ %= mod
print(ans)

Measured memory_bytes: 94176
//atcoder clange
#include <stdio.h>

int main(void){
    int N;
    int i,j,k,n;
      scanf("%d", &N);//数値の取得
    
    int ans =0;
    ans = 180 *(N - 2);

    printf("%d",ans);

    //int max = max(a, N);
    return 0;     
}

Measured memory_bytes: 128
var i,j:longint;
    fx,fy,x,y:longint;
    n,m:longint;
    a,next,last,father:array[0..200050]of longint;
    v,newv:array[0..200050]of boolean;
    ans:longint;
function gf(x:longint):longint;
begin
  if father[x]=x then exit(x) else
  begin
    father[x]:=gf(father[x]);
    gf:=father[x];
  end;
end;
begin
  read(n,m);
  for i:=1 to n do
  read(a[i]);
  for i:=1 to n do
  father[i]:=i;
  for i:=1 to m do
  begin
    read(x,y);
    fx:=gf(x);
    fy:=gf(y);
    if fx<>fy then father[fx]:=fy;
  end;
  for i:=n downto 1 do
  begin
    next[i]:=last[gf(i)];
    last[gf(i)]:=i;
  end;
  for i:=1 to n do
  if not v[i] then
  begin
    x:=i;
    repeat
      newv[x]:=true;
      x:=next[x];
    until x=0;
    x:=i;
    repeat
      if newv[a[x]] then inc(ans);
      x:=next[x];
    until x=0;
    x:=i;
    repeat
      v[x]:=true;
      newv[x]:=false;
      x:=next[x];
    until x=0;
  end;
  writeln(ans);
end.



Measured memory_bytes: 1920
#include <bits/stdc++.h>
#define range(i, l, r) for(int (i) = (l); (i) < (r); (i)++)
#define reversed_range(i, l, r) for (int (i) = (r) - 1; (i) >= l; (i)--)
using namespace std;
template <typename T>
using vec = vector<T>;
using lint = long long;
using ulint = unsigned long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;

template <typename S, typename T>
ostream& operator <<(ostream& os, pair<S, T> p) {
    os << "(";
    os << p.first << ", " << p.second;
    return os << ")";
}

template <typename T>
ostream& operator <<(ostream& os, vec<T> v) {
    os << "[";
    for (int i = 0; i < v.size() - 1; i++) {
        os << v.at(i) << ", ";
    }
    return os << v.at(v.size() - 1) << "]";
}

template <typename T>
ostream& operator <<(ostream& os, set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename T>
ostream& operator <<(ostream& os, unordered_set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, unordered_map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

lint pow(lint num, lint e, lint MOD) {
    lint res = 1;
    lint cur_num = num;
    while (e) {
        if (e & 1) {
            res *= cur_num;
            res %= MOD;
        }
        cur_num *= cur_num;
        cur_num %= MOD;
        e >>= 1;
    }
    return res;
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    lint a, b, c;
    cin >> a >> b >> c;
    if (a + b == c || b + c == a || c + a == b) {
        cout << "Yes" << "\n";
    } else {
        cout << "No" << "\n";
    }
}

Measured memory_bytes: 256
use std::io::*;

fn main(){
    let s : String = input(); 
    let mut c : Vec<char> = s.chars().collect();
    c.sort();
    let ans = if (c[0] == c[1]) && (c[1] != c[2]) && (c[2] == c[3]){"Yes"}else{"No"};
    println!("{}", ans);
}

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

Measured memory_bytes: 4352
#include<stdio.h>
int main(){
    int i,n;
    long long int sum=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        if(i%3!=0&&i%5!=0)
        sum=sum+i;
    }
    printf("%lld",sum);
    return 0;
}

Measured memory_bytes: 1696
import java.util.Scanner;
class Main{
	public static void main(String[]args){
		Scanner sc = new Scanner(System.in);
		int S = sc.nextInt();
		int h = 0;
		int m =0;
		int s = 0;
		h=S / 3600;
		m = (S  - h * 3600) / 60;
		s = S -(h*3600+m*60);
		System.out.println(h+":"+m+":"+s);
		sc.close();
	}
}

Measured memory_bytes: 17228
(N, D), *Xs = readlines.map{|l| l.split.map(&:to_i)}

d = ->(i, j){Math.sqrt((0 ... D).map{|d| (Xs[i][d] - Xs[j][d])**2}.inject(:+))}
puts [*0 ... N].combination(2).count{|i, j| d[i, j] == d[i, j].to_i}

Measured memory_bytes: 1916
#include<iostream>
#include<string>
//#include<cmath>
//#include<array>
#include<algorithm>
//#include<deque>
#include<vector>
//#include<utility>
//#include<set>
//#include<map>
//#include<list>
//#include<bitset>

using namespace std;
using LLI = long long int;
LLI N;

//array<int, 8>dir_x = { 0,0,1,1,1,-1,-1,-1 };
//array<int, 8>dir_y = { 1,-1,1,0,-1,1,0,-1 };
//array<int, 4>dir_x2 = { 0,0,1,-1 };
//array<int, 4>dir_y2 = { 1,-1,0,0 };
//char alp[] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };

//class UnionFind {
//public:
//	vector<int>data;
//	UnionFind(int size) :data(size, -1) {};
//	bool unionset(int x, int y) {
//		x = root(x), y = root(y);
//		if (x != y) {
//			if (data[y] < data[x]) {
//				swap(x, y);
//			}
//			data[x] += data[y];
//			data[y] = x;
//		}
//		return x != y;
//	}
//	bool findset(int x, int y) {
//		return root(x) == root(y);
//	}
//	int root(int x) {
//		return data[x] < 0 ? x : data[x] = root(data[x]);
//	}
//	int size(int x) {
//		return -data[root(x)];
//	}
//};

//LLI gcd(LLI x, LLI y) {
//	LLI  r;
//	if (x < y) {
//		swap(x, y);
//	}
//	r = x % y;
//	while (r != 0) {
//		x = y;
//		y = r;
//		r = x % y;
//	}
//	return y;
//}
//LLI lcm(LLI x, LLI y) {
//	return x / gcd(x, y) * y;
//}

//long nCr(int n,int r) {
//	long ans = 1;
//	for (int i = n; i > n - r;i--) {
//		ans = ans * i;
//	}
//	for (int i = 1; i < r + 1;i++) {
//		ans = ans / i;
//	}
//	return ans;
//}

//const int n_max = 8;
//array<array<bool, n_max>, n_max>graph;
//int dfs(int v,int N,array<bool,n_max>visited) {
//	int ret = 0;
//	bool all_visited = true;
//	for (int i = 0; i < N;i++) {
//		if (visited[i] == false) {
//			all_visited = false;
//		}
//	}	
//	if (all_visited) {
//		return 1;
//	}
//	for (int i = 0; i < N;i++) {
//		if (graph[v][i] == false) {
//			continue;
//		}
//		if (visited[i] == true) {
//			continue;
//		}
//		visited[i] = true;
//		ret += dfs(i,N,visited);
//		visited[i] = false;
//	}
//	return ret;
//}

//vector<vector<int>>sub;
//int dfs(int id) {
//	if (sub[id].size() == 0) {
//		return 1;
//	}
//	int minP = (int)1e9;
//	int maxP = 0;
//	for (int i : sub[id]) {
//		int P = dfs(i);
//		minP = min(minP, P);
//		maxP = max(maxP, P);
//	}
//	return minP + maxP + 1;
//}

//#define debug(x) cerr << #x << " : " << x << endl
//#define debugv(x) cerr << #x << " : "; for(auto i:x) cerr << i << ", "; cerr<<endl

int main(void) {
	vector<int>vec(3);
	int res = 0;
	for (int i = 0; i < 3; i++) {
		int a;
		cin >> a;
		vec[i] = a;
	}
	sort(vec.begin(), vec.end());
	int b = vec[2] - vec[1];
	res += b;
	vec[1] += b;
	vec[0] += b;
	int c = vec[1] - vec[0];
	if (c % 2 == 1) {
		res += c / 2;
		res += 2;
	}
	else {
		res += c / 2;
	}
	cout << res << endl;
}

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

int main() {
  
  int N,K,A = 1;
  cin >> N >> K;
  
  for (int i = 0; i < N; i++) {
    if ( A < K) A *= 2;
    else A += K;
  }
  cout << A << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
struct Element{
    int v;
    int id;
    bool operator < (const Element &other)const{
        return v<other.v;
    }
};
Element a[200005];
int ans[200005];

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        a[i].id = i;
        scanf("%d",&a[i].v);
    }
    std::sort(a+1,a+1+n);
    int pos = n/2+1;
    for(int i = 1; i <= n; i++){
        if(i<pos) ans[a[i].id] = a[pos].v;
        else ans[a[i].id] = a[pos-1].v;
    }
    for(int i = 1; i <= n; i++) printf("%d\n",ans[i]);
    return 0;
}


Measured memory_bytes: 4652
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#ifdef i_am_noob
#define debug(a) print2(#a,a)
#else
#define debug(a) 
#endif
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
using namespace std;
using namespace __gnu_pbds;
 
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;
 
inline int add(int a, int b){return (a+b>=MOD?a+b-MOD:a+b);}
inline int sub(int a, int b){return (a+MOD-b>=MOD?a-b:a+MOD-b);}
int Pow(int a, int b){
	if(!b) return 1;
	int tmp=Pow(a*a%MOD,b>>1);
	return (b&1?tmp*a%MOD:tmp);
}
inline int inverse(int n){return Pow(n,MOD-2);}

const int maxn=100005;
//i_am_noob
int a,b,c;

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	cin >> a >> b >> c;
	print1(min(b/a,c));
	return 0;
}


Measured memory_bytes: 256
#　149D
n, k = map(int, input().split())
point={}
point['s'],point['p'],point['r'] = map(int, input().split())
s = input()

ans =0
before = [0]*k
for i in range(len(s)):
    if i >= k:
        if (s[i] == s[i-k]) & (before[i%k]==1):
            before[i%k] = 0
        else:
            ans += point[s[i]]
            before[i%k] = 1
    else:
        ans += point[s[i]]
        before[i%k] = 1
print(ans)

Measured memory_bytes: 3956
//#include <bits/stdc++.h>
#include<iostream>
#include<vector>
#include<map>
#include<math.h>

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

#define fi first
#define se second

using namespace std;

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

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

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

int main(void)
{
    int n, x;
    cin >> n >> x;
    
    int cnt = 1;
    int d = 0;

    irep(i, n) {
        int l;
        cin >> l;
        d += l;    
        if(d <= x) { cnt++; }
    }
    cout << cnt << endl;
    return 0;
} /*atcoder*/


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

int main() {
	// your code goes here
	string a, b, c; cin >> a >> b >> c;
	if (a.back() == b.front() && b.back() == c.front()) {
	    cout << "YES";
	} else {
	    cout << "NO";
	}
	
	return 0;
}


Measured memory_bytes: 3600
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>

typedef long long ll;
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;

    int m;
    m = max(a+b, max(a+a-1, b+b-1));
    cout << m << endl;
    return 0;
}


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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define LOOP(i) while(i--)
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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


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

	int N=in(),W=in();
	vector<ll> dp(W+1,0);

	for(int i=1;i<=N;i++){
		ll v=in(),w=in(),m=in();
		for(ll k=1;m>0;k<<=1){
			int coeff = min(k,m);
			for(int j=W;j>=coeff*w;j--){
				if(j-coeff*w>=0) chmax(dp[j],dp[j-coeff*w]+coeff*v);
			}
			m -= coeff;
		}
	}

	out(dp[W]);
	
	return 0;
}



Measured memory_bytes: 3300
#include <stdlib.h>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <string>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;

int main(){
  vector<int> A(5);
  int min_1=9;
  int index=-1;
  for(int i=0;i<5;i++){
    cin >> A.at(i);
    if(A.at(i)%10!=0){
      if(A.at(i)%10<=min_1){
	min_1=A.at(i)%10;
	index=i;
      }
    }
  }

  int ans=0;
  for(int i=0;i<5;i++){
    if(i==index) ans+=A.at(i);
    else{
      if(A.at(i)%10==0) ans+=A.at(i);
      else ans+=(A.at(i)/10)*10+10;
    }
  }

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


Measured memory_bytes: 256
s = input()[::-1]

# 0が2019個からなるリスト。modを保管する
cnts = [0] * 2019
cnts[0] = 1
mod_num = 0
d = 1

for c in s:
  t = d * int(c)
  mod_num += t
  mod_num %= 2019
  cnts[mod_num] += 1
  d *= 10
  d %= 2019

result = 0
for cnt in cnts:
  result += cnt * (cnt - 1) // 2

print(result)

Measured memory_bytes: 9268
N = int(input())
a = []
for i in range(0, N):
  a.append(int(input()))

sorted_a = sorted(a, reverse=True)
first_max = sorted_a[0]
second_max = sorted_a[1]

ans = ""
ans += (str(first_max) + '\n') * (a.index(first_max))
ans += (str(second_max) + '\n')
ans += (str(first_max) + '\n') * (N - a.index(first_max) - 1)
print(ans.rstrip('\n'))

Measured memory_bytes: 18448
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet};

mod util {
    use std::io::stdin;
    use std::str::FromStr;
    use std::fmt::Debug;

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

    #[allow(dead_code)]
    pub fn get<T: FromStr>() -> T
        where <T as FromStr>::Err: Debug
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    }

    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
        where <T as FromStr>::Err: Debug
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }
}

fn main() {
    util::get::<usize>();
    let a: Vec<usize> = util::gets();

    if match a.iter().max().unwrap() - a.iter().min().unwrap() {
           0 => a[0] == a.len() - 1 || 2 * a[0] <= a.len(),
           1 => {
               let _min = a.iter().cloned().min().unwrap();
               let x = a.iter().filter(|&&t| t == _min).count();
               let y = a.len() - x;
               x <= _min && 2 * (_min + 1 - x) <= y
           }
           _ => false,
       } {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 6524
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;



int main(){
    ll n;
    string s;
    cin>>n>>s;
    vector<ll> cnt(n,0);
    for(int i=0;i<n;i++){if(s[i]=='.'){cnt[i]++;}}
    for(int i=1;i<n;i++){cnt[i]+=cnt[i-1];}
    ll ans=min(cnt.back(),n-cnt.back());
    for(int i=0;i+1<n;i++){
        ans=min(ans,i+1-cnt[i]+cnt.back()-cnt[i]);
    }
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 2180