akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>

using std::cin;
using std::cout;
using std::endl;

int main(void) {
	int N,Q,M;
	cin >> N;
	cin >> Q;

	while (N!=0||Q!=0) {
		std::vector<int> count_mem(101);
		int com_date = 102;
		int count = 0;
		for (int i = 0; i < N; i++) {
			cin >> M;
			for (int j = 0; j < M; j++) {
				int date;
				cin >> date;
				count_mem[date]++;
			}
		}
		for (int i = 0; i < 101; i++) {
			if (!(count_mem[i] < Q) && count_mem[i] > count) {
				com_date = i;
				count = count_mem[i];
			}
		}
		if (com_date != 102) {
			cout << com_date << endl;
		}else {
			cout << 0 << endl;
		}

		
		cin >> N;
		cin >> Q;
	}
	return 0;
}

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

int n; //number of stones
int k; //farthest the frog can jump
vector<int> h; //height of the stones
vector<int> dp; //memorize heck

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

	dp.assign(n, INT_MAX);
	
	for(int i=0; i<n; i++){
		int x;
		cin >> x;
		h.push_back(x);
	}

	dp[0] = 0;
	for(int i=0; i<n; i++){
		for(int j=1; j<=k; j++){
			if(i-j>=0){
				dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]));	
			}
		}
	}

	cout << dp[n-1] << "\n";
	
}

Measured memory_bytes: 2168
#include<stdio.h>
#include<string.h>
int main(void)
{
	int a,c,d,e,f;
	char b[3];
	c=0;
	d=0;
	e=0;
	f=0;
	while(scanf("%d,%s",&a,&b)!=EOF) {
		if(strcmp(b,"A")==0) {
			c+=1;
		}
		else if(strcmp(b,"B")==0) {
			d+=1;
		}
		else if(strcmp(b,"AB")==0) {
			e+=1;
		}
		else if(strcmp(b,"o")==0) {
			f+=1;
		}
	}
	printf("%d\n",c);
	printf("%d\n",d);
	printf("%d\n",e);
	printf("%d\n",f);
	return 0;
}

Measured memory_bytes: 596
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
	int a[3];
	int step;
	while(cin>>a[0]>>a[1]>>a[2])
	{
		step=0;
		sort(a,a+3);
		while(a[0]<a[1]||a[1]<a[2])
		{
			if(a[0]==a[1])
			{
				a[0]+=1;
				a[1]+=1;
				step++;
			}
			else if(a[1]==a[2])
			{
				a[0]+=2;
				step++;
			}
			else
			{
				a[0]+=2;
				step++;
			}
			sort(a,a+3);
		}
		cout<<step<<endl;
	}
	return 0;
}

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

int main(){
    ll H;
    cin >> H;
    ll N = 2;
    ll M = 1;
    while (H != 1)
    {
        H = H/2;
        M += N;
        N = 2*N;
    }
    cout << M << endl;

    return 0;

}

Measured memory_bytes: 256
import java.util.*;

public class Main {


    static class Pair {
            int x=0;
            int y=0;
            Pair(int x , int y){
                this.x = x;
                this.y = y;
            }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return x == pair.x &&
                    y == pair.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

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


        int[][]  nums = new int[N][2];
        Set<Pair> s = new HashSet<>();
        for (int i = 0; i < N; i++) {
            nums[i][0]=sc.nextInt();
            nums[i][1]=sc.nextInt();
            s.add(new Pair(nums[i][0],nums[i][1]));
        }

//        if(N==1){
//            System.out.println(1);
//            return ;
//        }


        HashMap<Pair,Integer> m = new HashMap<>();
        int max = 0;
        Pair maxPair = new Pair(0,0);
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if(i!=j){
                    int p = nums[j][0] - nums[i][0];
                    int q = nums[j][1] - nums[i][1];
                    Pair nw = new Pair(p,q);
                    if(!m.containsKey(nw)){
                        m.put(nw,1);
                    }else{
                        m.put(nw,m.get(nw)+1);
                    }

                    if(m.get(nw) > max ){
                        max =m.get(nw);
                        maxPair = nw;
                    }

                }
            }
        }

        int count =0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if(i==j) continue;
                int p = nums[j][0] - nums[i][0];
                int q = nums[j][1] - nums[i][1];
                if(maxPair.x == p && maxPair.y == q){
                    count++;
                }
            }
        }

        System.out.println(N-count);
    }

}


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

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

using namespace std;
using ll = long long;

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

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

	int r=in(),D=in(),x=in();
	int n=x;
	REP(i,10){
		n = r*n-D;
		cout << n << endl;
	}
	return 0;
}

Measured memory_bytes: 256
class UNION_FIND(object):
    def __init__(self,n):
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])
            return self.parent[x]
 
    def size(self,x):
        return -self.parent[self.root(x)]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True

n,m=map(int,input().split())
u=UNION_FIND(n)

tmp = [0] * (m+1)
#ans[0] = int(n*(n-1)/2)

ab = []
for i in range(m):
    ab.append(list(map(int,input().split())))
    
ab = ab[::-1]

for i in range(m):
    if u.root(ab[i][0]-1) == u.root(ab[i][1]-1):
        tmp[i] = 0
    else:
        tmp[i] = u.size(ab[i][0]-1) * u.size(ab[i][1]-1)
    
    u.union(ab[i][0]-1, ab[i][1]-1)

