akhauriyash/Code-Regression huggingface dataset:
import itertools
N, M, Q = map(int, input().split())
abcd_lis = []
for i in range(Q):
	abcd_lis.append(list(map(int, input().split())))
lis = [i+1 for i in range(M)]

lis = list(itertools.combinations_with_replacement(lis, N))
maxi = 0
for i in lis:
  count = 0
  for j in range(Q):
    idx1 = abcd_lis[j][0]-1
    idx2 = abcd_lis[j][1]-1
    if i[idx2]-i[idx1] == abcd_lis[j][2]:
      count += abcd_lis[j][3]
  if maxi < count:
    maxi = count
print(maxi)

Measured memory_bytes: 85052
#pragma region includes, macros
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <map>
#include <set>
#include <list>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef int64_t i64;
typedef pair<i64, i64> P;

template<class T>
const T INF = numeric_limits<T>::max();
template<class T>
const T SINF = numeric_limits<T>::max() / 10;
static const i64 MOD = 1000000007;

//int dx[5] = {-1,0,0,0,1}, dy[5] = {0,-1,0,1,0};
//int dx[8] = {-1,0,1,1,1,0,-1,-1}, dy[8] = {1,1,1,0,-1,-1,-1,0};
//int dx[9] = {-1,0,1,1,1,0,-1,-1,0}, dy[9] = {1,1,1,0,-1,-1,-1,0,0};

struct edge {
    i64 from, to, cost;
    edge(i64 to, i64 cost) : from(-1), to(to), cost(cost) {}
    edge(i64 src, i64 to, i64 cost) : from(src), to(to), cost(cost) {}
};

// http://beet-aizu.hatenablog.com/entry/2018/04/08/145516
template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
    for (auto& e : t) fill_v(e, v);
}
//

#pragma endregion

int dx[4] = { 0,1,0,-1 }, dy[4] = { -1,0,1,0 };

vector< int64_t > divisor(int64_t n) {
    vector< int64_t > ret;
    for (int64_t i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(begin(ret), end(ret));
    return (ret);
}

int main() {
    i64 h, w;
    cin >> h >> w;
    vector<vector<int>> dp(10, vector<int>(10, 0));
    vector<string> s(h);
    for(int i = 0; i < h; ++i){
        cin >> s[i];
    }
    int l = 0;
    int r = -1;
    for(int i = 0; i < h; ++i){
        for(int j = 0; j < l; ++j){
            if(s[i][j] == '#'){
                cout << "Impossible" << endl;
                return 0;
            }
        }
        for(int j = l; j <= w; ++j){
            if(j == w) r = j - 1;
            else if(s[i][j] == '.'){
                r = j - 1;
                break;
            }
        }
        for(int j = r + 1; j < w; ++j){
            if(s[i][j] == '#'){
                cout << "Impossible" << endl;
                return 0;
            }
        }
        if(l > r){
            cout << "Impossible" << endl;
            return 0;
        }else{
            l = r;
        }
    }
    if(r == w - 1)cout << "Possible" << endl;
    else cout << "Impossible" << endl;
}

// n = am + b (a == b)
// n = a(m + 1) 1, 2, 4, 8


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define mp  make_pair
#define pb  push_back
void c_p_c(){
	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
}
void solve(){
    int n;
    cin>>n;
    int a=0,b=0,c=0,d=0;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        if(s=="AC"){
            a++;
        }
        else if(s=="WA"){
            b++;
        }
        else if(s=="TLE"){
            c++;
        }
        else if(s=="RE"){
            d++;
        }
    }
    cout<<"AC x "<<a<<endl<<"WA x "<<b<<endl<<"TLE x "<<c<<endl<<"RE x "<<d<<endl;
    return;
}
int32_t main(){
    c_p_c();
    int t;
    t=1;
    //cin>>t;
    while(t--){
       solve(); 
    }
	return 0;
}


Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  int N;
  cin >> N >> S;
  
  for(int i = 0; i < S.length(); i++){
    int x = S.at(i) - 'A';
    x = (x + N) % 26;
  	S.at(i) = 'A' + x;
    cout << S.at(i);
  }
  cout << endl;
}

Measured memory_bytes: 256
import numpy as np
N = int(input())
A = np.array(tuple(map(int, input().split())), dtype=np.int64) - np.arange(N) - 1
median = np.median(A)
if int(median * 2) & 1:
    print(int(min(np.abs(A - median + 0.5).sum(), np.abs(A - median - 0.5).sum())))
else:
    print(int(np.abs(A - median).sum()))

Measured memory_bytes: 34396
N, M = gets.split.map(&:to_i)
ABCs = readlines.map{|l| a, b, c = l.split.map(&:to_i); [a, b, -c]}
Inf = 1 << 50

d = Array.new(N + 1, Inf)
d[1] = 0
(N - 1).times do
  ABCs.each do |a, b, c|
    d[b] = [d[b], d[a] + c].min
  end
end
n = Array.new(N + 1, false)
N.times do
  ABCs.each do |a, b, c|
    next if d[a] == Inf
    if d[b] > d[a] + c
      d[b] = d[a] + c
      n[b] = true
    end
    n[b] = true if n[a] == true
  end
end
puts n[N] ? 'inf' : -d[N]

Measured memory_bytes: 2172
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
        a: usize,
        b: usize
    }
    println!("{}", (b + a - 3) / (a - 1));
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using ll = long long;
#define int long long
#define itn int
signed main(void){
    string s; cin>>s;
    int n = s.size();
    char mae = '?';
    int ans = 0;
    for(int i=0;i<n;i++){
        if(i==n-1&& mae == s[i]) break;
        if(mae != s[i]) {ans++; mae = s[i];}
        else {ans++; i++; mae = '?';}
    }
    cout<<ans<<endl;
}


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

