akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define reg register
#define pr std::pair<int, int>
#define fi first
#define se second
#define FIN(s) freopen(s, "r", stdin)
#define FOUT(s) freopen(s, "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define lep(i, l, r) for (int i = l; i < r; ++i)
#define irep(i, r, l) for (int i = r; i >= l; --i)
#define ilep(i, r, l) for (int i = r; i > l; --i)
#define Rep(i, n) rep(i, 1, n)
#define Lep(i, n) lep(i, 1, n)
#define IRep(i, n) irep(i, n, 1)
#define ILep(i, n) ilep(i, n, 1)
typedef long long ll;
typedef long double ld;

namespace modular {
    const int MOD = 1000000007;
    inline int add(int x, int y) { return (x += y) >= MOD ? x -= MOD : x; }
    inline void inc(int &x, int y) { (x += y) >= MOD ? x -= MOD : 0; }
    inline int mul(int x, int y) { return 1LL * x * y % MOD; }
    inline int qpow(int x, int y) {
        int ans = 1;
        for (; y; y >>= 1, x = mul(x, x))
            if (y & 1) ans = mul(ans, x);
        return ans;
    }
};  // namespace modular

namespace Base {
    template <typename Tp>
    inline Tp input() {
        Tp x = 0, y = 1;
        char c = getchar();
        while ((c < '0' || '9' < c) && c != EOF) {
            if (c == '-') y = -1;
            c = getchar();
        }
        if (c == EOF) return 0;
        while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
        return x *= y;
    }
    template <typename Tp>
    inline void read(Tp &x) {
        x = input<Tp>();
    }
    template <typename Tp>
    inline void chmax(Tp &x, Tp y) {
        x < y ? x = y : 0;
    }
    template <typename Tp>
    inline void chmin(Tp &x, Tp y) {
        x > y ? x = y : 0;
    }
};  // namespace Base
using namespace Base;
/*----------------------------------------------------------------------------*/

int A, B, C, D, N;

void solve() {
    N = A + B;
    int l = 0, r = N + 1, mid, ans = N + 1;
    int k = (std::max(A, B) - 1) / (std::min(A, B) + 1) + 1;
    while (l <= r) {
        mid = l + r >> 1;
        int a = A - mid / (k + 1) * k - mid % (k + 1), b = B - mid / (k + 1);
        if (b <= 1LL * a * k)
            l = mid + 1;
        else
            ans = mid, r = mid - 1;
    }
    int a = A - ans / (k + 1) * k - ans % (k + 1), b = B - ans / (k + 1);
    r = ans + b - a * k + 1;
    // printf("%d %d\n", ans, r);
    rep(i, C, std::min(D, ans)) putchar(i % (k + 1) ? 'A' : 'B');
    rep(i, std::max(C, ans + 1), D) putchar((i - r) % (k + 1) ? 'B' : 'A');
    puts("");
}

int main() {
    int T = input<int>();
    while (T--) {
        read(A), read(B), read(C), read(D);
        solve();
    }
    return 0;
}


Measured memory_bytes: 384
import java.util.*;

class Main {
    final Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Main().run();
    }

    private void run() {
        int a = sc.nextInt();
        int b = sc.nextInt();

        int t = 1;
        int ans = 0;
        while (t < b) {
            ans++;
            t += a - 1;
        }
        System.out.println(ans);


    }
}



Measured memory_bytes: 21844
import java.util.Scanner;

public class Main {

    private static Scanner sc;

    public Main() {
    }

    public static void main(String[] args) {
        sc = new Scanner(System.in);
        new Main().solve();
    }

