akhauriyash/Code-Regression huggingface dataset:
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())

def divisor(n): #約数
    f=[]
    d=[1]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append([i,c])
            c=0
    if n!=1:
        f.append([n,1])
    for i in range(len(f)):
        t=[]
        for j in range(1,f[i][1]+1):
            t.append(f[i][0]**j)
        for j in range(len(d)):
            for k in range(len(t)):
                d.append(d[j]*t[k])
    return sorted(d)

n=I()
div=divisor(n)
if len(div)%2==1:
    ddiv=div[len(div)//2+1:]
    ans=sum(ddiv)-len(ddiv)
else:
    if div[max(0,len(div)//2-1)]+1==div[len(div)//2]:
        if len(div)>=4:
            ddiv=div[len(div)//2+1:]
            ans=sum(ddiv)-len(ddiv)
        else:
            ans=0
    else:
        ddiv=div[len(div)//2:]
        ans=sum(ddiv)-len(ddiv)
print(ans)

Measured memory_bytes: 3316
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long ans = 1;
    for (int i = 1; i <=N; i++) {
      ans = (ans*i)%1000000007;
    }
    
    System.out.println(ans);
  }
}

Measured memory_bytes: 21716
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool issame(int x, int y)
	{
		return root(x) == root(y);
	}

	bool merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
ll gcd(ll a, ll b)
{
	if (b == 0)return a;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region LCM
ll lcm(ll a, ll b)
{
	return a / gcd(a, b) * b;
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	int h, w; cin >> h >> w;
	vector<int> alp(26);
	rep(i, h)
	{
		string s; cin >> s;
		for (char c : s)++alp[c - 'a'];
	}
	int odd = 0;
	int f = 0;
	rep(i, 26)
	{
		if (alp[i] % 2 == 1)++odd;
		f += alp[i] / 4;
	}
	if (h % 2 == 0 && w % 2 == 0)
	{
		if ((h / 2) * (w / 2) <= f)cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	else if ((h*w) % 2 == 0)
	{
		if ((h / 2) * (w / 2) <= f && odd == 0)cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	else
	{
		if ((h / 2) * (w / 2) <= f && odd == 1)cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
typedef long long ll;
const int maxn = 1e9;
const ll p = 1e9 + 7;

ll Pow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return ans;
}

ll C(ll n, ll m)
{
    if (m == 0)
        return 1;
    if (m > n - m)
        m = n - m;
    ll up = 1, down = 1;
    for (ll i = 1; i <= m; i++)
    {
        up = (up * (n - i + 1)) % p;
        down = (down * i) % p;
    }
    return up * Pow(down, p - 2) % p;
}
int main()
{
    ll n, a, b;
    cin >> n >> a >> b;
    //cout << Pow(2, n) - 1 << ' ' << C(n, a) << ' ' << C(n, b) << endl;
    cout << (Pow(2, n) - 1 - (C(n, a) + C(n, b)) % p + 2 * p) % p << endl;
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

// Chokudai is struct
type Chokudai struct {
	scanner *bufio.Reader
}

func (chokudai *Chokudai) getNextLine() string {
	var buffer string
	for {
		line, isPrefix, _ := chokudai.scanner.ReadLine()
		buffer += string(line)
		if isPrefix == false {
			break
		}
	}
	return buffer
}

func (chokudai *Chokudai) getIntList() []int {
	list := strings.Split(chokudai.getNextLine(), " ")
	l := len(list)
	result := make([]int, l)
	for i := 0; i < l; i++ {
		result[i], _ = strconv.Atoi(list[i])
	}
	return result
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	chokudai := Chokudai{bufio.NewReader(fp)}

	nk := chokudai.getIntList()
	n := nk[0]
	k := nk[1]
	s := chokudai.getNextLine()
	var prev byte
	prev = '1'
	var switched []int
	switched = append(switched, 0)
	for i := 0; i < n; i++ {
		if prev != s[i] {
			switched = append(switched, i)
			prev = s[i]
		}
	}
	switched = append(switched, n)
	max := 0
	l := len(switched)
	for i := 0; i < l-1; i += 2 {
		last := l - 1
		if i+2*k+1 <= l-1 {
			last = i + 2*k + 1
		}
		if max < switched[last]-(switched[i]) {
			max = switched[last] - (switched[i])
		}
	}
	fmt.Println(max)
}


Measured memory_bytes: 6784
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int A = scan.nextInt();
        int B = scan.nextInt();
        int C = scan.nextInt();
        int K = scan.nextInt();
     int p=0;
     for(int i=0;i<K&&p==0;i++){
         if (B<=A){B=B*2;}
         else if(C<=B){C=C*2;}

         if (B>A&&C>B){p=1;}
     }


if (p==0)System.out.println("No");
        if (p==1)System.out.println("Yes");
}
    }

Measured memory_bytes: 27032
n = int(input())
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))
zs = list(map(int, input().split()))
b = None
r=0
for x in xs:
    if b==None:
        b=x
        continue
    if x == b+1:
        r+=zs[b-1]
    b=x
print(sum(ys) + r)



Measured memory_bytes: 38488
#include<iostream>
#include<cstdio>
#include<algorithm>

struct Triangle{
	int sides[3];
};

bool checkTriangle(const Triangle& t){
	for(int i=0;i<3;i++){
		if(t.sides[i] + t.sides[(i+1)%3] <= t.sides[(i+2)%3])return false;
	}
	return true;
}

bool checkRightTriangle(Triangle& t){
	std::sort(t.sides, t.sides+3);
	return (t.sides[0] * t.sides[0] + t.sides[1] * t.sides[1] == t.sides[2] * t.sides[2]);
}

bool checkObtuseTriangle(Triangle& t){
	double cos = 1.0 * (t.sides[0] * t.sides[0] + t.sides[1] * t.sides[1] - t.sides[2] * t.sides[2]) / (2 * t.sides[0] * t.sides[1]);
	return (cos < 0);
}

bool checkAcuteTriangle(Triangle& t){
	double cos = 1.0 * (t.sides[0] * t.sides[0] + t.sides[1] * t.sides[1] - t.sides[2] * t.sides[2]) / (2 * t.sides[0] * t.sides[1]);
	return (cos > 0);
}

int main(){
	int a, b, c, tn = 0, rtn = 0, otn = 0, atn = 0;
	bool ignored = false;
	while(std::cin >> a >> b >> c, !std::cin.eof()){
		if(ignored)continue;
		Triangle t = {{a, b, c}};
		if(checkTriangle(t)){
			tn++;
			if(checkRightTriangle(t))rtn++;
			if(checkObtuseTriangle(t))otn++;
			if(checkAcuteTriangle(t))atn++;
		}
		else ignored = true;
	}

	printf("%d %d %d %d\n", tn, rtn, atn, otn);
}

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

int main() {
  
  int n, minCount = 10000;
  cin >> n;
  
  for(int i = 0; i < n; i++) {
    int a;
    cin >> a;
    int tempCount = 0;
    
    while(a % 2 == 0) {
      a /= 2;
      tempCount++;
    }
    
    if (tempCount < minCount) {
      minCount = tempCount;
    }
  }
  
  cout << minCount << endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 100005
#define eps 1e-12
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
        out(x / 10);
    }
    putchar('0' + x % 10);
}
int N;
int A[MAXN],B[MAXN],s[MAXN][2],ans[MAXN];
struct node {
    int to,next;
}E[MAXN * 10];
int head[MAXN * 2],sumE = 1;
bool vis[MAXN * 10];
void add(int u,int v) {
    E[++sumE].to = v;
    E[sumE].next = head[u];
    head[u] = sumE;
}
void euler_road(int u) {
    for(int &i = head[u] ; i ; i = E[i].next) {
        int w = i;
        if(!vis[w]) {
            vis[w] = vis[w ^ 1] = 1;
            int v = E[w].to;
            if(u != 2 * N + 1 && v != 2 * N + 1 && abs(u - v) == N) {
                if(u < v) ans[u] = 1;
                else ans[v] = -1;
            }
            euler_road(v);
        }
    }
}
void Solve() {
    read(N);
    for(int i = 1 ; i <= N ; ++i) {
        read(A[i]);
        if(A[i] != -1) {
            add(i,A[i]);add(A[i],i);
            s[A[i]][0]++;
        }
        else {
            add(i,2 * N + 1);add(2 * N + 1,i);
        }
    }
    for(int i = 1 ; i <= N ; ++i) {
        read(B[i]);
        if(B[i] != -1) {
            add(i + N,B[i] + N);add(B[i] + N,i + N);
            s[B[i]][1]++;
        }
        else {
            add(i + N,2 * N + 1);add(2 * N + 1,i + N);
        }
    }
    for(int i = 1 ; i <= N ; ++i) {
        if((s[i][0] ^ s[i][1]) & 1) {
            puts("IMPOSSIBLE");
            return;
        }
        if(s[i][0] % 2 == 0) {
            add(i,i + N);add(i + N,i);
        }
    }
    puts("POSSIBLE");
    euler_road(1);
    for(int i = 1 ; i <= N ; ++i) {
        out(ans[i]);space;
    }
    enter;
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
    Solve();
}


Measured memory_bytes: 20480
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(c) c.begin(), c.end()
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define gadd(x,y) x=add(x,y)
#define gmul(x,y) x=mul(x,y)
using namespace std;

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

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	string s;
	cin >> s;
	cout << count(all(s), '1') << '\n';
}


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

using namespace std;

#define int 		long long
#define endl		"\n"
#define mod			1000000007
#define IOS			ios::sync_with_stdio(0), cin.tie(0)


int32_t main() {

	IOS;

	string s, t;
	int cnt = 0;
	cin >> s >> t;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] != t[i])
			cnt++;
	}

	cout << cnt << endl;

	return 0;
}


