akhauriyash/Code-Regression huggingface dataset:
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <complex>
using namespace std;

#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define EPS 1e-8
#define DEB 0

typedef complex<double> P;

class circle{
  public:
	int x,y,r;
	circle(int _x, int _y, int _r){
		x=_x; y=_y; r=_r;
	}
};

double dot(P a, P b){
	return a.real()*b.real() + a.imag()*b.imag();
}
double cross(P a, P b){
	return a.real()*b.imag() - a.imag()*b.real();
}

double distance_ls_p(P p0, P p1, P p2){
	if( dot(p1-p0, p2-p0)<-EPS ) return abs(p2-p0);
	if( dot(p0-p1, p2-p1)<-EPS ) return abs(p2-p1);
	return abs(cross(p1-p0,p2-p0))/abs(p1-p0);
}

bool inside(circle& c, int x, int y){
	return (c.x-x)*(c.x-x) + (c.y-y)*(c.y-y) <= c.r*c.r ;
}

int main(){
	int n,m;
	vector<circle> vc;
	
	while(scanf("%d",&n),n){
		vc.clear();
		rep(i,n){
			int a,b,c; scanf("%d%d%d",&a,&b,&c);
			vc.pb( circle(a,b,c) );
		}
		scanf("%d",&m);
		rep(i,m){
			bool f = false;
			int tx,ty,sx,sy; scanf("%d%d%d%d",&tx,&ty,&sx,&sy);
			rep(j,n){
				if(	(inside(vc[j],tx,ty) && !inside(vc[j],sx,sy)) ||
					(!inside(vc[j],tx,ty) && inside(vc[j],sx,sy)) ){
					f = true;
#if DEB
					puts("hoge");
#endif					
					break;
				}else if( !(inside(vc[j],tx,ty) && inside(vc[j],sx,sy)) &&
						  (distance_ls_p(P(tx,ty),P(sx,sy),P(vc[j].x,vc[j].y))<=vc[j].r) ){
					f = true;
#if DEB
					puts("uguu");
#endif					
					break;
				}
			}
			puts(f ? "Safe" : "Danger");
		}
	}
	return 0;
}

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

using namespace std;

int main() {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if (a + b >= c) printf("%d\n", b + c);
    else printf("%d\n", a + b * 2 + 1);
    return 0;
}


Measured memory_bytes: 256
#include "stdio.h"

int main(void){
  int i,x,y;
  for(i = 0;i < 3000;i++){
    scanf("%d %d", &x, &y);
    if((x == 0) && (y ==0))break;
    if(x > y){
      int t = x;
      x = y;
      y = t;
    }
    printf("%d %d\n", x, y);
  }
}



Measured memory_bytes: 2036
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <list>
#include <set>
#include <bitset>
#include <iterator>
#define loop(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for(long long i = 0; i < (long long)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;
using LL = long long int;
using ULL = unsigned long long;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    rep(i, n) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    double ans = v[0];
    rep(i, n - 1) {
        ans = (ans + v[i + 1]) / 2;
    }
    printf("%.7lf\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int n,v[20],c[20],ans=0;
  cin>>n;
  for(int i=0;i<n;i++){cin>>v[i];}
  for(int i=0;i<n;i++){cin>>c[i];}
  for(int i=0;i<n;i++){
    if(v[i]>c[i])ans+=v[i]-c[i];
  }
  cout<<ans<<endl;
}

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

#define int long long
#define itn int
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL << (n))
constexpr int MOD = 1e9 + 7;

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = LLONG_MAX / 2;
using P = pair<int, int>;
using vec = vector<int>;
template <typename T>
using mat = vector<vector<T>>;

// clang-format off
template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) { return stream << p.first << "," << p.second; }
template <typename T>
void print(const vector<T> vec) { rep (i, vec.size() - 1) cout << vec[i] << ' '; cout << vec[vec.size() - 1] << '\n'; }
template <typename Arg>
void print(const Arg arg) { cout << arg << '\n'; }
template <typename Head, typename... Args>
void print(const Head head, const Args... args) { cout << head << " "; print(args...); }
template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) { rep (i, v.size()) cin >> v[i] >> w[i]; }
template <typename T>
void init(vector<T>& v) { rep (i, v.size()) cin >> v[i]; }
template <typename T>
T sum_(vector<T> vec, T init = 0) { return std::accumulate(all(vec), T(init)); }
template<typename T>
bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template<typename T>
bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <typename T>
int index(const T& vec, const typename T::iterator it) { return distance(vec.begin(), it); }
template <typename T = int>
mat<T> mmat(int n, int m=0) { return mat<T>(n, vector<T>(m)); }
template <typename T = int>
vector<T> ivec(int n) { vector<T> v(n); init(v); return v; }
// clang-format on

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// -------------------------------------------------------------------
// sort 1 2 3 4
// pqr 1 2 3 must impl >

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

    vec v = {1};
    For(b, 2, 40) {
        int p = 2;
        while (true) {
            int po = pow(b, p);
            if (po > 1001) break;
            v.pb(po);
            p++;
        }
    }

    sort(all(v));
    print(*(upper_bound(all(v), x) - 1));

    return 0;
}


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

int main() {
  int n, x;
  std::cin >> n >> x;
  int sum = 0;
  int min = 1000;

  for (int i = 0; i < n; i++) {
    int m;
    std::cin >> m;
    sum += m;
    min = std::min(min, m);
  }

  std::cout << n + (x - sum) / min << std::endl;
  return 0;
}


Measured memory_bytes: 256
from collections import Counter
N = int(input())
a = list(map(int,input().split()))

b = Counter(a)
sumnum=0
for j in b.keys(): 
    sumnum += (b[j] * (b[j]-1)) / 2