    private void solve() {
        String N = sc.next();
        boolean ans = false;
        if (N.charAt(0) == N.charAt(1) && N.charAt(1) == N.charAt(2)) {
            ans = true;
        }

        if (N.charAt(1) == N.charAt(2) && N.charAt(2) == N.charAt(3)) {
            ans = true;
        }

        if (ans) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define lowbit(x) ((x)&(-x))
#define inf 0x3f3f3f3f
#define endl "\n"
#define MP(x,y) (make_pair(x,y))
#define pll pair<int,int>
#define pi 3.1415926535
using namespace std;
ll n,k;
int main(){
    cin>>n>>k;
    ll ans = n%k;
    ans = min(ans,k-ans);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
from sys import stdin
input = stdin.readline

N = int(input())
S = input().rstrip()

ans = 0

R = 0
G = 0
B = 0

for i in range(N):
    if S[i] == "R":
        R += 1
    elif S[i] == "G":
        G += 1
    elif S[i] == "B":
        B += 1

ans += R * G * B

for i in range(N):
    for j in range(i + 1, N):
        k = 2 * j - i
        if k <= j or k >= N:
            continue
        if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            ans -= 1

print(ans)


Measured memory_bytes: 67984
#include <cstdio>
#include <iostream>

using namespace std;

const int max_n=36;

int n;
pair<char,int> P[max_n],P2[max_n],tmp;

void Bubble_sort()
{
    bool flag=true;
    for(int i=0;i<n-1 && flag;++i)
    {
        flag=false;
        for(int j=0;j<n-1-i;++j)
        {
            if(P[j].second>P[j+1].second)
            {
                tmp=P[j];
                P[j]=P[j+1];
                P[j+1]=tmp;
                flag=true;
            }
        }
    }
}

void Select_sort()
{
    for(int i=0;i<n-1;++i)
    {
        int min_j=i;
        for(int j=i+1;j<n;++j)
        {
            if(P2[j].second<P2[min_j].second)
            {
                min_j=j;
            }
        }
        if(min_j!=i)
        {
            tmp=P2[min_j];
            P2[min_j]=P2[i];
            P2[i]=tmp;
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        getchar();
        P[i].first=getchar();
        scanf("%d",&P[i].second);
        P2[i]=P[i];
    }

    Bubble_sort();

    for(int i=0;i<n-1;++i)
    {
        putchar(P[i].first);
        printf("%d ",P[i].second);
    }
    putchar(P[n-1].first);
    printf("%d\n",P[n-1].second);
    printf("Stable\n");



    Select_sort();

    for(int i=0;i<n-1;++i)
    {
        putchar(P2[i].first);
        printf("%d ",P2[i].second);
    }

    putchar(P2[n-1].first);
    printf("%d\n",P2[n-1].second);

    bool flag=true;
    for(int i=0;i<n;++i)
    {
        if(P[i].first!=P2[i].first)
        {
            flag=false;
            break;
        }
    }
    if(flag)
    {
        printf("Stable\n");
    }
    else
    {
        printf("Not stable\n");
    }

    return 0;
}



Measured memory_bytes: 3216
while True:
    m,f,r=map(int,input().split())
    if m==-1 and f==-1 and r==-1:
        break
    elif m==-1 or f==-1:
        print('F')
    elif m+f>=80:
        print('A')
    elif m+f>=65 and m+f<80:
        print('B')
    elif m+f>=50 and m+f<65:
        print('C')
    elif m+f>=30 and m+f<50 and r>=50:
        print('C')
    elif m+f>=30 and m+f<50 and r<50:
        print('D')
    elif m+f<30:
        print('F')


Measured memory_bytes: 5596
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
char c[N],s[N],t[N];
int n,k,Debug;
inline bool check(char *c,char *t){
	for(register int i=0;i<n;i++)
		if(c[i]>t[i]){
			if(Debug)	cout<<i<<' '<<c[i]<<' '<<t[i]<<endl;
			return false;
		}
		else	if(c[i]<t[i])	return true;
	return false;
}
inline bool run(){
	for(register int i=n-1;~i;i--)
		if(s[i]!=s[n-1])	return true;
	return false;
}
inline void com(char *c,char *t){
	if(check(c,t))	for(register int i=0;i<n;i++)	t[i]=c[i];
}
int main(){
	scanf("%d%d%s",&n,&k,s),k--;
	for(register int i=0;i<n;i++)	s[2*n-1-i]=s[i];
	while(k--&&run()){
		for(register int i=0;i<n;i++)	t[i]='z';
		for(register int i=0;i<=n;i++){
			for(register int j=i,k=n-1;j<i+n;j++)
				c[k--]=s[j];
			com(c,t);
		}
		reverse(t,t+n);
		for(register int i=0;i<n;i++)	s[2*n-1-i]=s[i]=t[i];
	}
	for(register int i=0;i<n;i++)	t[i]='z';
	for(register int i=0;i<=n;i++){
		for(register int j=i,k=0;j<i+n;j++) c[k++]=s[j];
		com(c,t);
	}
	cout<<t;
	return 0;
}


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

#define REP(i,n) for(ll i=0;i<(ll)n;i++)
#define dump(x)  cerr << "Line " << __LINE__ << ": " <<  #x << " = " << (x) << "\n";
#define spa << " " <<
#define fi first
#define se second
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()

using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;

template<typename T> using V = vector<T>;
template<typename T> using P = pair<T, T>;
template<typename T> vector<T> make_vec(size_t n, T a) { return vector<T>(n, a); }
template<typename... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec(ts...))>(n, make_vec(ts...)); }
template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){os << "(" << v.first << ", " << v.second << ")"; return os;}
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<vector<T>> &v){ for(auto &e : v){os << e << "\n";} return os;}
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;

template <class T> void UNIQUE(vector<T> &x) {sort(ALL(x));x.erase(unique(ALL(x)), x.end());}
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 (a>b) { a=b; return 1; } return 0; }
void fail() { cout << -1 << '\n'; exit(0); }
inline int popcount(const int x) { return __builtin_popcount(x); }
inline int popcount(const ll x) { return __builtin_popcountll(x); }
template<typename T> void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cerr<<v[i][0];for(ll j=1;j<w;j++)cerr spa v[i][j];cerr<<"\n";}};
template<typename T> void debug(vector<T>&v,ll n){if(n!=0)cerr<<v[0];
for(ll i=1;i<n;i++)cerr spa v[i];
cerr<<"\n";};

const ll INF = (1ll<<62);
// const ld EPS   = 1e-10;
// const ld PI    = acos(-1.0);
const ll mod = (int)1e9 + 7;
//const ll mod = 998244353;

int main(){

    ll N;
    cin >> N;
    ll res = 0;
    for(ll a=1;a<=N;a++){
        for(ll b=1;a*b<N;b++){
            res++;
        }
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 3688
from time import time
start_time = time()
D = int(input())
C = list(map(int,input().split()))
S = [list(map(int,input().split())) for i in range(D)]

INF = float('inf')
DF = 7000
last = [0] * 26
cur_ans = []
nexts = []
for i,s in enumerate(S):
    best_k = -1
    best_score = -INF
    scores = []
    for k,s in enumerate(s):
        score = s
        for j,c in enumerate(C):
            if j==k: continue
            score -= c * (i+1 - last[j])
        if score > best_score:
            best_score = score
            best_k = k
        scores.append((score,k))
    last[best_k] = i+1
    cur_ans.append(best_k + 1)
    for sc,k in scores:
        if k==best_k: continue
        if sc < best_score - DF: continue
        nexts.append((best_score-sc, i,k))
nexts.sort(key=lambda x:x[0])

def evaluate(ans):
    last = [0] * 26
    score = 0
    for i,(s,a) in enumerate(zip(S,ans)):
        score += s[a-1]
        last[a-1] = i+1
        for j,c in enumerate(C):
            score -= c * (i+1 - last[j])
    return score + 10**6

cur_score = evaluate(cur_ans)
selects = [-1] * D
for _,ni,nk in nexts:
    if selects[ni] >= 0: continue
    last = [0] * 26
    ans = []
    for i,s in enumerate(S):
        if selects[i] >= 0:
            last[selects[i]] = i+1
            ans.append(selects[i] + 1)
            continue
        if i==ni:
            last[nk] = i+1
            ans.append(nk + 1)
            continue
        best_k = -1
        best_score = -INF
        for k,s in enumerate(s):
            score = s
            for j,c in enumerate(C):
                if j==k: continue
                score -= c * (i+1 - last[j])
            if score > best_score:
                best_score = score
                best_k = k
        last[best_k] = i+1
        ans.append(best_k + 1)
    sc = evaluate(ans)
    if sc > cur_score:
        cur_score = sc
        cur_ans = ans
        selects[ni] = nk
    if time() - start_time > 1.9:
        break

print(*cur_ans, sep='\n')

Measured memory_bytes: 72264
#include <bits/stdc++.h>
using namespace std;
char s[3001],t[3001];
int f[3001][3001];
void fc(int x,int y)
{
	if(x==0||y==0)
	{
		return;
	}
	if(s[x-1]==t[y-1])
	{
		fc(x-1,y-1);
		printf("%c",s[x-1]);
	}
	else
	{
		if(f[x-1][y]>=f[x][y-1])
		{
			fc(x-1,y);
		}
		else if(f[x][y-1]>f[x-1][y])
		{
			fc(x,y-1);
		}
	}
}
int main()
{
	int i,j,n,m;
	scanf("%s\n%s",s,t);
	n=strlen(s);
	m=strlen(t);
	memset(f,0,sizeof(f));
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(s[i-1]==t[j-1])
			{
				f[i][j]=f[i-1][j-1]+1;
			}
			else
			{	
				f[i][j]=max(f[i-1][j],f[i][j-1]);
			}
		}
	}
	fc(n,m);
}

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

