akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
 bool prime[10000001];
int main() {
	int n;
	memset(prime,-1,sizeof(prime));
	for(int i=2;i<=10000000;i++) {
		if(!prime[i]) continue;
		for(int j=i*2;j<=10000000;j+=i) prime[j]=0;
	}
	while(scanf("%d",&n),n) {
		for(int i=n;i>=13;i--) {
			if(prime[i]&&prime[i-2]&&prime[i-6]&&prime[i-8]) {
				printf("%d\n",i);
				break;
			}
		}
	}
}

Measured memory_bytes: 10800
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main(){
	long n ,blood[4]={0};
	char s[3];
	while(scanf(" %ld,%s", &n, s)!=EOF){
		if(strcmp(s,"A")==0) ++blood[0];
		else if(strcmp(s,"B")==0) ++blood[1];
		else if(strcmp(s,"AB")==0) ++blood[2];
		else if(strcmp(s,"O")==0) ++blood[3];
	}
	
	for(int i=0; i<4; ++i) printf("%ld\n", blood[i]);

	return 0;
}

Measured memory_bytes: 1188
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i) 
const int N = 2e5 + 5, inf = 1e9 + 7 ;
using namespace std ;

int n, m, a[N], ans, e, ter[N], nxt[N], lnk[N], dep[N], sz[N] ;

void add(int x, int y) {
	ter[++ e] = y, nxt[e] = lnk[x], lnk[x] = e ;
}

void dfs(int p) {
	sz[p] = dep[p] ;
	for (int i = lnk[p] ; i; i = nxt[i]) {
		dep[ter[i]] = dep[p] + 1 ;
		dfs(ter[i]) ;
		sz[p] = max(sz[p], sz[ter[i]]) ;
	}
}

int _dfs(int p) {
	int res = 0 ;
	for (int i = lnk[p] ; i; i = nxt[i]) {
		res = max(res, _dfs(ter[i])) ;
	}
	if (dep[p] > m) res = max(res, dep[p] - m + 1) ;
	if (p == 1) return 0 ;
	if (res == dep[p]) ++ ans, res = 0 ;
	return res ;
}

int main() {
	scanf("%d%d", &n, &m) ;
	rep(i, 1, n) scanf("%d", &a[i]) ;
	rep(i, 2, n) add(a[i], i) ;
	ans = (a[1] > 1) ;
	dfs(1), _dfs(1) ;
	printf("%d\n", ans) ;
	return 0 ;
}

Measured memory_bytes: 8320
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n - 1; i >= 0; i--)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define mrep(i,from,n) for(int i = from; i < n; i++)
#define mreps(i,from,n) for(int i = from; i <= n; i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())
typedef long long ll;
typedef pair<ll, ll> P;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
ll MOD = 1000000007;

void solve()
{	
	int a, b, c; cin >> a >> b >> c;
	int ans = 0;
	for (int i = a; i <= b; i++)
	{
		if(c % i ==0)ans++;
	}
	cout << ans << endl;
	return;
}

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



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

using namespace std;

int dp[50];

void makeFib(int n) {
  dp[0] = 1;
  dp[1] = 1;
  for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
}

int main()
{
  int n; cin >> n;
  makeFib(n);

  cout << dp[n] << endl;
  return 0;
}


Measured memory_bytes: 3092
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int dp[N][23];
int n,L;
int a[N];
int q,x,y;
int ef(int id,int v){
	int l=id,r=n,ans=id;
	while(l<=r){
		int mid=(l+r)/2;
		if(a[mid]<=v)ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
void cl(){ // 
	for(int i=1;i<=n;i++)dp[i][0]=ef(i,a[i]+L);
	for(int j=1;j<23;j++){
		for(int i=1;i<=n;i++){
			dp[i][j]=dp[dp[i][j-1]][j-1];
		}
	}
}
int js(int x,int y){
	int ans=0,pos=x;
	for(int i=22;i>=0;i--){
		if(dp[pos][i]<y){
			pos=dp[pos][i];
			ans+=(1<<i);
		}
	}
	ans++;
	return ans;
}
int main()
{
	//freopen("H:\\c++1\\in.txt","r",stdin);
	//freopen("H:\\c++1\\out.txt","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	scanf("%d",&L);
	scanf("%d",&q);
	cl();
	while(q--){
		scanf("%d%d",&x,&y);
		if(x>y)swap(x,y);
		printf("%d\n",js(x,y));
	}
	return 0;
}
/*
9
1 3 6 13 15 18 19 29 31
10
4
1 8
7 3
6 7
8 5
*/
/*
4
2
1
2
*/

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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int &Ai : A) cin >> Ai;

    int ans = A.at(0);
    for (const int Ai : A) {
        ans = __gcd(ans, Ai);
    }

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 3696
n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 1
if n == 2:
  print(max(a))
else:
  a0 = a[0]
  a1 = a[1]
  r = 0
  while True:
    r = a1 % a0
    if r == 0:
      b0 = a0
      break
    elif r > a0:
      a1, a0 = r, a0
    else:
      a1, a0 = a0, r
  a1 = a[1]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a1
    if r == 0:
      b1 = a1
      break
    elif r > a1:
      a2, a1 = r, a1
    else:
      a2, a1 = a1, r
  a0 = a[0]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a0
    if r == 0:
      b2 = a0
      break
    elif r > a0:
      a2, a0 = r, a0
    else:
      a2, a0 = a0, r
  max_a = max(b0,b1,b2)
  for j in range(max_a,1,-1):
    if max_a % j == 0:
      c = list(map(lambda x: x % j,a))
      c_ng = [i for i in c if i > 0]
    #print("j=",j,"c=",c,"c_ng=",c_ng)
      if len(c_ng) <= 1:
        ans = j
        break
  print(ans)

Measured memory_bytes: 15008
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use itertools::Itertools;
use smallvec::alloc::collections::{BTreeMap, BTreeSet};

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    let mut sc = Scanner::new();
    let n = sc.next_usize();
    let k = sc.next_usize();
    let mut a = BTreeSet::new();
    let mut m = BTreeMap::new();
    for _ in 0..n {
        let ai = sc.next_usize();
        a.insert(ai);
        *m.entry(ai).or_insert(0) += 1;
    }
    
    let l = if a.len() > k { a.len() - k } else { 0 };
    let m = m
        .into_iter()
        .map(|(key, value)| (value, key))
        .sorted();

    println!("{}", m.take(l).map(|(v, _)| v).sum::<usize>());
}