tmp = tmp[::-1]

ans = 0
for i in range(m):
    ans = ans + tmp[i+1]
    print(ans)
    

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

int selectionsort(vector<int> &A,int N){
  int count=0;
  for(int i=0;i<N-1;i++){
    int minj=i;
    for(int j=i;j<N;j++){
      if(A.at(j)<A.at(minj)){
        minj=j;
      }
    }
    swap(A.at(i),A.at(minj));
    if(i!=minj){
      count++;
    } 
  }
  return count;
}

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


Measured memory_bytes: 3092
'''
Created on 2020/08/20

@author: harurun
'''
def main():
  import re
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  S=pin()[:-1]
  if re.fullmatch(r"[A-Z]*AC[A-Z]*",S)==None:
    print("No")
    return 
  print("Yes")
  return 

main()

Measured memory_bytes: 9868
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>

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

vector <bool> b;



int main()
{

	cin >> N ;
	int ans=0;
	a.resize(N+1);
	b.resize(N+1);

	FOR(i,1,N+1){
		cin >> a[i];
		b[i] = false;
	}

	FOR(i,1,N+1){
		if(b[i])
			continue;
		if(a[a[i]] == i){
			ans++;
			b[a[i]] = true;
		}
	}

	cout << ans;


}

Measured memory_bytes: 640
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define DEBUG true
#ifdef ONLINE_JUDGE
#undef DEBUG
#define DEBUG false
#endif 

using namespace std;

#define MAXN ((int)3e3+5)
#define MOD ((int)1e9 + 7)
#define INF ((int)1e9 + 9)
#define ll long long
#define _ << " " <<
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define TRACE(x) if(DEBUG) cerr << #x << " = " << x << endl;
#define TRACE2(x,y) if(DEBUG) cerr << #x << " = " << x << " | " << #y << " = " << y << endl;
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pii pair<int,int>
#define mid ((l+r)/2)

int n,m,k;
char d[MAXN][MAXN];
int ans[MAXN][MAXN];
int row[MAXN];

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
		{
			cin >> d[i][j];
			if(d[i][j] == '#')
				row[i]++;
		}
	int last = 0;
	for (int i = 0; i < n; ++i)
	{
		if(row[i])
		{
			last++;
			bool f=false;
			for (int j = 0; j < m; ++j)
			{
				if(d[i][j] == '#' && f) last++;
				if(d[i][j] == '#') f=true;
				ans[i][j] = last;
			}
		}
	}

	int t = n-1;
	while(row[t] == 0) t--;


	for (int i = t+1; i < n; ++i)
		for (int j = 0; j < m; ++j)
			ans[i][j] = ans[i-1][j]; 

	for (int i = n-2; i >= 0; --i)
	{
		for (int j = 0; j < m; ++j)
		{
			if(ans[i][j] == 0)
				ans[i][j] = ans[i+1][j]; 
		}
	}


	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
			cout << ans[i][j] << " ";
		cout << endl;
	}
}

Measured memory_bytes: 5760
def main():
    N = int(input())
    for h in range(1,3501):
        for n in range(1,3501):
            if 4 * h * n - N * n - N * h == 0:
                continue
            w = (N * h * n) / (4 * h * n - N * n - N * h)
            if w > 0 and w.is_integer():
                print(h,n,int(w))
                exit()




if __name__ == "__main__":
    main()

Measured memory_bytes: 66676
#include<bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
int main(){
  int N, C;
  cin >> N >> C;
  vector<vector<long long>> perpetual(401, vector<long long>(401, 0));
  for (int i=0;i<401;i++){
    perpetual.at(i).at(0) = 1;
    for (int j=1;j<401;j++){
      perpetual.at(i).at(j) = (perpetual.at(i).at(j-1) * i) % mod;
    }
  }
  vector<int> A(N), B(N);
  for (int i=0;i<N;i++){
    cin >> A.at(i);
  }
  for (int i=0;i<N;i++){
    cin >> B.at(i);
  }
  vector<vector<long long>> Med(N, vector<long long>(C+1));
  for (int k=0;k<=C;k++){
    for (int m=0;m<N;m++){
      for (int n=A.at(m);n<=B.at(m);n++){
        Med.at(m).at(k) += perpetual.at(n).at(k);
        Med.at(m).at(k) %= mod;
      }
    }
  }
  vector<vector<long long>> T(N, vector<long long>(C+1, 0));
  T.at(0).at(0) = 1;
  for (int j=0;j<=C;j++){
    for (int k=0;k<=C-j;k++){
      T.at(0).at(j+k) = Med.at(0).at(j);
    }
  }
  for (int i=1;i<N;i++){
    for (int j=0;j<=C;j++){
      for (int k=0;k<=C-j;k++){
        T.at(i).at(j + k) += T.at(i-1).at(k) * Med.at(i).at(j);
        T.at(i).at(j + k) %= mod;
      }
    }
  }
  cout << T.at(N-1).at(C) << endl;
  return 0;
}

Measured memory_bytes: 4096
#include<iostream>
using namespace std;
int main() {
    int n;
    long long a;
    long long max = -1000000;
    long long min = 1000000;
    long long sum = 0;
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> a;
        if (a > max) max = a;
        if (a < min) min = a;
        sum += a;
    }
    cout << min << " " << max << " " << sum << endl;
    return 0;
}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
#define MAX 2000000
#define K 10000

