akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

typedef long long ll;
//typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector<vector<int>> mat;
//typedef unsigned int uint;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

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

	int Q;
	priority_queue<int> lpq;
	priority_queue<int, vector<int>, greater<int>> rpq;
	int sl = 0, sr = 0;
	int m = INF;
	int B = 0;
	int q, a, b;

	cin >> Q;
	rep(i, 0, Q)
	{
		cin >> q;
		if (q == 1)
		{
			cin >> a >> b;
			B += b;
			if (m == INF)
			{
				m = a;
			}
			else
			{
				if (a < m)
				{
					lpq.push(a);
					sl += m - a;
				}
				else
				{
					rpq.push(a);
					sr += a - m;
				}

				if (SZ(lpq) > SZ(rpq))
				{
					int t = lpq.top();
					rpq.push(m);
					sr += (m - t)*SZ(rpq);
					sl -= (m - t)*SZ(lpq);
					m = t;
					lpq.pop();
				}
				if (SZ(lpq)+1 < SZ(rpq))
				{
					int t = rpq.top();
					lpq.push(m);
					sl += (t - m)*SZ(lpq);
					sr -= (t - m)*SZ(rpq);
					m = t;
					rpq.pop();
				}

			}
		}
		else
		{
			cout << m << " " << sl + sr + B << endl;
		}
	}

	return 0;
}



Measured memory_bytes: 3828
n = int(input())
cards = []
for i in range(n):
    mark, lank = (input().split())
    cards.append([mark, int(lank)])
    
for j in ['S','H','C','D']:
    for num in range(1,14):
        if not[j, num] in cards:
            print('{} {}'.format(j,num))


Measured memory_bytes: 5600
#include "bits/stdc++.h"
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>

using namespace std;

#ifndef _DEBUG
#define main_ main
#endif
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<string> vs;

template <typename T>
using keyVal = pair<string, T>;
template<typename T>
bool val_greater(const keyVal<T>& left, const keyVal<T>& right) {
	return left.second > right.second;
}

void init_global() {}

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

	int N;  cin >> N;
	vs S(N); FOR(i, 0, N) cin >> S[i];
		
	vi h(26, INF);
	FOR(i, 0, N) {
		vi th(26, 0);
		FOR(j, 0, S[i].size()) {
			th[S[i][j] - 'a']++;
		}

		FOR(c,0,26) {
			h[c] = min(h[c], th[c]);
		}
	}

	string ans = "";
	for (char c = 'a'; c <= 'z'; ++c) {
		ans += string(h[c - 'a'], c);
	}

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


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(" ").map(String::toInt)
    val minCost = Array(n + 1) { Array(n + 1) { Long.MAX_VALUE / 10 } }
    (1..n).forEach { minCost[it][it] = 0 }
    val branches = (1..m).map {
        val (a, b, c) = readLine()!!.split(" ").map(String::toInt)
        minCost[a][b] = c.toLong()
        minCost[b][a] = c.toLong()
        Triple(a, b, c)
    }
    for (j in 1..n)
        for (i in 1..n)
            for (k in 1..n)
                minCost[i][k] = Math.min(minCost[i][k], minCost[i][j] + minCost[j][k])

    println(branches.filter { minCost[it.first][it.second] < it.third.toLong() }.size)
}


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

int main() {
  ll N,ind;
  cin >> N;
  
  for (ll i=1;i<N;i++) {
    ll x=i*i;
    if (N<x) {
      ind = i;
      break;
    }
  }
  
  cout << (ind-1)*(ind-1);
}

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


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

  int ans = a + b + c - max(a, max(b, c));

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

Measured memory_bytes: 3556
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;

int main() {
	ll x,ans=100,count=0;
	cin >> x;
	while (ans < x) {
		ans += ans / 100;
		count++;
	}
	cout << count << endl;
}

Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <bitset>
#include <vector>
#include <queue>
#include <map>
#include <set>

#define i64 int64_t
#define ff(ii,nn,mm) for(int ii=nn;ii<mm;ii++)
#define st(vvv) sort(vvv.begin(),vvv.end())
#define rvs(vvv) reverse(vvv.begin(),vvv.end())
int inf = 1000000007;
i64 giant = 4000000000000000000;

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> data(2);
	ff(i, 0, 2) {
		data[i].first = 0;
		data[i].second = 0;
	}
	ff(i, 0, n) {
		int x;
		cin >> x;
		if (x > data[0].first) {
			data[0].first = x;
			data[0].second = i;
		}
		else if (x > data[1].first) {
			data[1].first = x;
			data[1].second = i;
		}
	}
	ff(i, 0, n) {
		if (i == data.at(0).second)cout << data[1].first << endl;
		else cout << data[0].first << endl;
	}
	return 0;
}

Measured memory_bytes: 1664
import math

a,b,h,m = map(int,input().split())

c = (h * 60 * 0.5) + (m * 0.5)
d = m * 6

if c > d:
  e = c - d
else:
  e = d - c

ans = (a * a) + (b * b) - 2 * a * b * math.cos(math.radians(e))
print(math.sqrt(ans))

Measured memory_bytes: 9416
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
	vector<int> a(3);
	for(int i=0;i<3;i++)
		cin >> a[i];
	sort(a.begin(),a.end());

	cout << a[0] << " " << a[1] << " " << a[2] << endl;
	
}