int main()
{
    ll n, k;
    cin >> n >> k;
    ll count = 0;
    vector<pair<int, int>> x(n);
    for (int i = 0; i < n; i++)
    {
        cin >> x.at(i).first >> x.at(i).second;
    }
    sort(x.begin(),x.end());
    for(int i=0;i<n;i++){
        count += x.at(i).second;
        if (k <= count)
        {
            cout << x.at(i).first << endl;
            break;
        }
    }
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int N = 300010;
const ll mod = 998244353;
ll factorial[N];

void init()
{
    factorial[0] = 1;
    for (int i = 1; i < N; i++)
    {
        factorial[i] = factorial[i - 1] * i % mod;
    }
}

ll powMod(ll n, ll m)
{
    ll ans = 1;
    while (m)
    {
        if (m & 1) ans = ans * n % mod;
        n = n * n % mod;
        m >>= 1;
    }
    return ans;
}

ll C(int n, int k)
{
    return factorial[n] * powMod(factorial[k], mod - 2) % mod *
           powMod(factorial[n - k], mod - 2) % mod;
}
int  main()
{
    ll n, a, b, k;
    cin >> n >> a >> b >> k;
    init();
    ll sum = 0;
    for(ll i = 0; i <= n; i++)
    {
        if(a * i <= k && (k - a * i) % b == 0)
        {
            ll tmp = (k - a * i) / b;
            if(tmp <= n)
            {
                sum += C(n, i) * C(n, tmp);
                if(sum > mod)
                    sum %= mod;
            }
        }
    }
    cout << sum << endl;
    return 0;
}

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


void solve() {
  int N;
  scanf("%d", &N);
  double arr[N];
  for (size_t i = 0; i < N; i++) {
    scanf("%lf", &arr[i]);
  }
  double sum=0;
  double AA = 1;
  for (size_t i = 0; i < N; i++) {
    AA = AA*arr[i];
  }
  for (size_t i = 0; i < N; i++) {
    sum += AA/arr[i];
  }
  printf("%lf", AA/sum);
}

int main() {
  solve();
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int m,n,d,re,s=0;
    cin>>m;
    if(m < 500)
    {
        d = m/5;
        cout<<d*5<<endl;
    }
    else
    {
        re = (m%500);
        d = re/5;
        s += d*5;
        m -= re;
        s += m*2;
        cout<<s<<endl;
    }


}


Measured memory_bytes: 256
import std.stdio;
import std.string;
import std.conv;

void main(){
    while(true){
	auto s = readln();
	if(stdin.eof()) break;
	auto s1 = split(chomp(s),',');
	real[] n;
	for(int i=0;i<12;i++) n ~= to!real(s1[i]);
	real r = n[10] / ( n[10] + n[11]);
	real len = 0;
	for(int i=0;i<10;i++) len += n[i];
	len *= r;
	int ans = 0;
	for(;ans<10;ans++){
	    len -= n[ans];
	    if(len <= 0) break;
	}
	writeln(ans+1);
    }
}

Measured memory_bytes: 2444
import Control.Applicative

myShow :: Int -> Int -> IO ()
myShow count5 count7 | count5 == 2 && count7 == 1 = putStrLn "YES"
                     | otherwise = putStrLn "NO"

main :: IO ()
main = do
    lst <- map read . words <$> getLine
    let count5 = foldr (\x y -> if x == 5 then y+1 else y) 0 lst
        count7 = foldr (\x y -> if x == 7 then y+1 else y) 0 lst
    myShow count5 count7


Measured memory_bytes: 508
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;
// ceil() 切り上げ, floor() 切り捨て
// next_permutation(all(x))

int		main(void)
{
	int N;
	cin >> N;
	string ans = "Yes";
	int T = 0, X = 0, Y = 0;
	for (int i = 0; i < N; i++)
	{
		int t, x, y;
		cin >> t >> x >> y;
		if (t%2 != (x+y)%2)
			ans = "No";
		if (t-T < abs(X-x)+abs(Y-y))
			ans = "No";
		T = t;
		X = x;
		Y = y;
	}
	cout << ans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define mt make_tuple
typedef long long int ll;

using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;

typedef long long int ll;

ll n, m;
ll a[114514], b[114514];
ll in[114514], out[114514];

vvi outlist(114514);

int main(void){
	cin >> n >> m;
	for(int i=0;i<n-1+m;i++){
		cin >> a[i] >> b[i];
		in[b[i]]++;
		out[a[i]]++;
		outlist[a[i]].pb(b[i]);
	}
	int root = -1;
	int ans[n+1];
	for(int i=1;i<=n;i++){
		if (in[i]==0) {
			root = i;
			ans[i] = 0;
			break;
		}
	}
	vi v = {root};
	while(1){
		/*cerr << "[";
		for(int i : v){
			cerr << i << " ";
		}cerr << "]" << endl;
		cerr << "in[]:";
		for(int i=1;i<=n;i++) cerr << in[i] << " "; cerr << endl;
		*/
		if (v.empty()) break;

		vi v2;
		for(int i : v){
			for(int j : outlist[i]){
				in[j]--;
				if (in[j]==0){
					v2.pb(j);
					ans[j] = i;
				}
			}
		}
		v = v2;
	}

	for(int i=1;i<=n;i++) cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 10112
/* https://codeforces.com/contest/1360/problem/H */
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using vs = vector<string>;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vpi = vector<pair<int, int>>;
using vpl = vector<pair<ll, ll>>;
using ld = double;

#define f first
#define s second 
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define pb push_back
#define	lb lower_bound
#define	ub upper_bound
#define	sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define ins insert

const int MAX = INT_MAX;
const ll MOD = 1e9+7;

ll fun(ll b, ll e) {
	ll res = 1;
	for (int i = 0;i < e;++i) {
		res = res * b % MOD;
	}

	return res;
}

int main() {
	int n;
	cin>>n;
	ll ans = 0;
	ans = fun(10, n) - fun(9, n) - fun(9, n) + fun(8, n);
	ans %= MOD;
	ans = (ans+MOD)%MOD;
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 3588
// ABC 152-E
// 2020.1.19 bal4u

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef long long ll;

#define gc() getchar_unlocked()

int in() {
	int n = 0; int c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

#define SIZE  1000005
int power[SIZE];

int ptbl[] = {
		 3,   5,   7,  11,  13,  17,  19,  23,  29,
   31,  37,  41,  43,  47,  53,  59,  61,  67,  71,
   73,  79,  83,  89,  97, 101, 103, 107, 109, 113,
  127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
  179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
  233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
  283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
  353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
  419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
  467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
  547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
  607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
  661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
  739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
  811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
  877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
  947, 953, 967, 971, 977, 983, 991, 997, 0 };

void prime_factor(int n) {
	int i, d, t;
	int *pp;

	if ((n & 1) == 0) {
		t = 0;
		do n >>= 1, t++;
		while ((n & 1) == 0);
		if (power[2] < t) power[2] = t;
	}
	for (pp = ptbl; n > 1 && *pp > 0; pp++) {
		if (n % *pp) continue;
		d = *pp, t = 0;
		do n /= d, t++;
		while (n % d == 0);
		if (power[d] < t) power[d] = t;
	}
	if (n > 1) {
		int b = (int)sqrt(n);
		for (i = 1009; n > 1; i += 2) {
			if (i > b) {
				if (power[n] == 0) power[n] = 1;
				break;
			}
			if (n % i == 0) {
				t = 0;
				do n /= i, t++;
				while (n % i == 0);
				if (power[n] < t) power[n] = t;
			}
		}
	}
}

#define MOD 1000000007
int A[10005]; int N;

int pow_mod(int x, int p)
{
	int r = 1;
	while (p) {
		if (p & 1) r = (ll)r * x % MOD;
		x = (ll)x * x % MOD;
		p >>= 1;
	}
	return r;
}

int extended_gcd(int a, int b, int *x, int *y) {
	int d;

	if (b == 0) { *x = 1; *y = 0; return a; }
	d = extended_gcd(b, a % b, y, x);
	*y -= a / b * (*x);
	return d;
}

int inverse(int a) {
    int x, y;
    extended_gcd(a, MOD, &x, &y);
    return x;
}

int main()
{
	int i;
	int P, ans;
	
	N = in();
	for (i = 0; i < N; ++i) {
		A[i] = in();
		prime_factor(A[i]);
	}
	P = 1;
	for (i = 2; i <= 1000000; i++) if (power[i]) {
		P = (ll)P * pow_mod(i, power[i]) % MOD;
	}
	ans = 0;
	for (i = 0; i < N; ++i) {
		ans = (ans + (ll)P * inverse(A[i]) % MOD) % MOD;
	}
	if (ans < 0) ans += MOD;
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 2816
#include <stdio.h>

int main(void) {
	int i,j,n,d[16][16],s;
	while(scanf("%d",&n) , n != 0){
		for(i = 1;i <= n;i++){
			for(j = 1;j <= n;j++){
				scanf("%d",&d[i][j]);
			}
		}
		for(i = 1;i <= n;i++){
			s = 0;
			for(j = 1;j <= n;j++){
				s+=d[i][j];
			}
			d[i][n+1] = s;
		}
		for(j = 1;j <= n;j++){
			s = 0;
			for(i = 1;i <= n;i++){
				s+=d[i][j];
			}
			d[n+1][j] = s;
		}
		s = 0;
		for(i = 1;i <= n;i++){
			s+=d[n+1][i];
		}
		d[n+1][n+1] = s;
		for(i = 1;i <= n+1;i++){
			for(j = 1;j <= n+1;j++){
				printf("%5d",d[i][j]);
			}
			printf("\n");
		}
	}
	return 0;
}

Measured memory_bytes: 616
// util
let scanInts () = stdin.ReadLine().Split() |> Array.map int
let scanIntsML n = [ for i in 1..n -> scanInts () ]
let frceil a b = a/b + (if a % b = 0 then 0 else 1)
let rec powerset = function
  | [] -> [[]]
  | x::xs -> let ps = powerset xs in ps @ List.map (List.append [x]) ps

// main
let [|D;G|] = scanInts ()

let alltup = // (point, num, bonus) ボーナス抜きのコスパで並べる
  scanIntsML D
  |> List.mapi (fun i a -> ((i+1)*100, a.[0], a.[1])) 
  |> List.rev // 

// 完全回答組が与えられたとき 中途を（必要があれば）一つ選んで総回数を返す
let trySelect ctups =
  let cnt = List.sumBy (fun (_,n,_) -> n) ctups
  let scr = List.sumBy (fun (p,n,b) -> b+p*n) ctups
  match G - scr with
    | tgt when tgt <= 0 -> Some(cnt)
    | tgt ->
        alltup // 候補は完全組でなく, 単独で目標を達成しうるものの 先頭
        |> List.filter (fun t -> not (List.contains t ctups))
        |> List.filter (fun (p,n,_) -> tgt <= p*(n-1))
        |> List.map (fun (p,n,_) -> cnt + (frceil tgt p))
        |> List.tryHead // コスパソート済みなので先頭でよい

alltup
|> powerset
|> List.choose trySelect
|> List.min
|> printfn "%d"

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

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin >> A.at(i);
  }
  int min_cost=1000000000;
  for(int i=-100;i<101;i++){
    int cost=0;
    for(int j=0;j<N;j++){
      cost+=(i-A.at(j))*(i-A.at(j));
    }
    min_cost=min(min_cost,cost);
  }
  cout << min_cost << endl;
}

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

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

template <typename T> void dprint(T begin, T end) {
    for (auto i = begin; i != end; i++) {
        cerr << (*i) << " ";
    }
    cerr << "\n";
}
const int MAXN = 220000;

int a[MAXN];
int was[MAXN];
vector<int> st;
vector<int> vv;
int n;
int go[MAXN];
vector<int> gg[MAXN];
vector<int> eds[MAXN];
int p[MAXN];

void run(int v) {
    was[v] = 1;
    st.push_back(v);
    int u = go[v];
    if (was[u]) {
        for (int i = 0; i < st.size(); ++i)
            if (st[i] == u) {
                for (int j = i; j < st.size(); ++j)
                    vv.push_back(st[j]);
                break;
            }
        return;
    }
    else {
        run(u);
    }
}

int dfs1(int v) {
    vector<int> vv;
    for (int u: eds[v]) {
        vv.push_back(dfs1(u));
    }
    sort(vv.begin(), vv.end());
    vv.resize(unique(vv.begin(), vv.end()) - vv.begin());
    a[v] = vv.size();
    for (int i = 0; i < vv.size(); ++i)
        if (vv[i] != i) {
            a[v] = i;
            break;
        }
    return a[v];
}

int get(int v) {
    vector<int> vv;
    for (int u: eds[v]) {
        vv.push_back(a[u]);
    }
    sort(vv.begin(), vv.end());
    vv.resize(unique(vv.begin(), vv.end()) - vv.begin());
    for (int i = 0; i < vv.size(); ++i)
        if (vv[i] != i) {
            return i;
        }
    return vv.size();
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", p + i), --p[i];
        eds[p[i]].push_back(i);
        go[i] = p[i];
    }
    run(0);
    memset(was, 0, sizeof(was));
    for (int i: vv)
        was[i] = 1;
    for (int i = 0; i < vv.size(); ++i) {
        int x = vv[i];
        for (int j: eds[x]) {
            if (!was[j])
                gg[i].push_back(dfs1(j));
        }
        sort(gg[i].begin(), gg[i].end());
        gg[i].resize(unique(gg[i].begin(), gg[i].end()) - gg[i].begin());
    }
    int k = gg[1].size();
    for (int i = 0; i < gg[1].size(); ++i)
        if (gg[1][i] != i) {
            k = i;
            break;
        }
    a[vv[1]] = k;
    for (int i = 2; i < vv.size(); ++i)
        a[vv[i]] = get(vv[i]);
    a[vv[0]] = get(vv[0]);
    if (get(vv[1]) == k) {
        cout << "POSSIBLE\n";
        return 0;
    }
    a[vv[0]] = k;
    for (int i = 1; i < vv.size(); ++i)
        a[vv[i]] = get(vv[i]);
    if (get(vv[0]) == k) {
        cout << "POSSIBLE\n";
        return 0;
    }
    cout << "IMPOSSIBLE\n";
    return 0;
}




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

int main(void){
    long int N,stock=0,cash=1000;
    cin>>N;
    long int A[N];
    for(int i=0;i<N;i++) cin>>A[i];
    for(int i=0;i<N-1;i++){
        if(A[i]<A[i+1]){
            stock+=cash/A[i];
            cash=cash%A[i];
        }
        if(A[i]>A[i+1]){
            cash+=A[i]*stock;
            stock=0;
        }
    }
    cout<<cash+A[N-1]*stock<<endl;
    return 0;
}

Measured memory_bytes: 3644
#include <stdio.h>
int main(){
	int i,j,A[101][101],n,a,b,c;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			A[i][j]=0;
		}
	}
	for(i=0;i<n;i++){
		scanf("%d%d",&a,&b);
		for(j=0;j<b;j++){
			scanf("%d",&c);
			A[a][c]=1;
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			printf("%d",A[i][j]);
			if(j<n)
			printf(" ");
		}
		printf("\n");
	}
	return 0;
}


Measured memory_bytes: 2112
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

cards = []
for _ in range(M):
  b,c = map(int,input().split())
  cards.append([c,b])
cards.sort(key=lambda x: -x[0])

res = 0
idx = 0
left = cards[idx][1]
for i,a in enumerate(A):
  if a > cards[idx][0]:
    res += sum(A[i:])
    break
  else:
    res += cards[idx][0]

    left -= 1
    if left <= 0:
      idx += 1
      if idx >= M:
        if i+1 < N:
          res += sum(A[i+1:])
        break
      else:
        left = cards[idx][1]

print(res)

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

int main()
{
    int n,a;
    scanf("%d %d",&n,&a);
    if(a >= n)
    {
        puts("Yes");
        return 0;
    }
    for(int i = 0; i <= a; ++i)
    {
        if((n-i)%500 == 0)
        {
            puts("Yes");
            return 0;
        }
    }
    puts("No");
    return 0;
}


Measured memory_bytes: 256
A,B,K = map(int,input().split())
list_A = list(range(A,min(B,A+K)))
list_B = list(range(max(A,B-K+1),B+1))
list_C = list_A + list_B
set_C = set(list_C)
list_D = sorted(list(set_C))
for i in list_D:
	print(i)

Measured memory_bytes: 3064
n = int(input())
s = int(input())
x = int(n**0.5)+1
def dsum(x,t):
  ret = 0
  while x>0:
    ret += x%t
    x //= t
  return ret
for i in range(2,x+1):
  if dsum(n,i) == s:
    print(i)
    exit()
for i in range(x,0,-1):
  if (n-(s-i))%i == 0:
    digit = (n-(s-i))//i
    if 0 < i < digit and 0 <= s-i < digit:
      print((n-(s-i))//i)
      exit()
if n == s:
  print(n+1)
  exit()
print(-1)

Measured memory_bytes: 40812
import unittest


class TestC(unittest.TestCase):
    def test_1(self):
        self.assertEqual(
            think([[10, 40, 70], [20, 50, 80], [30, 60, 90]]),
            210
        )

    def test_2(self):
        self.assertEqual(
            think([[100, 10, 1]]),
            100
        )

    def test_3(self):
        self.assertEqual(
            think([
                [6, 7, 8], [8, 8, 3], [2, 5, 2], [7, 8, 6],
                [4, 6, 8], [2, 3, 4], [7, 5, 1]
            ]),
            46
        )


def solve():
    list_of_abc = read()
    result = think(list_of_abc)
    write(result)


def read():
    n = read_int(1)[0]
    list_of_abc = []
    for _ in range(n):
        list_of_abc.append(read_int(3))
    return list_of_abc


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(list_of_abc):
    n = len(list_of_abc)
    elems = len(list_of_abc[0])

    # dp[0 to n - 1][0 to 2]
    dp = [[0 for _ in range(elems)] for _ in range(n)]

    for i, e in enumerate(list_of_abc[0]):
        dp[0][i] = e

    for i in range(1, n):
        for todays_act in range(elems):
            for yesterdays_act in range(elems):
                if todays_act == yesterdays_act:
                    continue
                dp[i][todays_act] = max(
                        dp[i][todays_act],
                        dp[i - 1][yesterdays_act] + list_of_abc[i][todays_act]
                )

    return max(dp[n - 1])


def write(result):
    print(result)


if __name__ == '__main__':
    # unittest.main()
    solve()

Measured memory_bytes: 89300
a,b,c,k = map(int, input().split())
goukei = 0
if k>=a:
  k -= a
  goukei += a
else:
  goukei += k
  k = 0
if k>=b:
  k -= b
else:
  k = 0
if k>0:
  goukei -= k
  
print(goukei)

Measured memory_bytes: 9192
# include <iostream>
# include <cmath>
# include <algorithm>
# include <stdio.h>
# include <cstdint>
# include <cstring>
# include <string>
# include <cstdlib>
# include <vector>
# include <bitset>
# include <map>
# include <queue>
# include <ctime>
# include <stack>
# include <set>
# include <list>
# include <random>
# include <deque>
# include <functional>
# include <iomanip>
# include <sstream>
# include <fstream>
# include <complex>
# include <numeric>
# include <immintrin.h>
# include <cassert>
# include <array>
# include <tuple>
# include <unordered_set>
# include <unordered_map>
using namespace std;


int h, w, n;
map<pair<int, int>, bool> used, used2;
vector<pair<int, int> > v;
long long ans[100];

void solve(int x, int y) {
    if (x < 3 || y < 3 || x > h || y > w) return;
    if (used2.count({x, y})) return;
    used2[{x, y}] = true;
    int c = 0;
    for (int i = -2; i <= 0; ++i)
        for (int j = -2; j <= 0; ++j)
            if (used.count({x + i, y + j})) ++c;
    ++ans[c];
    return;
}

int main(int argc, const char * argv[]) {
#ifdef __APPLE__
    freopen("/Users/danya.smelskiy/Documents/Danya/Resources/input.txt","r",stdin);
#endif
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> h >> w >> n;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        used[{x, y}] = true;
        v.push_back({x, y});
    }
    if (h < 3 || w < 3) {
        for (int i = 0; i <= 9; ++i)
            cout << 0 << '\n';
        return 0;
    }
    for (int i = 0; i < (int)v.size(); ++i) {
        int x = v[i].first;
        int y = v[i].second;
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k)
                solve(x + j, y + k);
        }
    }
    ans[0] = (h - 2ll) * (w - 2ll);
    for (int i = 1; i <= 9; ++i) {
        ans[0] -= ans[i];
    }
    for (int i = 0; i <= 9; ++i)
        cout << ans[i] << '\n';
    return 0;
}



