akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<vector>
#include<stdbool.h>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<set>
#include<string>
#include<stdlib.h>
typedef long long ll;
using namespace std;

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

Measured memory_bytes: 256
a, b, c = map(int, input().split())
if a * c <= b:
    print(c)
if a * c > b:
    print(b // a)
#h
# 
# 
# 
# e
# d
# h
# h
# r
# h
# b
# h
# cr
# h
# c
# b
# r
# y

Measured memory_bytes: 9156
import sys
input = sys.stdin.readline

N = int(input())
res = 0
ab = [list(map(int, input().split())) for _ in range(N)]
ab.reverse()
for i in range(N):
  a, b = ab[i][0], ab[i][1]
  if b != 1 and (b - ((a + res) % b)) % b > 0:
    res += b - ((a + res) % b)
print(res)

Measured memory_bytes: 56284
n = int(input())
num_list = sorted([ int(v) for v in input().split() ])
count_list = [0 for i in range(10**5+1)]

for i in num_list:
    count_list[i] += 1

def eating(x):
    if x % 2 == 0:
        return 2
    else:
        return 1
count_list = [ eating(i) for i in count_list if i > 0 ]


if count_list.count(2) % 2 == 0:
    print(len(count_list))
else:
    print(len(count_list)-1)

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
//const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

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

mint comb(int n,int a){
  mint x=1,y=1;
  rep(i,a){
    x*=n-i;
    y*=i+1;
  }
  return x/y;
}

int main(){
  int n,k;
  cin >> n >> k;
  
  if(n==k){
    cout << 1 << endl;
    rep(i,k-1) cout << 0 << endl;
  }
  else{
    rep(i,k){
      if(i+1<=(n+1)/2){
      mint ans=comb(k-1,i) * comb(n-k+1,i+1);
      cout << ans << endl;
      }
      else cout << 0 << endl;
    }
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<deque>
#include<tuple>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cstdint>
#include<unordered_map>
#include<sstream>
#include<boost/multiprecision/cpp_int.hpp>

#define rep(i, n) for(int i = 0; i < ( int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define vi vector<int>
#define vll vector<ll>
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define pb push_back

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

ll M = 1000000007;

typedef pair<int, int> P;

bool ps1(const P& element1, const P& element2)
{//first昇順
	return element1.first < element2.first;
}
bool ps2(const P& element1, const P& element2)
{//first降順
	return element1.first > element2.first;
}
bool ps3(const P& element1, const P& element2)
{//second昇順
	return element1.second < element2.second;
}
bool ps4(const P& element1, const P& element2)
{//second降順
	return element1.second > element2.second;
}


int main()
{
	int n,x;
	cin >> n >> x;
	vector<int>l (n);
	int d = 0;
	int count = 1;
	rep(i, n) {
		cin >> l[i];
		d += l[i];
		if (d <= x) {
			count++;
		}
		else { break; }
	}
	cout << count << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
using ll = long long;
using namespace std;
const int INF32       = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7        = 1'000'000'007;
const int MOD9        = 1'000'000'009;
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;
}

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

    int N, A, B;
    cin >> N >> A >> B;
    string s;
    cin >> s;

    int over = 0, dom = 0;
    REP(i, s.size()) {
        if (s[i] == 'a')
            dom++;
        if (s[i] == 'b')
            over++;
    }
    int mx  = A + B;
    int cnt = 0, ovcnt = 0;
    auto yes = []() { std::cout << "Yes" << '\n'; };
    auto no  = []() { std::cout << "No" << '\n'; };
    REP(i, s.size()) {
        if (s[i] == 'a' && cnt < mx) {
            yes();
            cnt++;
        } else if (s[i] == 'b' && cnt < mx && ovcnt < B) {
            yes();
            cnt++;
            ovcnt++;
        } else
            no();
    }

    return 0;
}

Measured memory_bytes: 848
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define LIM 1000000
 
bool is_prime[LIM+10];
 
int main(){
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
 
    for(int p=2;p*p<=LIM;p++)if(is_prime[p]){
        for(int k=p*p;k<=LIM;k+=p)is_prime[k] = false;
    }
 
    vector<int> primes;
    for(int i=2;i<=LIM;i++)if(is_prime[i])primes.push_back(i);
 
    int n;
    while(cin >> n && n){
        int pay = 0;
        for(int i=0;i<n;i++){
            int p, m;
            cin >> p >> m;
 
            pay += upper_bound(primes.begin(), primes.end(), p + m) - lower_bound(primes.begin(), primes.end(), p - m) -  1;
        }
 
        cout << pay << endl;
    }
    return 0;
}

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

typedef long long int ll;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define sz(x) int(x.size())
const ll mod = 1000000007;
const ll INF = 10010010010010010;


int main() {
    string s,t; cin >> s >> t;
    int ans = 0;
    rep(i,3) {
        if (s[i] == t[i]) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3604
#include<iostream>
#include<iomanip>
#include<cassert>
#include<math.h>
#include<complex>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;

ll N,K;
ll A[200010];
ll depth[200010];
P SetDepth(ll n,ll p){
    if(depth[n]!=-1)return P(n,p);
    depth[n]=depth[p]+1;
    return SetDepth(A[n],n);
}
int main(){
    cin>>N>>K;
    for(ll i=0;i<N;i++){
        cin>>A[i];A[i]--;
    }
    for(ll i=0;i<N;i++)depth[i]=-1;
    depth[0]=0;
    P np=SetDepth(A[0],0);
    ll n=np.first,p=np.second;
    ll cycleSize=depth[p]-depth[n]+1;
    if(K>200000){
        K%=cycleSize;
        while(K<depth[n])K+=cycleSize;
    }
    
    ll ans=0;
    for(ll i=0;i<K;i++){
        ans=A[ans];
    }
    cout<<ans+1<<endl;
    return 0;
}


Measured memory_bytes: 6716
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;

int n;

int main(void){
	stack<int> s;
	char c;
	while(scanf("%c",&c)!=EOF){
		if(c=='+'){
			int a=s.top();
			s.pop();
			int b=s.top();
			s.pop();
			s.push(a+b);
		}
		if(c=='-'){
			int a=s.top();
			s.pop();
			int b=s.top();
			s.pop();
			s.push(b-a);
		}
		if(c=='*'){
			int a=s.top();
			s.pop();
			int b=s.top();
			s.pop();
			s.push(a*b);
		}
		if(c>='0' && c<='9'){
			int d=c-'0';
			while(1){
				scanf("%c",&c);
				if(c>='0' && c<='9')d=d*10+(c-'0');
				else break;
			}
			s.push(d);
		}else scanf("%*c");
	}
	printf("%d\n",s.top());
	return 0;
}



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

using namespace std;

int main(){
	int n, w, d;
	while(cin >> n >> w >> d){
		vector< pair<int, int> > vp(n);
		for(int i=0;i<n;i++){
			int x, y; char f;
			cin >> x >> y >> f;
			int a, b;
			if(f == 'S'){
				a = x;
				b = y;
			} else if(f == 'E'){
				a = w+y;
				b = w-x;
			} else if(f == 'N') {
				a = w+d+w-x;
				b = d-y;
			} else if(f == 'W'){
				a = 2*w+d+d-y;
				b = x;
			}
			vp[i].first = (a-b+2*(w+d))%(2*(w+d));
			vp[i].second = (a+b)%(2*(w+d));
		}
		sort(vp.begin(),
				vp.end(),
				[](const pair<int, int>& a, const pair<int, int>& b){
					return a.second == b.second ? a.first < b.first : a.second < b.second;
				}
			);
		int res = n;
		for(int i=0;i<n;i++){
			int cnt = 1, pos = vp[i].second;
			for(int j=1;j<n;j++){
				pair<int, int> pr = vp[(i+j)%n];
				if(pr.first < pr.second ? (pr.first <= pos && pos <= pr.second) : (pos <= pr.second || pr.first <= pos)) continue;
				pos = pr.second;
				++cnt;
			}
			res = min(res, cnt);
		}
		cout << res << endl;
	}
}

Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
int main() {/*
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif */
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);  
    int n;
    cin>>n;
    int a[n];
    int l=-1;
    int s=0;
    for(int i=0;i<n;i++){
    	cin>>a[i];
    	l=max(l,a[i]);
    	s+=a[i];
    } 
    if(l < s-l) cout<<"Yes";
    else cout<<"No";
}

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

signed main() {
	string s;
	cin >> s;
	int ans = 0;
	int cou=0;
	rep(i, s.size()){
		if(s[i] == 'A' || s[i] == 'C'||s[i]=='G'||s[i]=='T'){
			cou++;
			ans = max(ans, cou);
		}
		else cou = 0;
	}
	cout << ans << endl;
	
	return 0;			
}

Measured memory_bytes: 3584
from collections import defaultdict

#入力、初期化
N = int(input())
D1 = defaultdict(int)
D2 = defaultdict(int)
A = 0
for i in range(N):
	a = int(input())
	A = A ^ a
	D1[a ^ (a - 1)] += 1

#計算
n = A.bit_length()
for i in range(n):
	if A >= 2 ** (n - i - 1):
		D2[2 ** (n - i) - 1] += 1
		A = A ^ (2 ** (n - i) - 1)

#判定
judge = "Yes"
for i in D2:
	if D2[i] > D1[i]:
		judge = "No"
		break
#出力
if judge == "No":
	print(-1)
else:
	print(len(D2))

Measured memory_bytes: 3444
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ABC153_a solver = new ABC153_a();
        solver.solve(1, in, out);
        out.close();
    }

    static class ABC153_a {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int H = in.nextInt();
            int A = in.nextInt();
            out.println((int) Math.floor(H / A) + ((H % A != 0) ? 1 : 0));
        }

    }
}



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