pub struct Scanner {
    buf: std::collections::VecDeque<String>,
}

impl Scanner {
    pub fn new() -> Self {
        Self {
            buf: std::collections::VecDeque::new(),
        }
    }

    fn scan_line(&mut self) {
        let mut flag = 0;
        while self.buf.is_empty() {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).unwrap();
            let mut iter = s.split_whitespace().peekable();
            if iter.peek().is_none() {
                if flag >= 5 {
                    panic!("There is no input!");
                }
                flag += 1;
                continue;
            }

            for si in iter {
                self.buf.push_back(si.to_string());
            }
        }
    }

    pub fn next<T: std::str::FromStr>(&mut self) -> T {
        self.scan_line();
        self.buf
            .pop_front()
            .unwrap()
            .parse()
            .unwrap_or_else(|_| panic!("Couldn't parse!"))
    }

    pub fn next_usize(&mut self) -> usize {
        self.next()
    }

    pub fn next_isize(&mut self) -> isize {
        self.next()
    }

    pub fn next_chars(&mut self) -> Vec<char> {
        self.next::<String>().chars().collect()
    }

    pub fn next_string(&mut self) -> String {
        self.next()
    }

    pub fn next_char(&mut self) -> char {
        self.next()
    }

    pub fn next_float(&mut self) -> f64 {
        self.next()
    }
}


Measured memory_bytes: 18748
#include <iostream>
#include <string>
#include <vector>
#include <cstdint>
#include <cstdlib>
#include <algorithm>
#include <cmath>

typedef long long ll;
using namespace std;

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

    ll sub = b - a;
    ll height_b = 0;
    for (auto i = sub; i > 0; --i) {
        height_b += i;
    }
    cout << (height_b - b) << endl;
    return 0;
}


Measured memory_bytes: 256
import std.stdio, std.string, std.conv, std.algorithm, std.numeric;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;


void main() {
    string s;
    scan(s);
    writeln(s.count!"a == '1'");
}



void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

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

using namespace std;

struct Card {
    char suit;
    int value;
};

void bubble(struct Card cards[], int N) {
    for (int i = 0; i < N; ++i) {
        for (int j = N - 1; j > i; --j) {
            if (cards[j].value < cards[j - 1].value) {
                swap(cards[j], cards[j - 1]);
            }
        }
    }
}

void selection(struct Card cards[], int N) {
    for (int i = 0; i < N; ++i) {
        int min_index = i;
        for (int j = i; j < N; ++j) {
            if (cards[j].value < cards[min_index].value) {
                min_index = j;
            }
        }

        swap(cards[i], cards[min_index]);
    }
}

bool isStable(struct Card A[], struct Card B[], int N) {
    for (int i = 0; i < N; ++i) {
        if (A[i].suit != B[i].suit) {
            return false;
        }
    }

    return true;
}

void print(struct Card cards[], int N) {
    for (int i = 0; i < N; ++i) {
        if (i == 0) {
            cout << cards[i].suit << cards[i].value;
        } else {
            cout << ' ' << cards[i].suit << cards[i].value;
        }
    }

    cout << endl;
}

int main() {
    Card A[100], B[100];
    int N;
    cin >> N;

    for (int i = 0; i < N; ++i) {
        cin >> A[i].suit >> A[i].value;
        B[i] = A[i];
    }

    bubble(A, N);
    selection(B, N);

    print(A, N);
    cout << "Stable" << endl;
    print(B, N);
    if (isStable(A, B, N)) {
        cout << "Stable" << endl;
    } else {
        cout << "Not stable" << endl;
    }

    return 0;
}



Measured memory_bytes: 3112
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			int n = scanner.nextInt();
			if (n == 0)
				break;
			Team[] teams = new Team[n];
			for (int i = 0; i < n; i++)
				teams[i] = new Team(scanner.nextInt(), scanner.nextInt(),
						scanner.nextInt(), scanner.nextInt());
			Arrays.sort(teams);
			int[] num = new int[1001];
			int s = 0;
			for (int i = 0; i < n && s < 26; i++) {
				int a = num[teams[i].u];
				if (s < 10 && a < 3 || s < 20 && a < 2 || s < 26 && a == 0) {
					System.out.println(teams[i].i);
					num[teams[i].u]++;
					s++;
				}
			}
		}
	}

	class Team implements Comparable<Team> {
		int i, u, a, p;

		public Team(int i, int u, int a, int p) {
			super();
			this.i = i;
			this.u = u;
			this.a = a;
			this.p = p;
		}

		@Override
		public int compareTo(Team o) {
			if (o.a == a && p == o.p)
				return i - o.i;
			if (o.a == a)
				return p - o.p;
			return o.a - a;
		}

	}
}

Measured memory_bytes: 21204
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i];}cout<<endl;
#define pprint(A,m,n) rep(j,0,m){print(A[j],n);}
const long mod=1e9+7;
const int size=1e5;
const int INF=1e9;
int main(){
	int N;string s;cin>>N>>s;
	s="A"+s;int count=0;
	rep(i,1,N+1){
		if(s[i]!=s[i-1]) count++;
	}cout<<count<<endl;
}

