akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
using namespace std;
int main()
{
  ios::sync_with_stdio(false);
  long long k,a,b;
  cin>>k>>a>>b;
  if(k<=a or a+2>b){cout<<k+1;return 0; }
  else cout<<(a+((k-a+1)/2)*(b-a)+1*(k-a+1)%2);

}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a,b,c;
	while(~scanf("%d%d",&a,&b)){
		c = (a + b + 1) / 2;
		printf("%d\n",c);
	}
	return 0;
}

Measured memory_bytes: 256
N, Y = map(int, input().split())
# N = 9
# Y = 45000


def judge(n, target):
    for x in range(n+1):
        for y in range(n+1-x):
            z = n - x - y
            total = 10000 * x + 5000 * y + 1000 * z
            if total == target:
                return '{} {} {}'.format(x, y, z)
    return '-1 -1 -1'


print(judge(N, Y))


Measured memory_bytes: 3060
from math import *
g=[[0]*202 for _ in range(202)]
for i in range(1,201):
    for j in range(1,201):
        g[i][j]=gcd(i,j)
n=int(input())
a=0
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            a+=g[g[i][j]][k]
print(a)

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

char s[1005];

int main() {
	int n;
	scanf("%d", &n);
	scanf("%s", s);
	if (n&1) puts("No");
	else {
		int m = n>>1;
		for (int i = 0; i < m; i ++) if (s[i] != s[i+m]) {puts("No"); return 0;}
		puts("Yes");
	}
	return 0;
}


Measured memory_bytes: 3732
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

long long N, M, dp[40][40], mod = 1000000007;

long long inv[1<<20]; // ith index will store (1/i)%mod
long long finv[1<<20]; // ith index will store (1/i!)%mod
long long fact[1<<20]; // ith index will store (i!)%mod

map<long long, long long> ma;