int A[MAX], B[MAX];

void countingSorting(int *A, int *B, int k, int len)
{
	int C[k];
	int i, j;
	for (i = 0; i < k; i++) {
		C[i] = 0;
	}
	for (i = 0; i < len; i++) {
		C[A[i]] = C[A[i]] + 1;
	}
	for (i = 1; i < k; i++) {
		C[i] = C[i] + C[i - 1];
	}
	for (i = 0; i < len; i++) {
		C[A[i]] = C[A[i]] - 1;
		B[C[A[i]]] = A[i];
	}
}

int main(void) {
	int n, i;
	cin >> n;
	for (i = 0; i < n; i++)
		cin >> A[i];
	countingSorting(A, B, K, n);

	for (i = 0; i < n; i++) 
	{
		if (i) cout << " ";
		cout << B[i];
	}
	cout << endl;
}


Measured memory_bytes: 18744
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<complex>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef complex<double> P;

int main(){
  vector<P> v;
  double a,b,c;
  while(~scanf("%lf,%lf",&a,&b)) v.push_back(P(a,b));
  double ans = 0.0;
  for(int i=1; i<v.size()-1; i++){
    double z;
    a = abs(v[0] - v[i]);
    b = abs(v[0] - v[i+1]);
    c = abs(v[i+1] - v[i]);
    z = (a + b + c) / 2.0;
    ans += sqrt(z*(z-a)*(z-b)*(z-c));
  }
  printf("%.6f\n",ans);
  return 0;
}

Measured memory_bytes: 0
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        Main m = new Main(sc);
        m.show(m.solve());
        sc.close();
    }
    
	//フィールド
    Scanner sc;
    int N;
    int K;
    
    //入力
    Main(Scanner sc) {
        this.sc = sc;
        this.N = sc.nextInt();
        this.K = sc.nextInt();
    }
    
    //解答処理
    private int solve() {
        int answer = 0;
        
        if (K >= 2) {
        	answer = N - K;
        }
    	
        return answer;
    }
    
    //出力
    public void show(int answer) {
        System.out.println(answer);
    }

}


Measured memory_bytes: 35684
#include<bits/stdc++.h>
using namespace std;
#define Fast ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
typedef vector<int>Vl;
typedef pair<int,int>pii;
typedef vector<pii>Vll;
typedef vector<pair<int,pii> >Vlll;
typedef priority_queue<int>PQL;
typedef map<int,int>M;
#define S second
#define F first
#define mp make_pair
#define ms(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define sl(n) cin>>n
#define pl(n) cout<<n
const int mod=1e9+7;
const int sze=1e5+2;
const int inf= (int)(1e19+10LL);
void solve()
{
  int n;
  sl(n);
  string str=to_string(n);
  for(int i=0;i<3;i++){
	  if(str[i]=='7'){
		  cout<<"Yes"<<endl;
		  return;
	  }
  }
  cout<<"No"<<endl;

		
}
 
signed main(){
   int test=1;
   //sl(test);
   while(test--){
      solve();
 
   }
  return 0;
}


Measured memory_bytes: 3660
// CppPractice.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n, k, h, cnt;
	cin >> n >> k;

	cnt = 0;
	for (int i = 0; i < n; i++) {
		cin >> h;
		if (h >= k) cnt += 1;
	}
	cout << cnt << endl;
}

// プログラムの実行: Ctrl + F5 または [デバッグ] > [デバッグなしで開始] メニュー
// プログラムのデバッグ: F5 または [デバッグ] > [デバッグの開始] メニュー

// 作業を開始するためのヒント: 
//    1. ソリューション エクスプローラー ウィンドウを使用してファイルを追加/管理します 
//   2. チーム エクスプローラー ウィンドウを使用してソース管理に接続します
//   3. 出力ウィンドウを使用して、ビルド出力とその他のメッセージを表示します
//   4. エラー一覧ウィンドウを使用してエラーを表示します
//   5. [プロジェクト] > [新しい項目の追加] と移動して新しいコード ファイルを作成するか、[プロジェクト] > [既存の項目の追加] と移動して既存のコード ファイルをプロジェクトに追加します
//   6. 後ほどこのプロジェクトを再び開く場合、[ファイル] > [開く] > [プロジェクト] と移動して .sln ファイルを選択します


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
vector<int> nos;
int N, M = 1e9+7, dp[10000][100], D;
int solve(int ind, int csum, int lmt){
    if (ind==N)
        return csum==0;
    if (!lmt && dp[ind][csum]!=-1)
        return dp[ind][csum];
    int ans = 0, till = (lmt? nos[ind]: 9);
    for (int i=0; i<=till; i++){
        ans += solve(ind+1, (csum+i)%D, (lmt && i==till));
        if (ans>=M)
            ans -= M;
    }
    if (!lmt)
        dp[ind][csum] = ans;
    return ans;
}
int main(){
    memset(dp, -1, sizeof(dp));
    string S;
    cin >> S >> D;
    N = S.size();
    nos.resize(N);
    for (int i=0; i<N; i++)
        nos[i] = S[i]-'0';
    cout << (solve(0, 0, 1)-1+M)%M << "\n";
}

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

using namespace std;

typedef long long ll;