Measured memory_bytes: 512
figs = [
  [[1, 0], [0, 1], [1, 1]],	# A
  [[0, 1], [0, 2], [0, 3]],	# B
  [[1, 0], [2, 0], [3, 0]],	# C
  [[0, 1], [-1, 1], [-1, 2]],	# D
  [[1, 0], [1, 1], [2, 1]],	# E
  [[0, 1], [1, 1], [1, 2]],	# F
  [[1, 0], [0, 1], [-1, 1]]	# G
]

names = %w(A B C D E F G)

### main

cont = true

while cont
  pl = []
  ln = 0

  while ! (line = gets).nil? && line != "\n"
    pl.push line.chop.split("").map{|s| s.to_i}
  end
  #p pl

  cont &&= ! line.nil?

  x = y = 0
  while pl[y][x] == 0
    x += 1
    if x > 7
      x = 0
      y += 1
    end
  end

  ans = nil

  for i in (0...figs.length)
    f = figs[i]

    for v in f
      x0 = x + v[0]
      y0 = y + v[1]
      found = true

      if (x0 < 0 || x0 > 7 || y0 < 0 || y0 > 7 ||
          pl[y0][x0] == 0)
        found = false
        break
      end
    end

    if found
      ans = i
      break
    end
  end

  puts names[ans]
end

Measured memory_bytes: 6132
#include <stdio.h>

int main(void)
{
int a,b;
scanf("%d %d",&a,&b);
if(a < b){
printf("a < b\n");
}
else if(a > b){
printf("a > b\n");
}
else if(a == b){
printf("a == b\n");
}
return 0;
}

Measured memory_bytes: 580
// Copyright 2020 yaito3014
#include <bits/stdc++.h>

int main() {
  using namespace std;
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, m, s, t;
  cin >> n >> m >> s >> t, --s, --t;
  struct Edge {
    int to, yen, snuuk;
  };
  vector<deque<Edge>> graph(n);
  for (int i = 0; i < m; ++i) {
    int u, v, a, b;
    cin >> u >> v >> a >> b, --u, --v;
    graph[u].push_back(Edge{v, a, b});
    graph[v].push_back(Edge{u, a, b});
  }
  using ll = long long;
  using P = pair<ll, int>;
  using pque = priority_queue<P, vector<P>, greater<P>>;
  constexpr ll INF = numeric_limits<ll>::max();
  vector<ll> yen_memo(n, INF), snuuk_memo(n, INF);
  pque pq;
  yen_memo[s] = 0;
  pq.emplace(0, s);
  while (!pq.empty()) {
    ll cost;
    int v;
    tie(cost, v) = pq.top();
    pq.pop();
    for (const auto& e : graph[v]) {
      if (yen_memo[e.to] <= cost + e.yen) continue;
      yen_memo[e.to] = cost + e.yen;
      pq.emplace(cost + e.yen, e.to);
    }
  }
  snuuk_memo[t] = 0;
  pq.emplace(0, t);
  while (!pq.empty()) {
    ll cost;
    int v;
    tie(cost, v) = pq.top();
    pq.pop();
    for (const auto& e : graph[v]) {
      if (snuuk_memo[e.to] <= cost + e.snuuk) continue;
      snuuk_memo[e.to] = cost + e.snuuk;
      pq.emplace(cost + e.snuuk, e.to);
    }
  }
  constexpr ll INITIAL_YEN = 1'000'000'000'000'000;
  vector<ll> ans(n, 0);
  for (int i = n; i > 0; --i) {
    ans[i - 1] = INITIAL_YEN - yen_memo[i - 1] - snuuk_memo[i - 1];
    if (i < n) ans[i - 1] = max(ans[i - 1], ans[i]);
  }
  for (const auto& e : ans) cout << e << '\n';
}


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

using namespace std;
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
#define EPS (1e-5)
#define bit(n,k) ((n>>k)&1)
const ll Mod = 1000000007;
const ll mod = 998244353;
struct H {
	ll x, y;
	bool operator<(const H& b) const {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H& b) const {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H& b) const { return x == b.x && y == b.y; }
	bool operator!=(const H& b) const { return (*this) != b; }
};
struct P {
	ll pos, cost;
	bool operator<(const P& b) const { return cost < b.cost; }
	bool operator>(const P& b) const { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E& b) const { return cost < b.cost; }
	bool operator>(const E& b) const { return cost > b.cost; }
};
template<typename T, typename U>
void chmin(T& a, U b) {
	if (a > b) a = b;
}
template<typename T, typename U>
void chmax(T& a, U b) {
	if (a < b) a = b;
}
template<typename T>
T max_0(T a) {
	if (a < 0) return 0;
	return a;
}
template<typename T>
T min_0(T a) {
	if (a > 0) return 0;
	return a;
}
ll read() {
	ll u;
	ll k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j % i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
ll bitcount(ll x) {
	int sum = 0;
	for (int i = 0; i < 20; i++)
		if ((1ll << i) & x) sum++;
	return sum;
}
ll fact_[200000];
ll comb(ll x, ll y, ll mod = Mod) {
	if (!fact_[0]) {
		fact_[0] = 1;
		for (int i = 1; i < 200000; i++) {
			fact_[i] = fact_[i - 1] * i % mod;
		}
	}
	if (x < y) return 0;
	return mod_pow(fact_[x], mod, mod) *
		mod_pow(fact_[x - y], mod - 2, mod) % mod *
		mod_pow(fact_[y], mod - 2, mod) % mod;
}//xCy
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
int n;
E a[200000];
struct A {
	int to, num;
};
vector<A>e[200000];
signed main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> a[i].from >> a[i].to;
		e[a[i].from].push_back(A{ a[i].to, i });
		e[a[i].to].push_back(A{ a[i].to, i });
	}
	queue<int>q;
	q.push(1);
	int ans = 0;
	while (!q.empty()) {
		int t = q.front(); q.pop();
		int r = 0, g = 1;
		for (int i = 0; i < e[t].size(); i++) {
			r = max(r, a[e[t][i].num].cost);
		}
		for (int i = 0; i < e[t].size(); i++) {
			if (a[e[t][i].num].cost == 0) {
				if (g == r) g++;
				ans = max(ans, g);
				a[e[t][i].num].cost = g++;
				q.push(e[t][i].to);
			}
		}
	}
	cout << ans << endl;
	for (int i = 1; i < n; i++) {
		cout << a[i].cost << endl;
	}
}

