akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[10010];
ll fac[1000010];
const ll mod=1e9+7;
ll sqr(ll x){	//sqr(5)=2,sqr(10)=3
	ll lft=0,rht=1e5;
	while(rht-lft>1){
		ll mid=(rht+lft)>>1;
		if(mid*mid<=x){
			lft=mid;
		}
		else{
			rht=mid;
		}
	}
	return lft;
}
ll qp(ll a,ll b,ll mod){
	ll ans=1;
	while(b){
		if(b&1)
			ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
ll getInv(ll x,ll p){
	return qp(x,p-2,p);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		int tmp=a[i],bound=sqr(a[i]);
		for(int j=2;j<=bound;j++){
			if(tmp%j==0){
				ll save=0;
				while(tmp%j==0){
					tmp/=j;
					save++;
				}
				fac[j]=max(fac[j],save);
				j=1;bound=sqr(tmp);
			}
		}
		if(tmp!=1){
			fac[tmp]=max(fac[tmp],1ll);
		}
	}
	ll sum=1;
	for(int i=2;i<=1000005;i++){
		sum=sum*qp(i,fac[i],mod)%mod;
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		ans=ans+getInv(a[i],mod)*sum%mod;
		ans%=mod; 
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 6656
gets # disrad 1 line

input = gets.chomp.split.map{|e| e.to_i / 400  }

input_less = input.select{|item| item < 8}
input_more = input.select{|item| item >= 8}

if input_less.length > 0

  answer_min = input_less.uniq.length
  answer_max = answer_min + input_more.length


else
  answer_min = 1
  answer_max = input_more.length

end

puts "#{answer_min} #{answer_max}"


Measured memory_bytes: 1788
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	string s, t; cin>>s>>t;
    s+=t.back();
    if(s==t) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
	return 0;
}


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using pii = pair<int, int>;

vi bin(ll x){
    if(x == 0) return {0};
    vi ans;
    while(x != 0){
        ans.pb(x % 2);
        x /= 2;
    }
    return ans;
}

void printv(vi v){
    for(auto i : v) cout << i;
    cout << endl;
}

void Main(){
	ll a, b;
	cin >> a >> b;
	if(a > 0) a--;
	
	// printv(bin(a));
	// printv(bin(b));
	
	// 0 から a までの XOR を求める　
	// mod 4 で a = 0 のとき a
	// a = 1 のとき 1
	// a = 2 のとき a + 1
	// a = 3 のとき 0
	
	auto f = [&](ll x){
	    switch(x%4){
	        case 0: return x; break;
	        case 1: return (ll)1; break;
	        case 2: return x+1; break;
	        case 3: return (ll)0; break;
	    }
	};
	
	// rep(i, 10) cout << f(i) << endl;
	// rep(i, 10) printv(bin(f(i)));
	
	// bin(f(a)) と bin(f(b)) の XOR を求める
	vi A = bin(f(a));
	vi B = bin(f(b));
	// printv(A);
	// printv(B);
	if(A.size() > B.size()) swap(A, B);
	rep(i, A.size()){
	    B[i] = B[i] ^ A[i];
	}
	
	// printv(A);
	ll ans = 0;
	ll p = 1;
	for(auto i : B){
	    ans += p * i;
	    p *= 2;
	}
    cout << ans << endl;
    return;
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);
static const int INF = 1e9+7;



int main(){
  int n;
  cin >> n;
  vector<int> p(n);
  REP(i,n) cin >> p[i];
  int cnt = 0;
  int min = p[0];
  REP(i,n){
    if(p[i] > min) continue;

    ++cnt;
    min = p[i];

  }

  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 4056
A,V=map(int,input().split())
B,W=map(int,input().split())
T=int(input())

if A<B:
  if A+V*T>=B+W*T:print('YES')
  else:print('NO')
else:
  if A-V*T<=B-W*T:print('YES')
  else:print('NO')




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

#define ll long long
#define mp make_pair
#define pb push_back

#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)

int n;
ll a[305];

void upd(ll &x, ll y) { if (y > x) x = y; }

ll solve(ll s, ll s0, ll a0) {
	string ss = bitset <60> (s).to_string();
	string ss0 = bitset <60> (s0).to_string();
	string sa0 = bitset <60> (a0).to_string();
	static ll dp[65][2][2];
	memset(dp, -0x3f, sizeof(dp));
	dp[0][0][0] = 0;
	rep(i, 60) rep(f0, 2) rep(f1, 2) if (dp[i][f0][f1] >= 0) {
		rep(c, 2) if (f0 || c <= sa0[i] - '0') {
			int c0 = (ss0[i] - '0') ^ c;
			rep(a, 2) if (f1 == ((c0 + c + a) >> 1 & 1) && ss[i] - '0' == ((c0 + c + a) & 1))
				upd(dp[i + 1][f0 | (c < sa0[i] - '0')][a], dp[i][f0][f1] | (1LL * c) << (60 - i - 1));
		}
	}
	return max(dp[60][0][0], dp[60][1][0]);
}

int main() {
	scanf("%d", &n);
	rep(i, n) scanf("%lld", &a[i]);
	ll s0 = 0;
	for (int i = 2; i < n; ++ i) s0 ^= a[i];
	ll s = a[0] + a[1];
	ll ans = solve(s, s0, a[0]);
	if (ans <= 0) puts("-1");
	else printf("%lld\n", a[0] - ans);
	return 0;
}


Measured memory_bytes: 3792
import sys
row = sys.stdin.readline


def read_int(row):
    return int(row().rstrip())

def read_string(row):
    return row().rstrip()

N = read_int(row)
S = read_string(row)

print("".join([chr((ord(i) + N - 26 if ord(i) + N > 90 else ord(i) + N)) for i in S]))

Measured memory_bytes: 3060
N,K = map(int, input().split())

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, 2*N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


if K >= N-1:
    ans = cmb(2*N-1, N, mod)
else:
    ans = 0
    for i in range(K+1):
        ans += cmb(N, K-i, mod)*cmb(N-1, K-i, mod)
        ans %= mod
print(ans)

Measured memory_bytes: 119020
fun main(args: Array<String>){
    val (n, k) = readLine()!!.split(" ").map { it.toInt() }
    val p = readLine()!!.split(" ").map { it.toInt() }

    val eSum = DoubleArray(n+1)
    for (i in 0 until n){
        eSum[i + 1] = eSum[i] + (p[i] + 1) / 2.0
    }
    var max = 0.0
    for (i in 0..n - k){
        max = Math.max(max, eSum[i+k] - eSum[i])
    }
    println(max)
}

Measured memory_bytes: 62088
import java.util.*;
public class Main {
  public static void main (String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int AC = 0, WA = 0, TLE = 0, RE = 0;
    for (int i=0; i<N; i++) {
        String num = sc.next();
    	switch (num) {
          case "AC": AC += 1;
            break;
          case "WA": WA += 1;
            break;
          case "TLE": TLE += 1;
            break;
          case "RE": RE += 1;
            break;
        }
    }
    int[] ans = {AC,WA,TLE,RE};
    String[] array = {"AC","WA","TLE","RE"};
    for (int i=0; i<4; i++) {
        System.out.println(array[i]+" x "+ans[i]);
    }
  }
}

Measured memory_bytes: 60344
def inp():
    return input()
def iinp():
    return int(input())
def inps():
    return input().split()
def miinps():
    return map(int,input().split())
def linps():
    return list(input().split())
def lmiinps():
    return list(map(int,input().split()))
def lmiinpsf(n):
    return [list(map(int,input().split()))for _ in range(n)]

s = inp()

if s == "RRR":
    print(3)
elif s == "SSS":
    print(0)
elif s == "RSS" or s == "SSR" or s == "RSR" or s == "SRS":
    print(1)
else:
    print(2)

Measured memory_bytes: 9088
#include<bits/stdc++.h>
#define ll long long int
#define loop(i,a,b) for(i=a;i<b;i++)
#define mod   998244353
#define INF 1000000000000
#define pb push_back
#define lim 500001
using namespace std;
int main()
{ll n,a,b,ans;

	cin>>n>>a>>b;
	if(abs(a-b)%2==0)
		ans=abs(a-b)/2;
	else
	{ll mx=max(a,b);
		ll mn=a+b-mx;
		ans=min(mn,n-mx+1)+(mx-mn-1)/2;
	}
	cout<<ans<<endl;return 0;}


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

using namespace std;

struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
    Node(int x)
    {
        data=x;
        left=NULL;
        right=NULL;
    }
};
#define Node struct Node

ll modpow(ll a, ll n)
{
    ll m=1e9+7;
    if(n==0)
        return 1;
    ll y=modpow(a,n/2)%m;
    if(n%2==0)
        return (y*y)%m;
    return (((y*y)%m)*a)%m;
}
ll dp[2005];
ll pro(ll s)
{
    ll m=1e9+7;
    if(s==0)
        return 1;
    if(dp[s]!=-1)
        return dp[s];
    ll ans=0;
    for(ll i=3;i<=s;i++)
    {
        ans+=pro(s-i);
        ans=ans%m;
    }
    return dp[s]=ans;
}

int main()
{
    int t=1;
    //cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        memset(dp,-1,sizeof(dp));
        cout<<pro(n)<<endl;
    }
    return 0;
}







Measured memory_bytes: 3564
//int a = stoi(c); 文字列をintへ
//小文字から大文字
//transform(a.begin(), a.end(), a.begin(), ::toupper);
//途中の出力をそのまま残さない
//数値計算 個数以外はdouble
//map<キー,値> p は辞書。p[キー] = 値
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//絶対値 abs()
//入力は空白で切れる
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//while(N)で回すとき、Nはコピーを作っておく
//小文字に対応する文字コード：S[i] - 'a'
//文字コード→小文字：(char)(数字+'a')
//グラフの距離:隣接行列で扱う
//等価なものに変換する思考
//bool型　初期値はTrue
//島渡りの問題：中間ノードに着目
//配列はvector<>を使う：意味わからないエラーがなくなる。
//背反な事象にちゃんとわける
//チェックリストはマップを使う
//数が大きい時の比較はstring型で行う
//全て0になったか調べたい->0になるたびにcntする
//またはかかつか
//例外処理は最初にする
//x = p^m + q^n...の約数の個数:(n+1)*(m+1)....
//N!のどの素因数で何回割れるか
//⇔1~Nまでの数がそれぞれどの素因数で何回割り切れるかの和
//パズルの問題->一般化して全探索
//数が大きい時のせぐふぉはコードテストで試してみる
//スペルミスに注意
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
	using namespace std;

//円周率
const double PI = 3.14159265358979323846;
//割るやつ
const ll M = (pow(10, 9) + 7);

// K進数でのNの桁数
ll dig(ll N, ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// a,bの最大公約数
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;
}

//nC2の計算
ll C(ll N) {
	return N * (N - 1) / 2;
}

//階乗計算
ll f(ll n) {
	if (n == 0 || n == 1) return 1;
	else return (n * f(n - 1)) % M;
}

//Nをdで何回割れるか
ll divcnt(ll N, ll d) {
	ll ans = 0;
	while (1) {
		if (N%d == 0) {
			ans++;
			N /= d;
		}
		else break;
	}

	return ans;
}

//素数判定
bool prime(ll num) {
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false;
	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2) {
		if (num % i == 0) return false;
	}
	return true;
}