int main () {
    ios::sync_with_stdio(false); cin.tie(0);
    int x; cin>>x;
    int a=x/500; x=x%500;
    cout<<1LL*a*1000+(x/5)*5<<endl;
}


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[i];
  }
  int f[100001] = {};
  for (int i = 0; i < n; i += 2) {
    f[a[i]]++;
  }
  int ma = 0, m1 = 0, ma1 = 0;
  int ans = n;
  for (int i = 0; i < 100001; ++i) {
    if (ma <= f[i]) {
      m1 = i;
      ma1 = f[i] - ma;
      ma = f[i];
    } else {
      ma1 = min(ma1, ma - f[i]);
    }
  }
  ans -= ma;
  int g[100001] = {};
  for (int i = 1; i < n; i += 2) {
    g[a[i]]++;
  }
  int m2 = 0, ma2 = 0;
  ma = 0;
  for (int i = 0; i < 100001; ++i) {
    if (ma <= g[i]) {
      m2 = i;
      ma2 = g[i] - ma;
      ma = g[i];
    } else {
      ma2 = min(ma2, ma - g[i]);
    }
  }
  ans -= ma;
  if (m1 == m2) {
    int c = min(ma1, ma2);
    ans += c;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n;
string s;

int main(){
	cin>>n>>s;
	vi b(10,n);
	vvi a(n);
	for(int i=n-1;i>=0;i--){
		b[s[i]-'0']=i;
		a[i]=b;
	}
	int res=0;
	for(int i=0;i<1000;i++){
		auto t=to_string(i);
		while(t.size()<3) t='0'+t;
		int id=-1;
		for(int j=0;j<3&&id<n;j++){
			id++;
			if(id==n) break;
			id=a[id][t[j]-'0'];
		}
		if(id<n){
//			cout<<t<<endl;
			res++;
		}
	}
	cout<<res<<endl;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using ll = long long;
using namespace std;
int main(){
    ll n,k;
    ll ans=0;
    ll a=1e9+7;
    cin>>n>>k;
    for(ll i=k;i<=n+1;i++){
        ans+=((n-i+1)*i+1)%a;
        //cout<<(n-i+1)<<" "<<i<<endl;
    }
    cout<<ans%a<<endl;
}

Measured memory_bytes: 3636
Module Module1

    Sub Main()
        Dim input As String = Console.ReadLine()
        Dim output As String = ""
        If input(0) = "1" Then
            output = output & "9"
        Else
            output = output & "1"
        End If
        If input(1) = "1" Then
            output = output & "9"
        Else
            output = output & "1"
        End If
        If input(2) = "1" Then
            output = output & "9"
        Else
            output = output & "1"
        End If
        Console.WriteLine(output)
    End Sub

End Module


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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
//template<typename T> using vec=std::vector<T>;

const int inf=1<<30;
const long long int infll=1LL<<58;
const double eps=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
	os << "[";
	for (const auto &v : vec) {
		os << v << ",";
	}
	os << "]";
	return os;
}

int p,q,a,n;

int gcd(int x,int y){
    if(y==0) return x;
    return gcd(y,x%y);
}

int dfs(int denom,int numer,int prev,int product,int num){
    int res=0;
    if((double)p/q-eps<=(double)numer/denom  and (double)numer/denom<=(double)p/q+eps) ++res;
    if(num==0) return res;

    {
        int tmp1=denom*prev,tmp2=numer*prev+denom*num;
        if((double)tmp2/tmp1<(double)p/q) return 0;
    }

    if((double)numer/denom>(double)p/q) return 0;

    int x=prev;
    while(true){
        if(product*x>a) break;
        res+=dfs(denom*x,numer*x+denom,x,product*x,num-1);
        ++x;
    }
    return res;
}

void solve(){
    while(cin >> p >> q >> a >> n){
        if(p==0 and q==0 and a==0 and n==0) break;
        cout << dfs(1,0,1,1,n) << endl;
    }
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	solve();
	return 0;
}

Measured memory_bytes: 3004
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

constexpr ll mod = 1e9+7;
struct mint {
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod){}
    
    friend ostream &operator<<(ostream& os,const mint& a){
        return os << a.x;
    }

    friend istream &operator>>(istream& is,mint& a){
        ll t;
        is >> t;
        a = mint(t);
        return (is);
    }

    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 {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        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 {
        mint res(*this);
        return res/=a;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,K;
    cin >> N >> K;
    vec<mint> F(K+1);
    mint ans = 0;
    for(ll i=K;i>=1;i--){
        mint n = K/i;
        F[i] = n.pow(N);
        for(int j=2*i;j<=K;j+=i) F[i] -= F[j];
        ans += F[i]*i;
    }
    cout << ans << "\n";
}

Measured memory_bytes: 3992
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pa;
const int maxn=20;
const int inf=1e9+7;
const int mod=1e9+7;
int a[maxn];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    printf("%s\n",n<=m?"Yes":"No");
}


Measured memory_bytes: 256
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

template <typename T>
using vector2 = vector<vector<T>>;
template <typename T>
vector2<T> initVec2(size_t n0, size_t n1, T e = T()){
    return vector2<T>(n0, vector<T>(n1, e));
}

template <typename T>
using vector3 = vector<vector<vector<T>>>;
template <typename T>
vector3<T> initVec3(size_t n0, size_t n1, size_t n2, T e = T()){
    return vector3<T>(n0, vector2<T>(n1, vector<T>(n2, e)));
}

vector2<int> ver, hor;
vector<int> usedV, usedH;

P dfs2(int v);

P dfs1(int v){
    if(usedH[v]){
        return {0, 0};
    }
    usedH[v] = true;
    P ret= {1, 0};
    for(int u : hor[v]){
        if(usedV[u]){
            continue;
        }
        P tmp = dfs2(u);
        ret.first += tmp.first;
        ret.second += tmp.second;
    }
    return ret;
}
P dfs2(int v){
    if(usedV[v]){
        return {0, 0};
    }
    usedV[v] = true;
    P ret = {0, 1};
    for(int u : ver[v]){
        if(usedH[u]){
            continue;
        }
        P tmp = dfs1(u);
        ret.first += tmp.first;
        ret.second += tmp.second;
    }
    return ret;
}

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

    int n;
    cin >> n;
    vector<P> vp(n);
    rep(i, n){
        int x, y;
        cin >> x >> y;
        vp[i] = {x, y};
    }

    ver = initVec2<int>(100001, 0);
    hor = initVec2<int>(100001, 0);
    rep(i, n){
        ver[vp[i].second].push_back(vp[i].first);
        hor[vp[i].first].push_back(vp[i].second);
    }

    usedV = vector<int>(100001, false);
    usedH = vector<int>(100001, false);

    int ans = 0;
    rep(i, n){
        P p = {0, 0};
        P tmp;
        tmp = dfs1(vp[i].first);
        p.first += tmp.first;
        p.second += tmp.second;
        tmp = dfs2(vp[i].second);
        p.first += tmp.first;
        p.second += tmp.second;

        ans += p.first * p.second;
    }

    cout << ans - n << endl;

    return 0;
}