Measured memory_bytes: 15872
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int a,b;
    cin>>a>>b;
    if(a == b){
        cout<<a*2<<endl;
    }
    else{
    int x = max(a,b);
    cout<<x*2-1<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.Random;
import java.util.Scanner;

public class Main {
    static int d = 365;
    static int[] c = new int[26];
    static int[][] s = new int[d][26];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Random random = new Random();
        d = sc.nextInt();
        for (int i=0;i<26;i++){
            c[i]=sc.nextInt();
        }
        for (int i=0;i<d;i++){
            for (int j=0;j<26;j++){
                s[i][j]=sc.nextInt();
            }
        }
        int[] t = new int[d];
        for (int i=0;i<d;i++)t[i]=sc.nextInt()-1;
        int m = sc.nextInt();
        long[] ans = new long[m];
        for (int i=0;i<m;i++){
            t[sc.nextInt()-1]=sc.nextInt()-1;
            ans[i]=function(t);
        }
        for (int i=0;i<m;i++)System.out.println(ans[i]);
    }
    static long function(int[] contest){
        long satisfaction = 0;
        int[] interval = new int[26];
        for (int i=0;i<d;i++){
            satisfaction+=s[i][contest[i]];
            for (int j=0;j<26;j++)interval[j]++;
            interval[contest[i]]=0;
            for (int j=0;j<26;j++)satisfaction-=c[j]*interval[j];
        }
        return  satisfaction;
    }
}


Measured memory_bytes: 71596
#include <bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
#define ll long long
const ll mod = 1000000007;


int main() {
int a,b;
cin>>a>>b;
cout<<max(0, a-2*b)<<endl;

    return 0;
}


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

int n, A[20];
int solve(int, int);

int main(){
  int q, m, ans;
  int i;
  scanf("%d",&n);
  for(i = 0; i < n; i++)scanf("%d",&A[i]);
  scanf("%d",&q);
  for(i = 0; i < q; i++){
    scanf("%d",&m);
    ans = solve(0, m);
    if(ans == 1)printf("yes\n");
    else printf("no\n");
  }
  return 0;
}

int solve(int i, int m){
  int result;
  if(m == 0)return 1;
  if(i >= n)return 0;
  result = solve(i + 1, m) || solve(i + 1, m - A[i]);
  return result;
}



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

using namespace std;
int main(){
 string s, ans;
 cin >> s;
 int cnt=0;

 for(int i = 0 ; i < s.length() ; i++){
   if(s[i] == '0'){
    ans[cnt] = '0';
    cnt++;
  }else if(s[i] == '1'){
   ans[cnt] = '1';
    cnt++;
  }else if(cnt !=0){
    cnt--;
    ans[i] = ' ';
    }
  }

  for(int i = 0 ; i < cnt ; i++){
    cout << ans[i] ;
  }
  cout << endl;
}


Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
char X[200005];
int main() {
	int n;
	scanf("%d%s", &n, X);
	int bits = 0;
	for (int i = n - 1; i >= 0; --i) {
		bits += X[i] == '1';
	}
	int vp = 0, vm = 0;
	int plus = bits + 1, minus = bits - 1;
	vector<int> dm(n), dp(n);
	for (int i = 0; i < n; ++i) {
		vp = (vp * 2 + X[i] - '0') % plus;
		if (minus) vm = (vm * 2 + X[i] - '0') % minus;
	}
	for (int i = n - 1; i >= 0; --i) {
		if (minus) dm[i] = i == n - 1 ? 1 % minus : (dm[i + 1] * 2) % minus;
		dp[i] = i == n - 1 ? 1 % plus : (dp[i + 1] * 2) % plus;
	}
	function<int(int)> f = [&](int v) {
		if (!v) return 0;
		int b = __builtin_popcount(v);
		return 1 + f(v % b);
	};
	for (int i = 0; i < n; ++i) {
		if (X[i] == '1') {
			if (!minus) printf("0\n");
			else printf("%d\n", 1 + f((vm - dm[i] + minus) % minus));
		} else {
			printf("%d\n", 1 + f((vp + dp[i]) % plus));
		}
	}
}


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

const int di[] = {1, 0, -1, 0};
const int dj[] = {0, 1, 0, -1};

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

    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];

    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    const int INF = 1001001001;
    vector<vector<int>> dist(h, vector<int>(w, INF));
    dist[0][0] = 0;

    while(!q.empty()){
        int i = q.front().first;
        int j = q.front().second;
        q.pop();

        rep(dir, 4){
            int ni = i + di[dir];
            int nj = j + dj[dir];

            if(ni<0 || ni>=h || nj<0|| nj>=w) continue;
            if(s[ni][nj] == '#') continue;
            if(dist[ni][nj] != INF) continue;

            dist[ni][nj] = dist[i][j] + 1;
            q.push(make_pair(ni, nj));
        }
    }

    if(dist[h-1][w-1] == INF){
        cout << -1 << endl;
        return 0;
    }

    vector<vector<bool>> is_fixed(h, vector<bool>(w, false));
    is_fixed[0][0] = true;
    is_fixed[h-1][w-1] = true;
    int i = h-1;
    int j = w-1;
    while(!(i==0 && j==0)){
        rep(dir, 4){
            int ni = i + di[dir];
            int nj = j + dj[dir];

            if(ni<0 || ni>=h || nj<0|| nj>=w) continue;
            if(dist[ni][nj] == INF) continue;
            if(dist[ni][nj] != dist[i][j] - 1) continue;

            is_fixed[ni][nj] = true;
            i = ni;
            j = nj;
        }
    }

    int res = 0;
    rep(i, h) rep(j, w){
        if(!is_fixed[i][j] && s[i][j]=='.') ++res;
    }

    cout << res << endl;

    return 0;
}

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