Measured memory_bytes: 3776
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        //1行目は単語w
        String w = sc.nextLine();
        String sa = new String();
        int count=0;
        while(true){
        	sa = sc.next();
        	if("END_OF_TEXT".equals(sa)){
        		break;
        	}
        	if (w.equals(sa.toLowerCase())) {
        		count ++;
        	}
        }
        sc.close();
        System.out.println(count);
    }
}



Measured memory_bytes: 26232
#include <bits/stdc++.h>
#include<iostream>
#include <string>
#include <typeinfo>
using namespace std;
 
int main() {
    int a,b,c,d;
    cin >> a >> b;
    c = a*b;
  	d = a+b;
  	if(c == 15)cout << "*" << endl;
  	else if(d == 15)cout << "+" << endl;
  	else cout << "x" << endl;

} 


Measured memory_bytes: 3552
N=int(input())
B=map(int,input().split())
B=list(B)
SUM=B[0]
for i in range(0,N-1):
    if i!=(N-2):
        if B[i]>=B[i+1]:
            SUM+=B[i+1]
        else:
            SUM+=B[i]
    
if B[N-3]<=B[N-2]:
    SUM+=B[N-2]
else:
    SUM+=B[N-2]
    
print(SUM)

Measured memory_bytes: 3064
def f(n, x):
    if n == 0:
        return min(x, 3)
    elif x == 0:
        return 0
    elif 0 < x and x <= layers_num[n - 1]:
        return f(n - 1, x - 1)
    elif x == 1 + layers_num[n - 1]:
        return p[n - 1] + 1
    elif 1 + layers_num[n - 1] < x <= 1 + 2 * layers_num[n - 1]:
        return p[n - 1] + 1 + f(n - 1, x - 2 - layers_num[n - 1])
    else:
        return 2 * p[n - 1] + 1


level0 = 'BPPPB'
N, X = map(int, input().split())

layers_num = []
p = []
for n in range(N):
    if n == 0:
        layers_num.append(len(level0))
        p.append(level0.count('P'))
    else:
        layers_num.append(layers_num[n - 1] * 2 + 3)
        p.append(2 * p[n - 1] + 1)