for i in range(N):
    print(int(sumnum - (b[a[i]]-1)))



Measured memory_bytes: 26780
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>

using namespace std;

inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str();}

typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EACH(t,i,c) for(t::iretator i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

const double EPS = 1e-10;

int main() {
	int n, k;

	while(cin >> n >> k, n) {
		vi cards(n+1);
		vi dp(n+1);
		vi dpw(n+2);
		bool white = false;

		int tmp;
		REP(i, k) {
			cin >> tmp;

			if(tmp) {
				cards[tmp] = 1;
			} else {
				white = true;
			}
		}

		int max = 0;
		FOR(i, 1, n+1) {
			if(cards[i]) {
				dp[i] = dp[i-1] + 1;
				dpw[i+1] = dp[i] + 1;
				if(!dpw[i-1]) {
					dpw[i-1] = 1;
				}
				if(max < dp[i]) {
					max = dp[i];
				}
			}
		}

		if(white) {
			FOR(i, 1, n+1) {
				if(cards[i]) {
					dpw[i] = dpw[i-1] + 1;
					if(max < dpw[i]) {
						max = dpw[i];
					}
				}
			}
		}

		cout << max << endl;
	}

	return 0;
}

Measured memory_bytes: 2324
#include<iostream>
#include<cstdio>
#include<complex>
#include<cmath>
using namespace std;
typedef complex<double> xy_t;

xy_t P[110];

double cross_product(xy_t a, xy_t b)
{
    return (conj(a)*b).imag();
}

int main()
{
    int N=0;
    double x,y;
    while(scanf("%lf,%lf", &x, &y)!=EOF)
    {
        P[N++]=xy_t(x,y);
    }
    double sum=0.0;
    for(int i=0;i+2<N;i++)
    {
        xy_t a=P[0], b=P[i+1], c=P[i+2];
        sum+=cross_product(b-a,c-a)/2.0;
    }
    printf("%.6f\n", abs(sum));
}


Measured memory_bytes: 3200
loop do

  a,op,b = gets.split(" ")

  a = a.to_i
  b = b.to_i

  case op
    when '+' then
      puts a + b
    when '-' then
      puts a - b
    when '*' then
      puts a * b
    when '/' then
      puts a / b
    when '?' then
      break
  end
   
end

Measured memory_bytes: 8692
# エラトステネスの篩
def make_prime_table(N):
    sieve = [0] * (N + 1)
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, N + 1):
        if sieve[i] != 0:
            continue
        sieve[i] = i
        for j in range(i * i, N + 1, i):
            if sieve[j] == 0:
                sieve[j] = i
    return sieve

N = int(input())

result = []
prime_table = make_prime_table(55555)
for i in range(3, 55555 + 1, 2):
    if prime_table[i] == i and i % 5 == 1:
        result.append(i)
    if len(result) == N:
        break
print(*result)