int main(){
 int A, B, C, D, L, a, b, c, d;
 scanf("%d", &L);
 scanf("%d", &A);
 scanf("%d", &B);
 scanf("%d", &C);
 scanf("%d", &D);
 a = ceil((double)A / C);
 b = ceil((double)B / D);
 if(a < b){
  c = b;
 }
 if(b < a){
  c = a;
 }
 d = L - c;
 printf("%d\n", d);
 return 0;
}
 
 
 

Measured memory_bytes: 600
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
XY = [tuple(map(int,input().split())) for i in range(n)]
for jun in itertools.permutations(range(n),n):
  cost = 0
  for i in range(1,n):
    cost += math.sqrt((XY[jun[i]][0]-XY[jun[i-1]][0])**2+(XY[jun[i]][1]-XY[jun[i-1]][1])**2)
  ans += cost
print(ans/math.factorial(n))


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

int main(){
    string S;
    cin >> S;
    sort(S.begin(), S.end());
    if(S[0] == S[1] && S[2] == S[3] && S[0] != S[2]){
        cout << "Yes" << "\n";
    }
    else{
        cout << "No" << "\n";
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main() {
	int n; string s, t;
	cin >> n >> s >> t;
	for (int i = n; i >= 0; i--) {
		if (s.substr(n - i, i) == t.substr(0, i)) {
			cout << 2 * n - i << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
N= int(input())
A = list(map(int, input().split()))
A.sort()
res = A[-1]
if N % 2 == 0:
    res += sum(A[int(N/2):-1]) * 2
else:
    res += sum(A[int(N/2)+1:-1]) * 2 + A[int(N/2)]
print(res)

Measured memory_bytes: 31444
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;

int solve(int A, int B, int N){
  int res = 0;
  A %= B;
  REP(i, N){
    A *= 10;
    res += A / B;
    A %= B;
  }
  return res;
}

int main() {
  int A, B, N;
  while(cin >>A){
    cin >>B >>N;
    cout <<solve(A, B, N) <<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int a[214514];
signed main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	if(n==1)cout<<a[0]<<endl;
	else if(n%2==0){
		for(int i=n-1;i>=1;i-=2)cout<<a[i]<<" ";
		for(int j=0;j<n-2;j+=2)cout<<a[j]<<" ";
		cout<<a[n-2]<<endl;
	}
	else {
		for(int i=n-1;i>=0;i-=2)cout<<a[i]<<" ";
		for(int j=1;j<=n-4;j+=2)cout<<a[j]<<" ";
		cout<<a[n-2]<<endl;
	}
}

Measured memory_bytes: 3712
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
using namespace std;
typedef long long int ll;

#define MOD 998244353


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

bool primeNumber(ll n){
    if(n < 2) return false;
    else{
        for(ll i = 2; i * i <= n; i++){
            if(n % i == 0) return false;
        }
        return true;
    }
}
  
  

int main(){
    ll r;
    cin >> r;
    
    if (1200 > r)cout << "ABC" << endl;
    else if (2800 > r)cout << "ARC" << endl;
    else cout << "AGC" << endl;
    
    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner  ;
public class Main{
public static void main(String[]args){

Scanner sc = new Scanner(System.in);

for(int i =1;;i++){
    int x = sc.nextInt();
    if(x == 0){
        break;
    }
    System.out.printf("Case %d: %d\n",i,x);
  
   
}
}
}



Measured memory_bytes: 64464
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Math;

class P
{
  static int[] Input(){
    return Console.ReadLine().Split().Select(int.Parse).ToArray();
  }

  static int[][] Input2(int n){
    int[][] X = new int[n][];
    for(int i = 0; i < n; i++){
      X[i] = Input();
    }
    return X;
  }

  static void Main()
  {
    int[] NH = Input();
    List<int> X = new List<int>();
    List<int> Y = new List<int>();
    for(int i = 0; i < NH[0]; i++){
      int[] XY = Input();
      X.Add(XY[0]);
      Y.Add(XY[1]);
    }
    Y.Sort();
    Y.Reverse();
    int mx = X.Max();
    int r = 0;
    foreach(int y in Y){
      if (y < mx)break;
      NH[1] -= y;
      r += 1;
      if (NH[1] <= 0) break;
    }
    if (NH[1] > 0)r += (NH[1] + mx -1) / mx;
    Console.WriteLine(r);
  }
}


Measured memory_bytes: 19392
/* tempate
 *
 *
 */

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;


#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int (i)=(n); (i)>=(0); (i)--)
#define SIZE(x) ((int)(x).size())
#define GCD(a, b) int gcd(int a,int b){return b?gcd(b,a%b):a;}
#define QP(a, b) int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define all(v) (v).begin(),(v).end()


template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
template<typename A, size_t N, typename T>
void FILL(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

typedef vector<int, int> vint;
typedef pair<int,int> pint;
typedef vector<pint>vpint;
typedef long long ll;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1LL << 60;
const ll MOD = 1000000007LL;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    vector<ll> a(n);
    vector<ll> b(n);
    rep(i, n) cin >> a[i];
    for(ll i = n - 1; i >= 0; i--){
        if(i == n - 1) continue;
        if(a[i] >= a[i + 1]){
            b[i] = b[i + 1] + 1;
        }
        else b[i] = 0;
    }
    sort(all(b));
    cout << b[n - 1];
    cout << endl;
    return 0;
}


Measured memory_bytes: 1792
import sys
readline = sys.stdin.readline

N = int(readline())
C = readline().rstrip()

ans = 0
left = 0
right = N - 1

while left < right:
  # Wを見つけるまで左からカーソル移動
  if C[left] == "R":
    left += 1
    continue
  while left < right and C[right] == "W":
    right -= 1
  if left == right:
    break
  ans += 1
  left += 1
  right -= 1
  
print(ans)

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


void solve(long long N, long long K){
    cout << (K>1 ? N-K : 0) << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    solve(N, K);
    return 0;
}


Measured memory_bytes: 256
def main():
    x, n = map(int, input().split())
    p_lst = list(map(int, input().split()))

    if n == 0:
        minimum = x
    else:
        if x not in p_lst:
            minimum = x

        else:
            lst = []
            flag = False
            x1 = x
            x2 = x

            while True:
                x1 += 1
                x2 -= 1

                if x1 not in p_lst:
                    lst.append(x1)
                    flag = True
                if x2 not in p_lst:
                    lst.append(x2)
                    flag = True

                if flag:
                    break

            minimum = min(lst)

    print(minimum)


if __name__ == '__main__':
    main()

Measured memory_bytes: 9108
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>
#include <utility>


using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// const ll INF = 1LL <<60;
// const int INF = 10000;

//最大公約数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

ll lmax(ll s,ll t){
  if(s>t){
    return s;
  }
  else{
    return t;
  }
}

ll lmin(ll s,ll t){
  if(s<t){
    return s;
  }
  else{
    return t;
  }
}

long long modpow(long long res,long long a, long long n, long long mod) {
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
// ここから開始
int main(){
  ll n,a,b;
  cin>>n>>a>>b;
  ll ans = 0;
  if(a>b) ans = 0;
  else if(n==1){
    if(a!=b) ans=0;
    else ans=1;
  } 
  else{
    ans=(b-a)*(n-2)+1;
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
typedef long long i64;
int main(){
    int a,b;
    cin >> a >> b;
    cout << ((b-a)+1)*(b-a)/2-b << endl;
    return 0;
}


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

using namespace std;
#define int long long
typedef pair <int, int> ii;

const int N = 1e5 + 5;
int n, d[N], subSize[N], f[N], g[N], tot;
map <int, int> ind;
vector <int> adj[N];

void dfs(int u, int pre, int s) {
	g[u] = s;
	for (int v : adj[u]) {
		if (v == pre) continue;
		tot += subSize[v];
		dfs(v, u, s - 2 * subSize[v] + n);
	}
}

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

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> d[i];
		f[i] = d[i];
		ind[d[i]] = i;
	}
	vector <ii> res; res.clear();
	sort(d + 1, d + 1 + n);
	for (int i = 1; i <= n; ++i)
		subSize[i] = 1;
	for (int i = n; i >= 2; --i) {
		int v = ind[d[i]];
		int du = d[i] + 2 * subSize[v] - n;
		if (ind.find(du) == ind.end()) {
			cout << -1 << endl;
			return 0;
		}
		int u = ind[du];
		if (u == v) {
			cout << -1 << endl;
			return 0;
		}
		subSize[u] += subSize[v];
		adj[u].push_back(v);
		adj[v].push_back(u);
		res.push_back({u, v});
	}
	dfs(ind[d[1]], -1, 0);
	for (int i = 1; i <= n; ++i) if (f[i] != g[i] + tot) {
		cout << -1 << endl;
		return 0;
	}
	for (ii d : res)
		cout << d.first << ' ' << d.second << endl;

	return 0;
}

Measured memory_bytes: 20208
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<int,int>;
/* ちゃんと考えてわかって実装 */

int main(void){
    string s;
    cin >> s;
    int n = s.length();
    int a = -1, b = -1;
    for(int i=0; i<n-2; i++){
        if(s[i] == s[i+1]){
            a = i + 1;
            b = i + 2;
            break;
        }
        else if(s[i] == s[i+2]){
            a = i + 1;
            b = i + 3;
            break;
        }
    }
    if(s[n-2] == s[n-1]){
        a = n-1;
        b = n;
    }
    cout << a << " " << b << endl;
    return 0;
}

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

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }

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

  string s;
  int ans = 0;
  cin >> s;
  rep(i, s.size()) {
    if (i % 2 == 0) {
      if (s[i] == 'p')
        ans--;
    }
    else
      if (s[i] == 'g')
        ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 512
import java.io.IOException;
import java.util.Scanner;

class Main {

	static long changecount = 0;
   public static void main(String args[]) throws IOException{

	   Scanner sc = new Scanner(System.in);

	   int n = sc.nextInt();


	   int[] A = new int[n];
	   for(int i = 0;i < n; i++){
		   A[i] = Integer.parseInt(sc.next());
	   }

	   int q = partition(A , 0 , n-1);
	   for(int i = 0;i < n; i++){

		   //System.out.print(A[i]);

		   if(i != q){
		      System.out.print(A[i]);
		   }else{
			   System.out.print( "["+ A[i]+"]" );
		   }


		   if(i < n-1 ){
			   System.out.print(" ");
		   }
	   }
	   System.out.println("");
	   sc.close();
   }

   public static int partition(int[] A, int p, int r){

	  int i = p-1;
      int x = A[r];



      for(int j = p; j < r; j++){

    	  if(A[j] <= x){
    		  i++;
    		  int tmp = A[i];
    		  A[i] = A[j];
    		  A[j] = tmp;
    	  }

      }


      int tmp = A[i+1];
	  A[i+1] = A[r];
	  A[r] = tmp;

	  return i+1;
   }


}

Measured memory_bytes: 73704
n = gets.to_i
vlist = []
n.times do
  u, k, *v = gets.split.map { |i| i.to_i }
  vlist[u-1] = v
end

q = []
q.push 0
d = Array.new(n, nil)
d[0] = 0

while !q.empty?
  u = q.shift
  vlist[u].each do |i|
    unless d[i-1]
      d[i-1] = d[u] + 1
      q.push i-1
    end
  end
end

d = d.map { |i| i ? i : -1 }
d.each_with_index do |i, idx|
  puts "#{idx+1} #{i}"
end

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

int main() {
    int a,b,c,result;
    cin >> a >> b >> c;
    
    result=0;
    for(int i=a;i<=b;i++){
        if(c%i==0)
         result++;
    }

    cout << result << endl;         
    return 0;
}



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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    ll n=s.size(), a, z;
    for(ll i=0 ; i<n ; i++){
        if(s[i] == 'A'){
            a = i;
            break;
        }
    }
    for(ll i=n-1 ; i>=0 ; i--){
        if(s[i] == 'Z'){
            z = i;
            break;
        }
    }
    cout << z - a + 1;
    return 0;
}


Measured memory_bytes: 720
#include <algorithm>
#include <string>
#include <math.h>
#include <vector>
#include <iostream>
using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;
    
    vector<int> A(N), B(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
    }
   
    vector<pair<int, int>> AB(N);
    for (int i = 0; i < N; i++) {
        AB[i] = make_pair(A[i], B[i]);
    }
    sort(AB.begin(), AB.end());
    
    long long result = 0;
    for (int i = 0; i < N; i++) {
        int buy = min(M, AB[i].second);
        result += (long long)buy * AB[i].first;
        M -= buy;
    }
    cout << result << endl;
    
}

Measured memory_bytes: 1792
N, MOD = int(input()), 10**9+7
memo = [{} for i in range(N+1)]

def 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

def dfs(cur, last3):
    #メモ化
    if last3 in memo[cur]:
        return memo[cur][last3]
    #最後までたどり着いた数列
    if cur == N:
        return 1
    #漸化式計算
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Measured memory_bytes: 3872
#include <iostream>
#include<math.h>
using namespace std;


int main() {
	int h,w,i,j;
	char x;
	cin>>h>>w;
	int grid[h][w],agrid[h][w],bgrid[h][w];
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			cin>>x;
			if(x=='.'){
				grid[i][j]=1;
			}
			else{
				grid[i][j]=0;
			}
		}
	}
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			if((i==0)||((j%2==0)&&(i!=h-1))){
				agrid[i][j]=0;
			}
			else{
				agrid[i][j]=1;
			}
			
			if((i==h-1)||((j%2==1)&&(i!=0))){
				bgrid[i][j]=0;
			}
			else{
				bgrid[i][j]=1;
			}
		}
	}
	
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			agrid[i][j]=agrid[i][j]*grid[i][j];
			bgrid[i][j]=bgrid[i][j]*grid[i][j];
		}
	}
	
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			if(agrid[i][j]==0){
				putchar('#');
			}
			else{putchar('.');}
		}
		putchar('\n');
	}
	putchar('\n');
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			if(bgrid[i][j]==0){
				putchar('#');
			}
			else{putchar('.');}
		}
		putchar('\n');
	}
}

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

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

  int sum = 0;
  for (int i = 0; i <= n; i ++) {
    int tmp = 0, x = i;
    while (x > 0) {
      tmp += x % 10;
      x /= 10;
    }
    if (tmp >= a && tmp <= b) {
      sum += i;
    }
  }

  cout << sum << endl;
}


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