Measured memory_bytes: 63604
while True:
    m,f,r=map(int,input().split())
    if (m,f,r)==(-1,-1,-1):
        break
    if m==-1 or f==-1:
        print("F")
    elif m+f>=80:
        print("A")
    elif 80>m+f>=65:
        print("B")
    elif 65>m+f>=50:
        print("C")
    elif m+f<30:
        print("F")
    elif 50>m+f>=30:
        if r>=50:
            print("C")
        else:
            print("D")


Measured memory_bytes: 5600
while 1:
    s=raw_input()
    if(s=='.'):
        break
    stack=[]
    ok=True
    for c in s:
        if(c=='(' or c=='['):
            stack.append(c)
        elif(c==')' or c==']'):
            if(not stack):
                ok=False
                break
            top=stack.pop()
            cor={')':'(', ']':'['}
            if(top!=cor[c]):
                ok=False
                break
    if(stack):
       ok=False 
    if(ok):
        print 'yes'
    else:
        print 'no'

Measured memory_bytes: 4256
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007; // 998244353
using ll = long long;
using namespace std;

int main(){
	int n, m; cin >> n >> m;
	vector<int> a(n);
	for( auto &k : a ) cin >> k;
	int sum = accumulate( a.begin(), a.end(), 0 );
	int cnt = 0;
	for( auto k : a ){
		if( 4*m*k >= sum ) ++cnt;
	}
	if( cnt >= m ){
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int h, w;
	char a[100][101];

	scanf("%d %d", &h, &w);
	for (int i = 0; i < h; ++i) {
		scanf("%s", a[i]);
	}

	//check low
	int check = 1;
	for (int i = 0; i < h; ++i) {
		check = 1;

		for (int j = 0; j < w; ++j) {
			if (a[i][j] == '#') {
				check = 0;
			}
		}
		if (check) {
			for (int j = 0; j < w; ++j) {
				a[i][j] = '\0';
			}
		}
	}

	//check line

	for (int i = 0; i < w; ++i) {
		check = 1;

		for (int j = 0; j < h; ++j) {
			if (a[j][i] == '#') {
				check = 0;
			}
		}
		if (check) {
			for (int j = 0; j < h; ++j) {
				a[j][i] = '\0';
			}
		}
	}

	int enter = 0;
	for (int i = 0; i < h; ++i) {
		enter = 0;
		for (int j = 0; j < w; ++j) {
			if (a[i][j] != '\0') {
				printf("%c", a[i][j]);
				enter = 1;
			}
		}
		if (enter) {
			printf("\n");
		}
	}

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ash ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll;


int main()
{
    ash;
    ll n,x;
    cin>>n>>x;
    string s;
    cin>>s;
    s[x-1]+=32;

    cout<<s<<"\n";


    return 0;
}


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

typedef pair<int, int> P;

int a[100000];
P card[100000];

int max(int a,int b){return a > b ? a : b;}

int main() {
  ios_base::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;

    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) {
        int c, b;
        cin >> c >> b;
        card[i] = P(b, c);
    }

    sort(a, a + n);
    sort(card, card + m);
    reverse(card, card + m);

    int t = 0;
    for(int i = 0; i < m; i++) {
        P p = card[i];
        int b = p.first;
        int c = p.second;
        for(int j = 0; j < c; j++) {
            a[t] = max(a[t], b);
            t++;

            if(t == n) break;
        }

        if (t == n) break;
    }

    long long s = 0;
    for(int i = 0; i < n; i++) s += a[i];
    cout << s;
    return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std ;
using namespace __gnu_pbds;

template <typename T> // *s.find_by_order(0), s.order_of_key(2) ;
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define reMin(a, b) a = min(a, b)
#define reMax(a, b) a = max(a, b)

#define lint long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define SET(x, val) memset(x, val, sizeof(x))
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

typedef vector < int > vi ;
typedef pair < int, int > pii ;

// template <typename T>
int modpow(int base, int exp, int modulo) {
  base %= modulo;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulo;
    base = (base * base) % modulo;
    exp >>= 1;
  }
  return result;
}

const int N = 1e6 + 2 ;
const int MOD = 1e9 + 7 ;
const lint INF = 1e18 ;

const int K = 1e5 ;
lint dp1[K], dp2[K] ;
int prods[K] ;

int n, k ;

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

    int cur ; vi divisors ; int j = 1 ;
    for(int i = 1; i <= n; )
    {
        cur = i ; divisors.pb(cur);
        prods[j++] = cur ;
        int low = cur + 1, high = n+2 ;
        while((high - low) > 1)
        {
            int mid = low + high >> 1 ;
            if((n/mid) < (n/cur)) high = mid ;
            else low = mid + 1 ;
        }
        if((n/low) < (n/cur)) i = low ;
        else i = high ;
    }
    divisors.pb(n+1);
    prods[j++] = n+1 ;
    j-- ;

    for(int i = 0; i < K; i++) dp2[i] = 1 ;
    dp2[0] = 0 ;

    for(int i = 0; i < k; i++)
    {
        for(int p = 1; p < j; p++)
        {
            lint cnt = prods[p + 1] - prods[p] ;
            int index = upper_bound(all(divisors), n/prods[p]) - divisors.begin() ;
            dp1[p] = (cnt * dp2[index]) % MOD ;
            // cout << cnt << " : " << prods[index] << " " << index << endl ;
        }
        for(int p = 1; p < j; p++) dp2[p] = (dp2[p-1] + dp1[p]) % MOD ;
        // for(int p = 1; p < j; p++) cout << dp1[p] << " " ;
        // cout << endl ;
    }
    cout << dp2[j-1] ;
}



