akhauriyash/Code-Regression huggingface dataset:
import sys


def simple(money, rate, charge, year):
    temp = 0
    for i in xrange(year):
        temp += int(money * rate)
        money -= charge
    return money + temp

def compound(money, rate, charge, year):
    temp = 0
    for i in xrange(year):
        money += int(money * rate)
        money -= charge
    return money + temp

m = int(sys.stdin.readline())
for z in xrange(m):
    money = int(sys.stdin.readline())
    year = int(sys.stdin.readline())
    n = int(sys.stdin.readline())
    result = []
    for i in xrange(n):
        simple_or_compound, rate, charge = sys.stdin.readline().split()
        simple_or_compound = int(simple_or_compound)
        rate = float(rate)
        charge = int(charge)
        if simple_or_compound == 0:
            result.append(simple(money, rate, charge, year))
        else:
            result.append(compound(money, rate, charge, year))
    result.sort()
    print result[-1]

Measured memory_bytes: 4280
#include <stdio.h>

int main(void) {
	int x,h;
    double a;
    while(1){
        scanf("%d",&x);
        scanf("%d",&h);
        if(!x && !h) break;
        a = sqrt(((double)x / 2) * ((double)x / 2) + h * h);
        printf("%f\n",x * x + x * a * 2);
    }
	return 0;
}

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

int main() {
	int n, m;
	std::cin >> n >> m;

	std::vector<int> a(n);
	std::vector<int> cnt(n + 1);
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
		cnt[a[i]]++;
	}

	std::vector<int> c(n + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < cnt[i]; j++) {
			c[std::max(0, i - j)]++;
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (c[i] == 0) {
			ans++;
		}
	}

	while (m--) {
		int x, y;
		std::cin >> x >> y;
		x--;

		if (a[x] - cnt[a[x]] + 1 >= 1 && --c[a[x] - cnt[a[x]] + 1] == 0) {
			ans++;
		}
		cnt[a[x]]--;
		a[x] = y;
		cnt[a[x]]++;

		if (a[x] - cnt[a[x]] + 1 >= 1 && c[a[x] - cnt[a[x]] + 1]++ == 0) {
			ans--;
		}
		std::cout << ans << std::endl;
	}
}

Measured memory_bytes: 3840
#include<stdio.h>
int main(void)
{
	int p[1000];
	int n,k,box,sum,i,j;
	scanf("%d %d",&n,&k);
	for(i=0;i<n;i++){
		scanf("%d",&p[i]);
	}
	for(i=0;i<n-1;i++){
		for(j=i+1;j<n;j++){
			if(p[i]>p[j]){
				box=p[i];
				p[i]=p[j];
				p[j]=box;
			}
		}
	}
	sum=0;
	for(i=0;i<k;i++){
		sum=sum+p[i];
	}
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 1700
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<cmath>
#include<limits>
#define ll long long
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int_INF 2147483647
#define pint_INF 2000000000
#define ll_INF 	9223372036854775807
#define MOD 1000000007
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define vvc vector<vector<char>>
#define vll vector<long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define sysp system("PAUSE")
#define pno cout << "no" << endl
#define pyes cout << "yes" << endl
#define pYes cout << "Yes" << endl
#define pNo cout << "No" << endl
using namespace std;

inline int ctoi(char c) {
	if ('a' <= c && c <= 'z') {
		return c - 'a';
	}
	else {
		return -1;
	}
}
inline char itoc(int i) {
	char c;
	c = 'a' + i;
	return c;
}
int main() {
    string s, t; cin >> s >> t;
    vi stable(26), ttable(26);

    for (int i = 0; i < s.size(); i++) {
        stable[ctoi(s[i])]++;
    }
	for (int j = 0; j < t.size(); j++) {
		ttable[ctoi(t[j])]++;
	}
	string strongS, weakT;

	for (int p = 0; p < 26; p++) {
		for (int t = 0; t < stable[p]; t++) {
			strongS += itoc(p);
		}
	}

	for (int q = 25; q >= 0; q--) {
		for (int t = 0; t < ttable[q]; t++) {
			weakT += itoc(q);
		}
	}

	if (strongS < weakT) {
		pYes;
	}
	else {
		pNo;
	}
}

Measured memory_bytes: 3596
#include <iostream>
 
using namespace std;
long long n, x, ans;
long long cel(long long n, long long x) {
    if(n % x == 0)
        return 2 * n - x;
    ans = n / x * 2 * x + cel(x, n % x);
    return ans ;
}
int main()
{
    while(cin >> n >> x) {
        ans = n + cel(n - x, x);
        cout << ans << endl;
    }
}

Measured memory_bytes: 504
def solve(res, d, n)
  t = [0, 1, 2, 3, 5, 7, 8, 9]
  if n == 0
    res
  else
    solve(res+t[n%8]*d, d*10, n/8)
  end
end
loop do
  n = gets.to_i
  if n == 0 then break end
  puts solve(0, 1, n)
end

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

int main() {
  int N;
  cin >> N;
  vector<int> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec.at(i);
  }
  int count = 1;
  
  sort(vec.begin(), vec.end());
  for(int i=1; i<N; i++){
    if(vec.at(i-1) != vec.at(i))count++;
  }
  cout << count << endl;
  
}

Measured memory_bytes: 3564
#include <iostream>

int main() {
    int H, W;
    while (std::cin >> H >> W, H || W) {
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                std::cout << ((i + j) & 1 ? '.' : '#');
            }
            
            std::cout << std::endl;
        }

        std::cout << std::endl;
    }
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(ll i=num, i##_len=(n); i<i##_len; ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const ll LLINF = 1LL<<60;
const int INTINF = 1<<30;
const int MOD = 1000000007;

void add(long long &a, long long b) {
  a += b;
  if (a >= MOD) a -= MOD;
}

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};