typedef pair<int, int> pii;

const int mod = 1e9 + 7;

int exp(int x, int n) {
    int ret = 1;
    while(n) {
        if(n & 1) ret = 1LL * ret * x % mod;
        x = 1LL * x * x % mod;
        n >>= 1;
    }
    return ret;
}
int inv(int x) {
    return exp(x, mod - 2);
}
int fact[500], invf[500];

int comb(int n, int k) {
    return 1LL * fact[n] * invf[k] % mod * invf[n - k] % mod;
}
int H(int n, int k) {
    return comb(n + k - 1, k);
}

int N, K;
string S;
vector<int> R, B;

struct Group {
    vector<int> f;
};
vector<Group> group;
Group tmp;

void dfs(int p, int g, int f) {
    if(p >= N) {
        group.push_back(tmp);
        return;
    }
    if(f) {
        group.push_back(tmp);
    }
    if(max(p + 2*g, p + 2) > N + 1) return;

    dfs(p, g + 1, 0);

    if(max(p + 2*g, p + 2) <= N + 1) {
        tmp.f.push_back(g);
        dfs(max(p + 2*g, p + 2), g, 1);
        tmp.f.pop_back();
    }
}

bool chk(vector<int> &f) {
    vector<int> used(K, 0);
    vector<pii> bpos;

    int pos1 = 0, pos2 = 0;
    for(int i = (int)f.size() - 1; i >= 0; i--) {
        if(f[i] == 0) continue;

        while(pos2 < B.size() && R[pos1] > B[pos2]) pos2++;

        if(pos2 == B.size()) return false;
        bpos.push_back(pii(B[pos2], f[i] - 1));

        used[ R[pos1] ] = 1;
        used[ B[pos2] ] = 1;

        pos1++;
        pos2++;
    }
    for(int i = 0; i < f.size(); i++) {
        if(f[i]) continue;
        
        for(int j = 0; j < K; j++) if(!used[j] && S[j] == 'r') {
            used[j] = 1;
            break;
        }
    }
    
    for(int i = (int)bpos.size() - 1; i >= 0; i--) {
        int need = bpos[i].second;
        int pos = bpos[i].first;

        for(int j = pos + 1; j < K; j++) {
            if(need == 0) break;
            if(!used[j]) {
                need--;
                used[j] = 1;
            }
        }
        if(need) return false;
    }

    return true;
}