Measured memory_bytes: 3136
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second

const ll MOD = 1e9+7;
const int MAX = 200050;
ll fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("in.txt", "r", stdin);
	COMinit();
	int h, w, a, b;
	cin >> h >> w >> a >> b;
	int y = h - a;
	int x = b + 1;
	ll ret = 0;
	while(true) {
		bool flag = y >= 1 && y <= h && x >= 1 && x <= w;
		if(!flag) break;
		int n = y - 1 + x - 1;
		ll p = COM(n,y-1);
		n = h - y + w - x;
		ll q = COM(n,h-y);
		ret += p*q;
		ret %= MOD;
		y--;
		x++;
	}
	cout << ret << '\n';
	return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

int main() {
    ll x;
    cin >> x;

    ll t = 100;
    for (int i = 1;; i++) {
        t += t / 100;
        if (t >= x) {
            cout << i << endl;
            break;
        }
    }

    return 0;
}

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

int main()
{
  int number = 0;
  string s;
  cin >> s;
  if (s[0] == '1') number++;
  if (s[1] == '1') number++;
  if (s[2] == '1') number++;
  cout << number << endl;
  return 0;
}
  

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
 int a[4],b[4],h,bb,i;
 while(cin>>a[0]>>a[1]>>a[2]>>a[3]>>b[0]>>b[1]>>b[2]>>b[3]){
  h=bb=0;
  for(i=0;i<4;i++)if(a[i]==b[i])h++;
  sort(a,a+4);sort(b,b+4);
  for(i=0;i<4;i++)if(find(b,b+4,a[i])!=b+4)bb++;
  bb -= h;
  cout<<h<<" "<<bb<< endl;
 }
}

Measured memory_bytes: 1180
from collections import deque


def solve():
    N = int(input())
    q = deque([1,2,3,4,5,6,7,8,9])
    cnt = 0
    l = []

    while cnt<N:
        p = q.popleft()
        l.append(p)
        cnt += 1
        for i in range(max((p%10)-1,0), min((p%10)+1, 9)+1):
            q.append(10*p+i)

    print(l[N-1])


if __name__ == "__main__":
    solve()


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

const int INF = 1e9;

int dist[100010];

void dfs(int u, int p, const vector<vector<pair<int, int>>>& g) {
	for (auto t : g[u]) {
		int v = t.first, cost = t.second;
		if (v == p) continue;
		dist[v] = dist[u] + cost;
		dfs(v, u, g);
	}
}

int main(int argc, char const *argv[])
{
	int n; cin >> n;
	vector<int> u(n - 1), v(n - 1), w(n - 1);
	rep(i, n - 1) {
		cin >> u[i] >> v[i] >> w[i];
		u[i]--; v[i]--;
	}

	vector<vector<pair<int, int>>> g(n);
	rep(i, n - 1) {
		g[u[i]].push_back(make_pair(v[i], w[i]));
		g[v[i]].push_back(make_pair(u[i], w[i]));
	}

	dist[0] = 0;
	dfs(0, -1, g);

	rep(i, n) printf("%d\n", (dist[i] % 2) ? 1 : 0);

	return 0;
}


Measured memory_bytes: 10112
#include <stdio.h>

int main(void){
	int a,b,c,d,e,f;
	int total=0;
	scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);

	total+=a*1;
	total+=b*5;
	total+=c*10;
	total+=d*50;
	total+=e*100;
	total+=f*500;

	if(total>=1000) printf("1\n");
	else printf("0\n");
	return 0;
}

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

int main() {
  int h, a;
  cin >> h >> a;
  int count = 0;

  for (int i = 0; h > 0; i++) {

    h -= a;
    count++;
  }

  cout << count;
  return 0;
}


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


Measured memory_bytes: 128
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rf = lambda: map(float, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

a, b, c = rm()
print(min(b, c), max(0, b+c-a))











Measured memory_bytes: 26972
N, M = map(int, input().split())
a = [0] * M
b = [0] * M

for i in range(M):
    a[i], b[i] = map(int, input().split())

s = []
t = []

for i in range(M):
    if a[i] == 1:
        s.append(b[i])
    elif b[i] == N:
        t.append(a[i])

if len(set(s) & set(t)) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")


Measured memory_bytes: 28144
#include <bits/stdc++.h>
using namespace std;
int a[300000];
bool cmp(int a, int b) { return a > b; }
int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n, cmp);
    int x, y;
    for (int i = 1; i <= n + 1; i++) {
        if (a[i] < i) {
            x = y = i - 2;
            break;
        }
    }
    int d1 = a[x + 1] - y;
    int d2 = x + 1;
    while (a[d2] > y) d2++;
    d2 -= x + 1;
    bool f = 0;
    if (d1 % 2 == 0) f = 1;
    if (d2 % 2 == 0) f = 1;
    if (f)
        cout << "First";
    else
        cout << "Second";
    //cout << endl << x << ' ' << y;
    //cout << endl << d1 << ' ' << d2;
}

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