int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    vector<ll> A(N);
    map<ll,ll> mp;
    rep(i,N) cin >> A[i], mp[A[i]]++;
    int kind = 0;
    for(auto itr = mp.begin(); itr != mp.end();++itr) {
        kind++;
    }
    if(!(kind % 2)) cout << kind - 1 << endl;
    else cout << kind << endl;
}


Measured memory_bytes: 7296
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
dp = np.zeros(S+1, np.int64)
dp[0] = 1
for a in A:
    prev = dp.copy()
    dp[a:] += dp[:-a]
    dp += prev
    dp %= MOD

answer = dp[S]
print(answer%MOD)


Measured memory_bytes: 27500
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        if (N==1||N==2){
            System.out.println("0");
        }else {
            System.out.println((int)Math.ceil(N/2.0)-1);
        }
    }
}


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

#define ll long long int
#define vi vector<int>
#define ii pair< int , int >
#define vii vector<ii>
#define FOR(i, n) for(ll i = 0; i < (ll)n; i++)
int MAX(int a, int b){return (a > b) ? a:b;}
int MIN(int a, int b){return (a < b) ? a:b;}
int ABS(int x){return (x > 0) ? x:-x;}
int left(int x){return (x<<1);}
int right(int x){return (x<<1)+1;}
int lsone(int x){return (x&(-x));}

const int MOD = 1e9 + 7;
int n, a[21][21];
int ans[(1<<22)];
bool found[(1<<22)];

int dp(int mask){
	if(found[mask]) return ans[mask];
	found[mask] = true;
	//Count the bits;
	int pos = 0;
	for(int i = 0; i < n; i++){
		if(mask&(1<<i)) pos++;
	}
	if(pos == n) return ans[mask] = 1;
	for(int i = 0; i < n; i++) if((mask&(1<<i)) == 0){
		if(a[pos][i]){
			ans[mask] = (ans[mask]+dp(mask+(1<<i)))%MOD;
		}
	}
	//printf("dp(%d, %d) = %d\n", mask, pos, ans[mask]);
	return ans[mask];
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			scanf("%d", &a[i][j]);
		}
	}
	printf("%d\n", dp(0));
}

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

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln "\n"
#define dbg(x) cout<<#x" = "<<(x)<<ln

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > mat;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

int h, w;
string s, t = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
	cin >> h >> w;
	rep(i,h) {
		rep(j,w) {
			cin >> s;
			if (s=="snuke") {
				cout << t[j] << i+1 << ln;
				return 0;
			}
		}
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
typedef long long ll;
typedef long double ld;
const ll MOD = 998244353;
void transform(ll* a, int n) {
	for (int len = 1; len < n; len <<= 1)
		for (int i = 0; i < n; i += 2 * len)
			for (int j = 0; j < len; ++j) {
				ll u = a[i + j], v = a[i + j + len];
				a[i + j] = (u + v) % MOD;
				a[i + j + len] = (u - v) % MOD;
			}
}
ll modex(ll a, ll p, ll m = MOD) {
	if (!p) return 1;
	if (p & 1) return a * modex(a, p - 1, m) % m;
	ll v = modex(a, p >> 1, m);
	return v * v % m;
}
int main() {
	int k;
	scanf("%d", &k);
	int n = 1 << k;
	vector<ll> a(n), b(n);
	ll sum = 0;
	for (int i = 0; i < n; ++i) {
		scanf("%lld", &a[i]);
		sum += a[i];
	}
	sum = modex(sum, MOD - 2);
	for (int i = 0; i < n; ++i) a[i] = a[i] * sum % MOD;
	b[0] = n - 1;
	fill(b.begin() + 1, b.end(), -1);
	transform(a.data(), n);
	transform(b.data(), n);
	a[0] = 0;
	for (int i = 1; i < n; ++i) {
		a[i] = b[i] * modex(a[i] - 1, MOD - 2) % MOD;
		a[0] -= a[i];
	}
	a[0] %= MOD;
	transform(a.data(), n);
	assert(a[0] == 0);
	ll div = modex(n, MOD - 2);
	for (int i = 0; i < n; ++i) printf("%lld\n", (a[i] + MOD) % MOD * div % MOD);
}


Measured memory_bytes: 6912
#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,i,j,n,m,l=0,r;
    cin>>n>>m;
    for(i=1;i<=3;i++){
        if(i!=n && i!=m){
            cout<<i;
            return 0;
        }
    }
}



Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
S = [0]*N
D = [0]*N

for i in range(N):
    if A[i]+i < N:
        S[A[i]+i] += 1
    if i - A[i] > 0:
        D[i - A[i]] += 1
ans = 0
for l in range(N):
    ans += S[l]*D[l]
    

print(ans)

Measured memory_bytes: 92940
#include <bits/stdc++.h>
using namespace std;
    
const int N = 2005;
const int maxn = 1000 * 100 * 3; 
	   
vector <int> v[N];
int vis[N];
int cnt, cnt2;
int n, k;

struct bian {
    int x, y;
}vv[N];
    
void dfs(int p, int deep) {
    if(deep > k / 2)
    	cnt++;
    int len = v[p].size();
    vis[p] = 1;
    for(int i = 0; i < len; i++){ 
    	if(vis[v[p][i]])
			continue;
    	dfs(v[p][i], deep + 1);
	}
	vis[p]=0;
}
    