void populate() {
    fact[0] = fact[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;

    for(int i = 2;i <= N;i++) {
        fact[i] = (i*fact[i-1])%mod;
        inv[i] = mod-((inv[mod%i]*(mod/i))%mod);
        finv[i] = (finv[i-1]*inv[i])%mod;
    }
}

void primeFactor(long long num) {
  for(long long i = 2;i * i <= num;i++) {
    if(num % i == 0) {
      ma[i]++;
      primeFactor(num/i);
      return;
    }
  }

  ma[num]++;
}

int main() {
  //freopen("input.in","r",stdin);
  //freopen("output.out","w",stdout);

  cin >> N >> M;
  if(M == 1) {
    cout << 1 << endl;
    return 0;
  }

  primeFactor(M);
  populate();

  for(int i = 1;i <= 30;i++) {
    for(int j = 0;j <= 30;j++) {
      if(j == 0) {
        dp[i][j] = 0;
      } else if(i == 1) {
        dp[i][j] = 1;
      } else {
        dp[i][j] = (dp[i][j-1] + dp[i-1][j-1]) % mod;
      }
    }
  }

  long long ans = 1;
  for(auto it = ma.begin();it != ma.end();it++) {
    // cout << it->first << " " << it->second << endl;
    long long tans = 0;
    for(int j = 1;j <= min((int)N, 30);j++) {
      tans = tans + ((((dp[j][it->second]*fact[N]) % mod)*((finv[N-j]*finv[j]) % mod)) % mod);
      tans %= mod;
    }

    ans = (ans * tans) % mod;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 5120
# include <bits/stdc++.h>
# define sz(x) (int)((x).size())
# define f first 
# define s second
# define pb push_back
# define ub upper_bound
# define lb lower_bound
# define all(x) x.begin(), x.end()
# define pqueue priority_queue
# define Speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
# define rep(i,n) for(int i=0;i<n;++i)
# define forn(i,n) for(int i=1;i<=n;++i)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

# define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
# define debug cerr<<"ERROR"<<endl
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

template<class T> void umin(T &a,T b){a=min(a,b);}
template<class T> void umax(T &a,T b){a=max(a,b);}

typedef long long ll;
typedef pair<int,int> pii;

const int dx[]={1,0,-1,0,-1,-1,1,1};
const int dy[]={0,1,0,-1,-1,1,-1,1}; 
const int inf=1e9,mod=1e9+7,N=2e5+5;

void solve(){
	string s;
	cin>>s;
	if(s[sz(s)-1]=='s'){
		cout<<s<<"es";
	}
	else {
		cout<<s<<"s";
	}
}

int main(){
 	Speed();
	int T=1; 
	//cin>>T;	
	while(T--)solve();
}

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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

int n;

map<pair<int, int>, int> cnt;

pair<int, int> calc_key(int num) {
  string str = to_string(num);
  int head = (int)(str[0] - '0');
  int tail = (int)(str.back() - '0');

  return make_pair(head, tail);
}

int main(void) {
  // Here your code !
  scanf("%d", &n);

  for (int i = 1; i <= n; ++i) {
    auto key = calc_key(i);

    cnt[key] += 1;
  }

  ll ans = 0LL;

  for (auto &e : cnt) {
    auto key = e.first;

    auto target = make_pair(key.second, key.first);

    ans += (ll)(cnt[key]) * (ll)(cnt[target]);
  }

  printf("%lld\n", ans);

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The massage in line %d, Function %s: %s\n", __LINE__, __FUNCTION__, s)
typedef long long LL;
typedef long double LD;
int read() {
    char ch = getchar();
    int x = 0, flag = 1;
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') flag *= -1;
    for(;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x * flag;
}
void write(LL x) {
    if(x < 0) putchar('-'), x = -x;
    if(x >= 10) write(x / 10);
    putchar(x % 10 + 48);
}

const int Maxn = 3009;
LL dp[Maxn][Maxn], n, a[Maxn];

void init() {
	n = read();
	rep (i, 1, n) a[i] = read();
}

LL calc(int l, int r) {
	if (l > r) return 0;
	if (dp[l][r] != LLONG_MAX) return dp[l][r];
	LL &res = dp[l][r], step = (r - l + 1) % 2 == n % 2;
	if (step) {
		res = calc(l, r - 1) + a[r];
		res = max(res, calc(l + 1, r) + a[l]);
	} else {	
		res = calc(l, r - 1) - a[r];
		res = min(res, calc(l + 1, r) - a[l]);
	}
	return res;
}

void solve() {
	rep (r, 0, n) 
		rep (s, 0, n) dp[r][s] = LLONG_MAX;
	cout << calc(1, n) << endl;
}

int main() {
 //   freopen("AtcoderDpL.in", "r", stdin);
  //  freopen("AtcoderDpL.out", "w", stdout);

    init();
    solve();

#ifdef Qrsikno
    debug("\nRunning time: %.3lf(s)\n", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
    return 0;
}



Measured memory_bytes: 70912
#include <iostream>                                                                                                                  #include <iostream>
using namespace std;
int main(){
  int A, B, Curtain;
  cin >> A >> B;
  Curtain = A -	B * 2;
  if(Curtain > 0){
    cout << Curtain << endl;
  }else{
    cout << 0 << endl;
  }

}


Measured memory_bytes: 256
#include <iostream>
#include <string.h>

using namespace std;
int main(void){
    char ch;
    int chara[26];
    int num;
    
    for(int i=0;i<26;i++){
        chara[i]=0;
    }
    
    while(cin>>ch){
        if('A'<=ch&&ch<='Z'){
            num=ch-'A';
            chara[num]++;
        }else if('a'<=ch&&ch<='z'){
            num=ch-'a';
            chara[num]++;
        }
    }
    
    for(int i=0;i<26;i++){
        cout<<(char)('a'+i)<<" : "<<chara[i]<<endl;
    }
    
    return 0;
}


Measured memory_bytes: 3092
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <queue>

typedef long long ll;
const ll LL_MAX (1LL<<60);

#define rep(i,s,e) for(ll i=(s); i<(e); i++) 

using namespace std;

ll bubble_sort(vector<ll> *a)
{
    bool is_sorted(false);
    const ll n (a->size());
    ll cnt(0);

    //cout << n << endl;

    while (!is_sorted)
    {
        is_sorted = true;
        for (ll i=n-1; i>=1; i--)
            if (a->at(i) < a->at(i-1))
                swap(a->at(i), a->at(i-1)), is_sorted = false, cnt++;
    }

    return cnt;
}

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

    ll n;
    cin >>n;
    vector<ll> a(n);
    rep(i,0,n) cin >> a[i];

    //for (auto i: a)
    //    cout << i << endl;

    ll cnt = bubble_sort(&a);

    rep(i,0,n) 
    {
        if (i != n-1)
            cout << a[i] << ' ';
        else
            cout << a[i] << endl;
    } 
    
    cout << cnt << endl;

    return 0;
}



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

int main() {
    int n; cin >> n;
    map<string, int> s;
    rep(i, n) {
        string t;
        cin >> t;
        s[t]++;
    }
    cout << "AC" << " x " << s["AC"] << endl;
    cout << "WA" << " x " << s["WA"] << endl;
    cout << "TLE" << " x " << s["TLE"] << endl;
    cout << "RE" << " x " << s["RE"] << endl;
    
}

Measured memory_bytes: 3628
#include <iostream>

#define _USE_MATH_DEFINES

#include <cmath>

using namespace std;

int main()
{
	int n;
	int i;
	double sd;
	double sum, point[1000] = {};
	double ave = 0;

	while (1){
		cin >> n;
		
		if (n == 0)
			break;

		sd = 0;
		sum = 0;
		for (i = 0; i < n; i++){
			cin >> point[i];
			sum += point[i];
		}
		ave = sum / n;
		for (i = 0; i < n; i++){
			sd += (point[i] - ave)*(point[i] - ave);
		}
		sd = sqrt(sd / n);

		cout << fixed << sd << endl;

	}

	return 0;
}

Measured memory_bytes: 1292
#include <bits/stdc++.h>
#include <unistd.h>
#include <sys/time.h>
#include <stdlib.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P, ll> T;
 
long long int INF = 2e18;
const ll fact_table = 1200008;
double Pi = 3.1415926535897932384626;

priority_queue <ll> pql;
priority_queue <P> pqp;
priority_queue <P> bag;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
ll dx[8]={1,0,-1,0,1,1,-1,-1};
ll dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//↓,→,↑,←

#define endl "\n"
#ifdef ENJAPMA
    #undef endl
#endif
#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)(); 
#define pc(x) cout << x << ",";
 
const ll mod = 998244353ll;
// const ll mod = 1000000007ll;
  
ll mypow(ll number1,ll number2, ll mod){
    if(number2 == 0){
        return 1ll;
    }else{
        ll number3 = mypow(number1,number2 / 2, mod);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
void YES(bool condition){
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}

/*
ll fact[fact_table + 5],rfact[fact_table + 5]; 
 
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=fact_table; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[fact_table] = mypow(fact[fact_table],mod - 2, mod);
    for(ll i=fact_table; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    assert(n >= r);
    assert(n >= 0);
    assert(r >= 0);
    return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;}
*/
bool multicase = false;

ll n,m,num,a,b,c,d,e,q;

ll x[100005], y[100005], z[100005];
ll k, ans;

void solve(){
    cin >> a >> b >> c >> k;
    if(a >= k){
        p(k);
    }else if(a + b >= k){
        p(a);
    }else{
        p(a - (k - a - b));
    }
    
    return;
}

int main(){
    // init();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll q, testcase = 1;
    if(multicase){
        cin >> q;
    }else{
        q = 1; 
    }
    while(q--){
        // pu("Case ");pu("#");pu(testcase);pu(": ");
        solve();
        testcase++;
    }
    // solve();
    return 0;
}
















Measured memory_bytes: 3656
import sys
import math
import heapq
from itertools import permutations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()

DIC = list(permutations(list(range(1, N+1)), N))
a=DIC.index(tuple(LI()))
b=DIC.index(tuple(LI()))

print(abs(a-b))


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

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

int main() {
    
    const double PI=3.14159265358979323846;
    double a,b,h,m;cin>>a>>b>>h>>m;
    
    double h1,m1,rad;
    h1 = (h + m/60)*30;
    m1 = m*6;
    rad = min(abs(h1 - m1),abs(360-(h1 - m1)));
    
    double c = sqrt(a*a + b*b - 2*a*b*cos(rad*PI/180));
    cout<<setprecision(12)<<c<<endl;

	return 0;
}

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

int main() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> h(n);
    for (int i = 0; i < n; i++) {
        std::cin >> h[i];
    }
    std::sort(h.begin(), h.end());
    int ans = h[n-1];
    for (int i = 0; i + k - 1 < n; i++) {
        ans = std::min(ans, h[i+k-1]-h[i]);
    }
    std::cout << ans << std::endl;
}

Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<time.h>
#include<cassert>
#include<functional>
#include<numeric>
#include <tuple>

using namespace std;
using ll = long long;
using ld = long double;
#define int long long
#define all(a) (a).begin(),(a).end()
#define EPS (1e-7)
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define H pair<int, int>
#define P pair<int, pair<int, int>>
#define Q(i,j,k) mkp(i,mkp(j,k))
#define rep(i,n) for(int (i) = 0 ; (i) < (n) ; (i)++)
#define reo(i,n) for(int (i) = 1 ; (i) <= (n) ; (i)++)
#define rng(i,s,n) for(int (i) = (s) ; (i) < (n) ; (i)++)
#define req(n,i) for(int (i) = (n) - 1 ; (i) >= 0 ; (i)--)
#define mkp make_pair
#define mem0(x) memset(x,0,sizeof(x))
#define vec vector
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
#define ssp(i,n) (i==n-1?"\n":" ")
#define ctoi(c) (int)(c-'a')
#define itoc(c) (char)(c+'a')
#define itn int
#define pri_que priority_queue
#define pp(x,y) pb(H{x,y})
#define ppp(x,y,z) pb(Q(x,y,z))
#define cyes cout<<"Yes\n"
#define cno cout<<"No\n"
const int mod = 1e9 + 7;
const int Mod = 998244353;
const ll inf = 3 * 1e18;
const int Inf = 15 * 1e8;
const vec<int>dx{ 0,0,-1,1 }, dy{ 1,-1,0,0 };
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
ll read() { ll u, k = scanf("%lld", &u); return u; }
string reads() { string s; cin >> s; return s; }
ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; }
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
ll bitcount(ll x) {
	int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++;
	return sum;
}
/*const int fn_ = 600000;
ll fact_[fn_], comp_[fn_];
ll comb(ll x, ll y, ll Mod = mod) {
	if (!fact_[0]) {
		fact_[0] = 1; comp_[0] = 1;
		for (int i = 1; i < fn_; i++) {
			fact_[i] = fact_[i - 1] * i % Mod;
			comp_[i] = mod_pow(fact_[i], Mod - 2, Mod);
		}
	}
	if (x < y) return 0;
	return fact_[x] * comp_[x - y] % Mod * comp_[y] % Mod;
}*/
//---------------------------------------------------------------
int n;
signed main() {
	cin >> n;
	vec<int>a;
	rep(i, n) a.pb(read());
	int res = inf, ans = 0;
	rep(i, n) {
		if (a[i] <= res) {
			ans++;
		}
		res = min(res, a[i]);
	}
	cout << ans << endl;
}

Measured memory_bytes: 2420
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[] s = sc.next().toCharArray();
        int ans = 0;
        for(int i = 0; i < n - 2; i++) {
            if(s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') ans++;
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 21716
#include<bits/stdc++.h>
#define MAX 200005
using namespace std;
 
int main(){
  int n, m, a, b, c[MAX][2], used[MAX];
  vector<int> v[MAX][2];
  char s[MAX];
  scanf("%d%d", &n, &m);
  fill(c[1], c[n+1], 0);
  fill(used+1, used+n+1, false);
  scanf("%s", s+1);
  for(int i = 0; i < m; i++){
    scanf("%d%d", &a, &b);
    v[a][s[b] - 'A'].push_back(b);
    v[b][s[a] - 'A'].push_back(a);
    c[a][s[b] - 'A']++;
    c[b][s[a] - 'A']++;
  }
  for(int i = 1; i <= n; i++){
    if(used[i] || (c[i][0] && c[i][1])) continue;
    deque<int> d = {i};
    while(!d.empty()){
      int t = d.front(); d.pop_front();
      if(used[t]) continue;
      int k = (c[t][0] == 0);
      for(auto it : v[t][k]){
        c[it][s[t] == 'B']--;
        if(!c[it][s[t] == 'B']) d.push_front(it);
      }
      used[t] = true;
    }
  }
  bool ans = false;
  for(int i = 1; i <= n; i++){
    if(c[i][0] && c[i][1]) ans = true;
  }
  puts(ans ? "Yes" : "No");
  
}

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

int main(){
  int N, K, a, S = 0;
  cin >> N >> K;
  
  vector<int> A(N);
  
  for (int i = 0; i < N; i++){
    cin >> a;
    A.at(a-1) += 1;
  }
  
  sort(A.begin(), A.end());
  
  for (int i = 0; i < N-K; i++){
    S += A.at(i);
  }
  cout << S << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
 
const int N = 2 * 1e5;
 
ll bpow(ll a, ll b) {
	long long res = 1;
	while (b > 0) {
		if (b & 1)
			res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}
 
int n;
map<int, int> compressed, cnt;
bitset<N> isHalf, halfCon;
set<int> halves;
 
vi conn[N];
int depth[N];
int ans = 0;


 
void count(int v, int m) {
	if (isHalf[v] && m) return;
	if (halfCon[v] && m) return;
	if (!cnt[v]) return;
	
	for (int u : conn[v]) {
		if (isHalf[u] || !cnt[u]) continue;
		if (halfCon[u] && m) return;
		int lim = min(cnt[u], cnt[v]);
		cnt[u] -= lim, cnt[v] -= lim;
		ans += lim;
	}
	
	if (isHalf[v]) {
		ans += cnt[v] / 2;
		cnt[v] %= 2;
	}
}


struct Comp
{
    // Compare 2 Player objects using name
    bool operator ()(const int& a, const int& b)
    {
		if (halfCon[a]) return false;
		if (halfCon[b]) return true;
        return depth[a] <= depth[b];
    }
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	vi a(n);
	rep(i, 0, n) {
		cin >> a[i];
		compressed[a[i]];
	}
	
	int pos = 0;
	for (auto& x : compressed) {
		if (!(bpow(2, ceil(log2(x.first))) - x.first)) {
			isHalf[pos] = 1;
			halves.insert(pos);
		}
		x.second = pos++;
	}
	
	rep(i, 0, n) {
		a[i] = compressed[a[i]];
		++cnt[a[i]];
	}
	
	for (pii i : compressed) {
		ll nxt = bpow(2, ceil(log2(i.first))) - i.first;
		if (nxt != i.first && compressed.count(nxt)) {
			conn[i.second].push_back(compressed[nxt]);
			conn[compressed[nxt]].push_back(i.second);
		}
	}
	
	queue<int> q, rq;
	vector<bool> vis(pos, false);
	
	rep(i, 0, pos) {
		if (sz(conn[i]) == 1) {
			q.push(i);
			vis[i] = true;
		}
	}
	
	while (!q.empty()) {
		int v = q.front();
		rq.push(v);
		q.pop();
		for (auto u : conn[v]) {
			if (!vis[u]) {
				q.push(u);
				depth[u] = depth[v] + 1;
				vis[u] = true;
			}
		}
	}
	
	halfCon.reset();
	set<int> semiHalves;
	for (int i : halves) {
		for (int u : conn[i]) {
			halfCon[u] = true;
			semiHalves.insert(u);
		}
	}
	
	rep(i, 0, n) {
		sort(all(conn[i]), Comp());
	}
	
	while (!rq.empty()) {
		int v = rq.front();
		rq.pop();
		count(v, 1);
	}
	
	for (int i : semiHalves) {
		count(i, 0);
	}
	
	for (int i : halves) {
		count(i, 0);
	}
	cout << ans;
}


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

using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int MAXN = 200010;
ll H, W;
ll A, B;
ll kaizyou[MAXN+1]; //iの階乗
ll r_kaizyou[MAXN+1]; //iの階乗の逆元
ll ans;

ll nCr (int n, int r) {
  return kaizyou[n] * r_kaizyou[n-r] % mod *r_kaizyou[r] % mod;
}

ll solve(ll x, ll v) {
  ll res = 1;
  while(v > 0) {
    if(v & 1) res = res * x % mod;
    
    x = x * x % mod;
    v >>= 1;
  }
  return res % mod;
}

int main(){
  cin >> H >> W >> A >> B;
  kaizyou[0] = 1;
  r_kaizyou[0] = 1;

  for(ll i = 1; i <= H + W; i++) {
    kaizyou[i] = kaizyou[i-1] * i % mod;
    r_kaizyou[i] = solve(kaizyou[i],mod-2);
  }


  /*  int C=H-A;
 
for(int i=C; i>=1; i--) ans=(ans+nCr(i-1+B-1,i-1)*nCr(H-i+W-B-1,H-i))%mod;
  */
  for(ll i = B; i < W; i++) {
    ans += nCr(H-A-1+i,i) * nCr(A+W-i-2,W-i-1) % mod;
  }

  cout << ans % mod <<endl;
}

    
  
  


Measured memory_bytes: 3328
import sys
sys.setrecursionlimit(10 ** 6)

n, m = map(int, input().split())
e = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    e[a-1].append(b-1)

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            print(-99999)
            exit()
        else:
            search_path(x, temp + [x])


t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(i, [i])

print(-1)


Measured memory_bytes: 13688
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Math;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using LayoutKind = System.Runtime.InteropServices.LayoutKind;
using StructLayoutAttribute = System.Runtime.InteropServices.StructLayoutAttribute;
using FieldOffsetAttribute = System.Runtime.InteropServices.FieldOffsetAttribute;

class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        if (n == 1) Console.WriteLine("Hello World");
        else
        {
            int a = int.Parse(Console.ReadLine());
            int b = int.Parse(Console.ReadLine());
            Console.WriteLine(a + b);
        }
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
    int Max,n;
    while(cin >> Max, Max){
        int map[252] = {};
        bool dist[252][252];
        cin >> n;
        for(int i = 1; i <= n; ++i){
            cin >> map[i];   
        }
        fill((bool*)dist,(bool*)(dist + n + 2),false);
        queue<int> q;
        q.push(0);
        while(!q.empty()){
            int x = q.front(); q.pop();
            for(int i = 1; i <= Max; ++i){
                int nx = x + i;
                if(nx >= n + 1){
                    dist[x][n + 1] = true;
                } else {
                    nx += map[nx];
                    if(nx >= n + 1){
                        dist[x][n + 1] = true;
                    } else if(nx <= 0){
                        dist[x][0] = true;
                    } else if(dist[x][nx] == false){
                        dist[x][nx] = true;
                        q.push(nx);
                    }
                }
            }
        }
        for(int i = 0; i < n + 2; ++i){
            dist[i][i] = true;
        }
        for(int k = 0; k < n + 2; ++k){
            for(int i = 0; i < n + 2; ++i){
                for(int j = 0; j < n + 2; ++j){
                    if(dist[i][k] && dist[k][j]) dist[i][j] = true;
                }
            }
        }
        
        bool f = false;
        for(int i = 0; i < n + 1; ++i){
            if(dist[0][i] && !dist[i][n + 1]){
                f = true;
                break;
            }
        }
        cout << (f?"NG":"OK") << endl;
    }
}

Measured memory_bytes: 1272
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int n,i,copy;
		n=stdIn.nextInt();
		int[] a=new int[n];
		for(i=0;i<n;i++){
			a[i]=stdIn.nextInt();
		}
		for(i=0;i<n/2;i++){
			copy=a[i];
			a[i]=a[n-i-1];
			a[n-i-1]=copy;
		}
		for(i=0;i<n;i++){
			System.out.print(a[i]);
			if(i==n-1){
			}else{
				System.out.print(" ");
			}
		}
		System.out.println();
		stdIn.close();
	}
}



Measured memory_bytes: 26328
#pragma once
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <numeric>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1000000007;
const int MAX_V = 201;
int now = 0;
int deco[1000];

void Sequence() {
	int n, t;
	cin >> n >> t;
	ll row = INF;
	ll rem = 0;
	int ac = 0;
	int rc = 0;
	int res = 0;
	for (size_t i = 0; i < n; i++)
	{
		ll a;
		cin >> a;
		if (row > a) {
			rc = 1;
		}
		else if (row == a) {
			rc++;
		}
		if (row >= a) {
			res += min(ac, rc);
			ac = 0;
		}
		row = min(a, row);
		if (i == 0) continue;
		if (row == a) continue;

		if (rem < a - row) {
			rem = a - row;
			ac = 1;
			res = 0;
		}
		else if (rem == a - row) {
			ac++;
		}

	}
	cout << (res + min(ac,rc)) << endl;
}
int main() {
	Sequence();
	return 0;
}



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

int gcd(int x,int y){
  if(y==0){
    return x;
  }
  return gcd(y,x%y);
}
  
int main(){
  int K,sum=0;
  cin >> K;
  for(int a=1;a<K+1;a++){
    for(int b=1;b<K+1;b++){
      for(int c=1;c<K+1;c++){
        sum+=gcd(a,gcd(b,c));
      }
    }
  }
  cout << sum << endl;
} 

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <map>
#include <unordered_map>
#include <chrono>
#include <numeric>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18+1;
const ll DIV = 1000000007;
//#define TEST
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef TEST
    chrono::system_clock::time_point start, end;
    start = chrono::system_clock::now();
#endif
    long N;
    cin >> N;
    std::vector<std::vector<bool>> F(N, vector<bool>(10, false));
    for(size_t i=0;i<N; i++)
    {
        bool run;
        for(size_t j=0;j<10; j++)
        {
            cin >> run;
            F[i][j] = run;
        }
    }
    std::vector<std::vector<ll>> P(N, vector<ll>(11, 0));
    for(size_t i=0;i<N; i++)
    {
        ll profit;
        for(size_t j=0;j<=10; j++)
        {
            cin >> profit;
            P[i][j] = profit;
        }
    }
    /*
    for(size_t i=0;i<N; i++)
    {
        for(size_t j=0;j<10; j++)
        {
            cerr << F[i][j] << " ";
        }
        cerr << endl;
    }
    for(size_t i=0;i<N; i++)
    {
        for(size_t j=0;j<=10; j++)
        {
            cerr << P[i][j] << " ";
        }
        cerr << endl;
    }
    */
    ll res = -INF;
    for(ll b=1;b<(1<<10); b++)
    {
        ll cc = 0;
        for(size_t i=0;i<N; i++)
        {
            ll c = 0;
            for(size_t j=0;j<10; j++)
            {
                if((b>>j & true) && F[i][j]) c++;
            }
            cc += P[i][c];
        }
        if(res < cc) res = cc;
    }
    cout << res << endl;
#ifdef TEST
    end = chrono::system_clock::now();
    cerr << static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0) << "[ms]" << endl;
#endif
    return 0;
}

Measured memory_bytes: 3680
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main(void) {
  int n;
  cin >> n;
  vector<ll> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] == 0) {
      cout << 0 << endl;
      return 0;
    }
  }
  ll x = 1e18;
  ll ans = 1LL;
  for (int i = 0; i < n; i++) {
    if (ans <= x / a[i]) {
      ans *= a[i];
    } else {
      ans = -1;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3968
#include<stdio.h>
#include<math.h>
int main(){
int a;
scanf("%d",&a);
char x[a];
scanf("%s",x);


int q=0;
for(int b=0;b<a-2;b++)
if(x[b]=='A'&& x[b+1]=='B'&& x[b+2]=='C')q+=1;


printf("%d",q);

return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,d;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	a+=b;
	c+=d;
	if(a>c)
		printf("Left");
	else if(c>a)
		printf("Right");
	else
		printf("Balanced");
	return 0;
} 

Measured memory_bytes: 256
m,d = map(int,input().split())

c = 0
for j in range(1,m+1):
    d1 = 1
    d2 = 0
    for i in range(d):
        if d1 >= 2 and d2 >= 2 and d1*d2 == j:
            c += 1
        if d1 < 9:
            d1 += 1
        else:
            d1 = 0
        if d1 == 0:
            d2 += 1
            
print(c)
    

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

pair <ll,ll> t[200006];

int main(){
  ll n;
  ll f = 1;
  ll i;

  scanf("%lld", &n);

  for(i = 0;i < n;i++){
    scanf("%lld %lld", &t[i].second, &t[i].first);
  }

  sort(t,t + n);

  ll sum = 0;
  for(i = 0;i < n;i++){
    sum += t[i].second;

    if(sum > t[i].first) f = 0;
  }

  if(f) printf("Yes\n");

  else printf("No\n");

  return 0;
}

Measured memory_bytes: 3328
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define F first
#define S second
#define _sz(x) (int)x.size()

using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;

string s ;

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

	cin >> s ;
	s[3] = '8' ;
	cout << s << '\n' ;
}


Measured memory_bytes: 256
from collections import Counter

M = 998244353
n = int(input())
d = list(map(int, input().split()))
counter = Counter(d)

if d[0] != 0 or counter[0] != 1:
    ans = 0
else:
    ans = counter[0]
    for i in range(1, max(d) + 1):
        if counter[i] == 0:
            ans = 0
            break
        m, n = counter[i - 1], counter[i]
        c = m ** n
        ans *= c

print(ans % M)

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


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

namespace mp = boost::multiprecision;

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

typedef pair<int, int> P;

bool pairsort1(const P& element1, const P& element2)
{//first昇順
	return element1.first < element2.first;
}
bool pairsort2(const P& element1, const P& element2)
{//first降順
	return element1.first > element2.first;
}
bool pairsort3(const P& element1, const P& element2)
{//second昇順
	return element1.second < element2.second;
}
bool pairsort4(const P& element1, const P& element2)
{//second降順
	return element1.second > element2.second;
}

int main() {
	int n;
	cin >> n;
	vector<pair<int,int>>x(n),ans(n);
	rep(i, n) {
		scanf("%d",& x[i].F);
		x[i].second = i;
	}
	sort(all(x), pairsort1);
	int ans1 = x[n / 2 - 1].first;
	int ans2 = x[n / 2].first;
	rep(i, n) {
		int &ite=ans[i].second ;
		ite = x[i].second;
		if (x[i].second >= n / 2) {
		    ans[ite].first = ans1;
		}
		else {
		    ans[ite].first=ans2;
		}
	}
	sort(all(ans), pairsort3);
	rep(i, n) {
		printf("%d\n", ans[i].first);
	}

}



Measured memory_bytes: 5376
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head

int d[5];
int main() {
	int u, v;
	for (int i = 0; i < 3; i++) cin >> u >> v, d[u]++, d[v]++;
	int cnt = 0;
	for (int i = 1; i <= 4; i++) {
		if(d[i] == 0) return 0*puts("NO");
		if(d[i]%2) cnt++;
	}
	if(cnt <= 2) puts("YES");
	else puts("NO");
	return 0;
}

Measured memory_bytes: 256
// #includes {{{
#ifdef MY_DEBUG
#include "header/header.hpp"
#else
#include <bits/stdc++.h>
#endif

using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define LET(x,a) __typeof(a) x(a)
//#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i)
#define ALL(c) (c).begin(), (c).end()
#define MP make_pair

#define EXIST(e,s) ((s).find(e)!=(s).end())

#define RESET(a) memset((a),0,sizeof(a))
#define SET(a) memset((a),-1,sizeof(a))
#define PB push_back
#define DEC(it,command) __typeof(command) it=command

//debug

#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)

typedef long long Int;
typedef unsigned long long uInt;
typedef long double rn;

template<class T>
T inf(){
	return numeric_limits<T>::has_infinity?numeric_limits<T>::infinity():(numeric_limits<T>::max()/2);
}

typedef pair<int,int> pii;

#ifdef MY_DEBUG
#include"print.hpp"
#include"debug.hpp"
#endif
// }}}

//{{{ Union-Find
struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		int r;
		compress(x,r);
		return r;
	}
	int size(int x) {
		return -data[root(x)];
	}
	void compress(int x,int &r){
		if(data[x]<0){
			r=x;
			return;
		}
		compress(data[x],r);
		data[x]=r;
	}
};
//}}}

int main(){
	int N, M;
	cin>>N>>M;
	UnionFind uf(N);
	REP(i,M){
		int X,Y,Z;
		cin>>X>>Y>>Z;
		X--;Y--;
		uf.unionSet(X,Y);
	}
	unordered_set<int> us;
	REP(i,N){
		us.insert(uf.root(i));
	}
	cout<<us.size()<<endl;
}

Measured memory_bytes: 4772
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
using namespace std;



ll power(ll a, ll b) {
    ll ans = 1;
    ll t = a;
    while (b) {
        if (b % 2) {
            ans = (ans * t) % mod;
        }

        t = (t * t) % mod;
        b /= 2;
    }

    return ans;
}



int main() {
//    cout << fixed << setprecision(20);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);



    ll fact[2000001];
    fact[0] = 1;
    for (int i = 1; i < 2000001; i++) fact[i] = (fact[i - 1] * i) % mod;
    int x, y;
    cin >> x >> y;
    if (2 * x - y < 0 || (2 * x - y) % 3) {
        cout << 0;
        return 0;
    }

    int b = (2 * x - y) / 3;
    int a = x - 2 * b;
    if (a < 0) {
        cout << 0;
        return 0;
    }
    ll ans = (fact[a + b] * power(fact[a], mod - 2)) % mod;
    ans = (ans * power(fact[b], mod - 2)) % mod;
    cout << ans;


}


Measured memory_bytes: 15872
#include <stdio.h>
#include <string.h>

int main(){
	int n,i,out,score,run;
	char str[8];

	scanf("%d",&n);

	for(i = 0;i < n;i++){
		out = 0;
		run = 0;
		score = 0;
		while(1){
			scanf("%s",str);
			if(strcmp(str,"HIT") == 0){
				run *= 2;
				run += 1;
				if(run >= 8){
					run -= 8;
					score++;
				}
			}else if(strcmp(str,"OUT") == 0){
				out++;
				if(out == 3){
					break;
				}
			}else if(strcmp(str,"HOMERUN") == 0){
				while(1){
					score += run%2;
					run /= 2;
					if(run == 0){
						break;
					}
				}
				score++;
			}
		}
		printf("%d\n",score);
	}

	return 0;
}

Measured memory_bytes: 596
# -*- coding: utf-8 -*-
str = input()
h = {}
count = 0
for c in list(str):
    if c in h:
        h[c] += 1
    else:
        count += 1
        h[c] = 1
if len(h.keys()) != 2:
    print("No")
    exit(0)
for v in h.values():
    if v != 2:
        print("No")
        exit(0)
print("Yes")



Measured memory_bytes: 3060
#include <iostream>
using namespace std;
long long N, A, B; int C, D;
int main() {
	cin >> N >> C >> D >> A >> B;
	long long E = A ? (A * 100 - 1) / C + 1 : 0;
	long long F = B ? (B * 100 - 1) / D + 1 : 0;
	if (N < E + F) cout << -1 << endl;
	else cout << N - E - F << endl;
	return 0;
}

Measured memory_bytes: 3104
def solve(li,nu,mu,cnt):
    if len(li) == 1:
        return li[0]
    next_num = (nu+mu)%(len(li))-1
    pop_num = (nu+mu)%(len(li))
    li.pop(pop_num)
    return solve(li,next_num,mu,cnt+1)

while True:
    n,m = map(int,raw_input().split())
    if n == m == 0:
        break
    lis = range(1,n+1)
    print solve(lis,n-1,m,0)

Measured memory_bytes: 4728
#include<bits/stdc++.h>
#define int long long
#define M 998244353
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define zero(dp) memset(dp,0,sizeof(dp))
#define pb emplace_back
#define sublime 
using namespace std;
int32_t main(){

ios
int t=1;
//cin>>t;
while(t--)
{
	int n,blue,red;cin>>n>>blue>>red;
	cout<<(n/(blue+red))*blue+min(blue,(n%(blue+red)));
}
}

Measured memory_bytes: 256
INPUT_LINE = gets.chomp!.split(" ").map! { |i| i.to_i }
X = INPUT_LINE[0]
N = INPUT_LINE[1]
INPUT_LINE2 = gets.chomp!.split(" ").map! { |i| i.to_i } unless N == 0
if N == 0
  puts X
  exit
end
tmp = 0
loop do
  if not INPUT_LINE2.include?(X - tmp)
    puts X - tmp
    break
  end
  if not INPUT_LINE2.include?(X + tmp)
    puts X + tmp
    break
  end
  tmp += 1
end


Measured memory_bytes: 14248
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD=998244353ll;
const int mx=2000001;
int n,m,fac[2000005],ifac[2000005];
int powM(int V,int T=MOD-2ll){
	int R=1;
	while(T){
		if(T&1) R=(LL)R*(LL)V%MOD;
		T>>=1;
		V=(LL)V*(LL)V%MOD;
	}
	return R;	
}
int C(int n,int m){
	if(n<m) return 0;
	if(!m) return 1;
	return (LL)fac[n]*(LL)ifac[m]%MOD*(LL)ifac[n-m]%MOD;
}
int main(){
	int i,j,k;
	scanf("%d%d",&n,&m);
	fac[0]=1;
	for(i=1;i<=mx;++i) fac[i]=(LL)fac[i-1]*(LL)i%MOD;
	ifac[mx]=powM(fac[mx]);
	for(i=mx-1;i>=0;--i) ifac[i]=(LL)ifac[i+1]*(LL)(i+1)%MOD;
	int res=0;
	for(i=n;i>=0;--i){
		if((i&1)!=(m&1)) continue;
		if(i>m) continue;
		for(j=0;j<=3 && j<=n-i;++j){
			for(k=0;k<=3 && k<=i;++k){
				int d=j*2*(m+1)+k*2*m;
				if(d+i>m*3) continue;
				int cur=(LL)C(n,i)*(LL)C((m*3-i-d)/2+n-1,n-1)%MOD*(LL)C(i,k)%MOD*(LL)C(n-i,j)%MOD;
				if((j+k)&1)
					res=(res+MOD-cur)%MOD;
				else
					res=(res+cur)%MOD;
			}
		}
		res%=MOD;
	}
	printf("%d\n",res);
	return 0;
}

Measured memory_bytes: 15872
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7

counter = defaultdict(int)
for a in A:
    counter[a] += 1

if N % 2 == 0:
    check = {i: 2 for i in range(1, N, 2)}
else:
    check = {i: 2 for i in range(2, N, 2)}
    check[0] = 1

unsatisfied = False
for key, val in counter.items():
    temp = check.get(key, None)
    if temp == None or temp < val:
        unsatisfied = True
        break

if unsatisfied:
    print(0)
else:
    print(2**(N//2) % mod)    

Measured memory_bytes: 18272
#!/usr/bin/env python3
#diverta2019 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(input())
_A = []
B_ = []
BA = []
cnt = 0
for _ in range(n):
    s = input()
    for i in range(len(s)-1):
        if s[i] == 'A' and s[i+1] == 'B':
            cnt += 1
    if s[0] != 'B' and s[-1] == 'A':
        _A.append(s)
    elif s[0] == 'B' and s[-1] != 'A':
        B_.append(s)
    elif s[0] == 'B' and s[-1] == 'A':
        BA.append(s)
a = len(_A)
b = len(B_)
ba = len(BA)
ans = cnt
if ba >= 1:
    if a + b > 0:
        ans += (ba-1) + min(a,b) + 1
    else:
        ans += ba - 1
else:
    ans += min(a,b)
print(ans)


Measured memory_bytes: 50408
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	g := make([][]int, n)
	var s string
	for i := 0; i < n; i++ {
		fmt.Scan(&s)
		g[i] = make([]int, n)
		for j := 0; j < n; j++ {
			g[i][j] = int(s[j] - '0')
		}
	}

	ok := isOk(g)
	if !ok {
		fmt.Println(-1)
		return
	}

	ans := count(g)
	fmt.Println(ans)

}

func isOk(g [][]int) bool {
	n := len(g)
	c := make([]int, n)

	var dfs func(v int) bool
	dfs = func(v int) bool {
		for u, o := range g[v] {
			if o == 0 || u == v {
				continue
			}

			if c[u] != 0 {
				if c[u] == c[v] {
					return false
				}
				continue
			}

			c[u] = -c[v]
			if !dfs(u) {
				return false
			}
		}

		return true
	}

	c[0] = 1
	res := dfs(0)

	return res
}

// Pair .
type Pair struct {
	first, second int
}

func count(g [][]int) int {
	const inf int = 1e9

	n := len(g)
	d := make([][]int, n)
	for i := 0; i < n; i++ {
		d[i] = make([]int, n)
		for j := 0; j < n; j++ {
			d[i][j] = inf
			if g[i][j] == 1 {
				d[i][j] = 1
			}
		}
		d[i][i] = 0
	}

	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				d[i][j] = min(
					d[i][j],
					d[i][k]+d[k][j],
				)
			}
		}
	}

	res := 0
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if d[i][j] == inf {
				continue
			}

			res = max(res, d[i][j])
		}
	}

	if res == 0 {
		return 0
	}

	return res + 1
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define ll long long
#define mod (1000000007)
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define yes cout << "yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;
#define no cout << "no" << endl;
#define all(x) (x).begin(),(x).end()

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

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