string LCS(string a, string b) {
    int n = a.length();
    int m = b.length();
    int dp[n + 1][m + 1];
    dp[0][0] = 0;
    int i, j;
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= m; j++) {
            if (i == 0 or j == 0) {
                dp[i][j] = 0;
            }
            else if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    int len = dp[n][m];
    string res = "";
    i--;
    j--;
    while (i > 0 and j > 0) {
        if (a[i - 1] == b[j - 1]) {
            res = a[i - 1] + res;
            i--;
            j--;
            len--;
        }
        else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        }
        else {
            j--;
        }
    }
    return res;
}

int main() {
  string a, b;
  cin >> a >> b;
  cout << LCS(a, b) << endl;
}


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

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

  std::vector<double> v(n);
  for (auto&& vi : v) std::cin >> vi;

  std::sort(v.begin(), v.end());

  double sum = v[0];
  for (int i = 1; i < n; ++i) sum = (sum + v[i]) / 2;

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

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <tuple>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(perm),end(perm)
#define showall(obj) for(auto x:obj)cout<<x<<' ';
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
typedef vector<int> vint;
typedef vector<ll> vll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
    int n; cin>>n;
    const double RATE = 380000.0;
    vector<string> u(n);
    vector<double> x(n);
    rep(i,n)cin>>x[i]>>u[i];
    double long ans = 0;
    rep(i,n){
        if(u[i] == "BTC")ans += x[i]*RATE;
        else ans += x[i];
    }
    cout<<fixed<<setprecision(10)<<ans<<endl; return 0;
}


Measured memory_bytes: 256
# include <bits/stdc++.h>
# define ll int64_t
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl

using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) (x*=i)%=mod;
    return x;
}

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

ll lcm(ll a,ll b)
{
   return a/gcd(a,b)*b;
}

//累乗だってさ
ll modpow(ll a,ll n,ll mod1) {
    ll res=1;
    while(n>0){
        if(n&1) res=res*a%mod1;
        a = a*a%mod1;
        n >>= 1;
    }
    return res;
}

ll combination(ll n,ll r){
    ll sum=1;
    rrep(i,min(r,n-r)) (sum*=(n-i+1))%=mod;
    return sum;
}