Measured memory_bytes: 9532
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = getInt(sc);
		int w = getInt(sc);
		String[] map = new String[h];
		for (int i = 0; i < h; i++) {
			map[i] = getString(sc);
		}
		for (String s : map) {
			System.out.println(s);
			System.out.println(s);
		}

	}

	/**
	 * *汎用メソッド<br>
	 * 入力した配列に対する順列を取得
	 *
	 * @param numArray
	 * @return
	 */
	private static List<Integer[]> getPermutation(int[] numArray) {
		List<Integer[]> permutation = new ArrayList<>();
		Integer[] ans = new Integer[numArray.length];
		boolean[] used = new boolean[numArray.length];

		return buildPermutaion(permutation, numArray, ans, used, 0);
	}

	/**
	 * *汎用メソッド(内部)<br>
	 * 入力した配列に対する順列を作成
	 *
	 * @param list
	 * @param numArray
	 * @param ans
	 * @param used
	 * @param depth
	 * @return
	 */
	private static List<Integer[]> buildPermutaion(List<Integer[]> list, int[] numArray, Integer[] ans, boolean[] used,
			int depth) {

		// 全部使い切った時=>できた順列を返す
		if (depth == numArray.length) {
			list.add(ans.clone());
			return list;
		}
		// 使い切っていない場合

		for (int i = 0; i < numArray.length; i++) {
			if (used[i]) {
				continue;
			}
			ans[depth] = numArray[i];
			used[i] = true;
			list = buildPermutaion(list, numArray, ans, used, depth + 1);

			used[i] = false;
		}

		return list;
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をlongで返却
	 *
	 * @return
	 */
	public static long getLong(Scanner sc) {

		return Long.parseLong(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をintで返却
	 *
	 * @return
	 */
	public static int getInt(Scanner sc) {

		return Integer.parseInt(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をStringで返却
	 *
	 * @return
	 */
	public static String getString(Scanner sc) {

		return sc.next();
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をint配列で返却
	 *
	 * @return
	 */
	public static int[] getIntArray(Scanner sc) {
		String line = "";
		// 直前にnext()を実行していると改行コードだけ取ってしまうのでその対策
		while (line.equals("")) {
			line = sc.nextLine();
		}

		String[] strArray = line.split(" ");
		int[] intArray = new int[strArray.length];
		for (int i = 0; i < strArray.length; i++) {
			intArray[i] = Integer.parseInt(strArray[i]);
		}
		return intArray;
	}

}


Measured memory_bytes: 38232
n,q=map(int,input().split())
s=input()
a=[0]*(n+1)
for i in range(n-1):
  if s[i:i+2]=='AC':
    a[i+1]=1
for i in range(n):
  a[i+1]+=a[i]
for i in range(q):
  l,r=map(int,input().split())
  print(a[r-1]-a[l-1])

Measured memory_bytes: 72500
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define fo(i,n)         for(int i=0;i<n;i++)
#define Fo(i,k,n)       for(int i=k;i<n;i++) 
#define endl            "\n"
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define vec(x)          vector<x>
#define matrix(x)       vector<vector<x>>
#define mem(a,b)        memset(a, b, sizeof a)
#define vii             vector<pair<int,int>>
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define MOD             998244353
#define deb(x)          cerr <<#x<<" = "<<x<<"\n"
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define all(v)          v.begin(),v.end()
#define rep(i,a,b)      for (int i = a; i<b; ++i)
#define len(s)          s.length()
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
 
int power(int a,int b,int m=mod)
{int ans=1;while(b>0){if(b&1)ans=(ans*a)%m;a=(a*a)%m;b>>=1;}
return ans;}

void angshuGod()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

const int N = 1e5+1;
const double pi = acos(-1);

void solve(){    

   	string s,t ;
   	cin>>s>>t;
   	int cnt = 0;
   	fo(i,len(s)){
   		if(s[i] != t[i]) cnt++;
   	}
   	cout<<cnt;
}

 
int32_t main()
{
    angshuGod();

    int t;

    t = 1;
    //cin>>t;

    while(t--){
        solve();
    }
    
    return 0;
}

Measured memory_bytes: 3784
#include <cstring>
#include <iostream>
#define M 1000000007
using namespace std;
int main() {
    string s; cin >> s;
    int d; cin >> d;
    long long dp[d][2] = {};
    int cur = 0, prev = 1, sum = 0;
    dp[0][prev] = 1;
    for (int i = 0; i < s.size(); i++) {
        for (int k = 0; k < d; k++) {
            dp[k][cur] = 0;
            for (int j = 0; j < 10; j++) {
                int k1 = k - j;
                if (k1 < 0) k1 = (k1 % d + d) % d;
                if (j <= s[i]-'0' || k1 != sum) dp[k][cur] += dp[k1][prev];
                else dp[k][cur] += dp[k1][prev] - 1;
            }
            dp[k][cur] %= M;
        }
        swap(cur, prev);
        sum += s[i] - '0';
        if (sum >= d) sum %= d;
    }
    cout << (dp[0][prev] - 1 + M) % M << endl;
}


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

int main()
{
  int H,W,h,w;
  cin >> H >> W >> h >> w;
  
  H = H - h;
  W = W - w;
  
  cout << H * W;
  
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
	unsigned long int a, b, c, d;
	long int A[100];
	int i = 0;
	int j;
	int sum = 0;

	for (i = 0; 100 > i; i++) {
		A[i] = 0;
	}
	

	scanf("%ld%ld", &a, &b);

	for (i = 0; b > i; i++) {
		scanf("%ld", &c);
		for (j = 0; c > j; j++) {
			scanf("%ld", &d);
			A[d - 1] = 1;
		}
	}

	for (i = 0; a > i; i++) {
		if (0 == A[i]) {
			sum++;
		}
	}

	printf("%d", sum);

	return 0;
}

Measured memory_bytes: 2152
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define F first
#define S second
#define ld long double
#define built __builtin_popcountll
#define mst(a,i) memset(a,i,sizeof(a))
#define all(x) x.begin(),x.end()
#define itit(it,a) for(auto it=(a).begin(); it!=(a).end(); it++)
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define repr(i,a,b) for(ll i=a; i>b; i--)
#define reprr(i,a,b) for(ll i=a; i>=b; i--)
#define pi 3.14159265358979323846264338327950288419716939937510582097494459230
ll max3(ll x,ll y,ll z) {return max(max(x,y),z);}
ll min3(ll x,ll y,ll z) {return min(min(x,y),z);}
const ll N=1e5+10,M=2e5+10,M2=1e6+10,mod=1e9+7,inf=1e17+10;
const int INF=1e9+7;
void add(int& a, int b) {a+=b;if(a>=mod){a-=mod;}}

#define trace(...) cerr<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
    cerr<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
    const char *comma=strchr(names+1,',');
    cerr.write(names,comma-names)<<" : "<<arg1<<" | ";
    __f(comma+1,args...);
}

int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
//assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
ll power(ll x,ll n){ll result=1;while(n>0){if(n%2==1)result=(result*x)%mod; x=((x%mod)*(x%mod))%mod;n=n/2;}return result;}

int n;
int a[410];

int cache[410][410];
int pref[410];

int dp(int l, int r){
    if(l>=r) return 0;
    int &ans=cache[l][r];
    if(ans!=-1) return ans;
    ans=inf;
    for(int i=l; i<r; i++){
        ans=min(ans,dp(l,i)+dp(i+1,r)+pref[r]-pref[l-1]);
    }
    return ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    rep(i,1,n+1) cin >> a[i];
    for(int i=1; i<=n; i++) pref[i]=pref[i-1]+a[i];
    mst(cache,-1);
    int res=dp(1,n);
    cout << res;
    return 0;
}

Measured memory_bytes: 1664
package main

import "fmt"

func main() {
	ans := []int{}
	for {
		var a, b int
		op := ""
		fmt.Scan(&a, &op, &b)
		if op == "?" {
			break
		}
		tmp := 0
		switch op {
		case "+":
			tmp = a + b
		case "-":
			tmp = a - b
		case "*":
			tmp = a * b
		case "/":
			tmp = a / b
		}
		ans = append(ans, tmp)
	}

	for _, v := range ans {
		fmt.Println(v)
	}
}



Measured memory_bytes: 1128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;


int main()
{
	ll n,p=1;
	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		p*=i;
		p%=1000000007;
	}
	cout<<p<<endl;
	return 0;
}

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

int main() {
    long long int N;
    cin >> N;
    vector<long long int> mult;
    for(int i = 1; i <= sqrt(N); i++) {
        if(N % i == 0) {
            mult.push_back(i);
        }
    }
    long long int min = (mult.at(0) - 1) + (N / mult.at(0) - 1);
    for(int i = 1; i < mult.size(); i++) {
        if(min > (mult.at(i) - 1) + (N / mult.at(i) - 1)) {
            min = (mult.at(i) - 1) + (N / mult.at(i) - 1);
        }
    }
    cout << min << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000

int beki(long long a,long long b,int M = modulo){
	int x = 1%M;
	while(b!=0){
		if(b&1){
			x=((long long)x*a)%M;
		}
		a=((long long)a*a)%M;
		b>>=1;
	}
	return x%M;
}

int get(int t){
	for(int i=0;true;i++){
		if(t==0)return i;
		int cnt = 0;
		int tt = t;
		while(tt!=0){
			if(tt%2==1)cnt++;
			tt/=2;
		}
		t %= cnt;
	}
}

int main(){
	
	int N;
	cin>>N;
	
	string S;
	cin>>S;
	
	int X = 0;
	for(int i=0;i<S.size();i++){
		if(S[i]=='1')X++;
	}
	
	if(X==0){
		for(int i=0;i<N;i++){
			cout<<1<<endl;
		}
		return 0;
	}
	int A = 0,B = 0;
	for(int i=0;i<N;i++){
		A *= 2;
		B *= 2;
		A += S[i]-'0';
		B += S[i]-'0';
		if(X!=1)A %= X-1;
		else A=0;
		B %= X+1;
	}
	
	for(int i=0;i<N;i++){
		if(S[i]=='0'){
			int t = B+ beki(2,N-1-i,X+1);
			t %= X+1;
			cout<<1+get(t)<<endl;
		}
		else{
			if(X==1){
				cout<<0<<endl;
				continue;
			}
			int t = A - beki(2,N-1-i,X-1);
			t += 2*(X-1);
			t %= X-1;
			cout<<1+get(t)<<endl;
		}
	}
	
	return 0;
}


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

string solve() {
    ll A, B,C, D;
    cin >> A >> B >> C >> D;
    while ( A > 0 && C > 0 ) {
        C -= B;
        if ( C <= 0 ) return "Yes";
        A -= D;
        if ( A <= 0 ) return "No";
    }
    return "";
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

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

using ll = long long int;
using P = std::pair<int, int>;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rag(con) std::begin(con), std::end(con)

constexpr ll mod = 1e9 + 7;

ll pow(ll x, ll m)
{

    ll re = 1, y = 1;

    for (int i = 0; i < 60; ++i)
    {
        if (m & y)
            re = re * x % mod;
        x = x * x % mod;
        y *= 2;
    }

    return re;
}

ll inv(ll x)
{

    return pow(x, mod - 2);
}

class mint
{
    ll num = 0;

public:
    mint(ll x = 0) : num(x) {}

    mint operator+(const mint &rhs) const
    {
        return (num + rhs.num) % mod;
    }
    mint operator*(const mint &rhs) const
    {
        return num * rhs.num % mod;
    }
    mint operator-(const mint &rhs) const
    {
        return (num - rhs.num + mod) % mod;
    }
    mint operator/(const mint &rhs) const
    {
        return num * inv(rhs.num) % mod;
    }
    mint operator+=(const mint &rhs)
    {
        return num = (num + rhs.num) % mod;
    }
    friend std::ostream &operator<<(std::ostream &os, const mint &rhs);
};

std::ostream &operator<<(std::ostream &os, const mint &rhs)
{

    os << rhs.num;

    return os;
}

int main()
{
    ll n, m;

    std::cin >> n >> m;

    std::vector<mint> fact(m + 1);

    fact[0] = 1;

    for (int i = 1; i <= m; ++i)
        fact[i] = fact[i - 1] * i;

    auto pp = [&](ll x, ll y) {
        return fact[x] / fact[x - y];
    };

    auto comb = [&](ll x, ll y) {
        return fact[x] / fact[x - y] / fact[y];
    };

    std::vector<mint> d(n + 1);

    d[n] = pp(m, n);

    for (int i = n - 1; i >= 0; --i)
    {
        d[i] = comb(n, i) * pp(m, n) * pp(m - i, n - i) - d[i + 1];
    }

    std::cout << d[0] << std::endl;

    return 0;
}

Measured memory_bytes: 11176
#include <bits/stdc++.h>
using ll = long long;
#define int ll
#define range(i, a, n) for(int (i) = (a); (i) < (n); (i)++)
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
using namespace std;
using vi = vector<int>;
const ll inf = 1L << 50;

class dinic{
	public :
		void init(int _n){
			n=_n;
			G.resize(n);
			iter.resize(n);
			level.resize(n);
		}

		void add_edge(int from,int to ,int cap){
			G[from].push_back((edge){to,cap, (int)G[to].size()});
			G[to].push_back((edge){from,0, (int)G[from].size()-1});
		}
	
		void add_edge_both(int from,int to ,int cap){
			add_edge(from,to,cap);
			add_edge(to,from,cap);
		}
	
		int max_flow(int s,int t){
			int flow=0;
			for(;;){
				bfs(s);
				if(level[t]<0) return flow;
				iter.assign(n,0);
				int f;
				while((f=dfs(s,t,DINIC_INF))>0){
					flow+=f;
				}
			}
		}
	private:
	
		int n;
		struct edge{int to,cap,rev;};
		static const int DINIC_INF = inf;
		vector< vector<edge> > G;
		vi level;
		vi iter;
	
		void bfs(int s){
			level.assign(n,-1);
			queue<int> que;
			level[s]=0;
			que.push(s);
			while(!que.empty()){
				int v=que.front();que.pop();
				for(int i=0;i< (int)G[v].size(); i++){
					edge &e=G[v][i];
					if(e.cap>0 && level[e.to] <0){
						level[e.to]=level[v]+1;
						que.push(e.to);
					}
				}
			}
		}

		int dfs(int v,int t,int f){
			if(v==t) return f;
			for(int &i=iter[v];i<(int)G[v].size();i++){
				edge &e= G[v][i];
				if(e.cap>0 && level[v]<level[e.to]){
					int d=dfs(e.to,t,min(f,e.cap));
					if(d>0){
						e.cap -=d;
						G[e.to][e.rev].cap+=d;
						return d;
					}
				}
			}
			return 0;
		}	
};

map<string, int> s2i;
vector<string> T = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};

signed main(void){
    rep(i, 7) s2i[T[i]] = i + 1;

    for(int n, w; cin >> n >> w, n;){
        dinic d;
        d.init(n + 9);

        range(i, 1, 8){
            d.add_edge(0, i, w);
        }

        int sum = 0;
        rep(i, n){
            int t, c; cin >> t >> c;
            sum += t;
            d.add_edge(9 + i, 8, t);
            rep(_, c){
                string in; cin >> in;
                int v = s2i[in];
                d.add_edge(v, 9 + i, inf);
            }
        }

        if(d.max_flow(0, 8) == sum){
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
    }

	return 0;
}

Measured memory_bytes: 3272
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    double a[n+1];
    for(int i=1;i<=n;i++)    cin>>a[i];
    double dp[n+1][n+1];
    memset(dp,0,sizeof dp);
    // for(int i=0;i<=n;i++)   dp[i][0]=1;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        double sum=0;
        for(int j=1;j<=n;j++){
            dp[i][j] = dp[i-1][j]*(1-a[i]) +  dp[i-1][j-1]*a[i];
            sum+=dp[i][j];
        }
        dp[i][0]=1-sum;
    }
    double ans=0;
    for(int i=(n+1)/2;i<=n;i++){
        ans+=dp[n][i];
    }
    cout<<setprecision(13)<<ans<<endl;
}


Measured memory_bytes: 70656
#include <iostream>
#include <deque>
#include <vector>
using namespace std;

int main()
{
    int K; cin>>K;
    vector<int> v(K, 1<<30);
    deque<int> q;
    q.push_back(1);
    v[1]=1;
    while (q.size()) {
        int p=q.front();
        q.pop_front();
        if (p==0) {
            cout<<v[p]<<endl;
            break;
        }
        if (v[p*10%K]>v[p]) {
            v[p*10%K]=v[p];
            q.push_front(p*10%K);
        }
        if (v[(p+1)%K]>v[p]+1) {
            v[(p+1)%K]=v[p]+1;
            q.push_back((p+1)%K);
        }
    }
}


Measured memory_bytes: 896
func main() {
  	let numberOfFiveHandredCoins = Int(readLine()!)!
  	let numberOfHandredCoins = Int(readLine()!)!
  	let numberOfFiftyCoins = Int(readLine()!)!
	let amount = Int(readLine()!)!
  
  	var hitCount = 0
  	
  	for fHNum in 0...numberOfFiveHandredCoins {
      	if amount == fHNum * 500 {
	      	hitCount += 1
          	continue
        }
      
      	for hNum in 0...numberOfHandredCoins {
        	if amount == fHNum * 500 + hNum * 100 {
              	hitCount += 1
              	continue
            }
          
          	for fNum in 0...numberOfFiftyCoins {
              	if amount == fHNum * 500 + hNum * 100 + fNum * 50 {
                  	hitCount += 1
                  	continue
                }
            }
        }
    }
  	print(hitCount)
}

main()

Measured memory_bytes: 7804
#include <iostream>
#include <map>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;

int main(void) {
  int N;
  cin >> N;
  map<int, int> A;
  rep(i, N) { 
    int a;
    cin >> a;
    A[a] = i;
  }
  
  int idx = 0;
  int count = 0;
  for(auto itr : A) {
    if(idx % 2 != itr.second %2) ++count;
    ++idx;
  }
  
  cout << count / 2 << endl;
  return 0;
}

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

int main()
{
    int n, k;
    string s;

    cin >> n >> k >> s;

    s[k - 1] = s[k - 1] + ('a' - 'A');
    
    cout << s;

    return 0;

}

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

int main(int argc, const char * argv[]) {
    char str[1001];
    char order[32];
    char p[1001];
    int a,b;
    int q,loop;
    int i,j;
    
    scanf("%s",str);
    scanf("%d",&q);
    for(loop=1;loop<=q;loop++){
        scanf("%s %d %d",order,&a,&b);
        if(strcmp(order,"print")==0){
            for(i=a;i<=b;i++){
                printf("%c",str[i]);
            }
            printf("\n");
        }
        else if(strcmp(order,"reverse")==0){
            j=0;
            for(i=a;i<=b;i++){
                p[j]=str[b-j];
                j++;
            }
            j=0;
            for(i=a;i<=b;i++){
                str[i]=p[j];
                j++;
            }
        }
        else{
            scanf("%s",p);
            j=0;
            for(i=a;i<=b;i++){
                str[i]=p[j];
                j++;
            }
        }
    }
    
    return 0;
}


Measured memory_bytes: 2104
#include"bits/stdc++.h"

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

using namespace std;

const ll MOD = 1e9 + 7;

int main(void) {
	int N; cin >> N;
	ll ans = 1;

	for (int i = 1; i <= N; i++) {
		ans = (ans * i) % MOD;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define me0(a) memset(a,0,sizeof(a))
#define me1(a) memset(a,-1,sizeof(a))
#define op freopen("in.txt", "r", stdin)
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
using namespace std;
const int INF = 0x3f3f3f3f;
typedef unsigned long long ULL;
typedef long long ll;
void read(int& val) { int x = 0; int bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; }
const int mod=1e9+7;
const int maxn = 2e6+11;
ll fct[maxn],ans;
int n,k;
char s[maxn];

ll qmi(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1; a=a*a%mod;
    }
    return res;
}
ll C(ll a,ll b){
    if(a<b) return 0;
    return fct[a]*qmi(fct[b],mod-2)%mod*qmi(fct[a-b],mod-2)%mod;
}
void init(){
    fct[0]=1;
    fo(i,1,maxn-1) fct[i]=fct[i-1]*i%mod;
}
int main(){
    init();
    read(k);scanf("%s",s);
    int len=strlen(s);
    n=len+k;
    ans=0;
    fo(i,len,n){
        ll t=(C(i-1,len-1)*qmi(25,i-len)%mod*qmi(26,n-i)%mod)%mod;
        ans = ((ans+t)%mod+mod)%mod;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 20344
double x[3],y[3],a,b,c,A,B,C,X,Y,r;
main(n,i,j,k){
	i=0,j=1,k=2;
	for(scanf("%d",&n);n--;printf("%.3f %.3f %.3f\n",X,Y,r)){
		scanf("%lf%lf%lf%lf%lf%lf",x,y,x+1,y+1,x+2,y+2);
		a=2*x[j]-2*x[i],b=2*y[j]-2*y[i],c=x[i]*x[i]-x[j]*x[j]+y[i]*y[i]-y[j]*y[j];
		A=2*x[k]-2*x[i],B=2*y[k]-2*y[i],C=x[i]*x[i]-x[k]*x[k]+y[i]*y[i]-y[k]*y[k];
		X=(b*C-B*c)/(a*B-A*b),Y=(c*A-C*a)/(a*B-A*b);
		r=hypot(x[i]-X,y[i]-Y);
	}
exit(0);}

Measured memory_bytes: 668
#include<cstdio>
#include<algorithm>
using namespace std;

int ketanowa(int N){
	
	int sum=0;
	
	while(N>0){
		sum+=N%10;
		N/=10;
	}
	
	return sum;
	
}

int main(void){
	
	int N,d[10],ds[100010],m=999999,t,i;
	
	
	scanf("%d",&N);
	
	for(i=1;i<=N-1;i++){
		t=ketanowa(i)+ketanowa(N-i);
		m=min(t,m);
	}
	
	printf("%d\n",m);
	
	return 0;
}


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

using namespace std;
#define ll long long
#define ld long double

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    ll x;
    cin >> x;
    int ans = 0;
    ans += x / 500 * 1000;
    x %= 500;
    ans += x / 5 * 5;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

#define Max 500000
#define INFTY 1000000000

struct card {
	char mark;
	int value;
}; typedef struct card card;

card L [Max/2 + 2], R[Max/2 + 2];

void  swap(card *x, card *y)
{
    card  buff;
	
	buff = *x;
	*x = *y;  
	*y = buff;
}

void printA(card A[Max], int N) {
	int i;

	for (i = 0; i < N; i++)
		printf("%c %d\n", A[i].mark, A[i].value);
}

void merge(card A[Max], int left, int mid, int right) {
	int i, j, k;

	int n1 = mid - left;
	int n2 = right - mid;

	// L[0...n1], R[0...n2] ?????????
	for (i = 0; i < n1; i++) L[i] = A[left + i];
	for (i = 0; i < n2; i++) R[i] = A[mid + i];

	L[n1].value = INFTY;
	R[n2].value = INFTY;
	i = 0;
	j = 0;

	for (k = left; k < right; k++) {
		if (L[i].value <= R[j].value)  A[k] = L[i++];
		else  A[k] = R[j++];
	}
}

void mergeSort(card A[Max], int left, int right) {
	int mid;

	if (left + 1 < right) {
		mid = (left + right)/2;
		mergeSort(A, left, mid);
		mergeSort(A, mid, right);
		merge(A, left, mid, right);
	}
}

int partition(card A[Max], int p, int r) {
	int x = A[r].value;
	int i = p-1;
	int j;
	
	for (j = p; j < r; j++)
		if (A[j].value <= x) swap(&A[++i], &A[j]);

	swap(&A[i + 1], &A[r]);

	return i + 1;
}

void quickSort(card A[Max], int p, int r) {
	int q;

	if (p < r) {
		q = partition(A, p, r);
		quickSort(A, p, q-1);
		quickSort(A, q+1, r);
	}
}

int main( ) {
	int N, i, q;
	card A[Max];
	card B[Max];

	scanf("%d", &N);

	for (i = 0; i < N; i++) {
		scanf(" %c", &A[i].mark);
		scanf("%d", &A[i].value);
		B[i] = A[i];
	}

	mergeSort(A, 0, N);
	quickSort(B, 0, N - 1);

	for (i = 0; i < N; i++) {
		if (A[i].mark != B[i].mark) {
			printf("Not stable\n");
			break;
		}
		else if (i == N - 1) {
			printf("Stable\n");
		}
	}

	printA(B, N);

	return 0;
}

Measured memory_bytes: 7804
#include <iostream>
#include <string>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

int main()
{
  string a, b;
  cin >> a >> b;
  if (a > b) cout << ">" << endl;
  else if (a < b) cout << "<" << endl;
  else cout << "=" << endl;
}


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

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int main() {
  int a;
  cin >> a;
  rep(i, 0, a) {
    int b, c;
    cin >> b >> c;
    if(b < c) {
      cout << b << endl;
      continue;
    }
    int s = b % c;
    cout << (s ? s : c) << endl;
  }
}

Measured memory_bytes: 3164
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
#define lol long long
#define SUM(n) ((n)+1)*(n)/2　//1〜nまでの総和を求める式
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) setprecision(x+1) //小数点桁数を指定する
#define abs(x,y) (max(x,y)-min(x,y))
#define all(v) v.begin(),v.end()
#define UPDight(a,b) (a+b-1)/b //小数点切り上げ 
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD=int(1e9)+7; 
using namespace std;
using pii = pair<int,int>;
typedef vector<int> vit;

int n, q;
vit edge[200005];
vector<lol> ans(200005, 0);
bool isvisited[200005] = {false};

void count(int p ,int x){
  if(isvisited[p]) return;
  ans[p] += x;
  isvisited[p] = true;
  rep(i, edge[p].size() ){
    count(edge[p][i] , ans[p]);
  }
  return;
}

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

  cin >> n >> q;
  int a, b;
  rep(i, n - 1){
    cin >> a >> b;
    edge[a].pu(b);
    edge[b].pu(a);
  }
  rep(i, q){
    cin >> a >> b;
    ans[a] += b;
  }
  count(1, 0);
  reps(i, n - 1){
    cout << ans[i] << " ";
  }
  cout << ans[n] << '\n';
  return 0;
}


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

int main() {
  int H, W;
  cin >> H >> W;
   
  vector<string> vec(H*W);
  
  for (int i = 0; i < H*W; i++) {
    cin >> vec.at(i);
  }
  
  for (int j = 0; j < W+2; j++) {
    cout << '#';
  }
  cout << endl;
  
  for (int k = 0; k < H; k++) {
    cout << '#' << vec.at(k) << '#' << endl;
  }
  
  for (int l = 0; l < W+2; l++) {
    cout << '#';
  }
}

Measured memory_bytes: 384
#include <stdio.h>

int main(void)
{
    char str[1000];
    int i = 0;
    int j;
    int n;

    while (scanf("%s", str) != EOF){
        while (str[i] != '\0'){
            if (str[i] == '@'){
                n = str[i+1] - 0x30;
                for (j = 0; j < n;j++){
                    printf("%c", str[i+2]);
                }
                i += 2;
            }
            else {
                printf("%c", str[i]);
            }
            i++;
        }
        printf("\n");
        i = 0;
    }

    return 0;
}

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

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 2005;
const int MOD = 924844033;

int n, k;
int fact[MAXN], dp[2][MAXN][MAXN][3], sum[2][MAXN][MAXN], sol[MAXN][MAXN];

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

void precompute () {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = mul(fact[i - 1], i);
    }
}

void calc () {
    dp[0][0][0][0] = dp[1][0][0][1] = 1;
    sum[0][0][0] = sum[1][0][0] = 1;
    for (int t = 0; t < 2; t++) {
        for (int pos = 1; pos <= n + 1; pos++) {
            for (int br = 0; br <= pos; br++) {
                dp[t][pos][br][0] = sum[t][pos - 1][br];
                if (br > 0) {
                    dp[t][pos][br][1] = sum[t][pos - 1][br - 1];
                    dp[t][pos][br][2] = add(dp[t][pos - 1][br - 1][0], dp[t][pos - 1][br - 1][2]);
                }
                sum[t][pos][br] = add(dp[t][pos][br][0], add(dp[t][pos][br][1], dp[t][pos][br][2]));
            }
        }
    }
    sol[0][0] = 1;
    for (int pos = 1; pos <= min(2 * k, n); pos++) {
        int len = (n + 1 - pos + 2 * k - 1) / (2 * k);
        bool lef = 0, rig = 0;
        if (pos - k <= 0) lef = 1;
        if (pos + (len - 1) * 2 * k + k > n) rig = 1;
        for (int br = 0; br <= n; br++) {
            int res = 0;
            for (int i = 0; i <= min(len, br); i++) {
                res = add(res, mul(sol[pos - 1][br - i], dp[lef][len + 1][i + rig][rig * 2]));
            }
            sol[pos][br] = res;
        }
    }
}

void fui () {
    int res = 0;
    for (int i = 0; i <= n; i++) {
        int val = mul(sol[min(2 * k, n)][i], fact[n - i]);
        if (i % 2 == 0) res = add(res, val); else res = sub(res, val);
    }
    cout << res;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    precompute();
    calc();
    fui();
    return 0;
}


Measured memory_bytes: 108492
def main():
    from functools import lru_cache
    N = int(input())
    MOD = 10**9 + 7

    def is_ok(last4):
        for i in range(4):
            t = list(last4)
            if i >= 1:
                t[i-1], t[i] = t[i], t[i-1]
            if "".join(t).count("AGC") >= 1:
                return False
        return True

    @lru_cache(maxsize=1000)
    def dfs(cur, last3):
        if cur == N:
            return 1
        ret = 0
        for c in "AGCT":
            if is_ok(last3 + c):
                ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
        return ret

    print(dfs(0, "TTT"))


if __name__ == '__main__':
    main()


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

int main(void) {
  int N;
  cin >> N;
  for (int i =0; i < N; i++) {
	string S;
	cin >> S;
	if (S == "Y") {
	  cout << "Four" << endl;
	  return 0;
	}
  }
  cout << "Three" << endl;
  return 0;
}

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

int main() {
  int N;
  string S;
  cin >>N>>S;
  int a =0;
  
  for(int i=0;i < N-2;i++){
    if(S[i] == 'A'){
      if(S[i+1] == 'B'){
        if(S[i+2] == 'C'){
          a++;
        }
      }
    }
  }
  cout << a << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
    int W, a, b;
    cin >> W >> a >> b;

    if( abs(a-b) < W ){
        cout << 0 << endl;
    }else{
        cout << abs(a - b) - W << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mii map<int,int>
#define msi map<string,int>
#define pb push_back
#define mp make_pair
#define M 1101
#define MOD 1000000007
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define repl(i,l,r) for(long long i=l;i<=r;++i)
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define ins insert
#define inf INT_MAX
#define vpi vector< pair<int,int> >
#define vpl vector< pair<ll,ll> >
#define eps 0.00001

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,x;cin>>n>>x;
    vi l(n+1);
    rep(i,1,n)
    {
        cin>>l[i];
    }
    int coun=1;
    int sum=0;
    rep(i,1,n)
    {
        sum+=l[i];
        if(sum<=x)
        {
            coun++;
        }
    }
    cout<<coun<<"\n";

    return 0;
    // check for long long or int
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int a, b;
    while(scanf("%d %d\n", &a, &b)) {
        if (a == 0 && b == 0) break;
        
        if (a < b) {
        int tmp = a;
        a = b;
        b = tmp;
        }
        
        int count = 1;
        int r = a % b;  
        
        while (r != 0) {
            a = b;
            b = r;
            r = a % b;
            count++;
        }
        
        printf("%d %d\n", b, count);
    }

    return 0;
}


Measured memory_bytes: 2040
n = int(input())
s = input()
ans = 0

for i in range(0,1000):
    num = str(i)
    if i < 10:
        num = "00"+num
    elif i <100:
        num = "0" + num
    f = 0
    for j in range(n):
        if s[j] == num[f]:
            f += 1
        if f == 3:
            break
    if f==3:
        ans +=1
print(ans)
                        


Measured memory_bytes: 68132
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i =0;i < n;i++)
int main() {
  int n;cin >> n;vector<int> h(n);
  REP(i, n) cin >> h[i];
  --h[0];
  for(int i = 1;i < n;i++) {
    if (h[i - 1] < h[i]) --h[i];
    if (h[i - 1] > h[i]) {
      cout <<"No" << endl;
      return 0;
    }
  }
  cout <<  "Yes" << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
using namespace std;
const int mod=1000000007;
long long a,b,c;
void factorial(int x, int y,int z)
{
    long long s=1,t=max(x,max(y,z));
    for(int i=0;i<=t;++i)
    {
        if(i>0) s=s*i%mod;
        if(i==x)  a=s;
        if(i==y)  b=s;
        if(i==z)  c=s;
    }
    return;
}
long long pw(long long x, int p=mod-2)
{
    long long r=1;
    for(;p;p>>=1,x=x*x%mod)  if(p&1)  r=r*x%mod;
    return r;
}
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    factorial(k-2,m*n-2,m*n-k);
    a=pw(a,mod-2);
    c=pw(c,mod-2);
    long long v=(a*b)%mod*c%mod,res=0;
    for(int i=1;i<n;++i)   res=(res+1ll*i*(n-i)*m*m*v)%mod;
    for(int i=1;i<m;++i)   res=(res+1ll*i*(m-i)*n*n*v)%mod;
    printf("%lld",(res+mod)%mod);
    return 0;
}


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

#define MAX_N 1000

using namespace std;

int main()
{
    int n, r;
    cin >> n >> r;

    int rez;

    if(n >= 10)
        rez = r;

    else
        rez = r + 100 * (10 - n);

    cout << rez << "\n";

    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("O3") //コンパイラ最適化用

#define _GLIBCXX_DEBUG //配列に[]でアクセス時のエラー表示
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
// Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはメントされる
#define REP(i, n) for (ll i = 0; i < ll(n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--) //ループ変数は1ずつデクリ
#define FOR(i, a, b) for (ll i = a; i < ll(b); i++)
#define FORD(i, a, b) for (ll i = a; i > ll(b); i--) //ループ変数は1ずつデクリ
// xにはvectorなどのコンテナ
#define ALL(x) x.begin(), x.end() // sortなどの引数を省略したい
#define SIZE(x) ll(x.size())      // sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 // 10^12:極めて大きい値,∞
#define MOD 1000000007    // 10^9+7:合同式の法
#define MAXR 100000 // 10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back // vectorヘの挿入
#define MP make_pair // pairのコンストラクタ
#define F first      // pairの一つ目の要素
#define S second     // pairの二つ目の要素
#define Umap unordered_map
#define Uset unordered_set
const unsigned int BIT_FLAG_0 = (1 << 0); // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1); // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2); // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3); // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4); // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5); // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6); // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7); // 0000 0000 1000 0000

int main() {

    ll n, a, b;
    cin >> n >> a >> b;
    ll ans = 0;

    FOR(i, 1, n + 1) {
        string num = to_string(i);
        int cnt = 0;
        REP(j, num.size()) { cnt += num[j] - '0'; }
        if (a <= cnt & cnt <= b) {
            ans += i;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define REPR(i, m, n) for (int i = (int)(m); i >= (int)(n); i--)
#define all(v) v.begin(), v.end()
typedef pair<int,int> pii;
#define fi first
#define se second
#define mp make_pair
typedef long long ll;

int n, k;
ll T[100100];

int check(ll P){
  int i = 0;
  rep(j, k){
    ll s = 0;
    while(s + T[i] <= P){
      s += T[i];
      i++;
      if(i == n) return n;
    }
  }
  return i;
}

int solve(){
  ll left = 0;
  ll right = 100100 * 10100;
  ll mid;
  while(right - left > 1){
    mid = (right + left) / 2;
    int v = check(mid);
    if(n <= v) right = mid;
    else left = mid;
  }
  return right;
}

int main(){
  cin >> n >> k;
  rep(i, n) cin >> T[i];
  ll ans = solve();
  cout << ans << endl;
  return 0;
}




Measured memory_bytes: 3896