Measured memory_bytes: 15872
let id x = x
let (h,w) = Scanf.scanf "%d %d\n" (fun h w -> (h,w))

let array = Array.init h (fun _ -> "#" ^ (Scanf.scanf "%s\n" id) ^ "#") 
let list = Array.to_list array

let str = String.make (w+2) '#'
          
let () =
  print_endline str;
  List.iter print_endline list;
  print_endline str

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

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

  int num;
  int cnt = 0;
  for (int i = 1; i <= N; i++){
    cin >> num;
    if (num != i) cnt += 1;
  }

  cout << (cnt <= 2 ? "YES" : "NO") << endl;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define Int int64_t
#define dump(x) cout << (x) << endl
#define fi first
#define se second
Int mod = 1e9+7;
Int INF = 1e18;
double EPS = 0.00000001;
//Int mod = 998244353;

int main() {
    Int n, k;
    cin >> n >> k;
    k--;
    vector<Int> a(n);
    for (Int i = 0; i < n; i++) cin >> a[i];
    vector<Int> a2;
    for (Int i = 0; i < n; i++) {
        if (i < n - 1 && a[i] == a[i + 1]) {
            i++;
            continue;
        }
        a2.push_back(a[i]);
    }
    Int m = (Int)a2.size();
    if (m == 0) return 0;
    vector<Int> b(200005, -1);
    vector<Int> next(m, -1);
    for (Int i = m - 1; i >= 0; i--) {
        if (b[a2[i]] >= 0) {
            next[i] = b[a2[i]];
        }
        b[a2[i]] = (i + 1) % m;
    }
    for (Int i = m - 1; i >= 0; i--) {
        if (next[i] < 0) next[i] = b[a2[i]];
    }
    if (m == 1 && k % 2 == 0) {
        cout << a2.front() << endl;
        return 0;
    }
    Int cur = 0;
    Int cnt = 1;
    
    //for (Int i = 0; i < m; i++) cout << next[i] << " "; cout << endl;
    
    while (next[cur] != 0) {
        if (cur > next[cur] || (cur + 1) % m == next[cur]) cnt++;
        cur = next[cur];
        if (next[cur] == 0 && cur == m - 1) cnt++;
    }
    Int p = cnt;
    cur = 0;
    cnt = 1;
    while (next[cur] != 0) {
        //Int pre = cur;
        Int x = next[cur];
        if (k < cnt && (next[cur] < cur)) {
            next[cur] = (cur + 1) % m;
        }
        if (next[cur] < cur || (cur + 1) % m == next[cur]) cnt++;
        cur = x;
    }
    //dump(cnt);
    if (cnt == 0) return 0;
    k %= p;
    //dump(p);
    cur = 0;
    cnt = 0;
    while (next[cur] != 0) {
        
        if (cnt < k) {
            if (cur > next[cur] || (cur + 1) % m == next[cur]) cnt++;
            cur = next[cur];
        
        }
        else {
            if (cur + 1 < next[cur]) {
                cur = next[cur];
                if (next[cur] == 0) {
                    cout << a2[cur] << " ";
                }
                continue;
            }
            cout << a2[cur] << " ";
            cur++;
            if (cur == m - 1 && next[cur] == 0) {
                cout << a2[cur] << " ";
            }
            if (cur == m) break;
        }
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 7920
#include<iostream>
using namespace std;
int main(){
	int n,m;
	int sumn=0,summ=0;
	scanf("%d%d",&n,&m);
	for(int i=n-1;i>=1;i--){
		sumn+=i;
	}
	for(int i=m-1;i>=1;i--){
		summ+=i;
	}
	printf("%d",summ+sumn);
	return 0;
}

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


int euc(int a,int b){
  if(a%b==0){return b;}
  return euc(b,a%b);
}


int main(){
  int a,b,c;
  cin>>a>>b>>c;
  int MX=euc(a+b,60);
  int ans=-1;
  int time=c;
  while(1){
    c%=a+b;
    if(c<=a){ans=time; break;}
    c+=60;
    time+=60;
    if(time>(a+b)*60/MX*2){break;}
  }
  cout<<ans<<endl;
  
  
  return 0;
}



Measured memory_bytes: 3100
// ref. https://ei1333.github.io/luzhiled/snippets/dp/knapsack-limitations.html
// ref. https://scrapbox.io/nojima/%E5%80%8B%E6%95%B0%E5%88%B6%E9%99%90%E4%BB%98%E3%81%8D%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>
#include <stack>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define sz(x) (ll)(x).size()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;
typedef vector<ll> vl;
typedef vector<P> vp;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

// Knapsack with limitation
template<typename T, typename Compare = greater<T>>
vector<T> knapsack_limitations(const vector<ll> &w, const vector<ll> &m, const vector<T> &v,
                               const ll& W, const T& NG, const Compare &comp = Compare()) {
  const ll n = (ll)w.size();
  vector<T> dp(W + 1, NG), deqv(W + 1), deq(W + 1);
  dp[0] = T();
  rep(i,n) {
    rep(a,w[i]) {
      ll s = 0, t = 0; // [s,t) is valid range. deqv[s] is used as slide max.
      for (ll j = 0; w[i] * j + a <= W; j++) { // Here, we get slide max of j in [j-m[i],j].
        if (dp[w[i] * j + a] != NG) {
          auto val = dp[w[i] * j + a] - j * v[i]; // value with out contribution of (v[i]*j).
          while(s < t && comp(val, deqv[t - 1])) --t;
          deq[t] = j;      // push
          deqv[t++] = val; // push
        }
        if (s < t) { // [s,t) is not blank
          dp[w[i] * j + a] = deqv[s] + j * v[i];
          if(deq[s] == j - m[i]) ++s;
        }
      }
    }
  }
  return dp;
}

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n,W;
  cin >> n >> W;
  vector<ll> v(n);
  vector<ll> w(n);
  vector<ll> m(n);
  rep(i,n) {
    cin >> v[i] >> w[i] >> m[i];
  }

  vector<ll> dp = knapsack_limitations(w, m, v, W, -1ll);
  ll ans = 0;
  rep(i,W+1) {
    chmax(ans, dp[i]);
  }
  cout << ans << endl;
}



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

int main(){
    
    long long L,R,min=2018,cou=0;
    cin>>L>>R;
    long long l=L%2019,r=R%2019;
    if(R-L>=2019){
        cout<<0;
        return 0;
    }else{
         for(int i=l;i<r;i++){
             for(int j=l+1;j<r+1;j++){
                 if((i*j)%2019<min){
                     min=(i*j)%2019;
                 }
                 cou++;
        }
        

    }
    cout<<min<<endl;
        return 0;
        
    }

}






Measured memory_bytes: 256
//FPC 2.6.2
var
  n,ans,a,i,j : Integer;
begin
  readln(n);
  ans := 0;
  for i := 1 to 9 do
  begin
    for j := 1 to 9 do
    begin
      a := i * j;
      if a=n then ans := 1;
    end;
  end;
  if ans=1 then
  writeln('Yes')
  else
  writeln('No');
end.


Measured memory_bytes: 128
#include<iostream>
#include<fstream>
#include<sstream>
#include<algorithm>
#include<cstdio>
#include<cctype>
#include<cassert>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<iomanip>
#include<utility>
using namespace std;
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define rg register
#define il inline
#define lch(x) ((x)<<1)
#define rch(x) ((x)<<1^1)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define rep0(i,n) for(register int i=0;i<(n);++i)
#define per0(i,n) for(register int i=(n)-1;i>=0;--i)
#define rep(i,st,ed) for(register int i=(st);i<=(ed);++i)
#define per(i,ed,st) for(register int i=(ed);i>=(st);--i)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef double dbl;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> il T qmin(const T &a,const T &b){return a<b?a:b;}
template<typename T> il T qmax(const T &a,const T &b){return a>b?a:b;}
template<typename T> il void getmin(T &a,const T &b){if(a>b) a=b;}
template<typename T> il void getmax(T &a,const T &b){if(a<b) a=b;}
il void fileio(string s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

const int inf=(int)1e9+7;
const ll linf=(ll)1e17+7;
const int N=100005;

int t[N],x[N],y[N],n;

int main(){
//	fileio("test");
	scanf("%d",&n);
	rep(i,1,n) scanf("%d%d%d",t+i,x+i,y+i);
	rep(i,1,n){
		int dis=abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);
		int tot=t[i]-t[i-1];
		if(dis<=tot&&!((tot-dis)&1)) continue;
		return puts("No"),0;
	}
	puts("Yes");
	return 0;
} 

Measured memory_bytes: 1408
import java.io.IOException;
import java.util.ArrayList;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) throws IOException {
        StringBuilder builder = new StringBuilder();
        int buf;
        int num;
        while ((buf = System.in.read()) != '\n') {
            builder.appendCodePoint(buf);
        }

        num = Integer.parseInt(builder.toString());
        ArrayList<Integer> list = new ArrayList<>(num);

        for (int i = 0; i < num; i++) {
            builder.setLength(0);
            while ((buf = System.in.read()) != ' ' && buf != '\n') {
                builder.appendCodePoint(buf);
            }

            list.add(Integer.valueOf(builder.toString()));
        }

        list.sort(Comparator.reverseOrder());
        long sum = list.get(0);
        int j = 1;
        boolean even = false;
        for (int i = 1; i < num - 1; i++) {
            sum += list.get(j);
            if (even) {
                j++;
            }
            even = !even;
        }

        System.out.print(sum);
    }
}