#define lld long long
#define pi pair<int,int>
#define pl pair<lld,lld>
#define mem0(x) memset(x,0,sizeof(x))
#define fillnum(x,n) fill(begin(x),end(x),n)
#define asort(x) sort(x.begin(),x.end())
#define dsort(x,t) sort(x.begin(),x.end(),greater<t>())

int main() {
    lld N;
    cin >> N;
    if(N >= 30){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3592
n = int(input())
a = list(map(int, input().split()))

nums = [0]*(max(a)+1)
for i in a: nums[i] += 1
ans = sum(nums[:3])
t = sum(nums[:3])
for i in range(len(nums)-3):
  t = t + nums[i+3] - nums[i]
  if ans < t: ans = t
print(ans)

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

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

    string s;
    cin >> s;

    int ans = 0;
    for (int i = 1; i < s.size(); i++) {
        if (s[i - 1] != s[i]) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 1100
#include <stdio.h>

void swap(int *a, int *b);

int main(void){
  int n, a, b, c;
  int i;

  scanf("%d", &n);
  for(i = 0; i < n; i++){
    scanf("%d%d%d", &a, &b, &c);
    if(a < b){
      swap(&a, &b);
    }
    if(a < c){
      swap(&a, &c);
    }
    if(a*a == b*b + c*c){
      printf("YES\n");
    }else{
      printf("NO\n");
    }
  }
  return 0;
}


void swap(int *a, int *b){
  int temp;

  temp = *a;
  *a = *b;
  *b = temp;
}

Measured memory_bytes: 580
import Control.Applicative ((<$>))
import Control.Monad (forM_)

main = do
  [n,m] <- map read.words <$> getLine :: IO [Int]
  coords <- map (map read.words).lines <$> getContents :: IO [[Int]]
  let ablist = take n coords
      cdlist = zip (drop n coords) [1..m]
  forM_ ablist $ \[a,b] -> do
    let (_,p) = minimum [(abs(a-head x)+abs(b-(head.tail)x),i)|(x,i)<-cdlist]
    print p


Measured memory_bytes: 1020
import math


def main():
    inputs = input().split()
    inputs = [int(i) for i in inputs]

    a = inputs[0]
    b = inputs[1]

    g = n = gcd(a, b)
    d = {}

    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i:
            continue
        d[i] = i
        while n % i == 0:
            n /= i

    if n != 1:
        d[n] = n

    print(len(d) + 1)


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <algorithm>
//#include <vector>

using namespace std;

#define MAX(x,y) (x>y?x:y)
#define MIN(x,y) (x<y?x:y)
#define ABS(x) (x>0?x:-(x))
#define INF 1000000000

void swap(int* a, int* b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void swap2(double* a, double* b)
{
	double tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

int gcd(int a, int b)
{
	if (a < b)
		swap(&a, &b);

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

int lcm(int a, int b)
{
	return a * b / gcd(a, b);
}


int main()
{
	int N, K, R;
	int b, c;
	int count = 0;
	int A[100000];

	
	scanf("%d%d", &N, &K);

	int a = 1;
	while (1)
	{
		if (N < a)
			break;

		count++;

		a *= K;
	}

	printf("%d", count);
}

Measured memory_bytes: 888
#include<iostream>
#include<algorithm> 
#include<cstdio>
#include<cctype>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<unordered_map>
#include<map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int N = 105;
const double pi = acos(-1.0);
const ll mod = 1e9+7;
void init(){
	ios::sync_with_stdio(false);cin.tie(0);
} 
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
int main()
{
	int ans=0,cnt[2020]={0};
	string a;cin>>a;
	reverse(a.begin(),a.end());
	int r=0,c=1;cnt[0]=1;
	for(int i=0;i<a.length();i++)
	{
		r=r+c*(a[i]-'0');
		c=c*10%2019;
		r=r%2019;
		ans+=cnt[r]++;
	}
	cout<<ans;
	return 0;
}

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

int main() {
  int a,b,c,d;
  cin >> a >> b >> c >> d;

  if (((int)fabs(a-b)<=d && (int)fabs(b-c)<=d) || (int)fabs(a-c)<=d){
    cout << "Yes" << endl;
  }else cout << "No" << endl;
}


Measured memory_bytes: 256
_,q=gets.split.map &:to_i
r=$<.map &:split
s=0
while r!=[]
t=r[0][1].to_i
s+=q
if 0<t-=q
r[0][1]=t
r.rotate!
else
puts"#{r.shift[0]} #{s+=t}"
end
end

Measured memory_bytes: 19336
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
long long a[1001];
int main(){
int n;
cin>>n;
a[0]=2;
a[1]=1;
for (int i=2;i<=n;i++)
    a[i]=a[i-1]+a[i-2];
cout<<a[n]<<endl;
return 0;
}


Measured memory_bytes: 256
N = 4
A = list(input())
total = 0

for bit in range(1 << (N-1)):
  f = A[0]
  for i in range(N-1):
    if bit & (1 << i):
      f += '+'
    else:
      f += '-'
    f += A[i+1]
  total = eval(f)
  if total == 7:
    print(f+'=7')
    break
    
    
  

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;


int main() {
	int N, K;
	cin >> N >> K;
	vector<PII> pairs;
	vector<int> edge[3000];
	for(int i=0; i<N-1; i++) {
		int a,b;
		cin >> a >> b;
		a--;b--;
		edge[a].push_back(b);;
		edge[b].push_back(a);
		pairs.push_back(PII(a,b));
	}
	
	int ans = 2000000;
	
	if(K%2==0) {
	for(int st=0; st<N; st++) {
		queue<int> qu;
		vector<int> memo(N,-1);
		qu.push(st); 
		memo[st] = 0;
		while(!qu.empty()) {
			int cur = qu.front();
			qu.pop();
			for(int i=0; i<edge[cur].size(); i++) {
				int next = edge[cur][i];
				if(memo[next] != -1) continue;
				memo[next] = memo[cur]+1;
				qu.push(next);
			}
		}
		int num = 0;
		for(int i=0; i<N; i++) {
			if(memo[i] > K/2) num++; 
			
		}
		ans = min(ans, num);
		
	}
	}
	else {
	for(int t=0; t<pairs.size(); t++) {
		queue<int> qu;
		vector<int> memo(N,-1);
		qu.push(pairs[t].first); qu.push(pairs[t].second);
		memo[pairs[t].first] = 0;
		memo[pairs[t].second] = 0;
		while(!qu.empty()) {
			int cur = qu.front();
			qu.pop();
			for(int i=0; i<edge[cur].size(); i++) {
				int next = edge[cur][i];
				if(memo[next] != -1) continue;
				memo[next] = memo[cur]+1;
				qu.push(next);
			}
		}
		int num = 0;
		for(int i=0; i<N; i++) {
			if(memo[i] > K/2) num++; 
			
		}
		ans = min(ans, num);
	}
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 512
#include<iostream>
#include<string>

using namespace std;

int main(){
    string s, t, u;
    int a, b;
    cin >> s >> t;
    cin >> a >> b;
    cin >> u;
    if(s==u)cout << a-1 << ' ' << b << endl;
    else if(t==u)cout << a << ' ' << b-1 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char c[10];
int main(){
	scanf("%s",c+1);
	for(int i=1;i<=3;++i){
		if(c[i]==c[i+1]){
			puts("Bad");
			return 0;
		}
	}
	puts("Good");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF (1ll << 60)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
using vl = vector<ll>;
using vvl = vector<vl>;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}
int main() {
    int N;
    cin >> N;
    for(int i = 1; i <= 9; i++) {
        for(int j = 1; j <= 9; j++) {
            if(i * j == N) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include <set>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define int long long
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
#define mod 1000000007
#define INF 10e10
template <typename T>

void print(T x)
{
	std::cout << x << " ";
}
template <typename T>

void println(T x)
{
	std::cout << x << "\n";
}


signed main(void) {
	int N;
	cin >> N;
	vector<string>s;
	rep(i, N) {
		string tmp;
		cin >> tmp;
		s.pb(tmp);
	}
	sort(s.begin(), s.end());
	s.erase(unique(s.begin(), s.end()), s.end());
	print(s.size());	
}

Measured memory_bytes: 11668
using System;
using System.Collections.Generic;
using System.Text;

namespace ALDS1_9_C {
    class PriorityQueue<T> where T : IComparable {
        List<T> heap;
        int size;

        public PriorityQueue() {
            heap = new List<T>();
        }

        public void Enqueue(T x) {
            heap.Add(x);
            int i = size++;

            while (i > 0) {
                int p = (i - 1) / 2;
                if (Compare(heap[p], x) <= 0)
                    break;
                heap[i] = heap[p];
                i = p;
            }
            heap[i] = x;
        }

        public T Dequeue() {
            T ret = heap[0];
            T x = heap[--size];

            int i = 0;
            while (i * 2 + 1 < size) {
                int a = i * 2 + 1;
                int b = i * 2 + 2;
                if (b < size && Compare(heap[b], heap[a]) < 0)
                    a = b;
                if (Compare(heap[a], x) >= 0)
                    break;
                heap[i] = heap[a];
                i = a;
            }
            heap[i] = x;
            heap.RemoveAt(size);
            return ret;
        }

        public T Peek() {
            return heap[0];
        }

        public int Count() {
            return size;
        }

        private int Compare(T x, T y) {
            return y.CompareTo(x);
        }
    }

    class Program {
        static void Main(string[] args) {
            PriorityQueue<int> pq = new PriorityQueue<int>();
            StringBuilder sb = new StringBuilder();
            bool inputEnd = false;
            while (!inputEnd) {
                string[] input = Console.ReadLine().Split(' ');
                switch (input[0]) {
                    case "insert":
                        pq.Enqueue(int.Parse(input[1]));
                        break;
                    case "extract":
                        sb.AppendLine(pq.Dequeue().ToString());
                        break;
                    case "end":
                        inputEnd = true;
                        break;
                }
            }
            Console.Write(sb);
        }
    }
}

Measured memory_bytes: 32656
#include <stdio.h>

int main(void)
{
	int a, b, c;

	scanf("%d %d %d", &a, &b, &c);

	if (a + b + c >= 22) //22以上の場合
	{
		printf("bust\n");
	}
	else //21以下の場合
	{
		printf("win\n");
	}

	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#include<stdlib.h>
int binarySearch(int n,int *s, int q, int *t){
    int left=0,right=n,i,mid;
     while(left<right){
         mid=(left+right)/2;
         if(*(s+mid) == *t) return 1;
         else if(*t<*(s+mid)) right=mid;
         else left=mid+1;
     }
     return 0;
    }
int main(void){
    int n,q,j,B,count=0;
    int *s,*t;
    scanf("%d\n",&n);
    s=malloc(sizeof(int)*(n));
    for(j=0;j<n;j++){
        scanf("%d",(s+j));
    }
    scanf("%d\n",&q);
    t=malloc(sizeof(int)*(q));
    for(j=0;j<q;j++){
        scanf("%d",(t+j));
    }
    for(j=0;j<q;j++){
        B=binarySearch(n,s,q,t+j);
        if(B==1) count++;
    }
    printf("%d\n",count);
    free(s);
    free(t);
    return 0;
}


Measured memory_bytes: 2096
#include<stdio.h>
double memo[100000]={0,1},x;
double F(int n, double p)
{
	if(n<=1)return n*p;
	else if(x=p*memo[n-1],x<1e-9)return x;
	else return p*(1+F(n-1,p/2)) + (1-p)*memo[n-1];
}
int main()
{
	int n,i,j;
	for(i=2;i<100001;++i)memo[i]=F(i,1);
	while(scanf("%d",&n),n)printf("%.12f\n", memo[n]);
	return 0;
}

Measured memory_bytes: 944
S = list(input())
countA = 0
countB = 0

for i in range(0, len(S)):
    if S[i] == "A":
        countA += 1
    elif S[i] == "B":
        countB += 1

if countA == 3 or countB == 3:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 9112
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i=0;i<(n);++i)
#define RANGE(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(n)-1;i>= 0;--i)

#define endl '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define uset unordered_set
#define BIG 2000000000
#define VERYBIG 1000000000000000ll
#define dcout cout<<fixed<<setprecision(20)
#define Accepted_MAGIC cin.tie(0);ios::sync_with_stdio(false)

// typedef long long ll;
using Real = long double;
#define int long long

const long long dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
const long long MOD = 1e9+7;
constexpr Real eps = 1e-9, pi = acos(-1);

template<typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
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;}

typedef pair<int, int> INTP;
typedef vector<int> INTV;
struct edge2 {int to, cost;};
struct edge3 {int from, to, cost;};

signed main(void){
  Accepted_MAGIC;
  
  int A[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int K; cin >> K; K--;
  cout << A[K] << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
from typing import Union, List
import io, sys
import bisect
from collections import deque


def main():
    w,h = list(map(int, sys.stdin.readline().split()))
    
    if w == h == 0:
        return "END"
    
    n = int( sys.stdin.readline() )
    x1y1x2y2_list = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]

    X1,Y1,X2,Y2 = list(map(list, zip(*x1y1x2y2_list)))

    all_X = compress(X1,X2,w)
    all_Y = compress(Y1,Y2,h)

    matrix =[ [0]*len(all_X) for _ in range(len(all_Y)) ]
    

    for i in range(n):
        matrix[ Y1[i] ][ X1[i] ] += 1
        matrix[ Y2[i] ][ X2[i] ] += 1
        matrix[ Y2[i] ][ X1[i] ] -= 1
        matrix[ Y1[i] ][ X2[i] ] -= 1


    for row in range(len(matrix)):
        for col in range(1, len(matrix[0])):
            matrix[row][col] += matrix[row][col-1]
    
    for row in range(1, len(matrix)):
        for col in range(len(matrix[0])):
            matrix[row][col] += matrix[row-1][col]

    del matrix[-1]

    for row in range(len(matrix)):
        del matrix[row][-1]

    
    cnt = 0

    for row in range(len(matrix)):
        for col in range(len(matrix[0])):
            if matrix[row][col] == 0:
                cnt += 1
                bfs_paint(matrix, col, row, cnt)


    print(cnt)


def compress(A1 :list, A2 :list, max_A):
    all_A = []
    #delta = [-1, 0, 1]
    delta = [0]

    for a in (A1 + A2):
        for d in delta:
            val = a + d

            if 0 <= val <= max_A:
                all_A.append(a + d)

    all_A += [0, max_A]
    all_A = sorted(set(all_A))

    for i in range(len(A1)):
        A1[i] = bisect.bisect_left(all_A, A1[i])
        A2[i] = bisect.bisect_left(all_A, A2[i])
    
    return all_A


def bfs_paint(matrix :List[list], col :int, row :int, cnt :int):
    queue = deque([ (col, row) ])
    matrix[row][col] = cnt
    delta = [(0,1),(0,-1),(1,0),(-1,0)]  # (column, row)

    while queue:
        c,r = queue.popleft()

        for d in delta:
            next_c = c + d[0]
            next_r = r + d[1]

            if (0 <= next_c < len(matrix[0])) and (0 <= next_r < len(matrix)) and \
                matrix[next_r][next_c] == 0:

                matrix[next_r][next_c] = cnt
                queue.append( (next_c, next_r) )


if __name__ == "__main__":
    while True:
        ret = main()
        
        if ret == "END":
            break



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


using namespace std;


// Powered by caide (code generator, tester, and library code inliner)


class Solution {
public:
  int n;
  vector<int> a;
  long long dp[11][2];

  long long dfs(int now, bool have)
  {
    if (now == n) {
      return have;
    }
    if(~dp[now][have]) {
      return dp[now][have];
    }
    long long res = 0;
    for (int i = a[now] - 1; i <= a[now] + 1; i++) {
      if (i % 2) {
        res += dfs(now + 1, have);
      } else {
        res += dfs(now + 1, true);
      }
    }
    return dp[now][have] = res;
  }

  void solve(std::istream& in, std::ostream& out)
  {
    in >> n;
    memset(dp, -1, sizeof dp);
    a.resize(n);
    for (auto&& i : a) {
      in >> i;
    }
    out << dfs(0, false) << "\n";
  }
};

void solve(std::istream& in, std::ostream& out)
{
  out << std::setprecision(12);
  Solution solution;
  solution.solve(in, out);
}


#include <fstream>
#include <iostream>


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


  istream& in = cin;


  ostream& out = cout;

  solve(in, out);
  return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int MOD = (int)1e9+7;

int n;
ll a[305][305];
ll chk[305][305];

int main(void) {
	//freopen("in.txt", "r", stdin);
	cin >> n;
	rep(i,0,n) rep(j,0,n) {
		cin >> a[i][j];
	}
	rep(i,0,n) rep(j,0,n) {
		if(i < j) chk[i][j] = 1;
	}
	rep(k,0,n) rep(i,0,n) rep(j,0,n) {
		if(a[i][k]+a[k][j] < a[i][j]) {
			cout << -1 << '\n';
			return 0;
		} else if(k != i && k != j && a[i][k]+a[k][j] == a[i][j]) {
			chk[i][j] = 0;
		}
	}
	ll ret = 0;
	rep(i,0,n) rep(j,0,n) {
		if(i<j) {
			ret += a[i][j] * chk[i][j];
		}
	}
	cout << ret << '\n';
	return 0;
}

Measured memory_bytes: 1664
N,M=map(int,input().split())
A,B=[],[]
count=0
for i in range(N):
	p=list()
	p=list(map(int,input().split()))
	A.append(p[1:])
for i in range(M):
	B.append(0)
for i in range(N):
	for j in range(len(A[i])):
		B[A[i][j]-1] += 1
for i in B:
	if i == N:
		count+=1
print(count)

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {

    	try(BufferedReader i = new BufferedReader(new InputStreamReader(System.in))){

    		String S = i.readLine();
    		int a = S.length();
    		Long r = S.chars().filter(c -> c=='0').count();
    		Long b = a - r;
	    	System.out.println(Math.min(r, b) * 2);
    	}
    }
}

Measured memory_bytes: 27860
use proconio::input;
use std::collections::BTreeMap;

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }

    let mut map = BTreeMap::new();
    for &na in &a {
        let entry = map.entry(na).or_insert(0);
        *entry += 1;
    }

    let mut first = 0;
    let mut second = 0;
    for (key, value) in map.iter().rev() {
        let mut value = *value;
        if first == 0 {
            if value >= 2 {
                first = *key;
                value -= 2;
            }
            if value >= 2 {
                second = *key;
                break;
            }
        } else {
            if value >= 2 {
                second = *key;
                break;
            }
        }
    }
    if first == 0 || second == 0 {
        println!("{}", 0);
    } else {
        println!("{}", first * second);
    }
}


Measured memory_bytes: 5960
import java.util.Scanner;
import java.util.Arrays;

public class Main {
	private static final long MOD = 1_000_000_000 + 7;

	// 反復二乗法を用いる
	public static long myPow(long a) {
		long ans = 1L;
		long x = a;
		long b = 1_000_000_000 + 5L;

		for(int i = 0; i < 64; i++) {
			if((b & (1L << i)) != 0L) {
				ans = (ans * x) % MOD;
			}
			x = (x * x) % MOD;
		}

		return ans;
	}

	public static long nck(int n, int k, long[] fact) {
		if(n < k || n < 0 || k < 0) {
			return 0;
		}
		return (((fact[n] * myPow(fact[n - k])) % MOD) * myPow(fact[k])) % MOD;
	}

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

		int n = sc.nextInt();
		int[] a = new int[n + 1];
		int[] count = new int[n + 1];

		int tar = 0;
		int l = 0; int r = 0;

		for(int i = 0; i < n + 1; i++) {
			a[i] = sc.nextInt();
			count[a[i]]++;
			if(count[a[i]] == 2) {
				tar = a[i];
				r = i + 1;
			}
		}

		for(int i = 0; i < n + 1; i++) {
			if(a[i] == tar) {
				l = i + 1;
				break;
			}
		}

		// n+1までの階乗の計算
		long[] fact = new long[n + 2];
		fact[0] = 1L;
		for(int i = 1; i <= n + 1; i++) {
			fact[i] = (fact[i - 1] * i) % MOD;
		}

		for(int k = 1; k <= n + 1; k++) {
			long comb1 = nck(n + 1, k, fact);
			long comb2 = nck(l + n - r, k - 1, fact);
			System.out.println((comb1 - comb2 + MOD) % MOD);
		}
	}
}


Measured memory_bytes: 59868
import math
n, m = map(int, input().split())

mod = 10**9 + 7

b = []

c = int(math.sqrt(m))
for i in range(2, c+2):
    count = 0
    while m % i == 0:
        count += 1
        m = m // i
    b.append(count)
if m > 1:
    b.append(1)

fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n + max(b)+3):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

def nck(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 1
for i in b:
    ans *= nck(n-1+i, i)
    ans %= mod

print(ans)

Measured memory_bytes: 15296
import numpy as np
import sys
input = sys.stdin.buffer.readline

k, q = map(int, input().split())

d = np.array(list(map(int, input().split())), np.int64)

for _ in range(q):
    n, x, m = map(int, input().split())
    tmp = x % m
    d_mod = (d-1) % m + 1 #ex. m = 3 then [0, 1, 2, 3, 4] becomes [3, 1, 2, 3, 1].
    d_cumsummod = np.cumsum(d_mod)
    d_cumsummod = np.concatenate((np.zeros(1, np.int64), d_cumsummod))
    d_q, d_r = divmod(n-1, k)
    tmp += (d_q * d_cumsummod[-1] + d_cumsummod[d_r])
    print((n-1) - tmp // m)


Measured memory_bytes: 14436
def main():
    S = [int(i) if i != '?' else -1 for i in input()]
    s = len(S)
    mod = 10 ** 9 + 7
    dp = [[0] * 13 for _ in range(s)]

    table = [[0] * 10 for _ in range(13)]
    for i in range(13):
        for j in range(10):
            table[i][j] = (i * 10 + j) % 13

    table2 = [[] for _ in range(13)]
    for i in range(13):
        for j in range(10):
            table2[table[i][j]].append(i)
    t = set(range(13))
    table2 = [t - set(i) for i in table2]

    if S[0] == -1:
        for i in range(10):
            dp[0][i] += 1
    else:
        dp[0][S[0] % 13] += 1

    for i in range(1, s):
        if S[i] == -1:
            temp = sum(dp[i - 1])
            for j in range(13):
                dp[i][j] = temp
                for k in table2[j]:
                    dp[i][j] -= dp[i - 1][k]
                dp[i][j] %= mod
        else:
            for j in range(13):
                dp[i][table[j][S[i]]] = dp[i - 1][j]

    print(dp[-1][5] % mod)


if __name__ == '__main__':
    main()

Measured memory_bytes: 63160
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import numpy as np
s = list(map(int, input().split()))
N = s[0]
M = s[1]
flag = 0
def fib(n):
    a, b = 0, 1
    c = [1]
    for i in range(n):
        a, b = b, a + b
        c.append(b)
    return c


broken = np.array([int(input()) for i in range(M)])
broken = np.append(-1,broken)
broken = np.append(broken,N+1)
#  -1段目とN+1段目が壊れていると表記して一貫した計算が可能に

gaps = np.array([])  # 壊れている段の間にある壊れていない段数
for i in range(M+1):
    gaps = np.append(gaps, broken[i+1]-broken[i]-1)
    if broken[i+1]-broken[i]-1 == 0:
        flag = 1
        break

gaps = np.array(gaps, np.int)  # 整数列に変換



if flag == 1:
    print(0)
else:
    fibs = fib(max(gaps))
    patterns = 1
    for i in range(len(gaps)):
        patterns *= fibs[gaps[i]-1]
    print(patterns % 1000000007)


Measured memory_bytes: 469076
import java.util.Scanner;
class Main{
	public static void main(String[]args) {
	Scanner scan=new Scanner(System.in);
	int a=scan.nextInt();
	double ans=0;
	for(int i=0;i<a;i++) {
		double b=scan.nextDouble();
		String str=scan.next();
		if(str.charAt(0)=='J') {
			ans+=b;
		}
		else {
			ans+=b*380000;
		}
	}
	System.out.println(ans);
	}
}

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

int x[50],n;

int isWin(int index){
  int i;
  for(i=0;i<n;i++){
    if(i==index) continue;
    if(x[i]!=0) break;
  }
  if(i==n) return 1;
  else return 0;
}

int main(void){
  int i,p;

  while(1){
    scanf("%d%d",&n,&p);
    if(!n && !p) break;

    memset(x,0,sizeof(x));
    for(i=0;;i++){
      if(i==n) i=0;
      if(p==0){
	p = x[i];
	x[i] = 0;
      }
      else if(p==1){
	p = 0;
	x[i]++;
	if(isWin(i)) break;
      }
      else{
	p--;
	x[i]++;
      }
    }
    printf("%d\n",i);
  }

  return 0;
}

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

int main(){
  double n;
  double yoko,tate,takasa;
  cin >> n;
  yoko = n / 3;
  tate = n / 3;
  takasa = n - yoko - tate;
  cout << fixed;
  cout << setprecision(6) << yoko * tate * takasa << '\n';
  return 0; 
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _USE_MATH_DEFINES
#include <cmath>
using namespace std;
#define pi M_PI
#include <vector>

int main(){
    int n, m, ans = 0;
    cin >> n >> m;
    ans = (n - 1) * (m - 1);
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import math
A,B,H,M = map(int,input().split()) #長針、短針、時間、分
deg_M = 2*M*math.pi / 60
deg_H = ((H + M/60)/12) * 2 * math.pi
#print(deg_M,deg_H)
deg = deg_M - deg_H
print(math.sqrt(A**2 + B**2 - 2*A*B*math.cos(deg)))

Measured memory_bytes: 9472
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

int main() {
	string s0, s1, s2;
	cin >> s0 >> s1 >> s2;

	cout << s0[0] << s1[1] << s2[2] << endl;
	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using datas=pair<ll,ll>;
using ddatas=pair<double,double>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
#define For(i,a,b) for(i=a;i<(ll)b;i++)
#define bFor(i,a,b) for(i=a;i>=(ll)b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N-1,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define endl "\n"
#define pb push_back
#define output(v) do{bool f=0;for(auto outi:v){cout<<(f?" ":"")<<outi;f=1;}cout<<endl;}while(0)
const ll mod=1000000007;
const ll inf=1LL<<60;
const double PI = acos(-1);
const double eps = 1e-9;
template<class T> inline bool chmax(T& a,T b){bool x=a<b;if(x)a=b;return x;} 
template<class T> inline bool chmin(T& a,T b){bool x=a>b;if(x)a=b;return x;} 

void startupcpp(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
}

double distance(ddatas& x,ddatas& y){
  double a=x.first-y.first,b=x.second-y.second;
  return sqrt(a*a+b*b);
}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

vec modncrlistp,modncrlistm;

ll modncr(ll n,ll r){
  ll i,size=modncrlistp.size();
  if(size<=n){
    modncrlistp.resize(n+1);
    modncrlistm.resize(n+1);
    if(!size){
      modncrlistp[0]=modncrlistm[0]=1;
      size++;
    }
    For(i,size,n+1){
      modncrlistp[i]=modncrlistp[i-1]*i%mod;
      modncrlistm[i]=modinv(modncrlistp[i]);
    }
  }
  return modncrlistp[n]*modncrlistm[r]%mod*modncrlistm[n-r]%mod;
}

ll modpow(ll a,ll n){
  ll res=1;
  while(n){
    if(n&1)res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll gcd(ll a,ll b){if(!b)return a;return (a%b==0)?b:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}
void judgement(int a){
  if(a){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  if(a){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
}

int main(){
  ll i,a,b,K,N,ans=1;
  cin>>a>>b;
  if((a+b)%3){
    cout<<0<<endl;return 0;
  }
  N=(a+b)/3;
  K=min(a,b)-N;
  if(K<0){
    cout<<0<<endl;return 0;
  }
  cout<<modncr(N,K)<<endl;
  return 0;
}

Measured memory_bytes: 10624
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int a = scan.nextInt();
        int b = scan.nextInt();
        int fee = n*a;
        if(fee>b)
        {
            System.out.println(b);
        }
        else
        {
            System.out.println(fee);
        }
    }
}


Measured memory_bytes: 22868
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author ExplodingFreeze
 */

#include <iostream>
#include <fstream>

#pragma comment(linker, "/stack:200000000")
#include <bits/stdc++.h>
#define int long long
#define f(i,a,b) for(int i=(a);i<(b);i++)
#define MOD 1000000007

using namespace std;


class BBounding {
public:
	void solve(std::istream& in, std::ostream& out) {
		int n,x,l,dist=0,ans=0;
		in >> n >> x;
		f(i,0,n)
		{
			in >> l;
			dist+=l;
			if(dist>x)
				break;
			ans++;
		}
		out << ans+1 << "\n";
	}
};


int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	BBounding solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 384
use std::io::{self, BufRead};

const M: u64 = 1000000007;

fn main() {
  let stdin = io::stdin();
  let mut lines = stdin.lock().lines();
  let xs: Vec<usize> = lines.next().unwrap().unwrap().split(' ').map(|x| x.parse().unwrap()).collect();
  let (n, m) = (xs[0], xs[1]);
  let ss: Vec<u32> = lines.next().unwrap().unwrap().split(' ').map(|x| x.parse().unwrap()).collect();
  let ts: Vec<u32> = lines.next().unwrap().unwrap().split(' ').map(|x| x.parse().unwrap()).collect();
  let mut memo1: Vec<Vec<u64>> = vec![vec![0; m]; n];
  let mut memo2: Vec<Vec<u64>> = vec![vec![0; m]; n];
  memo1[0][0] = (ss[0] == ts[0]) as u64;
  memo2[0][0] = memo1[0][0];
  for i in 1..n {
    memo1[i][0] = (ss[i] == ts[0]) as u64;
    memo2[i][0] = memo2[i-1][0] + memo1[i][0];
  }
  for j in 1..m {
    memo1[0][j] = (ss[0] == ts[j]) as u64;
    memo2[0][j] = memo2[0][j-1] + memo1[0][j];
  }
  for i in 1..n {
    for j in 1..m {
      memo1[i][j] = if ss[i] == ts[j] { 1 + memo2[i-1][j-1] } else { 0 };
      memo2[i][j] = (memo2[i][j-1] + memo2[i-1][j] + (M - memo2[i-1][j-1]) + memo1[i][j]) % M;
    }
  }
  println!("{}", memo2[n-1][m-1] + 1);
}

Measured memory_bytes: 86268
// Aizu 0230: Ninja Climbing
// 2017.9.10 bal4u@uu

#include <stdio.h>
#include <string.h>

#define QMAX 30000
typedef struct { int a, h, c; } Q;
Q que[QMAX+3]; int top, end;

int w[2][103];
char visited[2][103];

int main()
{
	int n, i, j, h, c, j2, h2;
	int ans;

	while (scanf("%d", &n) && n) {
		for (j = 0; j < 2; j++) for (i = 0; i < n; i++) scanf("%d", w[j]+i);
		w[0][n] = w[1][n] = 0;
		memset(visited, 0, sizeof(visited));
		h = 0; if (w[0][0] == 1) { while (w[0][h] == 1) h++; h--; }
		que[0].a = 0, que[0].h = h, que[0].c = 0;
		h = 0; if (w[1][0] == 1) { while (w[1][h] == 1) h++; h--; }
		que[1].a = 1, que[1].h = h, que[1].c = 0;
		ans = -1; top = 0, end = 2;
		while (top < end) {
			j = que[top].a, h = que[top].h, c = que[top].c; if (++top == QMAX) top = 0;
			if (h == n-1) { ans = c; break; }
			for (j2 = !j, i = 0; i <= 2; i++) {
				if ((h2 = h + i) >= n) continue;
				if      (w[j2][h2] == 1) { while (w[j2][h2] == 1) h2++; h2--; }
				else if (w[j2][h2] == 2) while (w[j2][h2] == 2) h2--;
				if (visited[j2][h2]) continue;
				visited[j2][h2] = 1;
				que[end].a = j2, que[end].h = h2, que[end].c = c+1; if (++end == QMAX) end = 0;
			}
		}
		printf(ans < 0 ? "NA\n" : "%d\n", ans);
	}
	return 0;
}

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

int main(){
  int x,n;//aは差
  cin >> x >> n;
  bool book = true;
  int p[n];//pは入力
  for(int i = 0;i < n;i++)
    cin >> p[i];
  
  for(int i = 0;i <= x;i++){
    book = true;
    for(int j = 0;j < n;j++){
      if(x - i == p[j]){
        book = false;
        break;
      }
    }
    if(book){
      cout << x - i << endl;
      return 0;
    }
    if(i == 0)
      continue;
    book = true;
    for(int k = 0;k < n;k++){
      if(x + i == p[k]){
        book = false;
        break;
      }
    }
    if(book){
      cout << x + i << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 3632
#include <stdio.h>
#include <string.h>
#include <math.h>
int main(){
	char num[15];
	long long n, found;
	scanf("%lld", &n);
	found = n;
	long long root = ceil(sqrt(n));
	for(int i = 2; i <= root; ++i){
		if(n%i == 0){
			found = n/i;
		}
	}
	sprintf(num, "%lld", found);
	printf("%ld\n", strlen(num));
	return 0;
}

Measured memory_bytes: 128
import java.util.*;

public class Main {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        if (N == 0) {
            System.out.println("0");
            return;
        }

        String ans = "";
        while (N != 0) {
            if (N % 2 != 0) {
                N--;
                ans = "1" + ans;
            } else {
                ans = "0" + ans;
            }
            N /= -2;
        }
        System.out.println(ans);
    }

}


Measured memory_bytes: 22100
a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
d=abs(a-b)
q=v-w
if q<=0:
    print("NO")
else:
    x=q*t
    if x>=d:
        print("YES")
    else:
        print("NO")


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


int main() {
  int N;
  cin >> N;
  
  vector<int> a(N);
  for (int i=0; i<N; i++) {
    cin >> a.at(i);
  }
  
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  int A=0, B=0;
  for (int i=0; i<N; i++) {
    if (i%2 == 0) A += a.at(i);
    else B += a.at(i);
  }
  
  cout << A - B << endl;
  
  return 0;
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout << fixed;
  int n, k;
  cin >> n >> k;
  vector<double> a(n);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    a[i] = (1.0 * x + 1) / 2;
  }
  double ans = 0.0;
  for (int i = 0; i < k; i++) {
    ans += a[i];
  }
  double cur = ans;
  for (int i = k; i < n; i++) {
    double foo = cur + a[i] - a[i - k];
    ans = max(ans, foo);
    cur = foo;
  }
  cout << ans << '\n';
  return 0;
}

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

using namespace std;
using ll = long long;

#define MOD 1000000007
template<int mod>
struct ModInt{
   int x;
   ModInt():x(0){}
   ModInt(long long y):x(y>=0?y%mod:(mod-(-y)%mod)%mod){}
   ModInt &operator+=(const ModInt &p){
	   if((x+=p.x)>=mod)x-=mod;
	   return *this;
   }
   ModInt &operator-=(const ModInt &p){
	   if((x+=mod-p.x)>=mod)x-=mod;
	   return *this;
   }
   ModInt &operator*=(const ModInt &p){
	   x=(int)(1LL*x*p.x%mod);
	   return *this;
   }
   ModInt &operator/=(const ModInt &p){
	   *this*=p.inverse();
	   return *this;
   }
   ModInt &operator^=(long long p){
	   ModInt res = 1;
	   for (; p; p >>= 1) {
		   if (p & 1) res *= *this;
		   *this *= *this;
	   }
	   return *this = res;
   }
   ModInt operator-()const{return ModInt(-x);}
   ModInt operator+(const ModInt &p)const{return ModInt(*this)+=p;}
   ModInt operator-(const ModInt &p)const{return ModInt(*this)-=p;}
   ModInt operator*(const ModInt &p)const{return ModInt(*this)*=p;}
   ModInt operator/(const ModInt &p)const{return ModInt(*this)/=p;}
   ModInt operator^(long long p)const{return ModInt(*this)^=p;}
   bool operator==(const ModInt &p)const{return x==p.x;}
   bool operator!=(const ModInt &p)const{return x!=p.x;}
   explicit operator int() const { return x; }
   ModInt operator=(const int p) {x = p; return ModInt(*this);}
   ModInt inverse()const{
	   int a=x,b=mod,u=1,v=0,t;
	   while(b>0){
		   t=a/b;
		   a-=t*b;
		   std::swap(a,b);
		   u-=t*v;
		   std::swap(u,v);
	   }
	   return ModInt(u);
   }
   friend std::ostream &operator<<(std::ostream &os,const ModInt<mod> &p){
	   return os<<p.x;
   }
   friend std::istream &operator>>(std::istream &is,ModInt<mod> &a){
	   long long x;
	   is>>x;
	   a=ModInt<mod>(x);
	   return (is);
   }
};
typedef ModInt<MOD> mint;
 
struct MComb {
   std::vector<mint> fact;
   std::vector<mint> inversed;
   MComb(int n) { // O(n+log(mod))
	   fact = std::vector<mint>(n+1,1);
	   for (int i = 1; i <= n; i++) fact[i] = fact[i-1]*mint(i);
	   inversed = std::vector<mint>(n+1);
	   inversed[n] = fact[n] ^ (MOD-2);
	   for (int i = n - 1; i >= 0; i--) inversed[i]=inversed[i+1]*mint(i+1);
   }
   mint ncr(int n, int r) {
		if (n < r) return 0;
		if (n < 0 || r < 0) return 0;
	   return (fact[n] * inversed[r] * inversed[n-r]);
   }
   mint npr(int n, int r) {
		if (n < r) return 0;
		if (n < 0 || r < 0) return 0;
	   return (fact[n] * inversed[n-r]);
   }
   mint nhr(int n, int r) {
	   assert(n+r-1 < (int)fact.size());
	   return ncr(n+r-1, r);
   }
   mint fac(int n) {
	   if(n < 0)return 0;
	   return fact[n];
   }
};
MComb comb(200000);
 


int main()
{
	ll s; cin >> s;
	mint ans = 0;

	for(int n = 1; n <= s / 3; n++) {
		ll sum = s - n * 3;
		mint cur = comb.ncr(sum + n - 1, n - 1);
		ans += cur;
	}
	cout << ans << endl;

}

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

int main(){
  string s, t;
  cin >> s >> t;
  int slen = s.size(), tlen = t.size();
  s = " " + s;
  t = " " + t;
  vvi dp(slen+1, vi(tlen+1));
  for(int i=1; i<=slen; i++){
    for(int j=0; j<=tlen; j++){
      if(s[i] == t[j]) dp[i][j] = dp[i-1][j-1] + 1;
      else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
    }
  }
  int len = dp[slen][tlen];
  string ans;
  int i = slen, j = tlen;
  while(len > 0){
    if(s[i] == t[j]){
      ans = s[i] + ans;
      i--;
      j--;
      len--;
    }
    else if(dp[i][j] == dp[i][j-1]) j--;
    else i--;
  }
  cout << ans << endl;
}


Measured memory_bytes: 38960