//逆元だってさ
ll modinv(ll a,ll mod1) {
    return modpow(a, mod1 - 2, mod1);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string n;
    cin>>n;
    rep(i,3){
        if(n[i]=='7'){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 3656
# Implementation by unihernandez22 || Idea by Vicfred
# https://atcoder.jp/contests/abc171/tasks/abc171_c
# math, greedy

n = int(input())

digits = []

while n > 0:
    n -= 1
    digits.append(chr(n%26+97))
    n //= 26

print(''.join(reversed(digits)))


Measured memory_bytes: 9140
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue> 
 
using namespace std;
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int H, N;

	cin >> H >> N;

	int sum = 0;

	for(int i = 0; i < N; i++) {
		int A;
		cin >> A;
		sum += A;
	}

	if(sum < H) {
		cout << "No" << endl;
	} else {
		cout << "Yes" << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
  int A, B;
  cin >> A >> B;
  rep(i,max(A,B))cout << min(A,B);
  cout << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A_list = [input() for i in range(N)]
B_list = [input() for i in range(M)]

all_segment = []
for width in range(N - M + 1):
    for height in range(N - M + 1):
        segment = [width_list[width: width + M] for width_list in A_list[height: height + M]]
        all_segment.append(segment)

if B_list in all_segment:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 4468
/**
 *   author: sahushivam
 *   created: 01 September 2019 (Sunday)  17:29:22
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,a,b) for(int i = a; i<b; i++)
#define MOD 1000000009
#define INF 1e18
#define F first
#define S second
#define PB push_back
#define MP make_pair

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    string s,s1;
    int c;
    cin>>s>>s1;
    for(int i=0;i<3;i++)
    {
      if(s[i]==s1[i])
        c++;
    }
    cout<<c;

return 0;
}

Measured memory_bytes: 256
from collections import Counter

n = int(input())
D = list(map(int,input().split()))
MOD = 998244353

ctr = Counter(D)

if D[0]!=0:
    print(0)
    exit()
if ctr[0] != 1:
    print(0)
    exit() 

ans = 1
for i in range(len(ctr)-1):
    ans *= pow(ctr[i], ctr[i+1], MOD)
    ans %= MOD
print(ans)

Measured memory_bytes: 62644
import math
import queue

mod = 1e9+7

def swap(a,b):
    return (b,a)

def gcd(a,b):
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def divisors(a):
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def main():
    n = int(input())
    ans = n*(n+1)//2-n
    print(int(ans))
    return

if __name__ == '__main__':
    main()

Measured memory_bytes: 4080
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n=nxtl(),s=nxtl();
    for(ll b=2;b<=sqrt(n);b++)
    {
        ll sum=0;
        ll temp=n;
        while(temp!=0)
        {
            sum+=temp%b;
            temp/=b;
        }
        if(sum==s)
        {
            cout<<b<<endl;
            return 0;
        }
    }
    ll test=1e18;
    for(ll f=1;f<=sqrt(n-s);f++)
    {
        if((n-s)%f==0)
        {
            ll sum=0;
            ll temp=n;
            ll b=(n-s)/f;
            b++;
            while(temp!=0)
            {
                sum+=temp%b;
                temp/=b;
            }
            if(sum==s)
            {
                if(b<test)
                    test=b;
            }
            if(f>0)
            {
                ll sum=0;
                ll temp=n;
                ll b=f;
                b++;
                while(temp!=0)
                {
                    sum+=temp%b;
                    temp/=b;
                }
                if(sum==s)
                {
                    if(b<test)
                        test=b;
                }
            }
        }
    }

    if(n==s&&test>n+1)
        test=n+1;


    if(test==1e18)
        cout<<"-1\n";
    else
        cout<<test<<endl;
    

    
    return 0;   
}


 
 


Measured memory_bytes: 256
#include <bits/stdc++.h>
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

std::string max(std::string s, std::string t) {
	if(s.size() > t.size()) return s;
	if(t.size() > s.size()) return t;
	if(s.size() == t.size()) {
		for(int i = 0; i < s.size(); i++) {
			if(s[i] > t[i]) return s;
			else if(t[i] > s[i]) return t;
		}
	}
	return s;
}

int main() {
	int n, m; scanf("%d%d", &n, &m);
	std::vector<int> cost = {-1, 2, 5, 5, 4, 5, 6, 3, 7, 6};
	std::vector<int> a(m);
	for(int i = 0; i < m; i++) scanf("%d", &a[i]);
	
	std::vector<std::string> dp(n + 1, "0"); dp[0] = "";
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(dp[i] == "0" or i + cost[a[j]] > n) continue;
			dp[i + cost[a[j]]] = max(dp[i + cost[a[j]]], dp[i] + std::string(1, (char)(a[j] + '0')));
		}
	}
	printf("%s\n", dp[n].c_str());
	return 0;
}


Measured memory_bytes: 32896
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<map>
using namespace std;
#define inf 1000000009
#define int long long
typedef pair<int, int> P;
struct edge { int to, cost; };
int color[114514];
vector<int>G[114514];
int n, m;

bool dfs(int v, int c) {
	color[v] = c;
	for (int i = 0; i < G[v].size(); i++) {
		if (color[G[v][i]] == c)return false;
		if (color[G[v][i]] == 0 && !dfs(G[v][i], -c))return false;
	}
	return true;
}
signed main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		G[a - 1].push_back( b - 1);
		G[b - 1].push_back(a - 1);
	}
	
	if (dfs(0, 1)) {
		int b = 0, w = 0;
		for (int i = 0; i < n; i++) {
			if (color[i] == 1)b++;
			else w++;
		}
		cout << b*w-m << endl;
	}
	else cout << n*(n - 1) / 2 - m << endl;
}

Measured memory_bytes: 7808
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for(int i = 0;i < (n);++i)
#define REPLL(i, n) for(ll i = 0;i < (n);++i)

#define endl "\n"
#define pb push_back
#define MOD 1000000007LL
#define PI 3.1415926

typedef long long ll;

template <typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template <typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template <typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
template <typename T> inline T POW(T a,T b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}

int n, m;
bool graph[8][8];
int dfs(int pos, bool visit[8]){
	bool allvisit = 1;
	REP(i, n){
		if(!visit[i]) allvisit = 0;
	}
	if(allvisit) return 1;

	int res = 0;
	REP(i, n){
		if(!graph[pos][i]) continue;
		if(visit[i]) continue;

		visit[i] = 1;
		res += dfs(i, visit);
		visit[i] = 0;
	}

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

	cin >> n >> m;
	int a, b;
	REP(i, m){
		cin >> a >> b;
		graph[a-1][b-1] = graph[b-1][a-1] = 1;
	}

	bool visited[8];
	REP(i, n) visited[i] = 0;
	visited[0] = 1;

	cout << dfs(0, visited) << endl;

	return 0;
}

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

struct team
{
  int id;
  int ac;
  int penalty;
  vector<int> wa;
  team(int i, int P) : id(i), ac(0), penalty(0), wa(P, 0) {}

  bool operator<(const team& t) const
  {
    if (ac != t.ac) {
      return ac > t.ac;
    } else if (penalty != t.penalty) {
      return penalty < t.penalty;
    } else {
      return id < t.id;
    }
  }
};

int main()
{
  int T, P, R;
  while (cin >> T >> P >> R && T != 0) {
    vector<team> v;
    for (int i = 0; i < T; i++) {
      v.push_back(team(i+1, P));
    }
    for (int i = 0; i < R; i++) {
      int tid, pid, tm;
      string s;
      cin >> tid >> pid >> tm >> s;
      --tid;  --pid;
      team& t = v[tid];
      if (t.wa[pid] == -1) {
        continue;
      }
      if (s == "CORRECT") {
        ++t.ac;
        t.penalty += 1200*t.wa[pid] + tm;
      } else {
        ++t.wa[pid];
      }
    }
    sort(v.begin(), v.end());
    for (vector<team>::const_iterator it = v.begin(); it != v.end(); ++it) {
      cout << it->id << ' ' << it->ac << ' ' << it->penalty << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 936
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RNG(i,from,to) for(int i=(from); i<(int)(to); i++)
#define gcd(i,j) __gcd((i), (j))
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vecll;
template<typename S, typename T> string to_string(pair<S, T> p) { return "("+to_string(p.first)+","+to_string(p.second)+")"; }
template<typename T> string to_string(T p[2]) { return "["+to_string(p[0])+","+to_string(p[1])+"]"; }
template<typename T> void println(T e){ cout << to_string(e) << endl; }
template<typename T> void println(const vector<T>& v){ cout << "[";for(const auto& e : v){ cout << to_string(e) << ","; }cout << "]";cout << endl; }
template<typename T> void println(const vector<vector<T>>& vv){ for(const auto& v : vv){ println(v); } }
template<typename Iter> void println(Iter first, Iter last){ for(auto it=first; it != last; it++){ cout << *it << " "; }; cout << endl; }
template<typename T> T mod_pow(T x, T n, const T &p) { T ret = 1; while(n > 0) { if(n & 1) (ret *= x) %= p; (x *= x) %= p; n >>= 1; } return ret; }
template<typename T> T mod_inv(T x, const T &p) { return mod_pow(x, p-2, p); }
const ll DVSR = 1e9+7;


int main(int argc, char const *argv[])
{
  ll X,A,B;
  cin >> X >> A >> B;
  cout << (X-A)%B << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

bool prime(int n)
{
    if (n < 2) return false;

    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }

    return true;
}
int main()
{
    int q, l[100010], r[100010];

    cin >> q;
    for (int i = 0; i < q; i++) cin >> l[i] >> r[i];

    bool n[100010] = {};

    for (int i = 0; i < 100010; i++) n[i] = prime(i);

    int sum[100010] = {}, t = 0;
    for (int i = 0; i < 100010; i++) {
        if (n[i] and n[(i + 1) / 2]) t++;
        sum[i] = t;
    }

    for (int i = 0; i < q; i++) {
        cout << sum[r[i]] - sum[l[i] - 1] << endl;
    }

    return 0;
}


Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a;
    cin>>b;
    if(a==1&&b==2 || a==2&&b==1)
    {
        cout<<"3";
    }
    else if(a==2&&b==3 || a==3&&b==2)
    {
        cout<<"1";
    }
    else if(a==1&&b==3 || a==3&&b==1)
    {
        cout<<"2";
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main(void){
    using namespace std;
    int N;
    std::cin >> N;

    vector<int> L(N);
    for (int i = 0; i < N;i++)
        cin >> L[i];

    sort(L.begin(), L.end());

    int ret = 0;
    for (int i = 0; i < N;i++){
        for (int j = i + 1; j < N;j++){
            for (int k = j + 1; k < N;k++){
                if(L[k] < L[i] + L[j])
                    ret++;
                else
                    break;
            }
        }
    }

    std::cout << ret << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main (void) {
    string s;
    int ans = 0;

    cin >> s;

    if (s[0] == '1') ans++;
    if (s[1] == '1') ans++;
    if (s[2] == '1') ans++;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
//g++ -std=c++17 -Wshadow -Wall -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -g PROGRAM -o OUTPUT -DLOCAL -lasan -lubsan
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define alli(a, n, k) (a + k), (a + n + k)
#define FP(i, a, b, k) for (__typeof(a) i = a; i < b; i += k)
#define FS(i, a, b, k) for (__typeof(a) i = a; i > b; i -= k)
#define IT(it, a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define eps 1e-6
#define pi 3.141592653589793
using namespace std;
using namespace __gnu_pbds;

template <class T>
inline T gcd(T x, T y)
{
    if (!y)
        return x;
    return gcd(y, x % y);
}
typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef vector<pair<int, int>> VPII;
typedef vector<pair<int, PII>> VPPI;
const int MOD = 1e9 + 7;
const int INF = 1e9;


inline ll modulo(ll a, ll m)
{
    return (a % m + m) % m;
}

inline ll modInverse(ll a, ll m)
{
    assert(__gcd(a, m) == 1);
    ll m0 = m;
    ll y = 0, x = 1;

    if (m == 1)
        return 0;

    while (a > 1)
    {
        ll q = a / m;
        ll t = m;

        m = a % m, a = t;
        t = y;

        y = x - q * y;
        x = t;
    }

    if (x < 0)
        x += m0;

    return x;
}

inline ll modPow(ll x, ll y, ll m)
{ //x^y % m
    if (y == 0)
        return 1LL;
    else if (y == 1)
        return x;
    else
    {
        ll ans = modPow(x, y / 2, m) % m;
        if (y & 1)
        {
            return (((ans * ans) % m) * x) % m;
        }
        else
        {
            return (ans * ans) % m;
        }
    }
}

vector<string> split(char d,string s)
{
    stringstream ss(s);
    string t;
    vector<string> words;
    while(getline(ss,t,d))
    {
        words.pb(t);
    }

    return words;
}

int main(int argc, char *argv[])
{
#ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
#endif
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ll k;
    cin >> k;
    if(k%2==0)
        cout << -1,exit(0);

    string v = to_string(k);

    int rem = 0;
    ll pw = 1;
    for (int i = 0; i <= 1e7;++i)
    {
        rem = (rem%k + ((7 % k) * (pw % k))%k)%k;
        pw = ((pw % k) * (10)) % k;
        if(rem==0)
        {
            cout << i+1;
            exit(0);
        }
    }

    cout << -1;

#ifdef LOCAL
    auto end = chrono::high_resolution_clock::now();
    double time_taken =
        chrono::duration_cast<chrono::nanoseconds>(end - start).count();

    time_taken *= 1e-9;

    cerr << "\nTime taken by program is : " << fixed
         << time_taken << setprecision(9);
    cerr << " sec" << endl;
#endif
    return 0;
}


Measured memory_bytes: 3684
import java.util.Scanner;

public class Main {
	static final long MOD = 1000000007;
	static long modpow(long n, long y){
		if(y == 0){
			return 1;
		}else if(y == 1){
			return n % MOD;
		}else{
			if(y % 2 == 0){
				long r = modpow(n , y / 2);
				return (r * r) % MOD;
			}else{
				long r = modpow(n , y / 2);
				long r2 = (r * r) % MOD;
				return (r2 * n) % MOD;				
			}
		}
	}
	static long modinv(long n){
		return modpow(n , MOD - 2);
	}
	static long comb(int N , int R, long fact[]){
		long ret = fact[N];
		ret = (ret * modinv(fact[R])) % MOD;
		ret = (ret * modinv(fact[N - R])) % MOD;
		return ret;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		long fact[] = new long[2 * n];
		fact[0] = 1;
		fact[1] = 1;
		for(int i = 2 ; i < fact.length ; ++i){
			fact[i] = ((long)(i) * fact[i - 1]) % MOD;
		}
		if(k >= n){
			System.out.println(comb(2 * n - 1 , n, fact));
			return ;
		}
		long S = 1;
		for(int i = 1 ; i <= k ; ++i){
			long x = comb(n, i, fact);
			long y = comb(n - 1 , i, fact);
			S += (x * y) % MOD;
			S = S % MOD;
		}
		System.out.println(S);
		
	}
}


Measured memory_bytes: 26452
/*
  AUTHOR:SOURABH
  CREATED:12:10:19
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<ll , null_type, less< ll >, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long int
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define W while
#define fn(i,x) for(i=0;i<x;i++)
#define fs(i,s,x) for(i=s;i<x;i++)
#define fr(i,x) for(i=x;i>=0;i--)
#define fit(it,s) for(it=s.begin();it!=s.end();it++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define mod 1000000007
#define MAX 100005
#define M 32

using namespace std;
using namespace __gnu_pbds;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    ll a,b,d;
    cin>>a>>b;
    d=a-2*b;
    cout<<max(0LL,d);
    return 0;
}







Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	long long a[10000], n, x, y, z;
	x = 1000000;
	y = -1000000;
	z = 0;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
		if (a[i] < x){
			x = a[i];
		}
		if (a[i] > y){
			y = a[i];
		}
				z = z + a[i];

			}


		
	
	cout << x <<" "<< y <<" "<< z << endl;
	return 0;

}

Measured memory_bytes: 3168
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

signed main() {
	string s; cin >> s;
	int c[26] = {};
	rep(i, 0, s.size()) {
		c[s[i] - 'a']++;
	}
	rep(i, 0, 26) {
		if (c[i] % 2) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
import math as m

def prime(n):
    if n <= 1:
        return False
    for i in range(2,int(m.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def Goldbach(n):
  x = []
  c = 0
  for i in range(n+1):
    if prime(i):
      x.append(i)
  for j in x:
    for k in x:
      if j > k:
        pass
      elif j + k == n:
            c += 1
      else:
        pass
  print(c)

while 1:
  n = int(input())
  if n == 0:
    break
  Goldbach(n)


Measured memory_bytes: 5676
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,d;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	if((fabs(b-a)>d||fabs(c-b)>d)&&fabs(c-a)>d)
	{
	    printf("No");
    }
	else
	{
		printf("Yes");
	}
	return 0;
} 

Measured memory_bytes: 256
s = input()
#print(s[3:-2])
if(s[0] =="A"):
  if(s[2:-1].count("C") == 1):
    a = s.index("C")
    s = list(s)
    del s[0]
    del s[a-1]
    s = ''.join(s)
    if(s.islower()):
      print("AC")
    else:
      print("WA")
  else:
    print("WA")
else:
  print("WA")
#print(tmp)

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

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

int main() {
  int n, m, sum = 0; cin >> n >> m;

  vector<int> v(n);
  rep(i, n) {
    cin >> v[i];
    sum += v[i];
  }

  // sum / (4m) の切り上げ
  int ok = (sum + 4 * m - 1) / (4 * m);
  int count = 0;
  for (const int a : v) {
    if (a >= ok) ++count;
  }
  cout << (count >= m ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(100000)
n,k = map(int,input().split())
x = [[] for _ in range(n+1)]
for _ in range(n-1):
  a,b = map(int,input().split())
  x[a].append(b)
  x[b].append(a)
ans = k
def search(i):
  l = len(x[i])
  if l == 0:
    return
  global ans
  for j in range(l):
    ans = (ans*(k-2-j))%1000000007
  for child in x[i]:
    x[child].remove(i)
    search(child)
l1 = len(x[1])
for j in range(l1):
  ans = (ans*(k-1-j))%1000000007
for child1 in x[1]:
  x[child1].remove(1)
  search(child1)
print(ans)

Measured memory_bytes: 87348
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;

string s;

// [s, t)
bool is(string &st, llong s, llong t) {
    while (s < t) {
        t--;

        if (st[s] != st[t]) return false;

        s++;
    }

    return true;
}

int main() {
    cin >> s;

    llong n = s.size();

    if (is(s, 0, n) &&
        is(s, 0, (n - 1) / 2) &&
        is(s, (n + 3) / 2 - 1, n)) {

        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define ALL(x) x.begin(),x.end()
 
template <typename T>
void cetak(T t){cout << t << ')' << endl;}
template <typename T, typename... V>
void cetak(T t, V... v) {cout << t; if (sizeof...(v)) cout << ", "; cetak(v...);}
 
#define debug(x...) cout << '(' << #x << ") = ("; cetak(x) 
#define sz(x) (int)(x.size())
#define lt(x) (int)(x.length())


const int MOD = 1e9 + 7;

int add(int x, int y){
    int ret = x + y;
    if(ret >= MOD) ret -= MOD;
    return ret;
}
int sub(int x, int y){
    int ret = x - y;
    if(ret < 0) ret += MOD;
    return ret;
}
int mul(int x, int y){
    return (long long)x * y % MOD;
}


const int mx = 1e5 + 10;

void solve(){
    char a;
    cin >> a;
    a++;
    cout << a << endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}


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

using namespace std;

long long dp[305][32];
int n,c,len[8],seq[8];
int cnt = 0;
//int fuckywh[305];

int main()
{
	scanf("%d%d",&n,&c);
	for(int i = 1;i <= n; ++ i) scanf("%d",&len[i]);
	sort(len + 1,len + 1 + n);
	for(int i = 1;i < n; ++ i) seq[i] = i;
	long long as = 0;
	do
	{
		memset(dp,0,sizeof(dp));
		int all = (1 << n - 1) - 1;
		dp[min(len[n] * n,c * n)][0] = 1;
		for(int i = 0;i <= c * n; ++ i)
			for(int j = c * n;j >= i; -- j)
				for(int k = 0;k <= all; ++ k)
				{
					if(!dp[j][k]) continue;
					if(i % n && !(k & 1 << i % n - 1))
					{
						dp[min(c * n,max(j,i + len[seq[i % n]] * n))][k | 1 << i % n - 1] += dp[j][k];
					}
				}
		as += dp[c * n][all];
		cnt ++;
	}while(next_permutation(seq + 1,seq + n));
	printf("%.11Lf\n",(long double)as * 1.0 / cnt / pow(c,n - 1));
	return 0;
}

Measured memory_bytes: 384
import math
import sys
from collections import defaultdict

input = sys.stdin.readline
mod = 1000000007

n = int(input())

n2 = [1]
for _ in range(n):
    n2.append(n2[-1] * 2 % mod)

zero = 0
plus = defaultdict(int)
minus = defaultdict(int)

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue
    elif a == 0:
        plus[(1, 0)] += 1
    elif b == 0:
        minus[(1, 0)] += 1
    else:
        p = math.gcd(a, b)
        a //= p
        b //= p
        if a * b > 0:
            plus[(abs(a), abs(b))] += 1
        else:
            minus[(abs(b), abs(a))] += 1

n -= zero
ans = 1

for k, v in plus.items():
    if minus[k] > 0:
        ans *= (n2[v] + n2[minus[k]] - 1)
        ans %= mod
        n -= v + minus[k]

ans *= n2[n]
ans %= mod
ans += zero - 1
ans %= mod
print(ans)


Measured memory_bytes: 138180
#include<bits/stdc++.h>
using namespace std;
#define vb __int128
#define ll long long
#define ld long double
#define full(a) a.begin(),a.end()
#define stoink stack<ll>
#define vec vector <ll>
#define vg vector<vector<ll> >
#define vgw vector<vector<pair<ll,ll> >
#define pa pair<ll,ll>
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define pre 0.00000000000000000001
#define inf 1000000000000
#define mod 998244353
ll n;
vec arr;
ll dp[3001][3001][2];
ll func(ll l,ll r,bool turn) {
	if(l > r)
		return 0;
	if(dp[l][r][turn] != -1)
		return dp[l][r][turn];
	ll v1 = func(l + 1,r,!turn);
	ll v2 = func(l,r -1,!turn);
	if(turn) {
		dp[l][r][turn] = max(v1 + arr[l],v2 + arr[r]);
	}
	else
		dp[l][r][turn] = min(v1,v2);
	return dp[l][r][turn];
}	
int main()
{	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	arr.resize(n);
	ll i,j,k;
	for(i = 0 ; i <= n ; i++)
		for(j = 0 ; j <= n ; j++)
			for(k = 0; k < 2 ; k++)
				dp[i][j][k] = -1;
	for(i = 0 ; i < n ; i++)
		cin >> arr[i];
	ll x = func(0,n-1,true);
	ll y = func(0,n-1,false);
	cout << x - y;
	return 0;
}

Measured memory_bytes: 144584
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
int main()
{
    ll n, k;
    cin >> n >> k;
    vector<int> a(n);
    vector<set<int>> vs(2*1e5+10);
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        vs[a[i]].insert(i);
    }
    int pos = 0;
    int cnt = 1;
    vector<int> last(n+1, 0);
    while(true)
    {
        int num = a[pos];
        if(vs[num].size() != 1)
        {
            auto itr = vs[num].lower_bound(pos+1);
            if(itr == vs[num].end())
            {
                pos = *vs[num].begin();
                cnt++;
            }
            else pos = *itr;
        }
        else cnt++;
        pos++;
        last[cnt] = pos;
        if(pos == n) break;
    }
    vector<int> ans;
    pos = last[k%cnt];
    while(pos < n)
    {
        int num = a[pos];
        auto itr = vs[num].lower_bound(pos+1);
        if(itr == vs[num].end()) ans.push_back(num);
        else pos = *itr;
        pos++;
    }
    for(int a : ans) cout << a << " ";
    cout << endl;
}


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

using namespace std;

int main () {
    int n = 0;
    cin >> n;
    vector<int> w(n);
    int sum = 0;
    for (int i=0; i<n; i++) {
        cin >> w.at(i);
        sum += w.at(i);
    }
    int buf = 0;
    int ans = 10000000;
    for (int i=0; i<n; i++) {
        buf += w.at(i);
        int bufbuf = sum - buf;
        if (abs(bufbuf - buf) < ans) ans = abs(bufbuf - buf);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int a;
	while(scanf("%d",&a),a){
		int sum=0;
		for(int i=1;i*i<=a;i++){
			if(a%i==0)sum+=i+(a/i);
			if(i*i==a)sum-=i;
		}
		if(sum==a+a)printf("perfect number\n");
		else if(sum<a+a)printf("deficient number\n");
		else printf("abundant number\n");
	}
}

Measured memory_bytes: 0
#include <iostream>
//#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;

ll mod = 1000000007 ;
//long double pie = acos(-1) ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
void myrev(string &a){reverse(a.begin(),a.end()) ;}

int main(){
	ll n ; cin >> n ;
	string s,t ;
	cin >> s >> t ;
	myrev(s) ; myrev(t) ;
	vll dp(n) ;
	vll sum(26,0) ;
	dp.at(0) = 1 ;
	sum.at(t.at(0)-'a') = 1 ;
	for(int i=1;i<n;i++){
		dp.at(i) = sum.at(s.at(i)-'a') ;
		(sum.at(t.at(i)-'a')+=dp.at(i)) %= mod ;
	}
	cout << dp.at(n-1) << endl ;
}



Measured memory_bytes: 4028
package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := makeWordScanner()
	x := eGetInt(scanner)
	xd := x / 500
	xm := x % 500
	yd := xm / 5
	fmt.Println(1000*xd + yd*5)
}

////////////////////////////////////////////////////////////////////////////////
// ライブラリ
////////////////////////////////////////////////////////////////////////////////
const (
	TooLarge = math.MaxInt64
	TooSmall = math.MinInt64
)

func makeScanner(maxByte int) *bufio.Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]uint8, 0, 8192), maxByte)
	return scanner
}
func makeCharScanner() *bufio.Scanner {
	scanner := makeScanner(8192)
	scanner.Split(bufio.ScanRunes)
	return scanner
}
func makeWordScanner() *bufio.Scanner {
	scanner := makeScanner(8192)
	scanner.Split(bufio.ScanWords)
	return scanner
}
func eGetLine(r *bufio.Scanner) string {
	if r.Scan() {
		return r.Text()
	}
	err := r.Err()
	if err != nil {
		log.Fatal(err)
	}
	// EOF
	return ""
}
func eGetInt(r *bufio.Scanner) int {
	line := eGetLine(r)
	return eAtoi(line)
}
func eGetInt64(r *bufio.Scanner) int64 {
	line := eGetLine(r)
	return eAtoInt64(line)
}
func eGetFields(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Fields(line)
}
func eGetInts(r *bufio.Scanner) []int {
	fields := eGetFields(r)
	ints := make([]int, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoi(fields[i])
	}
	return ints
}
func eGetInt64s(r *bufio.Scanner) []int64 {
	fields := eGetFields(r)
	ints := make([]int64, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoInt64(fields[i])
	}
	return ints
}
func eGetChars(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Split(line, "")
}
func eAtoi(s string) int {
	n, err := strconv.Atoi(s)
	if err != nil {
		log.Fatal(err)
	}
	return n
}
func eAtoInt64(s string) int64 {
	n, err := strconv.ParseInt(s, 10, 64)
	if err != nil {
		log.Fatal(err)
	}
	return n
}
func pow(a, n int) int {
	if n == 0 {
		return 1
	}
	if n == 1 {
		return a
	}
	if n%2 == 1 {
		return pow((a*a), n/2) * a
	}
	return pow((a * a), n/2)
}
func powMod(a, n, mod int) int {
	if n == 0 {
		return 1 % mod
	}
	if n == 1 {
		return a % mod
	}
	if n%2 == 1 {
		return powMod((a*a)%mod, n/2, mod) * a % mod
	}
	return powMod((a*a)%mod, n/2, mod)
}

func factoricalMod(n, count, mod int) int {
	if count == 1 {
		return n % mod
	}
	return (n % mod) * (factoricalMod(n-1, count-1, mod)) % mod
}

func combinationMod(n, a, mod int) int {
	x := factoricalMod(n, a, mod)
	y := factoricalMod(a, a, mod)
	y = powMod(y, mod-2, mod)
	return ((x % mod) * (y % mod)) % mod
}
func countBitOfOn(i, numbits int) int {
	count := 0
	var bit uint64
	for bit = 0; bit < uint64(numbits); bit++ {
		t := 1 << bit
		if i&t > 0 {
			count++
		}
	}
	return count
}

type ints []int

func ToString(slice []int) string {
	format := fmt.Sprint(slice)
	return fmt.Sprint(format[1 : len(format)-1])
}


Measured memory_bytes: 640