int main() {
    int x, y;
    cin >> n >> k;
    for(int i = 0; i < N; i++) {
    	v[i].clear();
    	vis[i] = 0;
    }
    for(int i = 1; i <= n - 1; i++) {
    	cin >> x >> y;
		v[x].push_back(y);
    	v[y].push_back(x);
    	vv[i].x = x;
		vv[i].y = y;
    }
    int ans = maxn;
    if(k % 2) {
    	for(int i = 1; i <= n - 1; i++) {
    		cnt = 0;
    		vis[vv[i].x] = 1;
    		dfs(vv[i].y, 0);
    		vis[vv[i].x] = 0;
    		vis[vv[i].y] = 1;
    		dfs(vv[i].x, 0);
    		vis[vv[i].y] = 0;
    		ans = min(ans, cnt);
    	}
    }
    else {
    	for(int i = 1; i <= n; i++) {
    		cnt = 0;
			cnt2 = 0;
    		dfs(i, 0);
    		ans = min(cnt, ans);
    	}
    }
    cout << ans;
	return 0;
}


Measured memory_bytes: 512
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007

int main()
{
	int n, k;
	cin >> n >> k;
	int p[200001];
	for(int i = 0; i < n; i++){
		cin >> p[i];
	}
	int sortedlen[200001] = {};
	for(int i = 0; i < n; i++){
		if(i > 0 && sortedlen[i - 1] > 1){
			sortedlen[i] = sortedlen[i - 1] - 1;
			continue;
		}
		sortedlen[i] = 1;
		while(i + sortedlen[i] < n && p[i + sortedlen[i] - 1] < p[i + sortedlen[i]]) sortedlen[i]++;
	}

	set<int> s;
	for(int i = 0; i < k; i++){
		s.insert(p[i]);
	}
	int ans = 1;
	bool hasKSorted = (sortedlen[0] >= k);
	for(int i = 1; i + k - 1 < n; i++){
		auto itr = s.begin();
		int minnum = *itr;
		itr = s.end();
		itr--;
		int maxnum = *itr;
		if(sortedlen[i] >= k){
			if(!hasKSorted){
				hasKSorted = true;
				ans++;
			}
		} else if(!(p[i - 1] == minnum && p[i + k - 1] > maxnum)){
			ans++;
		}
		s.erase(p[i - 1]);
		s.insert(p[i + k - 1]);
		// cout << i << endl;
		// for(int j = 0; j < i; j++){
		// 	cout << p[j] << " ";
		// }
		// for(auto j = s.begin(); j != s.end(); j++){
		// 	cout << *j << " ";
		// }
		// for(int j = i + k; j < n; j++){
		// 	cout << p[j] << " ";
		// }
		// cout << ans << endl;
	}
	cout << ans << endl;
}

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

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define REPS(i, m, n) for (int i = (m); i <= (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define reps(i, n) for (int i = 0; i <= (int)(n); i++)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define rreps(i, x) for (int i = (int)(x); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> P;
const int inf = INT_MAX;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos(-1.0);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { fill( (T*)array, (T*)(array+N), val ); }


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

    int N; cin >> N;
    cout << 800 * N - 200 * (N / 15) << endl;
    return 0;
}

Measured memory_bytes: 256
# 解説を見ながら
N = int(input())
A = list(map(int,input().split()))

# リストを作って，Amaxまでの数字について，aiの約数ならば足す，最終的には，要素が１のやつが求めるもの
# 一回検討した要素はsetに入れて次出たときは使わないようにする
import numpy as np
#L = np.zeros((10**6+10,))
A.sort()
MAX=10**6+1
L = [0]*MAX
used = set()
#first = True  # firstのフラッグの使い回しをしていた．複数に分かれる条件分岐はしっかりとどのような分岐をするか書く癖をつけたほうがよい
for a in A:
    if L[a] == 2:
        continue
    if a in used:
        for i in range(0,MAX,a):
            L[i] = 2
        # L[::a] += 1　要素アクセスだから遅くなった?
        continue
    used.add(a)
    # L[1:][::a] += 1こういう書き方はリストではできないので注意
    L[a] = 1
    for i in range(2*a,MAX,a):
        L[i] = 2
    #L[::a] += 1
count = 0
for a in A:
    if L[a] == 1:
        count += 1
print(count)







Measured memory_bytes: 55256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
struct UnionFind {
    vector<int> A;
    UnionFind(int n) : A(n, -1) {}
    int find(int x) {
        if (A[x] < 0) return x;
        return A[x] = find(A[x]);
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (A[x] > A[y]) swap(x, y);
        A[x] += A[y];
        A[y] = x;
    }
};
template <class T>
struct SegTreeMin {
    vector<T> A;
    int N;
    T minval;
    SegTreeMin(int n, T minv) : minval(minv) {
        N = 1;
        while (N < n) N *= 2;
        A.assign(2*N, minval);
    }
    void set(int idx, T val) {
        idx += N;
        A[idx] = val;
        for (idx /= 2; idx > 0; idx /= 2) {
            A[idx] = min(A[2*idx+0], A[2*idx+1]);
        }
    }
    T query(int L, int R) { // [L, R)
        L += N, R += N;
        T ans = minval;
        while (L < R) {
            if (R & 1) ans = min(ans, A[--R]);
            if (L & 1) ans = min(ans, A[L++]);
            L /= 2, R /= 2;
        }
        return ans;
    }
};
int main()
{
    Int N, D; cin >> N >> D;
    vector<int> A(N); for (auto &a : A) cin >> a;
    vector<int> I(N); iota(begin(I), end(I), 0);
    sort(begin(I), end(I), [&](int i, int j) { return A[i] < A[j]; });
    vector<tuple<Int, int, int>> edges;
    auto add_edge = [&](int i, int j) {
        if (i == -1 || j == -1) return;
        edges.emplace_back(abs(i-j)*D+A[i]+A[j], i, j);
    };
    auto maxval = make_pair((Int)1e18, -1);
    using SegTree = SegTreeMin<pair<Int, int>>;
    auto S = SegTree(N, maxval);
    auto T = SegTree(N, maxval);
    for (int i = 0; i < N; i++) {
        auto p = S.query(0, I[i]);
        auto q = T.query(I[i], N);
        add_edge(I[i], p.second);
        add_edge(I[i], q.second);
        S.set(I[i], make_pair(-D * I[i] + A[I[i]], I[i]));
        T.set(I[i], make_pair(D * I[i] + A[I[i]], I[i]));
    }
    S = SegTree(N, maxval);
    T = SegTree(N, maxval);
    for (int i = N-1; i >= 0; i--) {
        auto p = S.query(0, I[i]);
        auto q = T.query(I[i], N);
        add_edge(I[i], p.second);
        add_edge(I[i], q.second);
        S.set(I[i], make_pair(-D * I[i] + A[I[i]], I[i]));
        T.set(I[i], make_pair(D * I[i] + A[I[i]], I[i]));
    }
    sort(begin(edges), end(edges));
    UnionFind uf(N);
    Int ans = 0;
    for (auto &tup : edges) {
        Int cost; int i, j; tie(cost, i, j) = tup;
        if (uf.find(i) != uf.find(j)) {
            uf.unite(i, j);
            ans += cost;
        }
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 36576
// C++ program to demonstrate default behaviour of 
// sort() in STL. 
#include <bits/stdc++.h> 
using namespace std;

/*
long long int lcm(long long int a,long long int b){
	
	
     a = (a/(__gcd(a, b))) * (b/(__gcd(a, b))) * (__gcd(a, b));
    
    return a;
	
}
*/
  
int main() 
{ 

   int n;
   
   cin >> n;
   
   double t = (n-(n/2));
   
   double w = t/n;
      
   printf("%.10f",w);
        
    return 0; 
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
#define LL long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n,k;
int a[200005];
double p[1005];
double ft[200005];

int main(){

	for (int i = 1; i <= 1000; i++ ){
		p[i] = 0;
		for ( int j = 1; j <= i; j++ ) p[i] += j;
		p[i] /= 1.0 * i;
	}

	scanf("%d%d",&n,&k);
	for ( int i = 1; i <= n; i++ ) scanf("%d",&a[i]);

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

	double ans = 0;
	for ( int i = k; i <= n; i++ ){
		ans = max( ans, ft[i] - ft[i-k] );
	}

	printf("%.9lf\n",ans);
	return 0;
}

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

int main() {
  char S;
  cin >> S;
  
  if (S=='a' || S=='i' || S=='u' || S=='e' || S=='o'){
    cout << "vowel" << endl ;
  }
  else{
    cout << "consonant" << endl ;
  }
      // ここにプログラムを追記
}


Measured memory_bytes: 256
def check_pickedup(N: int, M: int, V: int, P: int, A: list, accum_score: list, i: int) -> bool:
    th_score = A[P-1]
    if A[i] >= th_score:
        return True
    sum_surplus = (accum_score[i-1] - (accum_score[P-2] if P-2 >=0 else 0)) - ((i-1)-(P-2))*A[i]
    #print('i: ', i)
    #print('th_score: ', th_score)
    #print('sum_surplus: ', sum_surplus)
    #print('th_score - A[i]: ', th_score - A[i])
    if th_score - A[i] <= M and sum_surplus <= M*(N-V):
        return True
    return False

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    
    A.sort(reverse=True)
    
    accum_score = [A[0]] * N
    for i in range(1, N):
        accum_score[i] = accum_score[i-1] + A[i]
    
    # Reduce N-V scores each judge
    ans = 0
    was_checked = {}
    for i, a in enumerate(A):
        # Check a will be picked up
        if a in was_checked:
            ans += 1
            continue
        if check_pickedup(N, M, V, P, A, accum_score, i):
            ans += 1
            was_checked[a] = True
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()
   

Measured memory_bytes: 68632
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

white = 0
for i in range(h):
    white += s[i].count(".")
#print(white)
inf = 100000
smap = [[inf]*w for _ in range(h)]
smap[0][0] = 1
visited = [[0]*w for _ in range(h)]
visited[0][0] = 1

q = deque()
q.append(0)
q.append(0)

while q:
    y = q.popleft()
    x = q.popleft()
    if x != 0 and s[y][x-1] == "." and visited[y][x-1] == 0:
        lx = x-1
        q.append(y)
        q.append(lx)
        visited[y][lx] = 1
        smap[y][lx] = min(smap[y][lx], smap[y][x] + 1)

    if x != w-1 and s[y][x+1] == "." and visited[y][x+1] == 0:
        rx = x+1
        q.append(y)
        q.append(rx)
        visited[y][rx] = 1
        smap[y][rx] = min(smap[y][rx], smap[y][x] + 1)

    if y != 0 and s[y-1][x] == "." and visited[y-1][x] == 0:
        uy = y-1
        q.append(uy)
        q.append(x)
        visited[uy][x] = 1
        smap[uy][x] = min(smap[uy][x], smap[y][x] + 1)

    if y != h-1 and s[y+1][x] == "." and visited[y+1][x] == 0:
        dy = y+1
        q.append(dy)
        q.append(x)
        visited[dy][x] = 1
        smap[dy][x] = min(smap[dy][x], smap[y][x] + 1)


if smap[h-1][w-1] == inf:
    print(-1)
else:
    print(white-smap[h-1][w-1])


Measured memory_bytes: 40044
#include <iostream>
#include <string>
#include <vector>
#include <atcoder/dsu>
using ll=long long;
using namespace std;
using namespace atcoder;

int main(){
    int N,Q;
    cin>>N>>Q;
    dsu d(N);
    int a,b,c;
    for(int i=0;i<Q;i++){
        cin>>a>>b>>c;
        if(a){
            if(d.same(b,c)){
                cout<<1<<endl;
            }else{
                cout<<0<<endl;
            }
        }else{
            d.merge(b,c);
        }
    }

    return 0;
}

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

int main() {
  int N, L;
  cin >> N >> L;
  
  vector<string> S(N);    
  for (int i = 0; i < N; i++) {
    cin >> S.at(i);
  }
  
  sort(S.begin(),S.end());
  
  string sum = "";

  for (int i = 0; i < N; i++) {
    sum = sum + S.at(i);
  }  
   
  cout << sum << endl;
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL Hash[100050];
int main(){
  //  freopen("input.txt","r",stdin);
    LL n,k;
    scanf("%Ild%Ild",&n,&k);
    memset(Hash,0,sizeof(Hash));
    for(int i=1;i<=n;i++){
        LL a,b;
        scanf("%Ild%Ild",&a,&b);
        Hash[a]+=b;
    }
    for(int i=1;i<=100000;i++){
        if(Hash[i]) k-=Hash[i];
        if(k<=0){
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>    //faster version
using namespace std;
typedef long long LL;
const int MAX_N = 50 + 5;
const int MAX_M = 20 + 5;

int n, m, u, v;
LL path[MAX_N] = {0};
vector<LL> rec; //records the constraints

struct Edge {
    int to, next;
}edges[2*MAX_N];

int cnt = 0;
int head[MAX_N];

void addedge(int u, int v)
{
    edges[++cnt].to = v;
    edges[cnt].next = head[u];
    head[u] = cnt;
}

void dfs(int u, int p, LL S)   //set S repersents the path from root to node u
{
    path[u] = S ^ (1LL << (u-1));
    for (int j = head[u]; j != -1; j = edges[j].next)
    {
        Edge& e = edges[j];
        if (e.to != p)
        {
            dfs(e.to, u, path[u]);
        }
    }
}

int main()
{
    scanf("%d", &n);
    memset(head, -1, sizeof(head));
    for (int i = 1; i < n; i++)
    {
        scanf("%d %d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    dfs(1, -1, 0LL);

    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &u, &v);
        rec.push_back(path[u] ^ path[v]);
    }
    LL ans = 0;
    for (int S = 0; S < (1<<m); S++)
    {
        LL T = 0;
        for (int k = 0; k < m; k++)
        {
            if (S & (1<<k))
            {
                T |= rec[k];
            }
        }
        int cnt_s = __builtin_popcount(S), cnt_t = __builtin_popcountll(T);
        LL sgn = (cnt_s & 1 ? -1LL : 1LL);
        ans += sgn * (1LL << (n-1-cnt_t));
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;

enum inf3 = 1_001_001_001;
enum inf6 = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;


void main() {
    int n; string s;
    scan(n);
    scan(s);
    auto cnt = new int[](26);
    foreach (ch ; s) {
        cnt[ch - 'a']++;
    }
    long ans = 1;
    foreach (i ; 0 .. 26) {
        ans *= cnt[i] + 1;
        ans %= mod;
    }
    ans += mod - 1;
    ans %= mod;
    writeln(ans);
}



























int[][] readGraph(int n, int m, bool isUndirected = true, bool is1indexed = true) {
    auto adj = new int[][](n, 0);

    foreach (i; 0 .. m) {
        int u, v;
        scan(u, v);
        if (is1indexed) {
            u--, v--;
        }
        adj[u] ~= v;
        if (isUndirected) {
            adj[v] ~= u;
        }
    }

    return adj;
}

alias Edge = Tuple!(int, "to", int, "cost");

Edge[][] readWeightedGraph(int n, int m, bool isUndirected = true, bool is1indexed = true) {
    auto adj = new Edge[][](n, 0);

    foreach (i; 0 .. m) {
        int u, v, c;
        scan(u, v, c);
        if (is1indexed) {
            u--, v--;
        }
        adj[u] ~= Edge(v, c);
        if (isUndirected) {
            adj[v] ~= Edge(u, c);
        }
    }

    return adj;
}

void yes(bool b) {
    writeln(b ? "Yes" : "No");
}

void YES(bool b) {
    writeln(b ? "YES" : "NO");
}

T[] readArr(T)() {
    return readln.split.to!(T[]);
}

T[] readArrByLines(T)(int n) {
    return iota(n).map!(i => readln.chomp.to!T).array;
}

void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}


Measured memory_bytes: 508
#include <stdio.h>
#include <vector>
using namespace std;
#define FIND 1
#define FAIL 2
#define PB push_back
#define N (110)
int a[N], b[N], c[N], d[N], p[N], ans;
vector<int> v[N];
int n, flag, vst[N];
int dfs(int x){
    if (vst[x] == flag) return FAIL;
    vst[x] = flag;
    int y;
    for (auto it = v[x].begin(); it != v[x].end(); ++it){
        if (p[y=*it] == 0 || dfs(p[y]) == FIND){
            p[y] = x;
            return FIND;
        }
    }
    return FAIL;
}
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i){
        scanf("%d%d", a+i, b+i);
    }
    for (int i = 1; i <= n; ++i){
        scanf("%d%d", c+i, d+i);
    }
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j){
            if (a[i] < c[j] && b[i] < d[j]){
                v[i].PB(j);
            }
        }
    }
    for (int i = 1; i <= n; ++i){
        flag++;
        ans += dfs(i) == FIND;
    }
    printf("%d\n", ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;i++)
#define For(i,a,b) for(int i=(a),i##_end=(b);i<i##_end;i++)
#define per(i,a,b) for(int i=(b),i##_st=(a);i>=i##_st;i--)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define dbg(x) cerr<<#x" = "<<x<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Es(x,i) for(Edge *i=G[x];i;i=i->nxt)
typedef long long ll;
typedef pair<int,int> pii;
const int inf=~0u>>1,MOD=1e9+7;
inline int rd() {
    int x,c,f=1;while(!isdigit(c=getchar()))f=c!='-';x=c-'0';
    while(isdigit(c=getchar()))x=x*10+c-'0';return f?x:-x;
}
int a[55];
int main(){
	int n=rd();
	rep(i,1,n)a[i]=rd();
	int l=0,r=0,t,p;
	rep(i,1,n)if(a[i]>0)r=max(r,a[i]);else l=min(l,a[i]);
	if(r>-l)p=r;else p=l;
	rep(i,1,n)if(a[i]==p)t=i;
	printf("%d\n",2*n-1);
	rep(i,1,n)printf("%d %d\n",t,i);
	if(p>0)rep(i,1,n-1)printf("%d %d\n",i,i+1);
	else per(i,2,n)printf("%d %d\n",i,i-1);
}

Measured memory_bytes: 256
import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
"""
#decomment when needed
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
"""
a,b  = ips()

print(max(a+b,a-b,a*b))

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

#define int long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)
 
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
 
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
 
#if 1
//-------------
// DUMPマクロ
// https://www.creativ.xyz/dump-cpp-652/
 
// vector
template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    for (T& x : vec) is >> x;
    return is;
}
// pair
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
// vector
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
// map
template <typename T, typename U>
ostream& operator<<(ostream& os, map<T, U>& map_var) {
    os << "{";
    repi(itr, map_var) {
        os << *itr;
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set
template <typename T>
ostream& operator<<(ostream& os, set<T>& set_var) {
    os << "{";
    repi(itr, set_var) {
        os << *itr;
        itr++;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
 
#define DUMPOUT cerr
 
void dump_func() {
    DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&& ... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}
#ifdef DEBUG
#define DEB
#define dump(...)                                                              \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
            << endl                                                            \
            << "    ",                                                         \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
#endif



signed main(){
    int N;
    cin >> N;
    vector<int> X(N), L(N);
    vector<P> d(N);
    rep(i,N){
        cin >> X[i] >> L[i];
        
        d[i] = P(X[i]+L[i], X[i]-L[i]);
    }
    sort(d.begin(), d.end());
    
    rep(i,N) dump(d[i]);
    int ans = 0;
    int t=-INF; // 最後に選んだものの座標
    rep(i,N){
        if(t<=d[i].second){
            ans++;
            t = d[i].first;
            dump(d[i]);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3328
#include <iostream>
#include <cstdio>
using namespace std;
char c;
int n,m;
int f[110][110][110][110];
int linex[110][110],liney[110][110];
int X,Y;
struct LIMIT{
	int u,d,l,r;
}L;
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){
			scanf("%c",&c);
			while (c!='.'&&c!='o'&&c!='E') scanf("%c",&c);
			if (c=='E') X=i,Y=j;
			linex[i][j]=linex[i][j-1];
			liney[i][j]=liney[i-1][j];
			if (c=='o'){
				linex[i][j]++;
				liney[i][j]++;
			}
		}
	
    L.u=X-1;L.d=n-X;L.l=Y-1;L.r=m-Y;
    for(int u=0;u<=L.u;u++)
        for(int d=0;d<=L.d;d++)
            for(int l=0;l<=L.l;l++)
                for(int r=0;r<=L.r;r++){
                    int L=max(Y-l,r+1),R=min(Y+r,m-l);
                    if(L<=R){
                        f[u+1][d][l][r]=max(f[u+1][d][l][r],f[u][d][l][r]+(X-u-1>=d+1?linex[X-u-1][R]-linex[X-u-1][L-1]:0));
                        f[u][d+1][l][r]=max(f[u][d+1][l][r],f[u][d][l][r]+(X+d+1<=n-u?linex[X+d+1][R]-linex[X+d+1][L-1]:0));
                    }
                    L=max(X-u,d+1);
					R=min(X+d,n-u);
                    if(L<=R){
                        f[u][d][l+1][r]=max(f[u][d][l+1][r],f[u][d][l][r]+(Y-l-1>=r+1?liney[R][Y-l-1]-liney[L-1][Y-l-1]:0));
                        f[u][d][l][r+1]=max(f[u][d][l][r+1],f[u][d][l][r]+(Y+r+1<=m-l?liney[R][Y+r+1]-liney[L-1][Y+r+1]:0));
                    }
                }
    printf("%d\n",f[L.u][L.d][L.l][L.r]);
	return 0;
}


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

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const int MOD = 1000000007;
//const int MOD = 998244353;

// Lib
//
void normalize(vector<pll> &nums) {
    if (nums.size() > 1) {
        if (nums[nums.size()-1].first == nums[nums.size()-2].first) {
            nums[nums.size()-2].second += nums[nums.size()-1].second;
            nums.pop_back();
        }
    }
}

void zouka(vector<pll> &nums) {
    if (nums.back().second == 1) {
        nums.back().first += 1;
    }
    else {
        nums.back().second--;
        nums.push_back(pll(nums.back().first+1, 1));
    }
    normalize(nums);
}

int main(){
#ifdef MYLOCAL
    ifstream in("input.txt");
    cin.rdbuf(in.rdbuf());
#endif
    int N; cin >> N;
    vector<ll> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    ll low = 0, high = N+1;
    while (high - low > 1) {
        ll mid = (low + high) / 2;

        vector<pll> nums;
        nums.push_back( {0, a[0]} );

        bool ok = true;
        for (int i = 1; i < N; ++i) {
            if (a[i-1] < a[i]){
                nums.push_back(pll(0, a[i] - a[i-1]));
            }
            else {
                ll sum = 0;
                while (nums.size() > 0 && sum + nums.back().second <= a[i-1] - a[i]) {
                    sum += nums.back().second;
                    nums.pop_back();
                }
                nums.back().second -= a[i-1] - a[i] - sum;

                if (nums.back().first == mid-1) {
                    if (nums.size() == 1) {
                        ok = false;
                        break;
                    }
                    long long num = nums.back().second;
                    nums.pop_back();
                    zouka(nums);
                    nums.push_back(pll(0, num));
                }
                else zouka(nums);
            }
            normalize(nums);
        }

        if (ok) high = mid;
        else low = mid;
    }
    cout << high << endl;
    return 0;
}


Measured memory_bytes: 1792
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
  long N = sc.nextLong();
  long ans=sc.nextLong();
  long tmp;
  for(int i=1;i<N;i++){
    tmp=sc.nextLong();
    ans=ans/gcd(ans,tmp)*tmp;
  }
  System.out.println(ans);
}
public static long gcd(long m, long n) {
  if (n == 0) {
    return m;
  }
  return gcd(n, m % n);
}
}


Measured memory_bytes: 23636
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        int n = int.Parse(Console.ReadLine());
        List<int> s = Console.ReadLine().Split().Select(int.Parse).Distinct().ToList();
        n = s.Count();
        int q = int.Parse(Console.ReadLine());
        List<int> t = Console.ReadLine().Split().Select(int.Parse).ToList();
        s.Sort();
        int count = 0;
        for (int i = 0; i < q; i ++) {
            count += binarySearch(s,n,t[i]);
        }
        Console.WriteLine(count);
    }
    static int binarySearch(List<int> s, int n, int t) {
        int l = 0;
        int r = n;
        while(l < r) {
            int m = (l+r)/2;
            if (s[m]<t) l = m+1;
            else if (s[m]>t) r = m;
            else return 1;
        }
        return 0;
    }
}


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

int main() {
  string s;
  cin >> s;
  ll cost = 0, cnt = 0;
  rep(i, s.size()) {
    if (s[i] == 'W') {
      cost += i - cnt;
      cnt++;
    }
  }
  cout << cost << endl;
  return 0;
}


Measured memory_bytes: 640
N = int(input())
a = list(map(int, input().split()))
left = sum(a)
light = 0
ans = 10 **10

for i in range(0, N-1):
    left -= a[i]
    light += a[i]
    tmp = abs(left-light)
    if tmp < ans:
        ans = tmp

print(ans)
    

Measured memory_bytes: 23792
// eddy1021
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod7=1000000007LL;
inline LL getint(){
  LL _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline LL add(LL _x, LL _y, LL _mod=mod7){
  _x+=_y;
  return _x>=_mod ? _x-_mod : _x;
}
inline LL sub(LL _x, LL _y, LL _mod=mod7){
  _x-=_y;
  return _x<0 ? _x+_mod : _x;
}
inline LL mul(LL _x, LL _y ,LL _mod=mod7){
  _x*=_y;
  return _x>=_mod ? _x%_mod : _x;
}
LL mypow(LL _a, LL _x, LL _mod){
  if(_x == 0) return 1LL;
  LL _ret = mypow(mul(_a, _a, _mod), _x>>1, _mod);
  if(_x & 1) _ret=mul(_ret, _a, _mod);
  return _ret;
}
LL mymul(LL _a, LL _x, LL _mod){
  if(_x == 0) return 0LL;
  LL _ret = mymul(add(_a, _a, _mod), _x>>1, _mod);
  if(_x & 1) _ret=add(_ret, _a, _mod);
  return _ret;
}
void sleep(double sec = 1021){
  clock_t s = clock();
  while(clock() - s < CLOCKS_PER_SEC * sec);
}
#define Bye exit(0)
int __ = 1 , _cs;
/*********default*********/
const int N=303030;
const int mod=998244353;
int fac[N], ifac[N];
void build(){
  fac[0]=ifac[0]=1;
  for(int i=1; i<N; i++){
    fac[i]=mul(fac[i-1], i, mod);
    ifac[i]=mypow(fac[i], mod-2, mod);
  }
}
LL n, a, b, k;
void init(){
  n=getint();
  a=getint();
  b=getint();
  k=getint();
}
int cal(int tk){
  return mul(fac[n], mul(ifac[tk], ifac[n-tk], mod), mod);
}
void solve(){
  LL ans=0;
  for(LL i=0; i<=n; i++){
    if(i*a > k) break;
    LL res=k-i*a;
    if(res % b) continue;
    res /= b;
    if(res > n) continue;
    ans=add(ans, mul(cal(i), cal(res), mod), mod);
  }
  cout<<ans<<endl;
}
int main(){
  build();
  //__ = getint();
  while(__ --){
    init();
    solve();
  }
}


Measured memory_bytes: 2560
#include <cstdlib>
#include <iostream>
#include <set>
#include <string>
using namespace std;

const int numberOfAlphabet = 26;
const char last = 'a';

string convert(int n) {
	string res = "";
	while(n) {
		res += 'a' + (n % numberOfAlphabet);
		n /= numberOfAlphabet;
	}

	return res;	
}

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

	string prefix = "pre";
	const string postfix(2, last);
	set<string> used;

	for(int i = 0; i < 50; ++i) {
		string myWord = prefix + convert(i) + postfix;
		cout << "?" << myWord << endl;
		string opWord;
		cin >> opWord;
		if(opWord[0] != last || used.find(opWord) != used.end())
			break;

		used.insert(opWord);
		prefix = opWord[opWord.size() - 1];
	}

	cout << "!OUT" << endl;

	return EXIT_SUCCESS;
}

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

string fixedNum( string a )
{
    if( a.size() == 1 )
        return a;
    for( int i = 0; i < a.size(); i++ )
        if( '1'<= a[i] && a[i] <= '9' )
            return a.substr( i, a.size() );
    return "0";
}

string calcAddition( string a, string b )
{
    a = fixedNum(a); b = fixedNum(b);
    int as = a.size(), bs = b.size(), d = as > bs ? as - bs : bs - as;
    string s = "0", t = "0";
    for( int i = 0; i < d; i++ )
        as > bs ? t += "0" : s += "0";
    s += a; t += b;

    for( int i = s.size() - 1; i >= 1; i-- )
    {
        s[i] += t[i] - '0';
        if( s[i] > '9' )
        {
            s[i] -= 10;
            s[i-1]++;
        }
    }

    return s[0] == '0' ? s.substr( 1, s.size() ) : s;
}

string calcMultiplication( string a, string b )
{
    a = fixedNum(a); b = fixedNum(b);
    int as = a.size(), bs = b.size(), d = as > bs ? as - bs : bs - as;
    string s = "0", t = "0", x = "", sum = "", zero = "", digit = "";
    for( int i = 0; i < d; i++ )
        as > bs ? t += "0" : s += "0";
    s += a; t += b;

    for( int i = 0; i < s.size(); i++ )
        zero += "0";
    
    x = zero;
    sum = zero;

    for( int i = s.size() - 1; i >= 1; i-- )
    {
        for( int j = s.size() - 1; j >= 1; j-- )
            x[j] = ( t[i] - '0' ) * ( s[j] - '0' );
        for( int j = s.size() - 1; j >= 1; j-- )
        {
            int f = x[j] / 10;
            x[j-1] += f;
            x[j] = x[j] - 10 * f + '0';
        }
        x += digit;
        sum = calcAddition( x, sum );
        digit += "0";
        x = zero;
    }
    return sum;
}

int main()
{
    string a, b;

    cin >> a >> b;

    int as = a.size(), bs = b.size();
    string s = a.substr( 1, as ), t = b.substr( 1, bs );

    if( a[0] == '-' && b[0] == '-' )
        cout << calcMultiplication( s, t ) << endl;
    else if( a[0] >= '0' && b[0] >= '0' )
        cout << calcMultiplication( a, b ) << endl;
    else
    {
        if( a == "0" || b == "0" )
            cout << "0" << endl;
        else if( a[0] == '-' )
            cout << '-' << calcMultiplication( s, b ) << endl;
        else
            cout << '-' << calcMultiplication( a, t ) << endl;
    }
    return 0;
}



Measured memory_bytes: 3240
void main() {
	auto ip = readAs!(int[]), a = ip[0], b = ip[1];
	int tmp;
	tmp += a-1;
	if(b >= a) tmp++;
	tmp.writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

T[] deepcopy(T)(T[] a) {
	static if(isArray!T) {
		T[] res;
		foreach(i; a) {
			res ~= deepcopy(i);
		}
		return res;
	} else {
		return a.dup;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long n,a,b;
const int nmax=100005;
int h[nmax];
bool can(int t){
  long long sum=0;
  for(int i=0;i<n;i++){
    if(h[i]-b*t>0){
      sum+=(h[i]-b*t+a-b-1)/(a-b);
    }
  }
  return sum<=t;
}
int main(){
  cin >> n >> a >> b;
  for(int i=0;i<n;i++){
    cin >> h[i];
  }
  int left=0,right=1000000005;
  while(left!=right){
    int mid=(left+right)/2;
    if(can(mid)){
      right=mid;
    }
    else{
      left=mid+1;
    }
  }
  cout << left << endl;
}

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

#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPL(i,a,n) for(ll i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"
#define SORTVG(v) sort(v.begin(),v.end(),greater<>())
#define SORTV(v) sort(v.begin(),v.end())
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007

typedef long long ll;
typedef pair<int,int> Pii;
typedef vector<int> Vi;

template<class T> void chmax(T& a, T b) {if(a < b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a > b){a=b;}}
template<class T> void YesNo(T& a) {if(a){cout << "Yes" << ENT;}else{cout << "No" << ENT;}}
template<class T> void YESNO(T& a) {if(a){cout << "YES" << ENT;}else{cout << "NO" << ENT;}}
template<class T> void AorB(T& a, string A,string B) {if(a){cout << A << ENT;}else{cout << B << ENT;}}

int n,m;
vector<int> used(n,0);
vector< vector<int> > connect(n,vector<int>(n,0));

void dfs(int now,int p,int depth){
    used[now]=depth;
    for(auto i : connect[now]){
        if(i==p) continue;
        dfs(i,now,depth+1);
    }
}

void atcoder(){
    cin >> n;
    m=n-1;
    vector<int> a(m),b(m);
    REP(i,0,m){
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }
    used=Vi(n,0);
    connect=vector< vector<int> >(n);
    REP(i,0,m){
        connect[a[i]].push_back(b[i]);
        connect[b[i]].push_back(a[i]);
    }
    dfs(0,-1,0);
    int m,ch=-1;
    REP(i,0,n){
        if(used[i]>ch){
            ch=used[i];
            m=i;
        }
    }
    used=vector<int>(n,0);
    dfs(m,-1,0);
    ch=0;
    REP(i,0,n) chmax(ch,used[i]);
    
    if(ch%3!=1) cout<<"First"<<ENT;
    else cout<<"Second"<<ENT;
}

signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    atcoder();
    return 0;
}


Measured memory_bytes: 23296