int main() {
    fact[0] = 1;
    for(int i = 1; i < 500; i++) {
        fact[i] = 1LL * fact[i - 1] * i % mod;
    }
    for(int i = 0; i < 500; i++) {
        invf[i] = inv(fact[i]);
    }

    cin >> N >> K >> S;

    for(int i = 0; i < S.size(); i++) {
        if(S[i] == 'r') R.push_back(i);
        else B.push_back(i);
    }

    dfs(0, 0, 1);

    int ans = 0;
    for(int g = 0; g < group.size(); g++) {
        vector<int> f = group[g].f;

        int sum = 0;
        int x = 0;
        for(int i = 0; i < f.size(); i++) {
            sum += f[i];

            if(f[i] == 0) x++;
            else x += 2*f[i] - 1;
        }

        if(f.size() > R.size()) continue;
        if(sum + f.size() > K) continue;

        int t = fact[ f.size() ];

        int cnt = 0;
        for(int i = 0; i < f.size(); i++) {
            cnt++;
            if(i == f.size() - 1 || f[i] != f[i + 1]) {
                t = 1LL * t * invf[cnt] % mod;
                cnt = 0;
            }
        }

        t = 1LL * t * H(2*sum + 2*f.size() + 1, N - x - (int)f.size() + 1) % mod;

        if(chk(f)) {
            ans += t;
            ans %= mod;
        }
    }

    cout << ans;
}