Measured memory_bytes: 2172
#include "bits/stdc++.h"
using namespace std;
const int N = 13;
using ll = long long int;

int cost[N];
vector<int> v[N];

int main(){
    int n, m, x;
    cin >> n >>  m >>  x;
    for(int i = 0; i < n; ++i){
        cin >> cost[i];
        for(int j = 0; j < m; j++){
            int xx;
            cin >> xx;
            v[i].push_back(xx);
        }
    }
    int res = INT_MAX;
    for(int i = 0; i < (1 << n); i++){
        int valid = 1;
        int price = 0;
        vector<int> skills;
        for(int j = 0; j < m; j++) skills.push_back(0);
        for(int j = 0; j < n; j++){
            if((i & (1 << j)) > 0){
               // if(i == 6) cout << j << endl;
                price += cost[j];
                for(int k = 0; k < m; k++){
                    skills[k] += v[j][k];
                }
            }
        }
        for(int j = 0; j < m; j++){
            if(skills[j] < x) valid = 0;
        }
        if(valid){
           // cout << i << ' ' << price << endl;
            res = min(res, price);
        }
    }
    if(res == INT_MAX) res = -1;
    cout << res;
    return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <list>
#include <fstream>
#include <iomanip>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <bitset>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int

#include <nmmintrin.h>
#ifdef _MSC_VER

#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

struct Edge {
	int from, to, s;
};

int main() {
	string a, b;

	cin >> a >> b;
	int len = a.length();
	a += a;

	REP(i,len) {
		if (a.substr(i, len) == b) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll F(ll n, ll b) {
	ll re = 0;
	while (n > 0) {
		re += n % b;
		n /= b;
	}
	return re;
}

int main() {
	ll n, s, i;
	cin >> n >> s;
	if (n == s) {
		printf("%lld\n", n + 1);
		return 0;
	}
	for (i = 2; i * i <= n; i++) {
		if (F(n, i) == s) {
			printf("%lld\n", i);
			return 0;
		}
	}
	for (; i >= 1; i--) {
		if ((n - s) / i >= 1 && F(n, (n - s) / i + 1) == s) {
			printf("%lld\n", (n - s) / i + 1);
			return 0;
		}
	}
	printf("-1\n");
	return 0;
}

Measured memory_bytes: 256
import sys


def alg_combination_mod(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i) % mod
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, readline().split()))
    for i in range(k):
        if n - k + 1 >= i + 1:
            t = alg_combination_mod(n - k + 1, i + 1, mod)
            t *= alg_combination_mod(k - 1, i, mod)
            print(t % mod)
        else:
            print(0)


if __name__ == '__main__':
    solve()


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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007



int main(){
  
  ll n,K;
  cin >> n >> K;
  vector<ll> a(n),f(n);
  rep(i,n)cin >> a[i];
  rep(i,n)cin >> f[i];
  sort(ALL(a));
  sort(ALL(f),greater<ll>());
  vector<pair<ll,ll>> v(n);
  rep(i,n)v[i] = make_pair(a[i],f[i]);
  ll left = -1,right = 1e13;
  while(right-left > 1){
    ll mid = (right+left)/2;
    ll k = K;
    rep(i,n){
      if(v[i].second*v[i].first <= mid)continue;
      k -= (v[i].first - mid/v[i].second);
    }
    if(k >= 0)right = mid;
    else left = mid;
  }
  cout << right << endl;




  return 0;
}

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

using namespace std;

int n,m;
string s;
vector<int> res;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m;
	cin >> s;
	int pos = n;
	while(pos)
	{
		bool ok = false;
		for (int i=min(pos,m);i>=1;i--)
			if (s[pos - i] == '0')
			{
				ok = true;
				pos -= i;
				res.push_back(i); 
				break;
			}  
		if (!ok)
		{
			cout << -1;
			return 0;
		}
	}
	for (int i=res.size()-1;i>=0;i--)
		cout << res[i] << ' ';
}