int n, a[100];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cout << a[n - 1];
	for (int i = n - 2; i >= 0; i--) {
		cout << " " << a[i];
	}
	cout << endl;
}


Measured memory_bytes: 3076
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    String s1 = scan.next(),s2=scan.next();
    int count = 0;
    for(int i=0;i<s1.length();i++){
      if(s1.charAt(i)!=s2.charAt(i))count++;
    }
    System.out.println(""+count);
  }
}

Measured memory_bytes: 43260
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 107;
int n,a[maxn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    int sum1 = 0;
    int sum2 = 0;
    for(int i=1;i<=n;i+=2)
    {
        sum1+=a[i];
    }
    for(int i=2;i<=n;i+=2)
    {
        sum2+=a[i];
    }
    if(n&1)cout<<sum1-sum2<<endl;
    else cout<<sum2-sum1<<endl;
    return 0;
}


Measured memory_bytes: 256
/* Ahmed Maher ( Acro_14 ) */
#include <bits/stdc++.h>
typedef long long ll;
const ll oo = 0x3f3f3f3f;
int const N = 1e5+5;
using namespace std;
//string alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
//string BN(ll x){bool f=0;string Bn;int i=62;while(i--){if ((ll)x & (1LL << i)){Bn+='1';f=1;}else{if(f)Bn+='0';}}return Bn;}//Decimal to Binary converter
 int n = N;