ll fac(ll n){
    ll t = 1;
    rep1(i, n + 1)t *= i;
    return t;
}

int main()
{
    string n;
    ll ans = 0;
    bool a = false;
    cin >> n;
    if (n[0] - '0' != 9) {
        ans = 9 * (n.size() - 1) + n[0] - '0';
        rep1(i, n.size() - 1){
            if (n[i] - '0' != 9) {
                --ans;
                break;
            }
        }
    }else{
        rep0(i, n.size()){
            if (n[i] - '0' != 9 && !a) {
                a = true;
                --ans;
            }
            ans += 9;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
using namespace std;
typedef pair<int,int> P;
double dat[100][100];
int dp[6][1010];//動的計画法
int prime[10000001];
char str[1010][1010];
vector<pair<int,int> > pc[100001];
int ABS(int a){return max(a,-a);}
int main(){
  int n,m;
  char change[127],befo,aft,tmp;
  while(cin>>n,n){
	  for(int i=0;i<127;i++) change[i]=0;
	  for(int i=0;i<n;i++){
		  cin>>befo>>aft;
		  change[befo]=aft;
	  }
	  cin>>m;
	  for(int i=0;i<m;i++){
		  cin>>tmp;
		  if(change[tmp]==0) cout<<tmp;
		  else{
			  cout<<change[tmp];
		  }
	  }
	  cout<<endl;
  }
    return 0;
}


Measured memory_bytes: 5408
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int n;
    int m;
    int k;
    scanf("%d", &n);
    scanf("%d", &m);
    scanf("%d", &k);

    long long int *a;
    long long int *b;
    long long int temp;
    int i;
    a = (long long int *)malloc(sizeof(long long int) * n + 1);
    a[0] = 0;
    for (i = 1; i < n + 1; i++)
    {
        scanf("%lld", &temp);
        a[i] = a[i - 1] + temp;
    }
    b = (long long int *)malloc(sizeof(long long int) * m + 1);
    b[0] = 0;
    for (i = 1; i < m + 1; i++)
    {
        scanf("%lld", &temp);
        b[i] = b[i - 1] + temp;
    }

    int answer = 0;
    int j = m;
    for (i = 0; i < n + 1; i++)
    {
        if (a[i] > k)
        {
            break;
        }
        while (b[j] > k - a[i])
        {
            j -= 1;
        }
        answer = answer > (i + j) ? answer : (i + j);
    }

    printf("%d\n", answer);

    free(a);
    free(b);
    return 0;
}

Measured memory_bytes: 4604
n, h = map(int, input().split())

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

amax = max(a)
cnt = 0
for bi in sorted(b, reverse=True):
    if bi < amax:
        break
    cnt += 1
    h -= bi
    if h <= 0:
        break

if h > 0:
    if h % amax == 0:
        cnt += h // amax
    else:
        cnt += h // amax + 1

print(cnt)

Measured memory_bytes: 12080
def culuc(a):
    cnt = 0
    while a%2==0:
        a//=2
        cnt+=1
    return cnt
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return a*b//gcd(a,b)
n,m = map(int,input().split())
a = list(map(int,input().split()))
cnt = culuc(a[0])
for i in a:
    if culuc(i)!=cnt:
        print(0)
        exit()
res = a[0]//2
for i in a:
    res = lcm(res,i//2)
    if res>m:
        print(0)
        exit()
print((m//res+1)//2)

Measured memory_bytes: 14244
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,x;
	scanf("%d %d %d",&a,&b,&x);
	if(x>=a&&a+b>=x)
	{
		printf("YES");
	}
	else
	{
		printf("NO");
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<map>
#include<functional>
#include<queue>
using namespace std;
int main() {
   int x;
   cin>>x;
   int n=0;
   for(int i=1;i<=x;i++){
       n+=i;
       if(n>=x){
           cout<<i<<endl;
           return 0;
       }
   }
}   



Measured memory_bytes: 256
h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))
    
ans=[]  
for i in range(h-1):
    for j in range(w):
        if a[i][j]%2==1:
            ans.append([i+1,j+1,i+2,j+1])
            a[i+1][j]+=1
  
for j in range(w-1):
    if a[h-1][j]%2==1:
        ans.append([h,j+1,h,j+2])
        a[h-1][j+1]+=1
print(len(ans))
for i in range(len(ans)):
    print(ans[i][0],end=" ")
    print(ans[i][1],end=" ")
    print(ans[i][2],end=" ")
    print(ans[i][3])
 

Measured memory_bytes: 30832