Measured memory_bytes: 48880
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
  int W = sc.nextInt();
  int a = sc.nextInt();
  int b = sc.nextInt();
  if((a <= b && b <= a+W)||(b <= a && a < b+W))System.out.println("0");
  else if(b >= a+W)System.out.println(b-a-W);
  else System.out.println(a-b-W);
}}


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

using namespace std;

typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli>> mat;

string abcd;

int main(){
	cin >> abcd;
	vll i = vll(3);
	for(i[0] = 0;i[0] < 2;i[0]++){
		for(i[1] = 0;i[1] < 2;i[1]++){
			for(i[2] = 0;i[2] < 2;i[2]++){
				lli a = abcd[0]-'0';
				if(i[0] == 0) a += abcd[1]-'0';
				else a -= abcd[1]-'0';
				if(i[1] == 0) a+= abcd[2]-'0';
				else a-= abcd[2]-'0';
				if(i[2] == 0) a+= abcd[3]-'0';
				else a -= abcd[3]-'0';
				if(a == 7){
					cout 
					<< abcd[0] << (i[0] == 0 ? '+' : '-')
					<< abcd[1] << (i[1] == 0 ? '+' : '-')
					<< abcd[2] << (i[2] == 0 ? '+' : '-')
					<< abcd[3] << "=7" << endl;
					return 0;
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<iomanip>

using namespace std;
using ll = long long;
using P = pair<int, int>;

const int MOD = 1e9 + 7;
const int MAX = 1e9;
const ll LLMAX = 1e18;
const int INF = numeric_limits<int>::max();
const ll LLINF = numeric_limits<ll>::max();
const double PI = acos(-1.0);

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

int main() {
    int A, B, C; cin >> A >> B >> C;
    int K; cin >> K;

    int t = 0;
    while(A >= B) {
        B *= 2;
        t++;
    }

    while(B >= C) {
        C *= 2;
        t++;
    }

    if (t <= K) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3632
import sys
import math
import itertools
import bisect
from copy import copy,deepcopy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(map(int,input().split()))
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N = i()
H = l()
H[0] -= 1
for i in range(N-1):
    if H[i] > H[i+1]:
        print('No')
        exit()
    elif H[i] != H[i+1]:
        H[i+1] -= 1
print('Yes')

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

using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<double> vd;

#define REP(i,a,b) for(int i=(a);i<=(b);++i)
#define pb push_back

const int N = 1e5;
const ll L = 1e18;
const ll MOD = 1e9 + 7;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n, a;
	cin >> n >> a;

	n %= 500;
	if(n <= a) cout << "Yes\n";
	else cout << "No\n";

	return 0; 	
}

Measured memory_bytes: 384
# AGC032C

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


def hoge():
    from collections import defaultdict
    n, m = map(int, input().split())

    ns = defaultdict(set)
    used = {}
    for _ in range(m):
        u,v = map(int, input().split())
        ns[u-1].add(v-1)
        ns[v-1].add(u-1)
        used[u-1,v-1] = False
        used[v-1,u-1] = False


    seen = [False] * n
    prev = [None] * n
    cs = []
    count = 0
    done = True
    if not all(len(item)%2==0 and len(item)>0 for item in ns.values()):
        print("No")
        return


    for start in range(n):
        if seen[start]:
            continue
        q = [start]
        current_seen = [False] * n
        update = False
        while q:
    #         print(q)
            u = q.pop()
            current_seen[u] = True
            for v in ns[u]:
                if used[u,v] or prev[u]==v:
                    continue
                prev[v] = u
                if current_seen[v]:
                    # サイクル検出
                    count += 1
                    c = set()
                    tmp = v
                    while tmp not in c:
                        c.add(tmp)
                        used[tmp, prev[tmp]] = used[prev[tmp], tmp] = True
                        tmp = prev[tmp]
                    cs.append(c)
                    for u in c:
                        seen[u] = True
                    update = True
                    break
                q.append(v)
            if update:
                break
        if not update:
            print("No")
            done = False
            break

    def sub(cs):
        if len(cs)==1:
            return "No"
        elif len(cs)==2:
            if len(set(cs[0] & cs[1]))>=3:
                return "Yes"
            else:
                return "No"
        else :
            return "Yes"
    #     u2s = defaultdict(set)
    #     nns = defaultdict(set) # i番目のサイクルと重なるサイクル
    #     for i,s in enumerate(cs):
    #         for u in s:
    #             nns[i] |= u2s[u]
    #             u2s[u].add(i)
    #     for i,s in nns.items():
    #         for j in s:
    #             nns[j].add(i)
    #     count = 0
    # #     print(u2s)
    # #     print(nns)
    #     seen = [False] * len(cs)
    #     for start in range(len(cs)):
    #         if seen[start]:
    #             continue
    #         q = [start]
    #         seen[start] = True
    #         while q:
    #             u = q.pop()
    #             for v in nns[u]:
    #                 if not seen[v]:
    #                     q.append(v)
    #                     seen[v] = True
    #         count += 1
    #     if count<=3:
    #         return "Yes"
    #     else:
    #         return "No"
    if done:
        print(sub(cs))
    #     print("Yes")
hoge()

Measured memory_bytes: 130388
import sys
import time
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21


def dijkstra(graph, start, n):
    h = []
    heapq.heappush(h, (0, start))
    costs = [INF for _ in range(n)]
    while h:
        cost, cur = heapq.heappop(h)
        if costs[cur] != INF:
            continue
        costs[cur] = cost
        for edge in graph[cur]:
            ecost, tgt = edge
            if costs[tgt] == INF:
                heapq.heappush(h, (cost + ecost, tgt))

    return costs


def dist(x1, y1, x2, y2):
    return math.sqrt(abs(x1 - x2) ** 2 + abs(y1 - y2) ** 2)


def main():
    xs, ys, xe, ye = getlist()
    N = getN()
    graph = [[] for i in range(N + 3)]
    circles = []
    circles.append([xs, ys, 0])
    circles.append([xe, ye, 0])
    for i in range(N):
        circles.append(getlist())

    for i in range(N+1):
        for j in range(i+1, N+2):
            # print(i, j)
            x1, y1, r1 = circles[i]
            x2, y2, r2 = circles[j]
            ray = max(dist(x1, y1, x2, y2) - r1 - r2, 0)
            graph[i].append((ray, j))
            graph[j].append((ray, i))

    print(dijkstra(graph, 0, N+2)[1])

if __name__ == '__main__':
    main()


Measured memory_bytes: 145284
scale = {
  "yotta" => 24 ,
  "zetta" => 21 ,
  "exa"   => 18 ,
  "peta"  => 15 ,
  "tera"  => 12 ,
  "giga"  => 9  ,
  "mega"  => 6  ,
  "kilo"  => 3  ,
  "hecto" => 2  ,
  "deca"  => 1  ,
  "deci"  => -1 ,
  "centi" => -2 ,
  "milli" => -3 ,
  "micro" => -6 ,
  "nano"  => -9 ,
  "pico"  => -12,
  "femto" => -15,
  "ato"   => -18,
  "zepto" => -21,
  "yocto" => -24,
}

n = gets.to_i
n.times do
  s = gets.chomp
  s =~ /^(\S+) (\w+ )?(\w+)$/
  if $1[0] == ?0
    e = -1
    e -= 1 until $1[1 - e] != ?0
    precision = $1.size + e - 1
    x = $1[1 - e] + (precision > 1 ? ?. : "") + $1[2-e..-1]
  elsif $1.count(?.) > 0
    precision = $1.size - 1
    e = 0
    e += 1 until $1[e + 1] == ?.
    x = $1[0] + ?. + $1[1..e] + $1[e+2..-1]
  else
    precision = $1.size
    e = $1.size - 1
    x = $1[0] + ?. + $1[1..-1]
  end
  e += scale[$2.strip] if $2
  unit = $3
  printf("%s * 10^%d %s\n", x, e, unit)
end


Measured memory_bytes: 7876
//Author- Vaibhav singh
//will be expert soon 
// *#####################################################################################*
#include<bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_multiset tree<long long , null_type,less_equal<long long >, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_set tree<long long , null_type,less<long long >, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
#define ll long long int
#define YES cout<<"YES"<<"\n";
#define NO cout<<"NO"<<"\n";
#define ld     long double
#define yes cout<<"yes"<<"\n";
#define no cout<<"no"<<"\n";
#define No cout<<"No"<<"\n";
#define Yes cout<<"Yes"<<"\n";
#define f(i,a) for(i=0;i<a;i++)
#define fo(i,a) for(i=1;i<=a;i++)
#define fa(i,a) for(auto i:a)
#define r(i,a) for(auto i=a.rbegin();i!=a.rend();i++)
#define en cout<<"\n";
#define ull unsigned long long int
#define o(x) cout<<x<<"\n";
#define o1(x) cout<<x<<" ";
#define pb push_back
#define F first
#define in insert
#define mp make_pair
#define S second
#define pre(n) cout<<fixed<<setprecision(n);
#define      gcd(a,b)    __gcd(a,b)
#define bs            binary_search
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define test ll t;cin>>t;while(t-->0)
const ll Mod = 998244353;
#define mod 1000000007
#define pi 3.14159265358979323846
#define re return 0;
// *#######################################################################################*
// *#########################################################################################*
    //      ll ans=0,b[5000005]={0},a[5000005],i,n,x=0;                
    

int main()
{
      
      fast
     
   ll n,m,i;
   cin>>n>>m;
   string a[n];
   
   f(i,n)
   {
         cin>>a[i];
   }
  sort(a,a+n);
  string z;
  
  f(i,n)
  {
        z+=a[i];
  }
   
   o(z)
   
   
   
   

    re
}

Measured memory_bytes: 256
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
int main(){
    int N;
    R(N);
    if(N<1000)printf("ABC\n");
    else printf("ABD\n");
    return 0;
}


Measured memory_bytes: 256