int ans[664580];
int *Seive(){
    vector<bool> good(n);
    for(int i = 1; i < n; i++){
        good[i] = true;
    }
    good[1] = false;
    for(ll i = 2; i < n; i++){
        if(good[i]){
            // i = 1e7
            for(ll j = 1LL * i * i; j < n; j += i){
                good[j] = false;
            }
        }
    }
    int j=0;
    for(int i = 1; i < n; i++){
        if(good[i]){
           ans[j]=i;
           j++;
        }
    }
    return ans;
/*to print */
//    int *p;
//    p=Seive();
//      for(int i=0;i<10e7;i++){
//      cout << *(p + i) << endl;
//      system("pause");
//   }
/*end of print*/
}

int main()
{
    int *p,arr[N];
    p=Seive();
    for(int i=0;i<N;i++)arr[i] = *(p + i);
    int x;
    cin>>x;
        for (int i=0;i<N;i++){
            if (arr[i]>x && arr[i-1]<x){cout<<arr[i]<<endl;break;}
            else if (arr[i]==x){cout<<x<<endl;break;}
        }
}

//       int anss[t+1];
//            anss[j]=ans;
//     for(int j=1;j<=t;j++) printf("Case %d: %d\n",j,anss[j]);


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

int main(){
  string s;
  cin >> s;
  int len = s.length();
  for(char c = 'a'; c <= 'z'; c++){
    FOR(i,0,len){
      if(i + 1 < len){
        if(s[i]==c && s[i+1]==c){
          cout << i + 1 << " " << i + 2 << endl;
          return 0;
        }
      }
      if(i + 2 < len){
        if(s[i]==c && s[i+2]==c){
          cout << i + 1 << " " << i + 3 << endl;
          return 0;
        }
      }
    }
  }
  cout << -1 << " " << -1 << endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;
static const ll LOGN=55;


int main(void) {
  ll N;
  cin >> N;
  ll i;
  map<string, ll> mp;
  ll t[1111];
  ll sum[1111]={};
  
  string s;
  for(i=1; i<=N; i++) {
    cin >> s >> t[i];
    mp[s]=i;
    sum[i]=sum[i-1]+t[i];
  }
  
  string X;
  cin >> X;
  pt(sum[mp[s]]-sum[mp[X]]);
  
}





Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <time.h>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define reps(x,c) for(auto x:c)
#define all(x) begin(x), end(x)
#define pb(a) emplace_back(a) 
#define mp(a,b) make_pair((a),(b))
#define pl pair<ll,ll>
#define INF 2147483600
#define MOD 1000000007
#define fi first
#define se second
#define dbg(x) cout << #x"="<< (x) << endl
#define dbgv(x) cout<<#x<<endl;reps(y,x){cout<<y<<" ";}cout<<endl

ll dist_town[10][10];
const int V=210;
using P=pair<int,int>;
vector<P> G[V];
int dist[V];
bool used[V];
void dijkstra(int s){
  fill_n(dist,V,INF);
  fill_n(used,V,false);
  priority_queue<P,vector<P>,greater<P>> q;
  q.push(P(0,s));
  while(!q.empty()){
    int d; int t;
    tie(d,t)=q.top();q.pop();
    if(used[t])continue;
    used[t]=true;dist[t]=d;
    for(P e: G[t]){
      if(dist[e.second]<=d+e.first)continue;
      q.push(P(d+e.first,e.second));
    }
  }
}

int main(){
  ll n,m,r;cin>>n>>m>>r;
  vector<ll> town(r);
  rep(i,r){
    cin>>town[i];
  }
  ll a,b,c;
  rep(i,m){
    cin>>a>>b>>c;
    G[a].emplace_back(c,b);
    G[b].emplace_back(c,a);
  }

  rep(i,r){
    dijkstra(town[i]);
    rep(j,r){
      dist_town[i][j]=dist[town[j]];
    }
  }

  vector<ll> A;
  rep(i,r){
    A.pb(i);
  }
  ll temp=0,ans=INF;
  do{
    temp=0;
    rep(i,A.size()-1){
      temp+=dist_town[A[i+1]][A[i]];
    }
    ans=min(temp,ans);
  } while( next_permutation(all(A))); 

  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    int n; cin>>n;
    vector<ll> p(n+1), q(n+1);
    rep(i,n+1) cin>>p[i];
    q[n]=p[n];
    rep(i,n) q[n-i-1]=q[n-i]+p[n-i-1];
    vector<ll> an(n+1);
    an[0]=1;
    if(p[0]==1){
        if(n==0){
            cout<<1<<endl;
            return 0;
        }
        else{
            cout<<-1<<endl;
            return 0;
        }
    }
    else if(p[0]>1){
        cout<<-1<<endl;
        return 0;
    }
    rep(i,n){
        ll a=an[i]-p[i];
        if(a<=0){
            if(i<n){
                cout<<-1<<endl;
                return 0;
            }
        }
        else{
            an[i+1]=min(a*2,q[i+1]);
        }
    }
    if(an[n]!=p[n]){
        cout<<-1<<endl;
        return 0;
    }
    ll ans=0;
    rep(i,n+1) ans+=an[i];
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 5624
#include<stdio.h>
int main(void)
{
    int a,i,j;
    scanf("%d",&a);
    int n[9][9];
    for(i=0;i<9;i++){
        for(j=0;j<9;j++){
            n[i][j]=(i+1)*(j+1);
        }
    }

    for(i=0;i<9;i++){
        for(j=0;j<9;j++){
            if(a==n[i][j]){
                printf("Yes\n"); return 0;
            }
        }
    }

    printf("No\n");
    return 0;
}

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

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;

#define rep(idx, N) for (u64 idx = 0; idx < N; idx++)

int main() {
  u64 d, t, s;
  cin >> d >> t >> s;

  if (s * t >= d)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 3600
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<ctype.h>
#include<stdio.h>
#include<set>
#include<vector>
#include<map>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<numeric>
#include<string>
typedef long long ll;
using namespace std;

ll gcd(ll a, ll b){
if(a<b){return gcd(b,a);}
else if(a%b){return gcd(b,a%b);}
else{return b;}
}
int main(){
  string S;
  cin>>S;
  ll N=S.size();
  cout<<S.substr(0,N-8)<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
long long mod = 1000000007;
#define REP(i, n) for (long long i = 0; i < (n); i++)
#define rep(i, a, n) for (long long i = a; i < (n); i++)
long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return (t * t) % mod;
    } else {
        return (modpow(m, n - 1) * m) % mod;
    }
}

template <typename A, size_t N, typename T> void Fill(A (&array)[N], const T& val) {
    std::fill((T*)array, (T*)(array + N), val);
}
// long long mod = 998244353;
long long power(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return t * t;
    } else {
        return modpow(m, n - 1) * m;
    }
}

long long moddiv(long long a, long long b) { return (a * modpow(b, mod - 2)) % mod; }

const ll INF = 1LL << 60;

void print_binary(long long a) {
    for (int i = 31; i >= 0; i--) {
        cout << (a >> i & 1);
    }
    cout << endl;
}

ll nCkmod(ll n, ll k) {
    ll denomi = 1;
    for (int i = n; i > n - k; i--) {
        denomi *= i;
        denomi %= mod;
    }
    ll numera = 1;
    REP(i, k) {
        numera *= (i + 1);
        numera %= mod;
    }
    return moddiv(denomi, numera);
}
map<ll, ll> cnt;
void primeFactors(long long n) {
    while (n % 2 == 0) {
        cnt[2]++;
        n = n / 2;
    }
    for (int i = 3; i <= sqrt(n); i = i + 2) {
        while (n % i == 0) {
            cnt[i]++;
            n = n / i;
        }
    }
    if (n > 2) {
        cnt[n]++;
    }
}
int main() {
    ll n;
    cin >> n;
    ll c3 = 0, c5 = 0, c15 = 0, c25 = 0, c75 = 0;
    rep(i, 2, n + 1) { primeFactors(i); }
    for (auto x : cnt) {
        if (x.second >= 74) {
            c75++;
            c25++;
            c15++;
            c5++;
            c3++;
        } else if (x.second >= 24) {
            c25++;
            c15++;
            c5++;
            c3++;
        } else if (x.second >= 14) {
            c15++;
            c5++;
            c3++;
        } else if (x.second >= 4) {
            c5++;
            c3++;
        } else if (x.second >= 2) {
            c3++;
        }
    }
    ll ans = 0;
    ans += c75;
    ans += (c3 - 1) * c25;
    ans += (c5 - 1) * c15;
    ans += (c3 - 2) * c5 * (c5 - 1) / 2;
    cout << ans << endl;
}

Measured memory_bytes: 3620
#include <iostream>

using namespace std;

int main()
{
    char b;
    cin>>b;
    if(b=='A')
    {
        cout<<"T";
    }
    else if(b=='T')
    {
        cout<<"A";
    }
    else if(b=='C')
    {
        cout<<"G";
    }
    else if(b=='G')
    {
        cout<<"C";
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<string>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<climits>
using namespace std;
#define rep(i, j) for(int i = 0; i < j; i++)
#define f(i, k, j) for(int i = k; i < j; i++)
#define P pair<int, int>
const int INF = INT_MAX - 10;

int n;
vector< vector<int> > field, dp;

int check1(int j, int i){
    while(field[j][i] == 1) i++;
    return i - 1;
}

int check2(int j, int i){
    while(field[j][i] == 2) i--;
    return i;
}

int main(){
    while(cin >>n && n){
        field.clear(); dp.clear();
        field = vector< vector<int> >(2);
        rep(i, 2) field[i] = vector<int>(n);
        dp = vector< vector<int> >(2);
        rep(i, 2) dp[i] = vector<int>(n, INF);
        dp[0][0] = 0; dp[1][0] = 0;
        rep(j, 2) rep(i, n) cin >>field[j][i];

        while(true){
            bool endFlg = true;
            rep(i, n){
                rep(j, 2){
                    //cout <<j <<", " <<i <<endl;
                    if(field[j][i] == 1 && field[j][i + 1] == 1){
                        int bef = dp[j][check1(j, i)];
                        dp[j][check1(j, i)] = min(dp[j][check1(j, i)], dp[j][i]);
                        if(bef != dp[j][check1(j, i)]) endFlg = false;
                        //cout <<"dp[" <<j <<"][" <<check1(j, i) <<"] = " <<dp[j][check1(j, i)] <<endl;
                    }
                    else if(field[j][i] == 2){
                        int bef = dp[j][check2(j, i)];
                        dp[j][check2(j, i)] = min(dp[j][check2(j, i)], dp[j][i]);
                        if(bef != dp[j][check2(j, i)]) endFlg = false;
                        //cout <<"dp[" <<j <<"][" <<check2(j, i) <<"] = " <<dp[j][check2(j, i)] <<endl;
                    }else{
                        rep(k, 3){
                            int nj = (j + 1) % 2, ni = i + k;
                            if(ni >= n) continue;
                            int bef = dp[nj][ni];
                            dp[nj][ni] = min(dp[nj][ni], dp[j][i] + 1);
                            if(bef != dp[nj][ni]) endFlg = false;
                            //cout <<"dp[" <<nj <<"][" <<ni <<"] = " <<dp[nj][ni] <<endl;

                        }
                    }
                }
            }
            if(endFlg) break;
        }
        if(field[0][n - 1] == 2) dp[0][n - 1] = INF;
        if(field[1][n - 1] == 2) dp[1][n - 1] = INF;
        int ans = min(dp[0][n - 1], dp[1][n - 1]);
        if(ans == INF) cout <<"NA" <<endl;
        else cout <<ans <<endl;
        //rep(i, 2){
        //    rep(j, n){
        //        cout <<dp[i][j] <<" ";
        //    }
        //    cout <<endl;
        //}
    }

    return 0;
}

Measured memory_bytes: 1216
a,b,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
xyc = [list(map(int,input().split())) for i in range(m)]

ans = min(a) + min(b)
for i in range(m):
    ans = min(ans,a[xyc[i][0]-1]+b[xyc[i][1]-1]-xyc[i][2])
print(ans)

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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pl;

const int INT_INF = 2147483646;
const ll LL_INF = 9223372036854775807;
const double PI=3.1415926535897932;

bool SecondCompare(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}
 
bool SecondCompareDes(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second>b.second;
}

ll minll(ll a, ll b){
    if(a >= b)  return b;
    else    return a;
}

ll maxll(ll a, ll b){
    if(a >= b)  return a;
    else    return b;
}

ll gcd(ll a, ll b){
    ll tmp;
    if(a%b == 0){
        return b;
    }
    else{
        return gcd(b, a%b);
    }
}


const ll SIZE = 1e5+10;
ll r;

int main(){
    cin >> r;
    ll ans = r*r;

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
typedef long long ll;

int main(){
    ll a, b;
    cin >> a >> b;
    ll ab;
    if(b < 10){
        ab = a * 10 + b;
    }else if(b < 100){
        ab = a * 100 + b;
    }else{
        ab = a * 1000 + b;
    }
    for(ll i = 1; i * i <= ab; ++i){
        if(i * i == ab){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}


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

int main(){
    int N;
    cin >> N;
    vector<int> vec(N);
    rep(i, N){
        cin >> vec.at(i);
    }

    int tmp;
    rep(i, N){
        for (int j = i + 1; j < N; j++)
        {
            if(vec.at(i) > vec.at(j)){
                tmp = vec.at(i);
                vec.at(i) = vec.at(j);
                vec.at(j) = tmp;
            }
        }
    }
    int current = 0;
    int count = 0;
    rep(i, N){
        if(current < vec.at(i)){
            current = vec.at(i);
            count += 1;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 3556
#include <bits/stdc++.h>
#define v vector
#define r resize
using namespace std;typedef long long l;v<bool> s;v<l> a,b; v<v<l>> g;void d(l e,l c){if(s[c])return;s[c]=1;a[c]=e+b[c];for(l h:g[c])d(a[c],h);return;}l n,q,x,y;int main(){cin>>n>>q;g.r(n);b.r(n);s.r(n);a.r(n);for(int i=0;i<n-1;i++){l x,y;cin>>x>>y;g[x-1].push_back(y-1);g[y-1].push_back(x-1);}for(int i=0;i<q;i++){cin>>x>>y;b[x-1]+=y;}d(0,0);for(int i=0;i<n;i++)cout<<a[i]<<" ";}

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

int main() {
  int n, m;
  while (true) {
    cin >> n >> m;
    if (n==0 && m==0) {
      break;
    }
    int a[n];
    for (int i=0; i<n; i++) {
      cin >> a[i];
    }
    int ans = -INT_MAX;
    for (int i=0; i<n; i++) {
      for (int j=0; j<n; j++) {
	if (i!=j && a[i]+a[j]<=m) {
	  ans = max(ans,a[i]+a[j]);
	}
      }
    }
    if (ans<0) {
      cout << "NONE" << endl;
    } else {
      cout << ans << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod = 1e9 + 7;
#define pival 3.14159265358979323846264338327950L
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pqq priority_queue
#define all(a) a.begin(), a.end()
#define sz(a) (ll)(a.size())
#define endl '\n'
#define DEBUG
#ifdef DEBUG
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1)
    {
        cerr << name << " = " << arg1 << endl;
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args)
    {
        const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " = " << arg1 << " || ";
        __f(comma+1, args...);
    }
#else
#define debug(...)
#endif
template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ; ";
    return os << "}";
}
template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
    return os << "[ " << p.first << ", " << p.second << "]" ;
}
ll power(ll x, ll y, ll p)
{ 
    ll res = 1;  
    x = x % p;
    while (y > 0) { 
        if (y & 1) res = (res * x) % p; 
        y = y >> 1;
        x = (x * x) % p;   
    } 
    return res; 
}
const ll L = 1e5 + 5;
vector <ll> ad[L];
ll vis[L];
ll val[L];
ll F;
void bfs(ll ind)
{
	deque <ll> q;
	vis[ind] = 1;
	q.push_front(ind);
	while(!q.empty())
	{
		ll p = q.front();
		q.pop_front();
		for(ll v : ad[p])
		{
			if(!vis[v])
			{
				vis[v] = 1;
				if (val[v] == 0) {
					val[v] = p;
				}
				else {
					F = 1;	
				}
				q.push_back(v);
			}
		}
	}
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 	ll n, m, u, v;
 	cin >> n >> m;
 	while (m--) {
 		cin >> u >> v;
 		ad[u].pb(v);
 		ad[v].pb(u);
 	}
 	bfs(1); 
 	for (ll i = 2; i <= n; i++) {
 		if (val[i] == 0) F = 1;
 	}
 	if (F == 1) {
 		cout << "No" << endl;
 		return 0;
 	} 
 	else {
 		cout << "Yes" << endl;
 		for (ll i = 2; i <= n; i++) {
 			cout << val[i] << endl;
 		}
 	}
	return 0;
}

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

const int M=1e5+5;

int n,t,ans=0,x,y;

int main(){
	scanf("%d%d",&n,&t);
	scanf("%d",&x);
	for(int i=2;i<=n;i++){
		scanf("%d",&y);
		ans+=min(y-x,t);
		x=y;
	}
	ans+=t;
	printf("%d\n",ans);
}

Measured memory_bytes: 256
// B.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	int ans = 0;
	for (int i = 1; i < n - 1; ++i) {
		ans += (a[i] < a[i - 1] && a[i] > a[i + 1]) || (a[i] < a[i + 1] && a[i] > a[i - 1]);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
X, K, D = map(int, input().split())

if abs(X) < (K * D):
    a = abs(X) % D
    b = abs(D - a)
    c = abs(X) // D + 1
    if (K - c) % 2 == 0:
        goal = b
    else:
        goal = a
else:
    goal = abs(X) - ( D * K )

print(goal)

Measured memory_bytes: 9144
use proconio::{input, fastout};

#[fastout]
fn main() {
    input!{
        n: usize,
        v: [i32; n],
	c: [i32; n],
    }
    let mut ret = 0;
    for i in 0..n {
	if v[i] - c[i] > 0 {
	    ret += v[i] - c[i]
	}
    }
    println!("{}", ret)
}


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

using namespace std;

const int MX = 500;
int a[MX][MX];
vector<pair<int,int> > b[MX];
bool dead[MX];

int main() {
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> a[i][j];
			a[i][j]--;
		}
		b[ a[i][0] ].push_back({i, 0});
	}
	
	int ans = n;
	for(int q = 1; q < m; q++){
		int p = 0;
		while(dead[p]) p++;
		for(int i = p + 1; i < m; i++)
			if(b[i].size() > b[p].size() && !dead[i]) p = i;
			
		ans = min(ans, int(b[p].size()));
		
		dead[p] = true;
		
		for(int z = 0; z < b[p].size(); z++){
			int i = b[p][z].first;
			int pos = b[p][z].second;
			while(dead[ a[i][pos] ]) pos++;
			b[ a[i][pos] ].push_back( {i, pos} );
		}
		b[p].resize(0);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2048
#include<stdio.h>
#include<stdlib.h>
int H[2000000000];

int parent(int i){
  return i/2;
}

int left(int i){
  return 2*i;
}

int right(int i){
  return 2*i + 1;
}

void print(int *H,int i,int n){
  int l,r,p;
  l=left(i);
  r=right(i);
  p=parent(i);
  printf("node %d: key = %d, ",i,H[i]);
  if(i==1){
    if(l<=n){
      printf("left key = %d, ",H[l]);
    }
    if(r<=n){
      printf("right key = %d, ",H[r]);
    }

  }
  else {
    if(p<=n){
      printf("parent key = %d, ",H[p]);
    }
    if(l<=n){
      printf("left key = %d, ",H[l]);
    }
    if(r<=n){
      printf("right key = %d, ",H[r]);
    }


  }
  printf("\n");
}

void maxHeapify(int *H,int i,int n){
  int largest,temp,l,r;
  l=left(i);
  r=right(i);
  if(l<=n&&(H[l] > H[i])){
    largest = l;
}
  else{
    largest=i;
}
  if(r <= n&&(H[r] > H[largest])){
    largest = r;
}
  if(largest!=i){
    temp=H[i];
    H[i]=H[largest];
    H[largest]=temp;
    maxHeapify(H,largest,n);
}
}

void buildMaxHeap(int *H,int n){
  int i;
  for(i=n/2;i>=1;i--){
    maxHeapify(H,i,n);
}
}

int main(){
  int i,n;
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&H[i]);
  }
  buildMaxHeap(H,n);
  /* for(i=1;i<=n;i++){
    print(H,i,n);
    }*/
  for(i=1;i<=n;i++){
    printf(" %d",H[i]);
}
  printf("\n");
  return 0;
}



Measured memory_bytes: 3684
#include <bits/stdc++.h>
#define endl '\n'
#define LL long long
#define LD long double
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define debug(x) cerr << #x << " is " << x << endl;
using namespace std;
int const MAXN = 3000 + 5;
int n, m, k;
LL dp[MAXN][MAXN][4];
int a[MAXN][MAXN];
bool valid(int x, int y){
    return x >= 0 && x < n && y >= 0 && y < m;
}
LL solve(int x, int y, int have){
    if(!valid(x,y)) return -1e18;
    if(x == n -1 && y == m - 1){
        if(have) return a[x][y];
        return 0;
    }
    LL & ret = dp[x][y][have];
    if(ret != -1) return ret;
    ret = 0;
    if(have){
        ret = a[x][y] + max(solve(x + 1, y, 3), solve(x, y + 1, have - 1));
    }
  
    return ret = max(ret,max(solve(x + 1, y, 3), solve(x, y + 1, have)));
}
int main(){
    ios_base::sync_with_stdio (0),cin.tie(0);
    cin >> n >> m >> k;
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i < k; i++){
        int x, y, v;
        cin >> x >> y >> v;
        x--, y--;
        a[x][y] = v;
    }
    cout << solve(0,0, 3);
}

Measured memory_bytes: 321604
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


inf = float('inf')


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_list_of_int():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


def get_root(root, x):
    y = x
    while y != root.get(y, y):
        y = root.get(y, y)
    z = x
    while z != root.get(z, z):
        root[z] = y
        z = root.get(z, z)
    return y


# inputs
N, M = 0, 0
A, B = [], []


def set_inputs():
    global N, M, A, B
    N, M = get_list_of_int()
    for _ in range(M):
        a, b = get_list_of_int()
        A.append(a)
        B.append(b)


def main():
    set_inputs()
    nc2 = N * (N - 1) // 2
    inconv = [0] * M
    conns = 0
    root = dict()
    conns_dict = defaultdict(int)
    for i in range(1, M+1):
        inconv[M-i] = nc2 - conns
        if i == M:
            break
        a, b = A[M-i], B[M-i]
        a_root = get_root(root, a)
        a_conns = conns_dict[a_root]
        b_root = get_root(root, b)
        b_conns = conns_dict[b_root]
        if a_conns == 0 and b_conns == 0:
            root[a] = a
            root[b] = a
            conns_dict[a] = 2
            conns += 1
        elif a_conns == 0:
            root[a] = b_root
            conns_dict[b_root] = b_conns + 1
            conns += b_conns
        elif b_conns == 0:
            root[b] = a_root
            conns_dict[a_root] = a_conns + 1
            conns += a_conns
        elif a_root != b_root:
            root[b_root] = a_root
            conns_dict[a_root] = a_conns + b_conns
            conns += a_conns * b_conns
    for i in inconv:
        print(i)


if __name__ == '__main__':
    main()


Measured memory_bytes: 94168
n=int(input())
a=list(map(int,input().split()))
dict={}
for i in range(n):
  if a[i] not in dict:
    dict[a[i]]=1
  else:
    dict[a[i]]+=1
ans=0
for i in dict:
  if dict[i]<i:
    ans+=dict[i]
  elif dict[i]==i:
    continue
  else:
    ans+=dict[i]-i
print(ans)

Measured memory_bytes: 21676
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
using ll=long long;

int main(){
    int N;
    cin >> N;
    ll a[N+10];
    ll count = 0;
    for(int i = 0; i < N; ++i){
        cin >> a[i];
        ll tmp = a[i];
        while(tmp % 2 == 0){
            tmp /= 2;
            count++;
            //cout << tmp << endl;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 384
import std.stdio,
       std.string,
       std.conv;

void main() {
  int[][] c;
  for (int i = 0; i < 3; i++) {
    c ~= to!(int[])(readln.chomp.split);
  }

  int[3] a, b;
  // a[0] = 0 と仮定
  foreach (i, e; c[0]) {
    b[i] = e;
  }
  for (int i = 1; i < 3; i++) {
    a[i] = c[i][i] - b[i];
  }

  bool f = true;
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      // writeln(c[i][j], " == ", a[i], " + ", b[j]);
      f = f & (c[i][j] == a[i] + b[j]);
    }
  }

  writeln(f ? "Yes" : "No");
}


Measured memory_bytes: 256
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //System.setIn(Main.class.getResourceAsStream("input"));
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int h = sc.nextInt();
        int w = sc.nextInt();
        int n = sc.nextInt();
        int max = Math.max(w,h);
        int result = n/max + (n%max == 0 ? 0 : 1);
        System.out.println(result);
    }


    private static int nextInt(Scanner sc) {
        return Integer.valueOf(sc.nextLine());
    }
    private static int[] toArray(String text) {
        return Arrays.stream(text.split("\\s")).mapToInt(Integer::valueOf).toArray();
    }

}

Measured memory_bytes: 21716
//

fun main() {
    abc099c()
}

fun abc099c() {
    val n = readLine()!!.toInt()
    val pay = mutableSetOf(1, 6, 9)
    var six = 6
    var nine = 9
    while (six <= n || nine <= n) {
        six *= 6
        if (six <= n) pay.add(six)
        nine *= 9
        if (nine <= n) pay.add(nine)
    }
    var step = 1
    var base = mutableSetOf(0)
    while (base.isNotEmpty()) {
        val next = mutableSetOf<Int>()
        for (b in base) {
            for (p in pay) {
                val t = b + p
                if (t > n) continue
                if (t == n) {
                    println(step)
                    return
                }
                next.add(t)
            }
        }
        step++
        base = next
    }
}


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



int gcb(int a, int b){
    if(a < b){
        int x = a;
        a = b;
        b = x;
    }
    int amari = a % b;
    if(amari == 0) return b;

    return gcb(b, amari);
}
int gcb_3(int a, int b, int c){
    return gcb(gcb(a, b), c);
}

int main(){
    int n;cin >> n;
    ll ans = 0;
    rep(i, n)rep(j, n)rep(k, n){
        ans += gcb_3(i, j, k);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin>>n>>k;
  int a[n];
  int b[n];
  for(int i=0;i<n;i++){
    cin>>a[i];
    b[i]=INT_MAX;
  }
  b[0]=0;
  for(int i=1;i<n;i++){
	  for(int j=1;j<=k;j++)
	  if(i-j>=0){
    b[i]=min(b[i-j]+abs(a[i]-a[i-j]),b[i]);
	  }
  }
  cout<<b[n-1];
  
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int c[15][15];
int g[200][200];
typedef int weight;
int n;
int d[200][200];
int ABS(int a){return max(a,-a);}
weight minimum_steiner_tree(const vector<int>& T) {
  const int numT = T.size();
  if (numT <= 1) return 0;
for(int i=0;i<n;i++)for(int j=0;j<n;j++)d[i][j]=99999999;

for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(g[i][j])d[i][j]=1;
for(int i=0;i<n;i++)d[i][i]=0;
  for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        d[i][j] = min( d[i][j], d[i][k] + d[k][j] );

  weight OPT[(1 << numT)][n];
  for (int S = 0; S < (1 << numT); ++S)
    for (int x = 0; x < n; ++x)
      OPT[S][x] = 99999999;

  for (int p = 0; p < numT; ++p) // trivial case
    for (int q = 0; q < n; ++q)
      OPT[1 << p][q] = d[T[p]][q];

  for (int S = 1; S < (1 << numT); ++S) { // DP step
    if (!(S & (S-1))) continue;
    for (int p = 0; p < n; ++p)
      for (int E = 0; E < S; ++E)
        if ((E | S) == S)
          OPT[S][p] = min( OPT[S][p], OPT[E][p] + OPT[S-E][p] );
    for (int p = 0; p < n; ++p)
      for (int q = 0; q < n; ++q)
        OPT[S][p] = min( OPT[S][p], OPT[S][q] + d[p][q] );
  }
  weight ans = 99999999;
  for (int S = 0; S < (1 << numT); ++S)
    for (int q = 0; q < n; ++q)
      ans = min(ans, OPT[S][q] + OPT[((1 << numT)-1)-S][q]);
return ans;
}
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		for(int i=0;i<a;i++)for(int j=0;j<b;j++)scanf("%d",&c[i][j]);
		for(int i=0;i<200;i++)for(int j=0;j<200;j++)g[i][j]=0;
		vector<int>t;
		for(int i=0;i<a*b;i++){
			if(c[i/b][i%b])t.push_back(i);
			for(int j=0;j<a*b;j++){
				if(ABS(i/b-j/b)+ABS(i%b-j%b)==1)g[i][j]=1;
			}
		}
		n=a*b;
		int ret=minimum_steiner_tree(t);
		printf("%d\n",a*b-ret-1);
	}
}

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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define P pair<int,int>
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7;
const ll LINF = 1e18;

//while(x!=0){
            //sum+=x%10;
           // x/=10;
        //}
        //各桁の和

//pair<int,int> p[100000];
//P r[100000];
//cin >> tmp;
//p[i]=make_pair(tmp,i);
//cout << p[i].second+1 << endl;//ペアの右側つまりiを出力

//s.find(w[i])==string::npos
//findの使い方

//for(int i=0;i<n;i++){
   // b[i]=x%2;
    //x/=2;
  //}二進数

long long int n,cnt=0,ans=0,a,b,c,cmp,data,m,h,w,x,y,xcmp,ycmp,sum=0;

string s,ww;

vector<int> z;

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

       cin >> s >> ww;
       if(s==ww){
           Cout("=");
       }
       else if(s<ww){
           Cout("<");
       }
       else{
           Cout(">");
       }
return 0;
}


Measured memory_bytes: 256
S = input()

ans = 0
cnt = 0

for topcodeer in S :
    if topcodeer == "g" :
        if cnt > 0 :
            cnt -= 1
            ans += 1
        else :
            cnt += 1
    else :
        if cnt > 0 :
            cnt -= 1
        else :
            cnt += 1
            ans -= 1

print(ans)


Measured memory_bytes: 3316
#include <iostream>
#include <queue>

int main()
{
    int n, no;
    long long yen, num;
    long long total[4001];
    std::queue<int> que;
    
    for (int i = 0; i < 4001; ++i) {
        total[i] = 0;
    }

    std::cin >> n;
    
    while (n != 0) {
        
        bool update = false;
        /*input*/
        for (int i = 0; i < n; ++i) {
            scanf("%d %lld %lld", &no, &yen, &num);
            total[no] += yen * num;
            que.push(no);
        }
        /*output*/
        while (!que.empty()) {
            if (total[que.front()] >= 1000000) {
                std::cout << que.front() << std::endl;
                update = true;
            }
            total[que.front()] = 0;
            que.pop();
        }
        if (!update) {
            std::cout << "NA" << std::endl;
        }
        std::cin >> n;
    }
    
    return 0;
}

Measured memory_bytes: 1284
<?php
fscanf(STDIN, "%d", $N);
$a = [];
$ans = 0;
for ($i = 0; $i < $N; $i++) {
    fscanf(STDIN, "%d", $a[]);
}
sort($a);
$b = $a;

//Lowから
$low = array_splice($a, 0, ceil($N / 2));
rsort($a);
$high = $a;

$tmp = 0;
for ($i = 0; $i < count($high); $i++) {
    if ($i === 0) {
        $tmp += abs($low[0] - $high[0]);
    } else {
        $tmp += abs($low[$i - 1] - $high[$i]);
    }
}
for ($i = 1; $i < count($low); $i++) {
    $tmp += abs($high[$i - 1] - $low[$i]);
}
$score1 = $tmp;

rsort($b);
//highから
$high = array_splice($b, 0, ceil($N / 2));
sort($b);
$low = $b;

$tmp = 0;
for ($i = 0; $i < count($low); $i++) {
    if ($i === 0) {
        $tmp += abs($high[0] - $low[0]);
    } else {
        $tmp += abs($high[$i - 1] - $low[$i]);
    }
}
for ($i = 1; $i < count($high); $i++) {
    $tmp += abs($low[$i - 1] - $high[$i]);
}
$score2 = $tmp;

printf("%d", max($score1, $score2));


Measured memory_bytes: 19060
import fractions

a, b, k = map(int, input().split())
gcd = fractions.gcd(a, b)
divisor = []
for i in range(int(gcd ** 0.5)):
    if gcd % (i + 1) == 0:
        divisor.append(i + 1)
        if gcd // (i + 1) != i + 1:
            divisor.append(gcd // (i + 1))
divisor.sort(reverse = True)
print(divisor[k - 1])

Measured memory_bytes: 5176