print(f(N - 1, X - 1))


Measured memory_bytes: 38256
#include <bits/stdc++.h>
#define ll long long
#define lf long double
#define INF 10000000000000000
#define MAX 300001
#define M 998244353
using namespace std;

int main() {
  int n;
  cin >> n;
  int a[n];
  for (int i=0;i<n;i++) cin >> a[i];
  int mx = 0;
  int i = 0;
  while (i<n) {
    int j = i+1;
    while(j<n && a[j]<=a[j-1]) j++;
    mx = max(mx, j-i-1);
    i = j;
  }
  cout << mx;
  return 0;
}

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

int main() {
  int A, B, C;
  cin >> A >> B >> C;

  if (A == B) {
    cout << C << endl;
  }
  else if (A == C) {
    cout << B << endl;
  }
  else {
    cout << A << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vs = vector<string>;
#define  rep(i,n) for(ll i = 0; i < (n); ++i)
#define  red(i,n) for(ll i = (n)-1; i >= 0; --i)
#define  all(a)   begin(a),end(a)
#define  pb(a)    push_back(a)
#define  yn     cout<<"Yes\n"; else cout<<"No\n";
inline ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
const int INF=1000000009;
const ll LINF = 1e18;

int main()
{
    int n,y;
    cin>>n>>y;
    for(int t=0;t<=n;t++)for(int f=0;f<=n-t;f++){
        if(10000*t+5000*f+1000*(n-t-f)==y) cout<<t<<" "<<f<<" "<<n-t-f<<endl,exit(0);
    }
    cout<<"-1 -1 -1\n";
    
    return 0;
}


Measured memory_bytes: 256
program main
  implicit none
  integer :: N
  integer,allocatable :: H(:)
  logical :: flag
  integer :: out
  integer :: i,j
  read(*,*) N
  allocate(H(N))
  read(*,*) H(:)

  out = 1
  do I = 2,N
     flag=.true.
     do j = 1,i-1
        if (H(j) > H(i)) then
           flag=.false.
           exit
        end if
     end do
     if (flag) then
        out = out+1
     end if
  end do
  write(*,'(i0)') out
  stop 
end program main

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
import fractions
def lcm(x,y):
  return (x * y) // fractions.gcd(x, y)
r = A[0]
for i in range(N-1):
  r = lcm(r,A[i+1])
ans = 0
for i in range(N):
  ans += r//A[i]
print(ans%1000000007)

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

using namespace std;

int gcd(int x,int y){
     return y?gcd(y,x%y):x;
}

int main()
{
    int x,y;
    cin >> x >> y;
    cout << x+y-(gcd(x,y)-1)<< endl;
    return 0;
}



Measured memory_bytes: 3116
N, A, B = map(int, input().split())
if (A + B) % 2 == 0:
    print(B - (A + B) // 2)
    exit()
to1 = A - 1
toN = N - B
if to1 < toN:
    B -= to1 + 1
    print(to1 + 1 + B - (1 + B) // 2)
else:
    A += toN + 1
    print(toN + 1 + N - (A + N) // 2)


Measured memory_bytes: 9044
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>
#include <bitset>

using namespace std;
typedef long long ll;

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<int> > g(N);
  for (int i = 0; i < M; ++i) {
    int A, B;
    cin >> A >> B;
    --A; --B;
    g[A].push_back(B);
    g[B].push_back(A);
  }
  vector<int> par(N);
  vector<bool> visited(N);
  queue<int> q;
  visited[0] = true;
  par[0] = -1;
  q.push(0);
  while (not q.empty()) {
    int u = q.front();
    q.pop();
    for (auto v : g[u]) {
      if (not visited[v]) {
	par[v] = u;
	visited[v] = true;
	q.push(v);
      }
    }
  }
  cout << "Yes" << endl;
  for (int i = 1; i < N; ++i) {
    cout << par[i] + 1 << endl;
  }
  return 0;
}


Measured memory_bytes: 9620
def solve():
    N, K  = map(int, input().split())
    H = sorted([int(input()) for _ in range(N)])
    ans = float("inf")
    for i in range(N-K+1):
        ans = min(ans, H[i+K-1]-H[i])
    print(ans)

if __name__ == '__main__':
    solve()

Measured memory_bytes: 8280
# -*- coding:utf-8 -*-
import sys
if __name__ == "__main__":
    n = int(input())
    s = [ input() for tmp in range(n) ]
    alphabetDic = { alphabet : 0 for alphabet in [ chr(tmp) for tmp in range(ord('A'), ord('A')+26) ] }
    ans = 0
    for word in s:
        alphabetDic[word[0]] += 1
    factors = [ alphabetDic[tmp] for tmp in ['M', 'A', 'R', 'C', 'H'] if alphabetDic[tmp] > 0 ]
    if len(factors) <= 2:
        print(ans)
        sys.exit()
    for tmp in range(len(factors)):
        for tmp2 in range(tmp+1, len(factors)):
            for tmp3 in range(tmp2+1, len(factors)):
                ans += factors[tmp]*factors[tmp2]*factors[tmp3]
    else:
        print(ans)

Measured memory_bytes: 9776
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;

int main()
{

	ios_base:: sync_with_stdio(false); cin.tie(0);
	int n; cin>>n;
	int L; cin>>L;
	ll sum=0;
	for(int i=1; i<=n; i++) {
		sum+=L+i-1;
	}
//	cout<<sum<<endl;
	ll lol=sum;
	ll ans=0;
	ll mn=1e9;
	for(int i=1; i<=n; i++) {
		lol-=(L+i-1);
		if(abs(sum-lol)<mn) {
			mn=abs(sum-lol);
			ans=lol;
		}
		lol+=(L+i-1);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int man = 1e4+10;
#define IOS ios::sync_with_stdio(0)
template<typename T>T gcd(T a, T b) {return b==0?a:gcd(b, a%b);}
template<typename T>T exgcd(T a,T b,T &g,T &x,T &y){if(!b){g = a,x = 1,y = 0;}else {exgcd(b,a%b,g,y,x);y -= x*(a/b);}}
#ifndef ONLINE_JUDGE
#define debug(fmt, ...) {printf("debug ");printf(fmt,##__VA_ARGS__);puts("");}
#else
#define debug(fmt, ...)
#endif
typedef long long ll;
const ll mod = 1e9+7;
struct node{
	int w,v;
	friend bool operator <(node a,node b){
		return a.w < b.w;
	}
}a[man];
int dp[man];

int main() {
	#ifndef ONLINE_JUDGE
		//freopen("in.txt", "r", stdin);
		//freopen("out.txt","w",stdout);
	#endif
	int n,t;
	cin >> n >> t;
	for(int i = 1;i <= n;i++)cin >> a[i].w >> a[i].v;
	sort(a+1,a+1+n);
	for(int i = 1;i <= n;i++){
		for(int j = t + a[i].w - 1;j >= a[i].w ;j--){
			dp[j] = max(dp[j],dp[j-a[i].w] + a[i].v);
		}
	}
	int ans = 0;
	for(int i = 1;i <= n;i++)ans = max(ans,dp[t+a[i].w-1]);
	cout <<ans <<endl;
	return 0;
}

Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx") 
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i<(b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define dF2(i,a,b) for(int i=(a);i>(b);--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define INF 0x3f3f3f3f
#define INFll 0x3f3f3f3f3f3f3f3f
#define y0 _lxybz_
#define y1 _ljmnzyzhhhoscartxdy_
typedef long double ld;
typedef long long ll;
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize
#define lo(x) ((x)&(-(x)))
#define trav(a, x) for (auto &a : x)
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
const ld Pi = 4*atan((ld)1);
template<class T> void chmin(T &a,const T&b) { a = min(a, b); }
template<class T> void chmax(T &a,const T&b) { a = max(a, b); }
namespace IO{
template<class T> inline void read(T&ret)
{
	ret=0; int f=1; char c=getchar();
	while(c<48||c>57){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>=48 && c<=57)ret=ret*10+c-48,c=getchar();
	ret*=f;
}
template<class T> inline void prin(const T&ret)
{
	if(!ret){putchar(48);return;} static T o; o=ret;
	if(o<0){putchar('-');o=-o;}
	static int op[25],tt; tt=0;
	while(o){
		op[++tt]=o%10;
		o/=10;
	}
	for(int i=tt;i;--i)putchar(op[i]+48);
}
template<class T> inline void pri_(const T&ret)
{
	prin(ret);putchar(' ');
}
template<class T> inline void priE(const T&ret)
{
	prin(ret);putchar('\n');
}
}
using namespace IO;

#define N 
#define MO 1000000007
inline int ksm(int p, int k)
{
	static int vv[70];
	vv[0]=p; int s=1;
	for(int i=1; i<=29; ++i)vv[i]=(long long)vv[i-1]*vv[i-1]%MO;
	for(int i=29; i>=0; --i){
		if(k>=1<<i){
			k-=1<<i;
			s=(long long)s*vv[i]%MO;
		}
	}
	return s;
}
int n,a,b,op;
inline void _Sol_()
{
	read(n);read(a);read(b);
	if(n<=2){
		priE(0);return;
	}
	int _op=1;
	op=1; int ss=(ksm(2,n)+MO-1)%MO;
	F(i,n-a+1,n)op=(ll)op*i%MO;F(i,n-b+1,n)_op=(ll)_op*i%MO;
	F(i,1,a)op=(ll)op*ksm(i,MO-2)%MO;F(i,1,b)_op=(ll)_op*ksm(i,MO-2)%MO;
	ss=(ss+MO-_op)%MO;
	priE((ss+MO-op)%MO);
}

int main()
{
	int T=1; //read(T);
	while(T--)_Sol_();
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=60,inf=1e9;
struct xxx{
	int y,nxt,mark;
};
int mark[N],d[N],vis[N];
int n,m,ban,ans,T;
struct Tree{/*{{{*/
	xxx a[N*2];
	int h[N],pre[N];
	int tot;
	void init(){
		memset(h,-1,sizeof(h));
		memset(pre,-1,sizeof(pre));
		tot=0;
	}
	void add(int x,int y){a[++tot].y=y; a[tot].nxt=h[x]; h[x]=tot; a[tot].mark=0;}
	void dfs(int fa,int x){
		int u;
		pre[x]=fa;
		for (int i=h[x];i!=-1;i=a[i].nxt){
			u=a[i].y;
			if (u==fa||u==ban) continue;
			dfs(x,u);
		}
	}
}ta,tb;/*}}}*/
namespace G{/*{{{*/
	xxx a[N*2];
	int h[N],inst[N],vis[N];
	int tot;
	void init(){
		memset(h,-1,sizeof(h));
		tot=0;
	}
	void add(int x,int y){a[++tot].y=y; a[tot].nxt=h[x]; h[x]=tot;/*printf("%d %d\n",x,y);*/}
	bool dfs(int x){
		int u;
		inst[x]=1; vis[x]=1;
		for (int i=h[x];i!=-1;i=a[i].nxt){
			u=a[i].y;
			if (!vis[u]){
				if (!dfs(u)) return false;
			}
			else if (inst[u])
				return false;
		}
		inst[x]=0;
		return true;
	}
	bool NoCir(){
		memset(vis,0,sizeof(vis));
		memset(inst,0,sizeof(inst));
		for (int i=1;i<=n;++i)
			if (!vis[i])
				if (!dfs(i)) return false;
		return true;
	}
}/*}}}*/
int Tm;
void dfs(int fa,int x){
	int u,tm;
	tm=++Tm;
	vis[x]=1;
	for (int i=ta.h[x];i!=-1;i=ta.a[i].nxt) mark[ta.a[i].y]=tm;
	for (int i=tb.h[x];i!=-1;i=tb.a[i].nxt){
		u=tb.a[i].y;
		if (u==fa||u==ban||mark[u]!=tm) continue;
		dfs(x,u);
	}
}
int solve(int rt){
	int ret=0;
	G::init();
	ban=rt;
	memset(ta.pre,0,sizeof(ta.pre));
	ta.dfs(0,rt);
	memset(tb.pre,0,sizeof(tb.pre));
	tb.dfs(0,rt);

	memset(vis,0,sizeof(vis));
	dfs(0,rt);

	for (int i=1;i<=n;++i){
		if (vis[i]) continue;
		if (!vis[ta.pre[i]]) 
			G::add(i,ta.pre[i]);
		if (!vis[tb.pre[i]]) 
			G::add(tb.pre[i],i);
		++ret;
	}
	if (!G::NoCir()) return inf;
	return ret;
}
void Solve(){
	ans=inf;
	for (int i=1;i<=n;++i) 
		ans=min(ans,solve(i));
	int tmp;
	for (int i=1;i<=n;++i){
		if (d[i]!=1) continue;
		for (int j=1;j<=n;++j){
			if (i==j||j==ta.a[ta.h[i]].y) continue;
			tmp=ta.a[ta.h[i]].y;
			ta.a[ta.h[i]].y=j;
			int ttmp=ans;
			ans=min(ans,solve(i)+1);
			if (ttmp!=ans&&ans==1)
				int debug=1;
			ta.a[ta.h[i]].y=tmp;
		}
	}
	if (ans==inf) ans=-1;
	printf("%d\n",ans);
}
void init(){
	ta.init();
	tb.init();
	memset(d,0,sizeof(d));
}

int main(){
#ifndef ONLINE_JUDGE
	//freopen("a.in","r",stdin);
#endif
	int x,y;
	scanf("%d",&T);
	for (int o=1;o<=T;++o){
		scanf("%d",&n);
		init();
		for (int i=1;i<n;++i){
			scanf("%d%d",&x,&y);
			ta.add(x,y); ta.add(y,x);
			++d[x]; ++d[y];
		}
		for (int i=1;i<n;++i){
			scanf("%d%d",&x,&y);
			tb.add(x,y); tb.add(y,x);
		}
		Solve();
	}
}

Measured memory_bytes: 384
a,b,c,d= map(int, input().split())
alice=[0]*(b-a+1)
bob=[0]*(d-c+1)
ct=0
for i in range (a,b+1):
    alice[ct]=i
    ct+=1
ct=0
for i in range (c,d+1):
    bob[ct]=i
    ct+=1
ans=len(set(alice)&set(bob))
if ans==0:
    print(ans)
else:
    print(ans-1) 

Measured memory_bytes: 3064
N = int(input())
S = input()

res = 0
for i in range(N-2):
    n = 1
    while True:
        j = i+n
        k = j+n
        if k > N-1: break
        res += (S[i] != S[j] and S[j] != S[k] and S[k] != S[i])
        n += 1
    
    
rgb = S.count("R") * S.count("G") * S.count("B")
print(rgb - res)


Measured memory_bytes: 9160
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>
#include <map>

typedef long long ll;
#define rep(i, a, n) for(int i = a; i<n; i++)
#define ALL(a) begin(a), end(a)
#define mii map<int, int>
#define msi map<string, int>
#define vi vector<int>
#define vl vector<ll>
#define MOD 1000000007
#define INF 1e9
#define showVector(v) rep(i,0,v.size()){p(v[i]);p(" ")} pl("")
#define p(s) std::cout << s ;
#define pl(s)  std::cout << s << endl;
using namespace std;

// 素数判定 O(√n)
bool is_prime(int n){
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0) return false;
    }
    return true;
}

// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

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;
}
int main() {
    int N;
    cin >> N;
    vl a(N);
    map<char, ll> mp;
    ll numbers = 0;
    int kinds = 0;
    rep(i, 0, N) {
        string s;
        cin >> s;
        if (s[0] == 'M' || s[0] == 'A' || s[0] == 'R' || s[0] == 'C' || s[0] == 'H') {
            mp[s[0]]++;
            numbers++;
        }
    }

    string march = "MARCH";
    ll res = 0;
    rep(a, 0, 5) {
        rep(b, a+1, 5) {
            rep(c, b+1, 5) {
                res += mp[march[a]] * mp[march[b]] * mp[march[c]];
            }
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 1024
# https://abc095.contest.atcoder.jp/tasks/arc096_a

use strict;

chomp(my $input = <STDIN>);
my ($priceA, $priceB, $priceAB, $numA, $numB) = split(/ /, $input);
my $total = 0;
my $numAB = 0;

# A or Bを優先して買う場合
if ( ($priceA + $priceB) / 2 < $priceAB )
{
    $total = $priceA * $numA + $priceB * $numB;
    print $total . "\n";
    exit 0;
}

# ABを優先して買う場合

# 数量が少ない方を全部満たすだけABを買う
{
    my $min = $numA > $numB ? $numB : $numA;
    $numA -= $min;
    $numB -= $min;
    $numAB = 2 * $min;
}

# 残りについてABのほうがお得ならABで満たす
{
    if ($numA > 0 && $priceA > ($priceAB * 2))
    {
        $numAB += 2 * $numA;
        $numA = 0;
    }

    if ($numB > 0 && $priceB > ($priceAB * 2))
    {
        $numAB += 2 * $numB;
        $numB = 0;
    }
}


$total = $priceA * $numA + $priceB * $numB + $priceAB * $numAB;
print $total . "\n";

Measured memory_bytes: 512
#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef long long ll;
// constexpr ll MOD = 998244353;
constexpr ll MOD = 1000000007;

// struct UnionFind {
//     vector<ll> par;
//     vector<ll> siz;
    
//     UnionFind(ll N): par(N), siz(N,1LL) {
//         for (ll i=0;i<N;i++) par[i] = i;
//     }

//     ll root(ll x) {
//         if (par[x] == x) return x;
//         else return par[x] = root(par[x]);
//     }

//     void unite(ll x, ll y) {
//         ll rx = root(x);
//         ll ry = root(y);
//         if (rx == ry) return;
//         par[rx] = ry;
//         siz[ry] += siz[rx];
//     }

//     bool same(ll x, ll y) {
//         ll rx = root(x);
//         ll ry = root(y);
//         return rx == ry;
//     }

//     ll size(ll x) {
//         return siz[root(x)];
//     }
// };

int main(void) {
    string S, T, U;
    int A, B;
    cin >> S >> T >> A >> B;
    cin >> U;
    if (S == U) A--;
    else B--;
    cout << A << " " << B << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
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; }
const int INF = 1e9+7;

int n, A, B, C;
vector<int> l(8);

int dfs(int cur, int a, int b, int c) {
    if(cur == n) {
        if(a > 0 && b > 0 && c > 0) {
            return abs(a-A) + abs(b-B) + abs(c-C) - 30;
        }else return INF;
    }
    int r0 = dfs(cur+1, a, b, c);
    int r1 = dfs(cur+1, a+l.at(cur), b, c) + 10;
    int r2 = dfs(cur+1, a, b+l.at(cur), c) + 10;
    int r3 = dfs(cur+1, a, b, c+l.at(cur)) + 10;
    return min({r0, r1, r2, r3});
}

int main() {
    cin >> n >> A >> B >> C;
    for(int i = 0; i < n; ++i) cin >> l.at(i);

    cout << dfs(0, 0, 0, 0) << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main(){
  int N, M, a;
  priority_queue<int> pq;

  cin >> N >> M;

  for(int i=0; i<N; i++) {
    cin >> a;
    pq.push(a);
  }

  for(int i=0; i<M; i++) {
    int p = pq.top(); pq.pop();

    pq.push(p / 2);
  }

  ll ans = 0;
  while(pq.size()) {
    ans += pq.top();
    pq.pop();
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 892
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int A, B;

		final int N = scanner.nextInt();
		prepare(N);
		int[] except = new int[N];

		final int M = scanner.nextInt();
		final int K = scanner.nextInt();

		for (int i = 0; i < M; i++) {
			A = scanner.nextInt() - 1;
			B = scanner.nextInt() - 1;
			union(A, B);
			except[A]++;
			except[B]++;
		}

		for (int i = 0; i < K; i++) {
			A = scanner.nextInt() - 1;
			B = scanner.nextInt() - 1;
			if (find(A) == find(B)) {
				except[A]++;
				except[B]++;
			}
		}

		scanner.close();

		for (int i = 0; i < N; i++) {
			System.out.print(desc[find(i)] - except[i]);
			System.out.print(i == N - 1 ? "\n" : " ");
		}
	}

	static int[] parent;
	static int[] desc;

	static void prepare(int n) {
		parent = new int[n];
		for (int i = 0; i < n; i++) {
			parent[i] = i;
		}
		desc = new int[n];
	}

	static int find(int x) {
		if (parent[x] == x)
			return x;
		else
			return find(parent[x]);
	}

	static void union(int x, int y) {
		int xRoot = find(x);
		int yRoot = find(y);
		if (xRoot == yRoot)
			return;
		if (desc[xRoot] >= desc[yRoot]) {
			parent[yRoot] = xRoot;
			desc[xRoot] += desc[yRoot] + 1;
		} else {
			parent[xRoot] = yRoot;
			desc[yRoot] += desc[xRoot] + 1;
		}
	}
}


Measured memory_bytes: 95360
def f(n):
    if n % 2:
        return 3 * n + 1
    else:
        return n / 2


def main():
    s = int(input())
    l = [s]
    c = s
    while True:
        c = int(f(c))
        if c in l:
            n = len(l) + 1
            break
        l.append(c)
    print(n)



if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
N = int(input())
A = [0] * N
Z = 0
cnt = 0
for i in range(N):
  a = int(input())
  if a > Z + 1:
    z = (a - 1) // (Z + 1)
    cnt += z
    a = 1
  Z = max(a, Z)
print(cnt)

Measured memory_bytes: 3956
#include<bits/stdc++.h>
using namespace std;
int main(){

    int a[5];
    //int b;
    for(int i=0;i<5;i++) cin>>a[i];
    for(int i=0;i<5;i++) {
        if(a[i]==0){
            cout<<i+1<<endl;
        break;}
    }
   // cout<<b+1<<endl;
}


Measured memory_bytes: 3616
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
using namespace std;

int main() {
    int n;
    cin >> n;
    double a[n];
    double total = 0;
    rep(i, n) {
        cin >> a[i];
        total += 1 / a[i];
    }

    cout << fixed << setprecision(15) << 1 / total << endl;
}

Measured memory_bytes: 256
/* Isn't passion overrated?*/

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long
#define mod 1000000007
using namespace std;
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
vector<vector<ll> >arr;
vector<ll>cost;
vector<ll>ans,out;
void dfs(ll root, ll parent)
{
    bool b = false;
    ll val = -1;
    ll idx = -1;
    vector<ll> :: iterator itr = lower_bound(ans.begin(),ans.end(),cost[root]);
    if(itr == ans.end())
    {
        ans.pb(cost[root]);
    }
    else
    {
        idx = itr - ans.begin();
        val = ans[idx];
        ans[idx] = cost[root];
        b = true;
    }
    out[root] = ans.size();
    for(ll i = 0; i < arr[root].size(); i++)
    {
        if(arr[root][i] == parent)
            continue;
        dfs(arr[root][i],root);
    }
    if(b)
    {
        ans[idx] = val;
    }
    else
    {
        ans.pop_back();
    }
}
int main()
{
    ios_base:: sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
    ll n;
    cin>>n;
    arr = vector<vector<ll> >(n+1);
    cost = vector<ll>(n+1);
    for(ll i = 1; i <= n; i++)
        cin>>cost[i];
    out = vector<ll>(n+1);
    for(ll i = 0; i < n-1; i++)
    {
        ll a,b;
        cin>>a>>b;
        arr[a].pb(b);
        arr[b].pb(a);
    }
    dfs(1,1);
    for(ll i = 1; i < out.size(); i++)
        cout<<out[i]<<endl;
    return 0;
}


Measured memory_bytes: 31620
void main() {
	auto D = ri;
	iota(D).map!(v => v % 26 + 1).each!writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

long rl() {
	return readAs!long;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 2752
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <iterator>
#include <cmath>
#include <deque>
#include <stack>
#include <functional>
#include <queue>
using namespace std;
#define int unsigned long long

signed main()
{
    {
        if (fopen("input.txt", "r")) {
            freopen("input.txt", "r", stdin);
            freopen("output.txt", "w", stdout);
        }
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(NULL);
        std::cout.tie(NULL);
    }

    int a, b, c;
    cin >> a >> b >> c;
    if (c <= a + b) {
        cout << "No";
        return 0;
    }
    if (4LL * a * b < (c - a - b) * (c - a - b))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define rep1(i,n) for(int i=1;i<=int(n);++i)
#define all(a) a.begin(),a.end()
#define lb(s,x) lower_bound(all(s),x)-s.begin()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define INF 1e9
typedef long long ll;

int n;
vector<string> s;

int solve(int Y,int X){
    int W = 2*n-max(Y,X);
    vector<string> s1;
    rep(i,W){
        s1.push_back(s[Y+i].substr(X,W));
    }

    // bool b[W][W] = {};
    int imos[W][W+1] = {};
    rep(y,W){
        rep(x,W){
            imos[y][x+1] = imos[y][x] + (s1[y][x] != s1[x][y]);
        }
    }

    int res = 0;
    rep(i,2*n){
        int sy = Y+i, sx = X+i;
        if(sx>=n || sy>=n){
            break;
        }
        bool ok = true;
        rep(j,n){
            if(imos[j][j+1] != imos[j][n+1]){
                ok = false;
            }
        }
        if(ok) res++;
    }
    return res;
}


int main(void){
    cin>>n;
    s.resize(n);
    rep(i,n){
        cin>>s[i];
        s[i] += s[i];
    }
    rep(i,n){
        s.push_back(s[i]);
    }
    int res = 0;

    rep(i,n){
        res += solve(0,i);
    }
    rep1(i,n-1){
        res += solve(i,0);
    }
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 2392
#define Bobyama
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>

#define _overload(a, b, c, d, ...) d
#define _rep1(X, A, Y) for (int (X) = (A);(X) <= (Y);++(X))
#define _rep2(X, Y) for (int (X) = 0;(X) < (Y);++(X))
#define rep(...) _overload(__VA_ARGS__, _rep1, _rep2)(__VA_ARGS__)
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define all(X) (X).begin(),(X).end()
#define len(X) ((int)(X).size())
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = 100000;
int N, M;
int a[MAX_N];
bool rotten[MAX_N+1];

ll dp[MAX_N+1];

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

  cin >> N >> M;
  rep(i, M) cin >> a[i];

  rep(i, M) rotten[a[i]] = true;

  dp[0] = dp[1] = 1;

  for (int i = 2; i <= N; ++i) {
    if (rotten[i]) continue;
    if (!rotten[i-2]) dp[i] = dp[i-2];
    if (!rotten[i-1]) dp[i] = mod(dp[i]+dp[i-1], MOD);
  }

  cout << dp[N] << endl;

  return 0;
}


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

int main(int argc, char const *argv[])
{
	int x,y,e;
	while(cin>>x>>e,x)
	{
		double ans=100000;
		y=0;
		while(x>=0)
		{
			ans=min(ans,fabs(sqrt(x*x+y*y)-e));
			--x,++y;
		}
		printf("%.6f\n",ans);
	}
	return 0;
}


Measured memory_bytes: 3160
N = int(input())
S = input()

cum_e = [0]
for c in S:
    cum_e.append(cum_e[-1] + int(c == 'E'))

ans = N
for i in range(N):
    tmp = i - cum_e[i] + cum_e[-1] - cum_e[i+1]
    ans = min(ans, tmp)
print(ans)

Measured memory_bytes: 15520
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <string>
#define REP(i,a,b) for (int i = a; i < (b); i++)
#define sz(t) int(t.size())
#define INF 1000000000
const int DIV = 1000000000 + 7;
using namespace std;
typedef long long ll;

int dp[62][2][2][2];

int main(void) {
    ll l,r;
    cin >> l >> r;
    dp[60][0][0][0] = 1;

    for (int i = 59; i >= 0; i--) {
        int lb = l >> i & 1; 
        int rb = r >> i & 1; 

        // cout << lb << " " << rb << endl;
        // s means most significant bit is the same or unknown
        // j means x is greater than l
        // k means y is less than r
        REP(j, 0, 2) REP(k, 0, 2) REP(s, 0, 2) {
            int pre = dp[i + 1][j][k][s];
            REP(x, 0, 2) REP(y, 0, 2) {
                int ni = i, nj = j, nk = k, ns = s;
                if (x && !y) continue;

                if (!s && x != y) continue;
                if (!s && x&y) ns = 1;

                if (!j && lb && !x) continue;
                if (!j && !lb && x) nj = 1;

                if (!k && !rb && y) continue;
                if (!k && rb && !y) nk = 1;

                dp[ni][nj][nk][ns] += pre;
                dp[ni][nj][nk][ns] %= DIV;
            }
        }
    }

    ll ans = 0;
    REP(j, 0, 2) REP(k, 0, 2) REP(s, 0, 2) {
        ans += dp[0][j][k][s];
        ans %= DIV;
    }

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


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

int h,w,tc;

void cpy(char dst[10][10], const char src[10][10]) {
    for(int j=0; j<10; j++)
        for(int i=0; i<10; i++)
            dst[j][i] = src[j][i];
}
void paint(char dst[10][10], int sc, int tc, int x, int y) {
    if(x<0 || y<0 || x>=w || y>=h) return;
    if(sc == tc) return;
    if(dst[y][x] == sc) {
        dst[y][x] = tc;
        paint(dst, sc, tc, x-1, y);
        paint(dst, sc, tc, x, y-1);
        paint(dst, sc, tc, x+1, y);
        paint(dst, sc, tc, x, y+1);
    }
}

int dfs(int d, int c, const char src[10][10]) {
    char map[10][10];
    int res=0;
    memset(map, 0, sizeof(map));


    cpy(map,src);

    paint(map,map[0][0], c, 0, 0);

    if(d==5) {
        int res=0;
        paint(map, map[0][0], 100, 0, 0);
        for(int j=0; j<10; j++)
            for(int i=0; i<10; i++)
                if(map[j][i] == 100) res++;
        return res;

    }


    if(d==4) return dfs(d+1, tc, map);

    for(int cc=1; cc<=6; cc++) {
        res = max(dfs(d+1, cc, map), res);
    }
    return res;
}



int main(void) {
    while(true) {
        char map[10][10] = {};
        scanf("%d%d%d",&h,&w,&tc);
        if(!h) break;

        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++)
                scanf("%d", &map[j][i]);
        printf("%d\n", dfs(0, map[0][0], map));

    }
    return 0;
}

Measured memory_bytes: 1032
using System;

class B
{
	static void Main()
	{
		var h = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
		Console.WriteLine(Gcd(h[0], h[1]));
	}

	static int Gcd(int a, int b) { for (int r; (r = a % b) > 0; a = b, b = r) ; return b; }
}



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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> A(N), B(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
  }
  vector<int> idx(N);
  iota(idx.begin(), idx.end(), 0);
  sort(idx.begin(), idx.end(), [&](int a, int b) { return B[a] < B[b]; });
  int time = 0;
  for (auto i : idx) {
    time += A[i];
    if (time > B[i]) {
      cout << "No" << '\n';
      return 0;
    }
  }
  cout << "Yes" << '\n';
  return 0;
}


Measured memory_bytes: 2560
#include<cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  int a[50];
  for (int i=0;i<=n;i++) a[i]=0;
  for (int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    a[x]+=1;
    a[y]+=1;
  }
  for (int i=1;i<=n;i++){
    cout<<a[i]<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
typedef long long ll;

int main() {
  int a, b, ans = 0;
  cin >> a >> b;
  if (6 <= a && a <= 12) ans = b / 2;
  else if (13 <= a) ans = b;
  cout << ans << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int cnt = 0;
	int arr[3], brr[3] = {1, 0, -1};
	for(int i = 0; i<3; ++i) cin>>arr[i];
	int k;cin>>k;
	vector<int> v;
	for(int i = 0; i < 3; ++i){
		cnt += brr[i]*min(arr[i], k);
		k -= arr[i];
		k = max(k, 0);
	}

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




Measured memory_bytes: 3572
#!/usr/bin/env python

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

ma = ima = 0 
for i in range(n):
    if a[i] >= ma: 
        ma = a[i]
        ima = i 

ans = a[ima]+b[ima]
print(ans)


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

int main() {
  int a, b, c, d, e;
  cin >> a >> b >> c >> d >> e;
  int ans;
  if (a == 0) ans = 1;
  if (b == 0) ans = 2;
  if (c == 0) ans = 3;
  if (d == 0) ans = 4;
  if (e == 0) ans = 5;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int(i)=0;i<(n);i++)
int h,w;
string s[51];

bool a(int x,int y){
  bool f=0;
  if(x>0&&s[y].at(x-1)=='#') f=1;
  if(x<w-1&&s[y].at(x+1)=='#') f=1;
  if(y>0&&s[y-1].at(x)=='#') f=1;
  if(y<h-1&&s[y+1].at(x)=='#') f=1;
  return f;
}

int main(){
  cin>>h>>w;
  bool f=1;
  REP(i,h) cin>>s[i];
  REP(i,h) REP(j,w) if(s[i].at(j)=='#') f=f*a(j,i);
  cout<<(f?"Yes":"No");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MM = 1000000000;
const int MOD = MM + 7;
const int MAX = 510000;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(ll i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
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;}
const ll INF = 1LL << 60;
const double pi = acos(-1.0);

int main() {
    string s; cin >> s;
    if(s == "keyence") {
        cout << "YES" << endl;
        return 0;
    }
    rep(i, s.size()) {
        Rep(j, i, s.size()) {
            string t = "";
            rep(k, s.size()) {
                if(i <= k && k <= j) continue;
                t.push_back(s[k]);
            }
            if(t == "keyence") {
                cout << "YES" << endl;
                return 0;
            }
        }
    }
    cout << "NO" << endl;
}

Measured memory_bytes: 3532
#include "stdio.h"
#define MAX_N 100
#define MAX_W 10000
int dp[MAX_N + 1][MAX_W + 1];
int max(int a,int b) {
	if (a > b)return a;
	else return b;
}
int main()
{
	int n, W;
	int w[MAX_N], v[MAX_W];

	scanf("%d%d", &n, &W);
	for (int i = 0; i < n;i++) {
		scanf("%d%d", &v[i], &w[i]);
	}//入力

	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j <= W; j++) {
			if (j < w[i]) {
				dp[i][j] = dp[i + 1][j];
			}
			else {
				dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
			}
		}
	}//漸化式から解く

	printf("%d\n", dp[0][W]);
    return 0;
}




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

int main() 
{
    long long N, M;
    cin >> N >> M;
    long long sum = 0;
    vector<int>A(M);
    for (int i = 0; i < M; i++) {
        cin >> A.at(i);
        sum += A.at(i);
    }
    
    if (sum <= N) {
        cout << N - sum << endl;
    }else{
        cout << -1 << endl;
    }
}

Measured memory_bytes: 3628
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        sc.nextInt();
        int w=sc.nextInt();
        if(n==1){
            System.out.println(Math.abs(w-sc.nextInt()));
            return;
        }
        int[] nums=new int[n];
        for(int i=0;i<n;i++){
            nums[i]=sc.nextInt();
        }
        System.out.println(Math.max(Math.abs(w-nums[n-1]),Math.abs(nums[n-1]-nums[n-2])));
    }
}

Measured memory_bytes: 26452