Measured memory_bytes: 38952
import math
a, b, h, m = map(int, input().split())

t1 = h * 30
t1 = m / 2 + t1
t2 = m * 6
r = abs(t1 - t2)
if r > 180:
    r = 360 - r
rr = math.cos(math.radians(r))
print(math.sqrt(a*a + b*b - 2*a*b*rr))

Measured memory_bytes: 9512
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,X;
  cin >> N >> X;
  
  vector<int>L(N);
  for (int i = 0; i < N; i++) {
    cin >> L.at(i);
  }
  
  int D = 0;
  int count = 0;
  for (int i = 0; i < N; i++) {
    if (D <= X){
      count++;
    }
    D = D + L.at(i);
    if (i == N-1 && D <= X){
      count++;
    }
  }
  cout << count << endl;
}
    

Measured memory_bytes: 3608
import collections
n, p = list(map(int, input().split()))
a = list(map(int, input().split()))
a2 = [ai%2 for ai in a]
a2 = collections.Counter(a2)

if a2[1] == 0:
  print(2 ** n if p == 0 else 0)
else:
  print( 2 ** (n-1))



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

int main() {
  int s;
  
  cin >> s;
  
  int joui2 = s/100;
  int kai2 = s-(joui2*100);
  
  int flag=0;
    
  if(joui2>0&&joui2<=12) //MMYY
    flag +=1;
  if(kai2>0&&kai2<=12) //YYMM
    flag +=2;
    
  if(flag == 3)
    cout << "AMBIGUOUS";
  if(flag == 2)
    cout << "YYMM";
  if(flag == 1)
    cout << "MMYY";
  if(flag == 0)
    cout << "NA";
  
}

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

#define ll long long
#define ldb long double
#define rep(i, x, n, j) for(int i=x;i<(int)n;i+=j)
#define F first
#define S second
#define per(i, x, n, j) for(int i=(int)n-1;i>=0;i-=j)
#define all(v) v.begin(),v.end()
#define sz(a) (int)a.size()

const int N = 2000100;
const ll MOD = 1e9+7;
const ll inf = 1e18+5;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;

int _;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	long long n; cin >> n;
	long long a[n];
	rep(i,0,n,1) cin >> a[i];
	long long xr = 0;
	for(int i=0; i<n; ++i) xr ^= a[i];
	rep(i,0,n,1){
		long long ans = xr^a[i];
		cout << ans << " ";
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 5144
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	am := make(map[int]int)
	var a int
	for i := 0; i < n; i++ {
		fmt.Scan(&a)
		am[a]++
	}

	k := len(am)
	if k%2 == 1 {
		fmt.Println(k)
	} else {
		fmt.Println(k - 1)
	}
}


Measured memory_bytes: 7936
#include <iostream>
#include <map>

using namespace std;

int main()
{
    std::string s;
    cin >> s;
#if 0
    int a[n];
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
#endif

    std::map<std::string, int> m;
    m["SUN"] = 7;
    m["MON"] = 6;
    m["TUE"] = 5;
    m["WED"] = 4;
    m["THU"] = 3;
    m["FRI"] = 2;
    m["SAT"] = 1;
    
    cout << m[s] << endl; 
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std; 
int gcd(int a, int b) {
    if (b == 0) return a; 
    return gcd(b, a%b);
}
int main() {
    ios::sync_with_stdio(false);

    int n; cin >> n; 
    int a[100010];

    for (int i = 1; i <= n; i++) cin >> a[i];
    // cout << gcd(5, 3);
    // return 0; 
    
    // prefix 
    int prefix[100010];
    for (int i = 1; i <= n; i++) {
        prefix[i] = gcd(prefix[i-1], a[i]);
    }
    // for (int i = 1; i <= n; i++) {
    //     cout << prefix[i] << "  ";
    // }
    // suffix
    int suffix[100010];
    for (int i = n; i >= 1; i--) {
        suffix[i] = gcd(suffix[i+1], a[i]);
    }
    // cout << endl; 
    // // for (int i = 1; i <= n; i++) {
    // //     cout << suffix[i] << "  ";
    // // }

    int best = 1; 
    for (int i = 1; i <= n; i++) {
        int val = gcd(prefix[i-1], suffix[i+1]);
        if  (val > best) best = val; 
    }

    cout << best << endl; 

    
}

Measured memory_bytes: 1408