Measured memory_bytes: 1096
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <string.h>

using namespace std;

#define MAX_A   (100000)
#define MAX_B   (100000)
#define INF (100000000000)
vector <long long> s, t, x;
vector <long long>::iterator itr;

int A, B, Q;

long long calcDistance(vector <long long>::iterator itr1, vector <long long>::iterator itr2, long long firstDistance) {
    long long distance1 = INF;
    long long distance2 = INF;
    
    distance1 = abs(*itr1 - *itr2);
    
    if (itr2 != s.begin() && itr2 != t.begin()) {
        distance2 = abs(*itr1 - *(itr2 - 1));
    }
    return min(distance1, distance2);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    /* A, B, Qの取得 */
    cin >> A >> B >> Q;
    
    /* s, tの取得*/
    long long tmp;
    for (int i = 0; i < A; i++) {
        cin >> tmp;
        s.push_back(tmp);
    }
    
    for (int i = 0; i < B; i++) {
        cin >> tmp;
        t.push_back(tmp);
    }
    
    /* sとtをソートしておく */
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    
    for (int i = 0; i < Q; i++) {
        cin >> tmp;
        x.push_back(tmp);
    }
    
    /* Q個の問いに答える */
    for (int i = 0; i < Q; i++) {
        long long min = INF;
        long long distance = INF;
        long long firstDistance = 0;
        
        /* 最初に東の神社に行く場合 */
        itr = lower_bound(s.begin(), s.end(), x[i]);
        firstDistance = abs(x[i] - *itr);
        distance = calcDistance(itr, lower_bound(t.begin(), t.end(), *itr), firstDistance) + firstDistance;
        if (distance < min && distance > 0) { min = distance; }
        
        /* 最初に西の神社に行く場合 */
        if (itr != s.begin()) {
            itr = itr - 1;
            firstDistance = abs(x[i] - *itr);
            distance = calcDistance(itr, lower_bound(t.begin(), t.end(), *itr), firstDistance) + firstDistance;
            if (distance < min && distance > 0) { min = distance; }
        }
        
        /* 最初に東の寺に行く場合 */
        itr = lower_bound(t.begin(), t.end(), x[i]);
        firstDistance = abs(x[i] - *itr);
        distance = calcDistance(itr, lower_bound(s.begin(), s.end(), *itr), firstDistance) + firstDistance;
        if (distance < min && distance > 0) { min = distance; }

        /* 最初に西の寺に行く場合 */
        if (itr != t.begin()) {
            itr = itr - 1;
            firstDistance = abs(x[i] - *itr);
            distance = calcDistance(itr, lower_bound(s.begin(), s.end(), *itr), firstDistance) + firstDistance;
            if (distance < min && distance > 0) { min = distance; }
        }
            
        cout << min << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3828
from copy import deepcopy
def inboard(x, y):
    return 0 <= x < 10 and 0 <= y < 10
while True:
    sr, sc = map(int, raw_input().split())
    if (sr, sc) == (0, 0): break
    N = input()
    pointList = map(int, raw_input().split())
    points = []
    for i in range(0, 2*N, 2):
        points.append((pointList[i], pointList[i+1]))
    canReach = set()
    canReach.add((sr, sc))
    jump = [(-2, -1), (-2, 0), (-2, 1),
            (-1, -2), (0, -2), (1, -2),
            (2, -1), (2, 0), (2, 1),
            (-1, 2), (0, 2), (1, 2)]
    for spr, spc in points:
        newset = set()
        for r, c in canReach:
            for dr, dc in jump:
                nr, nc = r + dr, c + dc
                if inboard(nr, nc) and spr-1 <= nr <= spr+1 and spc-1 <= nc <= spc+1:
                    newset.add((nr, nc))
        canReach = deepcopy(newset)
    print("OK" if len(canReach) > 0 else "NA")

Measured memory_bytes: 4324