//フィボナッチ数列
vector<ll> memo(pow(10, 6) + 1);
ll fibo(ll n) {
	if (n == 1) return 1;
	else if (n == 2) return 1;
	else if (memo[n] != 0) return memo[n];
	else return memo[n] = fibo(n - 1) + f(n - 2);
}

int main() {
	ll K; cin >> K;
	ll ans = 0;
	for (int a = 1; a <= K; a++) {
		for (int b = 1; b <= K; b++) {
			for (int c = 1; c <= K; c++) {
				ans += gcd(a, gcd(b, c));
			}
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 10976
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
int main() {
    // ifstream in("data1.txt");
    // cin.rdbuf(in.rdbuf());
    string S, T;
    cin >> S >> T;
    int ans = 0;
    if(S[0] == T[0]) {
        ans++;
    }

    if(S[1] == T[1]) {
        ans++;
    }

    if(S[2] == T[2]) {
        ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
ll powmod(ll n, ll k, ll m) {
ll r=1;
 for(; k>0; k >>=1) {
   if(k&1) r=(r*n)%m;
   n=(n*n)%m;
 }
  return r;
}

ll fact(ll n) {
ll a=1;
rep(i,n) {
a=a*(n-i);
}
return a;
}

ll pow(ll a, ll b) {
ll x=1;
rep(i,b) {
x=x*a;
}
return x;
}

long double dist(ll a, ll b, ll c, ll d) {
 double e=((a-c)*(a-c))+((b-d)*(b-d));
 double f=sqrt(e);
  CST(9);
  return f;
}
ll P[10]={1,2,3,4,5,6,7,8,9,10};
  

int main() {




 ll N;
  cin >>N;
  vl X(N);
  vl Y(N);
  rep(i,N) {
cin >>X.at(i)>>Y.at(i);
  }

double sum=0;
  do{
    
    rep(i,N-1) {
    double a=dist(X.at(P[i]-1), Y.at(P[i]-1),X.at(P[i+1]-1), Y.at(P[i+1]-1));
     sum+=a;
    //cout<<a<<endl;
    }
    
    
  }
  while (next_permutation(P,P+N));
  
    long double finale=(long double)sum/(long double)fact(N);
    CST(9);
  cout<<finale<<endl;
 
}
  
  

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

int a[111111];
int main() {
    int n;
    cin >> n;
    for(int x = 1; x < 101; x++)
        for(int y = 1; y < 101; y++)
            for(int z = 1; z < 101; z++)
                a[x * (x + y + z) + y * (y + z) + z * z]++;
    for(int i = 0; i < n; i++)
        cout << a[i + 1] << '\n';
    return 0;
}


Measured memory_bytes: 3796
/*
sonu_verma1
*/
#include <bits/stdc++.h>
// For policy based data structure
/*#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> */
using namespace std;
/*using namespace __gnu_pbds; 
typedef tree<int, null_type, less<int>, rb_tree_tag, 
             tree_order_statistics_node_update> 
    new_data_set;*/
 
#define MD 1000000007
#define X first
#define Y second
#define pb push_back
#define debug(val, ch) cout <<val <<ch
#define FOR(i, st, en, ch) for(register int i = (st); i <= (en) ; i += (ch))
#define RFOR(i, st, en, ch) for(register int i = (st); i >= (en) ; i -= (ch))
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
 
typedef long long int ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<int, bool> pib;
typedef pair<bool, int> pbi;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
/*********************************************************************/
void test(int r)
{
    int n;
    cin>>n;
    int f=0,cn=1,rm=7;
    map<int,int>mp;
    while(rm)
    {
        if(mp.find(rm)!=mp.end())
        {
            f=1;
            break;
        }
        mp[rm]=1;
        while(rm<n)
        {
            rm=rm*10+7;
            cn++;
        }
        rm=rm%n;

    }
    if(f==1)
        cout<<-1<<endl;
    else
        cout<<cn<<endl;

}
/***********************************************************************/
int main()
{
    fast();
    int t=1,r;
    // cin>>t;
    for(r=1;r<=t;r++)
        test(r);
    return 0;
}

Measured memory_bytes: 45760
#include<cstdio>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;

int wrong[100][100];

int main(void) {
    while(true) {
        int M,T,P,R;
        scanf("%d%d%d%d", &M, &T, &P, &R);
        if(!M) break;

        vector<pair<pair<int,int>,int> > pt(T); // solved, -time, tid

        memset(wrong, 0, sizeof(wrong));
        for(int i=0; i<T; i++) {
            pt[i].second = i+1;
        }
        for(int i=0; i<R; i++) {
            int m,t,p,j;
            scanf("%d%d%d%d", &m,&t,&p,&j);
            if(!j) { // success
                pt[t-1].first.first++;
                pt[t-1].first.second -= m;
                pt[t-1].first.second -= 20*wrong[t-1][p-1];
            } else { // fail
                wrong[t-1][p-1]++;
            }
        }

        sort(pt.begin(), pt.end());
        reverse(pt.begin(), pt.end());

        pair<int,int> last = pt[0].first;
        printf("%d", pt[0].second);
        for(int i=1; i<pt.size(); i++) {
            if(pt[i].first == last)
                printf("=");
            else
                printf(",");
            printf("%d", pt[i].second);
            last = pt[i].first;
        }
        printf("\n");

    }
    return 0;
}

Measured memory_bytes: 1084
#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;

#define ordered_set tree<long long, null_type,less<long long>, rb_tree_tag,tree_order_statistics_node_update>
//s.find_by_order(index) returns iterator to the index-th element
//in O(logn) time.



typedef unsigned long long ull;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vii;
typedef vector<string> vss;
typedef vector<pair<ll, ll> > vpll;
typedef unordered_map<ll ,ll> mpll;
typedef unordered_map<int ,int> mpii;
typedef unordered_map<char ,ll> mpcl;
typedef pair<ll , ll> pll;
typedef complex<double> cd;
typedef vector< complex<double> > vcd;


#define fore(i,n) for(i=0;i<n;i++)
#define forz(i,s,f) for(i=s;i<f;i++)
#define forer(i,n) for(i=n-1;i>=0;i--)
#define forzr(i,s,f) for(i=s;i>=f;i--)
#define mkp make_pair
#define pb push_back
#define eb emplace_back
#define ub upper_bound
#define lb lower_bound
#define ff first
#define ss second
#define pvec(i,vec) fore(i,vec.size())cout<<vec[i]<<" ";cout<<"\n";

const ll mod=1e9+7;
const ll modulo=998244353;
const double pi = 3.14159265358979323846;


ll power(ll x,ll y,ll m)//gives (x^y)%m
{
    ll ans=1;
    while (y>0)
    {
        if(y & 1)
        {
            ans=(ans*x)%m;
        }
        y=y/2;
        x=(x*x)%m;
    }
    return ans;
}

bool sortbysec(pll &a,pll &b)
{
    return(a.ss<b.ss);
}

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

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

long double logn(long double a,long double n)
{
	return(log(n)/log(a));
}

int Remainder(string str, int R) 
{ 
    // len is variable to store the 
    // length of Number string. 
    int len = str.length(); 
  
    int Num, Rem = 0;
  
    // loop that find Remainder 
    for (int i = 0; i < len; i++) { 
  
        Num = Rem * 2 + (str[i] - '0'); 
        Rem = Num % R; 
    } 
  
    // Return the remainder 
    return Rem; 
}

int main(int argc, char const *argv[])
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);
    
	ll te=1,test,i,j,n,m,flag,k,p,temp;
	//cin>>te;
	for(test=1;test<=te;test++)
	{
		cin>>n;
		string s;
		cin>>s;

		temp=0;
		fore(i,n)
		{
			if(s[i]=='1')
				temp++;
		}

		ll plus,minus;
		plus=Remainder(s,temp+1);
		if(temp>1)
			minus=Remainder(s,temp-1);
		vll ans(n);
		fore(i,n)
		{
			if(s[i]=='1')
			{
				if(temp==1)
				{
					ans[i]=0;
				}
				else
				{
					flag=(minus-power(2,(n-i-1),(temp-1))+(temp-1))%(temp-1);
					ans[i]=1;
					while(flag>0)
					{
						p=__builtin_popcount(flag);
						flag=flag%p;
						ans[i]++;
					}
				}
			}
			else
			{
				flag=(plus+power(2,(n-i-1),(temp+1)))%(temp+1);
				ans[i]=1;
				while(flag>0)
				{
					p=__builtin_popcount(flag);
					flag=flag%p;
					ans[i]++;
				}
			}
		}

		fore(i,n)
		{
			cout<<ans[i]<<"\n";
		}
		/*vll a(n);
		fore(i,n)
		{
			cin>>a[i];
		}*/
		
		//cout<<"hello\n";
		//cout<<"Case #"<<test<<": ";
	}

	return 0;
}

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

int main() {
	
	int a, b, c, k; cin >> a >> b >> c >> k;
	int ans = 0;
	if (k <= a) {
		ans = k;
	}
	else if (k < a && k <= a + b) {
		ans = a;
	}
	else {
		ans = a - (k - (a + b));
	}

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

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


//N以下でDで割れない個数
long long func(long long N,long long D){
  return N-(N/D);
}

long long lcm(long long x, long long y){
  long long m=x*y;
  
  long long g=x%y;
  while(g>0){
    x=y;
    y=g;
    g=x%y;
  }
  return m/y;
}

int main(){
  long long A,B,C,D;
  cin >> A >> B >> C >> D;
  cout << func(B,C)+func(B,D)-func(B,lcm(C,D))
    -func(A-1,C)-func(A-1,D)+func(A-1,lcm(C,D)) << endl;
}

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

ll A[101010],B[101010];
int N;
ll K;

ll solve(int ind,int bit){
  for(int i=bit+1;i<31;i++){
    if(((K>>i)&1)==0 && ((A[ind]>>i)&1)==1) return 0;
  }
  return B[ind];
}

int main(){
  cin>>N>>K;
  rep(i,N) cin>>A[i]>>B[i];
  ll ans=0;
  rep(i,N){
    bool flag=1;
    rep(j,31) if(((A[i]>>j)&1)==1 && ((K>>j)&1)==0){
      flag=0;
      break;
    }
    if(flag) ans+=B[i];
  }
  rep(i,31) if((K>>i)&1){
    ll tmp=0;
    rep(j,N) if(((A[j]>>i)&1)==0){
      tmp+=solve(j,i);
    }
    ans=max(ans,tmp);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long int n,i,j,k;
  cin>>n;
  long long int a[n][3],d[n][3];
  for(i=0;i<n;i++)
  {
    for(j=0;j<3;j++)
      cin>>a[i][j];
  }
  d[0][0]=a[0][0];
  d[0][1]=a[0][1];
  d[0][2]=a[0][2];
  for(i=1;i<n;i++)
  {
    d[i][0]=max(d[i-1][1]+a[i][0],d[i-1][2]+a[i][0]);
    d[i][1]=max(d[i-1][0]+a[i][1],d[i-1][2]+a[i][1]);
    d[i][2]=max(d[i-1][1]+a[i][2],d[i-1][0]+a[i][2]);
  }
  cout<<max(d[n-1][0],max(d[n-1][1],d[n-1][2]));
}

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

int main(){
    unsigned long N;
    cin >> N;
    vector<unsigned long> L;
    L.reserve(N);
    copy_n(istream_iterator<unsigned long>(cin), N, back_inserter(L));
    sort(L.begin(), L.end());
    unsigned long ans{0};
    for(unsigned long i = 2; i < N; ++i)for(unsigned long j = 1; j < i; ++j)for(unsigned long k = 0, c = L[i] - L[j]; k < j; ++k)ans += (c < L[k]);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main(){
	int N,a=0,b=0;
	string S;
	cin>>N>>S;
 
	for(int i=0;i<N;i++){
		if(S.at(i)=='#')
			a++;
		else if(S.at(i)=='.'&&a>0){
			b++;
			a--;
		}
	}
	cout<<b<<endl;
}


Measured memory_bytes: 640
n = int(input())
h = tuple(int(i) for i in input().split())
x, y = 0, abs(h[0]-h[1])
for i in range(2, n):
    v = min(x+abs(h[i-2]-h[i]), y+abs(h[i-1]-h[i]))
    x, y = y, v
print(y)

Measured memory_bytes: 14236
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <stack>
#include <climits>
#include <map>
#include <set>

using namespace std;

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

const ll mod = 1000000007;
const int inf = 1e9;
const long long INF = 1LL << 60;   // INFの値は1152921504606846976

int main()
{
    ll n,m;cin >> n >> m;
    vector<ll> v[100005];
    priority_queue<ll > pq;
    for(int i = 0; i < n; i++){
        ll a,b;
        cin >> a >> b;
        v[a].push_back(b);
    }
    ll ans = 0;
    for(int i = 1; i <= m; i++){
        for(int j = 0; j < v[i].size(); j++){
            if(j + i)
            pq.push(v[i][j]);
        }
        if(!pq.empty()){
            ans += pq.top(); 
            pq.pop();
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 5632
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n; cin>>n;
    vector <int> h(n);
    int ans=1;
    for(int i=0;i<n;i++){
        cin>>h[i];
    }
    
    for(int i=1;i<n;i++){
        bool can=true;
        for(int j=0;j<=i-1;j++){
            if(h[i]<h[j]) can=false;
        }
        if(can) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;


int main(){
  int a,b;
  string s;
  while(true){
    cin >> a >> s >> b;
    if(s == "?")break;
    else {
      if(s=="+"){
        cout << a+b << endl;
      }
      else if(s=="/"){
        cout << a/b<< endl;
      }
      else if(s=="-"){
        cout << a-b<<endl;
      }
      else if(s=="*"){
        cout <<a*b<<endl;
      }
    }
  }
  return 0;
}


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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// // assign avl ncm dijkstra geo2 kruskal graph uf lca BIT
// matrix dinic next_combination topcoder lcm vi st gin
// cusum segtree

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

    Int(n);
    vector<int> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }
    
    vb used(n, false);
    rep(i, n) {
        if (data[i] == 2) {
            used[i] = true;
        }
    }

    int cnt = 0;
    vi yui(2, 0);
    rep(i, n) {
        if (data[i] == -1) {
            yui[0]++;
        } else if (data[i] == -2) {
            yui[1]++;
        }
    }

    if ((yui[0] + yui[1]) % 2 == 0) {
        cnt = 0;
        rep(i, n) {
            if (data[i] == -2) {
                cnt++;
                used[i] = true;
            }
        }
        if (cnt % 2) {
            rep(i, n) {
                if (data[i] == -1) {
                    used[i] = true;
                    break;
                }
            }
        }
    } else if (yui[1] % 2 == 0) {
        rep(i, n) {
            if (data[i] == -2) {
                cnt++;
                used[i] = true;
            }
        }
    } else if (yui[0] && yui[1]) {
        rep(i, n) {
            if (data[i] == -2) {
                cnt++;
                used[i] = true;
            }
        }
        if (cnt % 2) {
            rep(i, n) {
                if (data[i] == -1) {
                    used[i] = true;
                    break;
                }
            }
        }
    } else if (yui[1]) {
        rep(i, n) {
            if (data[i] == -2) {
                cnt++;
                used[i] = true;
            }
        }
        for (int i = n-1; i >= 0; i--) {
            if (data[i] == -2) {
                used[i] = false;
                break;
            }
        }
    }

    cnt = 0;
    rep(i, n) cnt += used[i];

    cout << cnt << endl;
    rep(i, n) {
        if (used[i]) {
            cout << i+1 << endl;
        }
    }

    return 0;
}



Measured memory_bytes: 3224
#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
#include<map>

using namespace std;
#define REP(i, n) for(int i=0;i<(int)n;i++)
const int INF = (1<<29);

int n, m;

template<typename T>
struct Serializer{
	map<T, int> enc;
	vector<T> dec;
	int operator()(const T &t){
		auto it = enc.find(t);
		if(it != enc.end()) return it->second;
		dec.push_back(t);
		return enc[t] = dec.size() - 1;
	}
	size_t size(){
		return dec.size();
	}
};

int g[201][201], g2[201][201];

int main(){
	while(cin >> n, n){
		Serializer<string> se;
		REP(i, 200)REP(j, 200)
			g[i][j] = g2[i][j] = i == j ? 0 : INF;
		REP(i, n){
			string s;
			cin >> s;
			int p = s.find('-');
			int u = se(s.substr(0, p));
			int v = se(s.substr(p+1));
			g[u][v] = 1;
		}
		n = se.size();
		REP(i, n)REP(j, i){
			int f = 0;
			REP(k, n){
				if(g[i][k] == 1 && g[k][j] == 1 || g[j][k] == 1 && g[k][i] == 1){
					f = 0; break;
				}
				if(g[i][k] == 1 && g[j][k] == 1 || g[k][i] == 1 && g[k][j] == 1)
					f = 1;
			}
			if(f){
				if(g[i][j] == INF) g[i][j] = 0;
				if(g[j][i] == INF) g[j][i] = 0;
			}
		}
		REP(k, n)REP(i, n)REP(j, n) g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
		cout << n << endl;
		cin >> m;
		REP(i, m){
			string s;
			cin >> s;
			int p = s.find('-');
			int u = se(s.substr(0, p));
			int v = se(s.substr(p+1));
			if(g[u][v] & 1) puts("YES");
			else puts("NO");
		}
	}
	return 0;
}

Measured memory_bytes: 1568
#include <stdio.h>
int main(){
	int i, n, money = 100000;
	scanf("%d", &n);
	while(n--){
		money *= 1.05;
		money += 999;
		money /= 1000;
		money *= 1000;
	}
	
	printf("%d\n", money);
	
	return 0;
}

Measured memory_bytes: 592
//Program.cpp
//Author : Aaryan Srivastava 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#define pb push_back
#define popb pop_back
#define ull unsigned long long  
#define beg begin
#define mp make_pair
#define pii pair<int, int>
#define piii pair<pii,int>
#define rep(i,n) for(int (i) = 0 ; i < (n) ; i++)
#define repA(i,x,y) for(int i = (x) ; i <= (y) ; i++)
#define repD(i,x,y) for(int i = (x) ; i >= (y) ; i--)
#define all(c) (c).begin(),(c).end()
#define ff first
#define ss second 
#define fill(a,val) memset(a,val,sizeof(a))
#define Randomize mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
using ll = long long;
#define int ll
const int N = 2*1e5 +5 ;
const int mod = 1e9 + 7 ;
const int inf = 1e18 ;
const int SZ = 101 ;
const double eps = 1e-9 ;
using namespace std;
#ifdef AaryanS
#define mycout cout
#define mycerr cerr 
#endif

#ifndef AaryanS
#define mycout if(false) cout
#define mycerr if(false) cerr
#define AaryanS 0 
#endif

void solve()
{
	int n;
	cin >> n;
	vector<int> a;
	a.resize(n);
	for(auto &it : a) cin >> it ;
	int dp[n][n][2] = {} ;
	for(int i = 0 ; i < n ; ++i) 
		dp[i][i][0] = a[i], dp[i][i][1] = -a[i]; 
	
	for(int k = 2 ; k <= n;  ++k){	
		for(int l = 0 ; l + k - 1 < n ; ++l){
			int r = l + k - 1 ;
			dp[l][r][0] = max(dp[l+1][r][1] + a[l], dp[l][r-1][1] + a[r]); 			
			dp[l][r][1] = min(dp[l+1][r][0] - a[l], dp[l][r-1][0] - a[r]); 
		}
	}
	cout << dp[0][n-1][0] ;
}

     
int32_t main(int32_t argc, char *argv[])
{
    double t1 = clock() ;
    ios::sync_with_stdio(0);    
    cin.tie(0); cout.tie(0);
    int TC = 1, t = 0;
    //cin >> TC ;
    while(t++ < TC)
    {
        //cout << "Case " << t << ":\n" ;
        solve();
    }
    mycerr << "Time : " << 1000 *(clock() - t1)/CLOCKS_PER_SEC << " ms\n" ;
    return 0;
}


Measured memory_bytes: 140928
import itertools


def main():
    n = input()
    print(sev(n))


def sev(n: str) -> int:
    ret = 0
    d = len(n)
    while d > 2:
        for comb in itertools.product(['3', '5', '7'], repeat=d):
            s = ''.join(comb)
            if '3' in s and '5' in s and '7' in s and int(s) <= int(n):
                ret += 1
        d -= 1
    return ret


if __name__ == '__main__':
    main()


Measured memory_bytes: 9188
H,W = map(int,input().split())
a = list()
#入力
for i in range(H):
	a_line = list(input())
	a.append(a_line)

ans = list()
#全部白の行を削除
for line in a:
	if {'#'} <= set(line):
		ans.append(line)

column_list = list()
# 列
for column in range(len(ans[0])):
	count = 0
	# 行
	for line in ans:
		if line[column] == '.':
			count += 1
		else:
			count = 0
			break
	if count == len(ans):
		column_list.append(column)

column_list.sort(reverse=True)

for line_num in range(len(ans)):
	for pop_column in column_list:
		ans[line_num].pop(pop_column)

for line in ans:
	print(''.join(line))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(x)    (x).begin(),(x).end()
typedef long long ll;
const int MOD = (int)1e9 + 7;

int main(){
  int n,i;
  cin >> n >> i;
  cout << n-i+1 << endl;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <unordered_map>
#define maxn 100005
#define mod 1000000007
using namespace std;
typedef long long LL;
int t,n,m,ans;
char a[maxn];
int main()
{
    scanf("%d",&t);getchar();
    scanf("%s",a);
    if(t%2==1) {printf("No");return 0;}
    int len=strlen(a);
    for(int i=0;i<len/2;i++)
    {
        if(a[i]!=a[i+len/2]) {printf("No");return 0;}
    }
    printf("Yes");
    //while(t--)
    //{
    //scanf("%d%d",&n,&m);

    //printf("%d",ans);
    //}
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
#include<typeinfo>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef set<int> S;
#define rep(i, n) for(int i=0; i<n; i++)
const ll MOD=1e9+7;

int main(){

  string s, t;
  cin >> s >> t;
  int cnt=0;
  for(int i=0; i<3; i++){
    if(s[i]==t[i]){
      cnt++;
    }
  }
  cout << cnt << endl;

	return 0;
}

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

#define sz(x) int(x.size())
#define pii pair<int, int>
#define Task "abc"
#define For(i, a, b) for(int i = (a), _b = (b); i <= b; ++i)
#define Debug(X) cout << #X << " = " << X << '\n'
#define All(x) (x).begin(), (x).end()
#define mp make_pair

typedef unsigned long long ull;
typedef long long ll;

const int maxn = 2e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
//  freopen(Task".inp", "r", stdin);  freopen(Task".out", "w", stdout);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  ll ans = 0;
  sort(All(a), greater<int>());
  for (int i = k; i < n; ++i) ans += a[i];
  cout << ans;

}




Measured memory_bytes: 1024
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long r = sc.nextLong();
		long g = sc.nextLong();
		long b = sc.nextLong();
		System.out.println((g * 10 + b) % 4 == 0 ? "YES" : "NO");
	}
}

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

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

	string s;
	cin >> s;

	int a = -1, z = 0;
	for(int i = 0; i < s.size(); i++) {
		if(a == -1 && s[i] == 'A') a = i;
		if(s[i] == 'Z') z = i;
	}

	cout << z - a + 1 << endl;
}

Measured memory_bytes: 720
import itertools
import math

N = int(input())
x_list = [0] * N
y_list = [0] * N
for i in range(N):
    x_list[i], y_list[i] = map(int, input().split())
l_sum = 0
l = 0
for comb in itertools.combinations(range(N), 2):
    l = (
        (x_list[comb[0]] - x_list[comb[1]]) ** 2
        + (y_list[comb[0]] - y_list[comb[1]]) ** 2
    ) ** 0.5
    l_sum += l
ans = 2 * l_sum / N
print(ans)

Measured memory_bytes: 9372
#include<stdio.h>

int main(void) {
int i,j;
int n;
int ans[4][13] = {0};
char x;
int y;

scanf("%d", &n);

for (i = 0; i < 2*n; i++) {
scanf("%c %d", &x, &y);
if (x == 'S') ans[0][y-1] = 1;
else if (x == 'H') ans[1][y-1] = 1;
else if (x == 'C') ans[2][y-1] = 1;
else if (x == 'D') ans[3][y-1] = 1;
}

for (i = 0; i < 4; i++) {
for (j = 0; j < 13; j++) {
if (ans[i][j] == 0) {
if (i == 0) printf("%c %d\n", 'S', j+1);
else if (i == 1) printf("%c %d\n", 'H', j+1);
else if (i == 2) printf("%c %d\n", 'C', j+1);
else if (i == 3) printf("%c %d\n", 'D', j+1);
}
}
}

return (0);
}

Measured memory_bytes: 596
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <math.h> // sqrt
using namespace std;
typedef long long ll;

int main() {
    int A, B, C, X;
    cin >> A >> B >> C >> X;
    int ans = 0;
    int sum = 0;
    for (int i = 0; i <= A; i++) {
        for (int j = 0; j <= B; j++) {
            for (int k = 0; k <= C; k++) {
                sum = 500 * i + 100 * j + 50 * k;
                if (sum == X) {
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3540
import java.util.Scanner;

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

        int n = sc.nextInt();

        int i = 1;

        while (true) {
            int x = i;
            if (x % 3 == 0) {
                System.out.print(" " + i);
            } else {
                while (true) {
                    if (x % 10 == 3) {
                        System.out.print(" " + i);
                        break;
                    }
                    x /= 10;
                    if (x == 0) {
                        break;
                    }
                }
            }
            if (++i > n) {
                break;
            }
        }
        sc.close();
        System.out.println("");
    }
}



Measured memory_bytes: 28616
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e9;
const ll INF = 1e18;
const ld EPS = 1e-10;

int main(){
    int N, M;
    cin >> N >> M;
    int l[M], r[M], x[M];
    priority_queue<pii, vector<pii>, greater<pii> > que;
    rep(i, M){
        cin >> l[i] >> r[i] >> x[i];
        l[i]--, r[i]--;
        que.push(pii(r[i], i));
    }
    //dp[i][j][k]:=k個目まで並べて[0,i)が3つ、[i,j)が2つ、[j,k)が3つとなる並べ方
    int dp[N+1][N+1][N+1];
    rep(i, N+1) rep(j, N+1) rep(k, N+1) dp[i][j][k] = 0;
    dp[0][0][0] = 1;
    rep(k, N){
        rep(i, N+1) rep(j, N+1){
            dp[i][j][k+1] += dp[i][j][k], dp[i][j][k+1] %= MOD;
            dp[i][k][k+1] += dp[i][j][k], dp[i][k][k+1] %= MOD;
            dp[j][k][k+1] += dp[i][j][k], dp[j][k][k+1] %= MOD;
        }
        while(!que.empty() && que.top().first == k){
            pii p = que.top();
            que.pop();
            int a = p.second;
            rep(i, N+1) rep(j, N+1){
                if(x[a] == 1 && (l[a] < j || l[a] >= k+1)) dp[i][j][k+1] = 0;
                if(x[a] == 2 && (l[a] < i || l[a] >= j)) dp[i][j][k+1] = 0;
                if(x[a] == 3 && (l[a] < 0 || l[a] >= i)) dp[i][j][k+1] = 0;
            }
        }
    }
    int ans = 0;
    rep(i, N+1) rep(j, N+1){
        ans += dp[i][j][N], ans %= MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 106752
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
inline int read(){
	int v=0,f=1;
	char c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9'){
		v=v*10+c-'0';
		c=getchar();
	}
	return v*f;
}
const int Maxn=100005;
const LL mod=998244353;
int n,m1,m2,m3;
int F1[Maxn],F2[Maxn],F3[Maxn];
int cnt[Maxn];
LL w[Maxn],S1[1024],S2[1024],S3[1024];
LL dp[1024],ndp[1024];
vector<int> G1[Maxn],G2[Maxn],G3[Maxn];
void Add(LL &x,LL y){
	x+=y;
	if (x>=mod) x-=mod;
}
int main(){
	scanf("%d",&n);
	scanf("%d",&m1);
	for (int i=0;i<m1;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		G1[u].pb(v);G1[v].pb(u);
	}
	for (int i=1;i<=n;i++) F1[i]=F2[i]=F3[i]=0;
	for (int i=n;i>=1;i--){
		for (int j=0;j<G1[i].size();j++){
			int v=G1[i][j];
			if (v>i) cnt[F1[v]]++;
		}
		int t=0;
		while (cnt[t]) t++;
		F1[i]=t;
		for (int j=0;j<G1[i].size();j++){
			int v=G1[i][j];
			if (v>i) cnt[F1[v]]--;
		}
	}
	scanf("%d",&m2);
	for (int i=0;i<m2;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		G2[u].pb(v);G2[v].pb(u);
	}
	for (int i=n;i>=1;i--){
		for (int j=0;j<G2[i].size();j++){
			int v=G2[i][j];
			if (v>i) cnt[F2[v]]++;
		}
		int t=0;
		while (cnt[t]) t++;
		F2[i]=t;
		for (int j=0;j<G2[i].size();j++){
			int v=G2[i][j];
			if (v>i) cnt[F2[v]]--;
		}
	}
	
	scanf("%d",&m3);
	for (int i=0;i<m3;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		G3[u].pb(v);G3[v].pb(u);
	}
	for (int i=n;i>=1;i--){
		for (int j=0;j<G3[i].size();j++){
			int v=G3[i][j];
			if (v>i) cnt[F3[v]]++;
		}
		int t=0;
		while (cnt[t]) t++;
		F3[i]=t;
		for (int j=0;j<G3[i].size();j++){
			int v=G3[i][j];
			if (v>i) cnt[F3[v]]--;
		}
	}
	
	LL tmp=1e18;
	tmp%=mod;
	w[0]=1;
	for (int i=1;i<=n;i++){
		w[i]=w[i-1]*tmp%mod;
	}
	for (int i=1;i<=n;i++){
		Add(S1[F1[i]],w[i]);
		Add(S2[F2[i]],w[i]);
		Add(S3[F3[i]],w[i]);
	}
	dp[0]=1;
	memset(ndp,0,sizeof(ndp));
	for (int i=0;i<1024;i++){
		for (int j=0;j<1024;j++){
			Add(ndp[i^j],1ll*dp[i]*S1[j]%mod);
		}
	} 
	for (int i=0;i<1024;i++) dp[i]=ndp[i];
	
	
	memset(ndp,0,sizeof(ndp));
	for (int i=0;i<1024;i++){
		for (int j=0;j<1024;j++){
			Add(ndp[i^j],1ll*dp[i]*S2[j]%mod);
		}
	} 
	for (int i=0;i<1024;i++) dp[i]=ndp[i];
	
	memset(ndp,0,sizeof(ndp));
	for (int i=0;i<1024;i++){
		for (int j=0;j<1024;j++){
			Add(ndp[i^j],1ll*dp[i]*S3[j]%mod);
		}
	} 
	for (int i=0;i<1024;i++) dp[i]=ndp[i];
	printf("%lld\n",dp[0]);
}

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

int mod = 1'000'000'007;

int main(){
    int n, m;
    cin >> n >> m;
    vector<bool> check(n+1, true);
    int x;
    for (int i = 0; i< m; i++){
        cin >> x;
        check[x] = false;
    }
    vector<long long> ans(n+1, 0);
    ans[0] = 1;
    if (check[1]) ans[1] = 1;
    for (int i = 2; i <= n; i++){
        if (check[i]) ans[i] += ans[i-1] + ans[i-2];
        ans[i] %= mod;
    }
    cout << ans[n] % mod << endl;
}

Measured memory_bytes: 1024
# エラトステネスの篩
import math
def Eratosthenes(n):
    if n < 2:
        return None
    prime = [2]
    limit = math.ceil(n**0.5)
    data = list(range(3, n+1, 2))
    p = -1
    while p < limit:
        p = data[0]
        prime.append(p)
        data = [d for d in data if d%p != 0]
    return prime + data

q = int(input())
L, R = [], []
for _ in range(q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

r_max = max(R)

# r_maxまでの素数を記録する
memo1 = [0]*(r_max+1)
primes = Eratosthenes(r_max)
for p in primes:
    memo1[p] = 1

# r_maxまでの2017に似た数を記録する
memo2 = [0]*(r_max+1)
for p in primes:
    if (p+1)%2 == 0:
        if memo1[(p+1)//2] == 1:
            memo2[p] = 1
            
# 2017に似た数の累積和
import itertools
accum = list(itertools.accumulate(memo2))

# 出力
for i in range(q):
    print(accum[R[i]] - accum[L[i]-1])

Measured memory_bytes: 67544
using System.Linq;
using System;


public class hello
{
    public static void Main()
    {
        string line;
        for (; (line = Console.ReadLine()) != null;)
        {
            string[] s = line.Trim().Split(' ');
            var chk = Array.ConvertAll(s, int.Parse);
            if (chk.Any(x => x == -1)) break;
            var y1 = chk[0];
            var m1 = chk[1];
            var d1 = chk[2];
            var y2 = chk[3];
            var m2 = chk[4];
            var d2 = chk[5];
            var ans = new DateTime(y2, m2, d2, 0, 0, 0) - new DateTime(y1, m1, d1, 0, 0, 0);
            Console.WriteLine(ans.Days);
        }
    }
}

Measured memory_bytes: 9560
import numpy as np
c = [list(map(int, input().split())) for i in range(3)]
C = np.array(c)
check = np.zeros((3, 3))

for i in range(min(c[0])+1):
    check[0] = C[0] - i
    for j in range(min(c[1])+1):
        check[1] = C[1] - j
        for k in range(min(c[2])+1):
            check[2] = C[2] - k
            if list(check[0]) == list(check[1]) and list(check[0]) == list(check[2]):
                print("Yes")
                exit()

print("No")


Measured memory_bytes: 27092
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define pb push_back
#define pii pair<int64_t,int64_t>
#define mp make_pair
#define whole(v) begin(v),end(v)
#define print(c,n) for(int64_t i=0;i<n;i++) cout << c[i] << " ";
#define MOD 1000000007
void solve(){
	int n,m;
	cin >> n >> m;
	int dp[n+1];
	memset(dp,-1,sizeof(dp));
	dp[0]=dp[1]=1;
	for(int i=0;i<m;i++){
		int temp;
		cin >> temp;
		dp[temp] = 0;
	}
	for(int i=2;i<=n;i++){
		if(dp[i]!=0){
			dp[i] = (dp[i-1]+dp[i-2])%MOD;
		}
	}
	cout << dp[n];
}
int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);
	solve();
}

Measured memory_bytes: 640
def main():
    N=int(input())
    a_list=input()

    r=0
    g=0
    b=0
    s=0
    for i,a in enumerate(a_list):
        if a=="R":
            r+=1
            s+=g*b
        elif a=="G":
            g+=1
            s+=r*b
        elif a=="B":
            b+=1
            s+=r*g
    
    for i in range(1,N):
        for j in range(N):
            if j+2*i>=N:
                break

            s1=a_list[j]
            s2=a_list[j+i]
            s3=a_list[j+i*2]
            if s1!=s2:
                if s2!=s3:
                    if s1!=s3:
                        s-=1
    
    print(s)




if __name__ =='__main__': 
    main()

Measured memory_bytes: 68388
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        int a = int.Parse(Console.ReadLine());
        string b = Console.ReadLine();
        string ans = (a >= 3200) ? b : "red";
        Console.WriteLine(ans);



    }


}



Measured memory_bytes: 11092
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

// ----------- VECTOR ------------
template<typename T>
istream& operator >> (istream& is, vector<T>& vs){
  for(T& v: vs) is >> v;
  return is;
}
template<typename T>
ostream& operator << (ostream& os, vector<T>& vs){
  for (const T& v : vs) os << v << " ";
  return os;
}
// ----------- VECTOR ------------

int main() {
  LL N, K; cin >> N >> K;
  vector<int> A(N); cin >> A;

  if (K <= N) {
    int d = 0;
    for (int i = 0; i < K; ++i) {
      d = A[d] - 1;
    }
    cout << d + 1 << endl;
    return 0;
  }

  map<LL, int> m;
  vector<int> v(N + 1);
  m[0] = 0;
  LL d = 0;
  LL i = 1;
  for (;;++i) {
    d = A[d] - 1;
    if (m.count(d)) {
      break;
    }
    m[d] = i;
    v[i] = d;
  }
  LL index = (K - m[d]) % (i - m[d]);
  cout << v[m[d] + index]  + 1<< endl;
}


Measured memory_bytes: 14720
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, C, D;
  
  cin >> A >> B >> C >> D;
  
  if (A + B > C + D) {
    cout << "Left" << endl;
  }
  else if (A + B == C + D) {
    cout << "Balanced" << endl;
  }
  else {
    cout << "Right" << endl;
  }
}  

Measured memory_bytes: 3608