akhauriyash/Code-Regression huggingface dataset:
loop {
	n = gets.to_i
	break if n == 0

	schedule = (0..29).map{[]}
	(0..n-1).each{|member|
		gets.split(/\s+/).map(&:to_i)[1..-1].each{|day|
			schedule[day-1] << member
		}
	}

	x_day = -1
	(0..29).each{|current_day|
		current_members = schedule[current_day]
		(current_day-1).downto(0){|old_day|
			old_members = schedule[old_day]
			if current_members & old_members != []
				current_members |= old_members
			end
		}
		if current_members.size == n
			x_day = current_day + 1
			break
		end
	}

	puts x_day
}

Measured memory_bytes: 7124
while 1 :
	w, d = map(int,raw_input().split(" "))
	if w == d == 0: break
	front = map(int,raw_input().split(" "))
	side = map(int,raw_input().split(" "))
	number =  sum(front)
	for h in side:
		if h in front:
			front.remove(h)
		else :
			number += h
	print number

Measured memory_bytes: 4204
package main

import (
	"fmt"
)

func main() {
	type pair struct {
		a int
		b int
	}

	var pairList []pair
	var a, b int
	for {
		fmt.Scan(&a, &b)
		if a == 0 && b == 0 {
			break
		}
		pairList = append(pairList, pair{a: a, b: b})
	}

	for _, pair := range pairList {
		for i := 0; i < pair.a; i++ {
			for j := 0; j < pair.b; j++ {
				if i%2 == 0 {
					if j%2 == 0 {
						fmt.Print("#")
						continue
					}
					fmt.Print(".")
				} else {
					if j%2 == 0 {
						fmt.Print(".")
						continue
					}
					fmt.Print("#")
				}
			}
			fmt.Println()
		}
		fmt.Println()
	}
}



Measured memory_bytes: 1096
n = int(input());
a = n % 10

if a == 2 or a ==4 or a == 5 or a == 7 or a == 9:
  print("hon")
elif a ==0 or a == 1 or a == 6 or a == 8:
  print("pon")
else:
  print("bon")
  


Measured memory_bytes: 9164
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define repeat(i,a,b) for(int i=(a),i##__end=(b);i<i##__end;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,i##__end=(a);i>=i##__end;i--)
#define mst(a,x) memset((a),(x),sizeof(a))
#define pii pair<int,int>

char s[210][210];
int co[210];
bool f=true;
int n;
void dfs(int x,int c){
	if(co[x]==c)return;
	if(co[x]==3-c){
		f=false;
		return;
	}
	co[x]=c;
	repeat(i,0,n)
		if(s[x][i]=='1')dfs(i,3-c);
}

struct node{
	int to,dis;
	bool operator<(node x)const{
		return x.dis<dis;
	}
};
priority_queue<node> q;
int dis[210],vis[210];
int ans=10000;

void dijkstra(const int s0){
	repeat(i,0,n){
		vis[i]=0;
		dis[i]=10000;
	}
	dis[s0]=0;
	q=priority_queue<node>();
	q.push((node){s0,0});
	while(!q.empty()){
		int x=q.top().to; q.pop();
		if(vis[x])continue; vis[x]=1;
		repeat(p,0,n)
		if(s[x][p]=='1'){
			if(dis[p]>dis[x]+1){
				dis[p]=dis[x]+1;
				if(!vis[p])q.push((node){p,dis[p]});
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin>>n;
	repeat(i,0,n){
		cin>>s[i];
	}
	dfs(0,1);
	if(f==false){cout<<-1<<endl;return 0;}
	/*repeat(i,0,n)
	repeat(j,0,n)
	if(s[i][j]=='1'){
		s[i][j]=s[j][i]='0';
		dijkstra(i);
		ans=min(ans,dis[j]+1);
		s[i][j]=s[j][i]='1';
	}*/
	if(1 || ans==10000){
		ans=0;
		repeat(i,0,n){
			dijkstra(i);
			repeat(j,0,n)
				ans=max(ans,dis[j]+1);
		}
	}
	//else ans=ans/2+1;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define I_O		ios::sync_with_stdio(false),cin.tie(0)
#define ll		long long
#define ff		first
#define ss		second
#define mod 		1000000007
#define rep(i,n)	for(ll i=1;i<=n;i++)
#define repv(i,a,n)	for(ll i=a;i<=n;i++)
#define pb 		push_back
#define newl		'\n'
#define deb(x)		cout<<x<<" "
set<ll> s;
int a[100005],b[100005];
int main() 
{  
	I_O;
	int a[6];	rep(i,5)	cin>>a[i];
	rep(i,5)
	{
		if(a[i] == 0)
		{
			cout<<i;
			break;
		}
	}
} 

Measured memory_bytes: 3656
# -*- coding: utf-8 -*-
from itertools import product
import numpy as np
def solve():
    H, W = map(int, input().split())
    M = np.zeros((H,W), dtype=int)
    for h in range(H):
        M[h] = np.array(list(int(x=='.') for x in input()))

    Dist = float('inf')*np.ones((H*W, H*W))
    
    u = M&np.roll(M, 1, axis=0)&np.concatenate((np.zeros((1,W), dtype=int),np.ones((H-1,W), dtype=int)), axis=0)
    d = M&np.roll(M, -1, axis=0)&np.concatenate((np.ones((H-1,W), dtype=int),np.zeros((1,W), dtype=int)), axis=0)
    l = M&np.roll(M, 1, axis=1)&np.concatenate((np.zeros((H,1), dtype=int),np.ones((H,W-1), dtype=int)), axis=1)
    r = M&np.roll(M, -1, axis=1)&np.concatenate((np.ones((H,W-1), dtype=int),np.zeros((H,1), dtype=int)), axis=1)

    hu, wu = np.where(u)
    Dist[hu*W+wu, (hu-1)*W+wu] = 1
    hd, wd = np.where(d)
    Dist[hd*W+wd, (hd+1)*W+wd] = 1
    hl, wl = np.where(l)
    Dist[hl*W+wl, hl*W+wl-1] = 1
    hr, wr = np.where(r)
    Dist[hr*W+wr, hr*W+wr+1] = 1
    for v3 in range(H*W):
        Dist = np.minimum(Dist, Dist[:,v3:v3+1] + Dist[v3:v3+1,:])
    
    Dist[Dist==float('inf')] = -1
    Dist[np.arange(H*W),np.arange(H*W)] = -1

    return str(int(Dist.max()))

if __name__ == '__main__':
    print(solve())

Measured memory_bytes: 16236
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
//#include<set>
//#include<iostream>
using namespace std;

int l1,r1,l2,r2;
int main()
{
	scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
	if (l1<=l2 && r2<=r1) printf("%d\n",r2-l2);
	else if (l2<=l1 && r1<=r2) printf("%d\n",r1-l1);
	else if (r1<=l2) printf("0\n");
	else if (r2<=l1) printf("0\n");
	else printf("%d\n",min(r2,r1)-max(l2,l1));
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
signed main(){
  int n,z,w;cin>>n>>z>>w;
  vector<int> a(n);
  rep(i,n)cin>>a[i];
  int score=max(a[0]-w,w-a[0]);
  if(n>=2){
    int x=max(w-a[n-1],a[n-1]-w);
    int y=max(a[n-2]-a[n-1],a[n-1]-a[n-2]);
    score=max(x,y);
  }
  cout<<score<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int mod = 1e9+7;
const int maxn = 2e5+5;
int main() {
	string s;
	cin>>s;
	ll ans  = 0;
	for(int i=0;i<s.length();i++){
		ans = ans*10+(s[i]-'0');
		ans%=9;
	}
	if(ans==0){
		cout<<"Yes"<<endl;
	}else {
		cout<<"No"<<endl;
	}
	
    return 0;
}



Measured memory_bytes: 3748
#include <stdio.h>
#include <inttypes.h>

#define MOD_BY UINT32_C(1000000007)

uint32_t add(uint32_t a, uint32_t b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

uint32_t mul(uint32_t a, uint32_t b) {
	uint32_t r = 0;
	while (b > 0) {
		if (b & 1) r = add(r, a);
		a = add(a, a);
		b >>= 1;
	}
	return r;
}

int main(void) {
	uint32_t count[1024] = {0};
	int N;
	int i;
	uint32_t answer = 1;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 2; i <= N; i++) {
		int num = i;
		int j;
		for (j = 2; j * j <= num; j++) {
			while (num % j == 0) {
				num /= j;
				count[j]++;
			}
		}
		if (num > 1) count[num]++;
	}
	for (i = 2; i <= N; i++) {
		answer = mul(answer, add(count[i], 1));
	}
	printf("%" PRIu32 "\n", answer);
	return 0;
}


Measured memory_bytes: 128
n=int(input())
a=[[[0 for i in range(10)]for j in range(3)]for k in range(4)]
for q in range(n):
    b,f,r,v=map(int,input().split())
    a[b-1][f-1][r-1]+=v
for b in range(4):
    for f in a[b]:
        print(" "+" ".join(map(str,f)))
    if (not b==3):
        print("####################")


Measured memory_bytes: 5604
#include <iostream>
#include <vector>
using namespace std;
int N;
vector <int> G[5005];
int DP[5005][5005][2];
int Tmp[5005][2];
const int MOD = 1000000007;
int Sz[5005];
int Val[5005];
void Read()
{
    cin >> N;
    for(int i = 1; i < N; i++)
    {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
void precalcVal()
{
    Val[2] = 1;
    for(int i = 4; i <= N; i += 2)
    {
        Val[i] = (1LL * Val[i - 2] * (i - 1)) % MOD;
    }
}
void DFS(int node, int father)
{
    Sz[node] = 1;
    for(int i = 0; i < G[node].size(); i++)
    {
        int neighb = G[node][i];
        if(neighb == father)
            continue;
        DFS(neighb, node);
        Sz[node] += Sz[neighb];
    }
}
inline void Add(int& x, int y)
{
    x += y;
    while(x >= MOD)
        x -= MOD;
}
void DFS2(int node, int father)
{
    DP[node][1][1] = 1;
    int limit = 1;
    for(int i = 0; i < G[node].size(); i++)
    {
        int neighb = G[node][i];
        if(neighb == father)
            continue;
        DFS2(neighb, node);
        for(int i = 1; i <= limit + Sz[neighb]; i++)
            Tmp[i][0] = Tmp[i][1] = 0;
        for(int i = limit; i >= 1; i--)
        {
            for(int k = 0; k <= 1; k++)
            {
                for(int j = 1; j <= Sz[neighb]; j++)
                {
                    for(int l = 0; l <= 1; l++)
                    {
                        Add(Tmp[i + j][(l ^ k ^ 1)], (1LL * DP[node][i][k] * DP[neighb][j][l]) % MOD);
                        int aux = (1LL * DP[node][i][k] * DP[neighb][j][l]) % MOD;
                        Add(Tmp[i][(l ^ k)], (1LL * aux * Val[j]) % MOD);
                    }
                }
            }
        }
        limit += Sz[neighb];
        for(int i = 1; i <= limit; i++)
            DP[node][i][0] = Tmp[i][0], DP[node][i][1] = Tmp[i][1];
    }
}

void Solve()
{
    DFS(1, 0);
    DFS2(1, 0);
    int ans = 0;
    for(int i = 1; i < N; i++)
    {
        int val = (1LL * DP[1][i][0] * Val[i]) % MOD;
        Add(val, MOD - (1LL * DP[1][i][1] * Val[i]) % MOD);
        Add(ans, val);
    }
    ans = ((Val[N] - ans) % MOD + MOD) % MOD;

    cout << ans << "\n";
}
int main()
{
    Read();
    precalcVal();
    Solve();
    return 0;
}


Measured memory_bytes: 195328
s=input()
ans=chk=0
for i in range(2**(len(s)-1)):
    d=bin(i)[2:]
    d=("0"*(9-len(d))+d)[::-1]
    t=int(s[0])
    for i in range(len(s)-1):
        if d[i]=="0":
            t*=10
            t+=int(s[i+1])
        else:
            ans+=t
            t=int(s[i+1])
    ans+=t

print(ans)

Measured memory_bytes: 40688
import java.util.*;
public class Main
{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String str=in.next();
		int c=0;
		for(int i=0;i<=str.length()/2-1;i++)
		{
			if(str.charAt(i)!=str.charAt(str.length()-(i+1)))
			{
				c++;
			}
		}
		System.out.println(c);
	}
}

Measured memory_bytes: 35740
#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vll;
 
#define  pb     push_back
#define  all(x) (x).begin(), (x).end()
#define  rep(i,a,b) for(int i=a ; i<b ; ++i)
#define  repr(i,a,b) for(int i=a ; i>=b ; --i)
#define  deb(x) cout << #x << " - " << x << "\n";
#define  IOS    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define  D2(x)  { cerr << "[" << #x << ": "; for(auto it:x) cerr << it << " "; cerr << "]\n"; }
#define  ps(x,y) fixed<<setprecision(y)<<x
 
#define PI 3.141592653589793
const ll MOD = 1e9 + 7;
const ll INF = 1000000000000;
const ll MAX_N = 1e6 + 2;

void solve(){
    int n,k; cin >> n >>k;
    vi v(n);
    rep(i,0,n) cin >> v[i];
    
    rep(i,0,n-k) {
        if(v[i]<v[i+k]) cout << "Yes\n";
        else cout << "No\n";
    }
}
 
int main() {
    IOS;
    // int t; cin >> t;
    int t = 1; 
    while(t--) solve();
}

Measured memory_bytes: 3936
from collections import deque

def execute(d, command):
    func = command[0]
    if func == "insert":
        param = command[1]
        d.appendleft(param)
    elif func == "delete":
        param = command[1]
        try:
            d.remove(param)
        except:
            pass
    elif func == "deleteFirst":
        d.popleft()
    elif func == "deleteLast":
        d.pop()

def main():
    n = int(input())
    commands = [input().split() for _ in range(n)]

    ans = deque()
    for command in commands:
        execute(ans, command)
    print(*ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 526816
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

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

signed main()
{
    int H,W; cin>>H>>W;
    vector<string> s(H);
    REP(i,H) cin>>s[i];

    REP(i,H) REP(j,W){
        if(s[i][j]=='#') continue;
        int cnt=0;
        REP(k,8){
            int y=i+dy[k];
            int x=j+dx[k];
            if(y<0 or H<=y or x<0 or W<=x) continue;
            if(s[y][x]=='#') cnt++;
        }
        s[i][j]=(char)('0'+cnt);
    }
    REP(i,H) cout<<s[i]<<endl;

}


Measured memory_bytes: 256
/*	author:  Kite_kuma
	created: 2020.09.09 11:36:34 */

#include <iostream>
using namespace std;

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
struct iofast {
	iofast() {
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
	}
} iofast_;
int res;
int a[200000], b[200000];
int main() {
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) cin >> b[i];
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++) res ^= a[i] + b[j];
	cout << res << "\n";
}

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

const int Nmax=200010;

int main() {
	int N;
	ll ans=0;
	cin >> N;
	vector<ll> A(N,0),B(N,0),C(N,0);
	for(int i=0;i < N;i++) cin >> A[i];
	for(int i=0;i < N;i++) cin >> B[i];
	for(int i=0;i < N;i++) cin >> C[i];
	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	sort(C.begin(), C.end());
	vector<ll> hoo(N+2,0);
  	for(int i=0;i < N;i++){
      decltype(A)::iterator it = lower_bound(A.begin(), A.end(),B[i]);
      hoo[i]=(it-A.begin()); //cout <<hoo[i]<<endl;
      hoo[i]+=hoo[abs(i-1)];
    }
	for(int i=N-1;i >= 0;i--){
      	if(C[i] <= B[0]) break;
		decltype(B)::iterator it1 = lower_bound(B.begin(), B.end(),C[i]);
      	if(*(it1-1) <= A[0]) break;
      	
		ans+=hoo[it1-B.begin()-1];
      	//cout <<ans<<endl;
	}

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

Measured memory_bytes: 3328
## グリッドに関する処理
# ABC096C_ Grid Repainting 2

## 考え方
# あるマスが'#'である場合、その上下左右の1つ以上が必ず'#'である必要がある

## for test
# # 1
# height, width = 3, 3
# _s_list = ['.#.', '###', '.#.']

# # 2
# height, width = 5, 5
# _s_list = ['#.#.#', '.#.#.', '#.#.#', '.#.#.', '#.#.#']

# # 3


## for submit
import numpy as np
height, width = map(int, input().split())
_s_list = [input() for i in range(height)]
s_list = [list(ss) for ss in _s_list]  # 列×行に1文字ずつ区切ってリストへ追加 -> 2次元配列化
s_arr  = np.array(s_list)

# print(s_arr)  # debug
its_ok = True
for _h in range(height):
    for _w in range(width):
        # 自分が'#'のときだけチェック
        if s_arr[_h, _w] == '#':
            checker = False
            # 一番上でなければ、上のマスをチェック
            if _h >= 1:
                if s_arr[_h-1, _w] == '#':
                    checker = True
            # 一番下でなければ、下のマスをチェック
            if _h != height-1:
                if s_arr[_h+1, _w] == '#':
                    checker = True
            # 一番左でなければ、左のマスをチェック
            if _w >= 1:
                if s_arr[_h, _w-1] == '#':
                    checker = True
            # 一番右でなければ、右のマスをチェック
            if _w != width-1:
                if s_arr[_h, _w+1] == '#':
                    checker = True
            
            if checker is False:
                its_ok = False
                break
    
    if its_ok is False:
        break

if its_ok:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 12524
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <array>
#include <vector>
#include <functional>
#include <unordered_map> 
#include <map> 
#include <numeric>
#include <limits>
#include <utility>
#include <queue>
#include <random>
#include <bitset>
#include <memory>
#include <complex>
using namespace std;
typedef long long LL;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (a + b == c + d) {
        cout << "Balanced" << endl;
    }
    else if (a + b > c + d) {
        cout << "Left" << endl;
    }
    else {
        cout << "Right" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
using namespace std;
int main(){
    int N , K;
    cin >> N >> K;
    int arr[N];
    for (int i = 0 ; i < N ; i++)
        cin >> arr[i];

    int l = 0 , r = K;
    while(r < N){
        if (arr[r++] > arr[l++])
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}


Measured memory_bytes: 4372
#include <bits/stdc++.h>
#define rep(i,x,n) for(int (i)=(x);(i)<(n);(i)++)
using namespace std;

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

    cout << max(a+b,max(a-b,a*b)) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

constexpr int P = 998244353;

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

    int n, k;
    cin >> n >> k;
    n--;

    vector<int> l(k), r(k);
    for (int j = 0; j < k; j++) {
        cin >> l[j] >> r[j];
        r[j]++;
    }

    vector<int> s(n + 1);
    s[0] = 0;
    s[1] = 1;
    for (int i = 1; i <= n; i++) {
        ll t = 0;
        for (int j = 0; j < k; j++) {
            t += s[max(i - l[j] + 1, 0)];
            t -= s[max(i - r[j] + 1, 0)];
        }
        t %= P;
        if (i == n) {
            if (t < 0) t += P;
            cout << t << endl;
            break;
        }
        (s[i + 1] = s[i] + t) %= P;
    }

    return 0;
}

Measured memory_bytes: 3968
#include <stdio.h>
 
int main()
{
	int h,w,i,j;
	while(1){
		scanf("%d %d",&h,&w);
		if(h==0 && w==0)break;
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				printf("#");
				}
			printf("\n");
			}
		printf("\n");
		}
	return 0;
}
 

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  sort(a.rbegin(), a.rend());
  long long ans = 0;
  int t = n-1;
  rep(i,n) {
    int lim = 2;
    if (i == 0) lim = 1;
    rep(j,lim) {
      if (t > 0) {
        ans += a[i];
        t--;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4040
//package agc036;
import java.io.*;
import java.util.*;

public class Main {
	// ------------------------
	
	public static void main(String[] args) {
		MyScanner sc = new MyScanner();
		out = new PrintWriter(new BufferedOutputStream(System.out));
		// ------------------------
		long max=1000000000;
		long s=sc.nextLong();
		if(s==max*max)
			out.println("0 0 0 "+max+" "+max+" 0");
		else{
			long b=s%max,a=max-b,c=s/max;
			out.println("0 0 "+(c+1)+" "+a+" "+1+" "+max);
		}
		// ------------------------
		out.close();
	}
	//------------------------
	public static PrintWriter out;
	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}


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

int main(){
  int n,k; cin>>n>>k;
  vector<int> snuke(n,0);
  for (int i=0; i<k; i++){
    int d; cin>>d;
    for (int j=0; j<d; j++){
      int ta; cin>>ta;
      ta-=1;
      snuke[ta]+=1;
    }
  }
  cout<<count(snuke.begin(),snuke.end(),0)<<endl;
}

Measured memory_bytes: 3528
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10, mod = 1e9 + 7;
int k, n, res, pa[N], pb[N], s[N << 1]; char ch[N];
int Pow (int x, int y) {
	int tmp = 1;
	while (y) {
		if (y & 1) tmp = tmp * x % mod;
		x = x * x % mod, y >>= 1;
	} return tmp;
}
int C (int x, int y) {
	return s[x] * Pow (s[y], mod - 2) % mod * Pow (s[x - y], mod - 2) % mod;
}
signed main() {
	scanf ("%lld %s", &k, ch + 1);
	pa[0] = pb[0] = s[0] = 1; n = strlen (ch + 1);
	for (int i = 1; i <= n + k; ++i) s[i] = s[i - 1] * i % mod;
	for (int i = 1; i <= k; ++i)
		pa[i] = pa[i - 1] * 25 % mod, pb[i] = pb[i - 1] * 26 % mod;
	for (int i = 0; i <= k; ++i) {
		res = (res + pb[k - i] * (C (i + n - 1, i) * pa[i] % mod) % mod) % mod;
	} return printf ("%lld\n", res), 0;
}

Measured memory_bytes: 36052
#include <iostream>
using namespace std;
int main(){
    int n,x; cin >> n >> x;
    int m[n+1],mini=1000,sum=0;
    for(int i=0; i<n; i++) cin >> m[i], sum += m[i], mini = min(mini, m[i]);
    int ans = n + (x-sum)/mini; 
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,a,b,c,d;
int main()
{
    scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d);
    for(int i=0;i<n;i++)
    {
        LL l=a+i*c-(n-1-i)*d,r=a+i*d-(n-1-i)*c;
        if(l<=b&&b<=r)
        {
            printf("YES\n");
            return 0;
        }
    }
    printf("NO\n");
    return 0;
}


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

flag = True
for x in a:
    if (x % 2 == 0) and (x % 3 != 0 and x % 5 != 0):
        flag = False
        break

if flag:
    print("APPROVED")
else:
    print("DENIED")

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, a, b) for(int i = a; i < b; i++)
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define pb push_back
#define debug(x) cerr <<__LINE__<< ": " << #x << " -> " << x << endl
#define debug_vec(v) cerr<<__LINE__<<": "<<#v<<" -> ";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
int h, w, sy, sx, gy, gx;
string board[1010];

bool check(int i, int j) {
    return i >= 0 && i < h && j >= 0 && j < w && board[i][j] == '.';
}

void solve() {
    cin >> h >> w >> sy >> sx >> gy >> gx;
    sy--; sx--; gy--; gx--;
    rep(i, h) cin >> board[i];
    int warp[1010][1010];
    memset(warp, -1, sizeof(warp));
    using P = pair<int, pii>;
    priority_queue<P, vector<P>, greater<P>> pq;
    warp[sy][sx] = 0;
    pq.emplace(0, pii(sy, sx));
    while(pq.size()) {
        int y, x;
        tie(y, x) = pq.top().se;
        pq.pop();
        bool f = 0;
        rep(i, 4) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (!check(ny, nx)) continue;
            if (warp[ny][nx] == -1 || warp[ny][nx] > warp[y][x]) {
                warp[ny][nx] = warp[y][x];
                pq.emplace(warp[ny][nx], pii(ny, nx));
            }
        }
        REP(i, -2, 3) REP(j, -2, 3) {
            int ny = y + i;
            int nx = x + j;
            if (!check(ny, nx)) continue;
            if (warp[ny][nx] == -1 || warp[ny][nx] > warp[y][x] + 1) {
                warp[ny][nx] = warp[y][x] + 1;
                pq.emplace(warp[ny][nx], pii(ny, nx));
            }
        }
    }
    cout << warp[gy][gx] << endl;
}

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


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

int main() {
  int N;
  long K;
  cin >> N >> K;
  vector<long> vA(100001);
  for (int i=0; i<N; i++) {
    int ia, ib;
    cin >> ia >> ib;
    vA[ia] += ib;
  }
  for (int i=0; i<100001; i++) {
    K -= vA[i];
    if (K<=0) {
      cout << i << endl;
      break;
    }
  }
}

Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    int n, r = 0;
    int p, c = 0;
    while (std::cin >> n >> r && n > 0) {
        std::vector<int> v(n);
        for (int i = 0; i < n; i++) {
            v.at(n - i - 1) = i + 1;
        }
        for (int i = 0; i < r; i++) {
            std::cin >> p >> c;
            std::rotate(v.begin(), v.begin() + p - 1, v.begin() + p + c - 1);
        }
        std::cout << v.at(0) << '\n';
    }
    return 0;
}



Measured memory_bytes: 3092
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int a,b; 

int main()
{
	scanf("%d",&a);
	for(int i=a;i>=1;i--)
	{
	  b=int(sqrt(i));
	  if(b*b==i)
	  {
	  printf("%d\n",i);return 0;
	  }	
	  
	}
  
	return 0;
}

Measured memory_bytes: 256
import math

def f(X):
    N = len(X)
    ret = 0  
    for i in range(N):
        k = 0
        for j in range(i, N):
            if X[i] > X[j]:
                k += 1
        ret += k * math.factorial(N-i-1)
    return ret

N = int(input())

P = [int(_) for _ in input().split()]
Q = [int(_) for _ in input().split()]

a = f(P)
b = f(Q)

print(abs(a-b))


Measured memory_bytes: 3064
N=gets.to_i
F,P=2.times.map{N.times.map{gets.split.map &:to_i}}
p 1.upto(2**10-1).map{|a|
  c=[0]*N
  N.times do |i|
    10.times do |j|
      c[i] += 1 if a[j]!=0 && F[i][j]!=0
    end
  end
  N.times.map{|i| P[i][c[i]]}.inject :+
}.max


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

using namespace std;

int main( )
{
	int n;
	int s[1001];
	double sum, m;
	
	cout.setf( ios::fixed );
	while( cin>>n ) {
		if( 0 == n ) { break; }

		sum = 0;
		for( int i=0; i<n; i++ ) {
			cin>>s[i];
			sum += s[i];
		}
		m = sum / n;
		sum = 0;
		for( int i=0; i<n; i++ ) {
			sum += pow( s[i]-m , 2 );
		}
		cout<<sqrt( sum/n )<<endl;
	}
		
	return 0;
}

Measured memory_bytes: 1236
a, b = map(int, input().split())
count = 0
for i in range(b - a + 1):
    l = len(str(a + i))
    if l % 2 != 0:
        l = l - 1
    check = 0
    for j in range(l // 2):
        if int(str(a + i)[j]) == int(str(a + i)[l - j]):
            check += 1
    if check == l // 2:
        count += 1
print(count)

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

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll zero = 0;
const ll INF = 10000000000000000; //10^16
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;

int main(void){
    ll A,B,N;
    cin >> A >> B >> N;
    ll ans;
    if(N >= B-1){
        ans = A*(B-1)/B;
    }
    else{
        ans = A*N/B - N/B *A;
    }
    printf("%lld\n",ans);
    
}


Measured memory_bytes: 3724
#include<stdio.h> 
#include<stdlib.h> 
#include<algorithm>
#include<queue>
#include<iostream>
#include<ctype.h>
#include<cstring>
#define MAXN 100005
using namespace std;
#define LOCAL 0
int h[MAXN],dp[MAXN];
int main()
{
#if LOCAL
freopen("input.dat","r",stdin);
//freopen("output.dat","w",stdout); 
#endif 
	int n;
	scanf("%d",&n);
	for(int i =1;i<=n;i++)	scanf("%d",h+i);
	 dp[1]=0;
	 dp[2]=abs(h[2]-h[1]);
	 for(int i =3;i<=n;i++)
	 {
	 	dp[i]= min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
	 }
	 printf("%d\n",dp[n]);
	return 0; 
}

Measured memory_bytes: 1024
import java.io.*;
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int count=0;
    int n=sc.nextInt();
    int[] a;
    a=new int[n];
    for(int i=0;i<n;i++){
      a[i]=sc.nextInt();
    }
    for(int i=0;i<n-1;i++){
      for(int j=n-1;j>i;j--){
        if(a[j]<a[j-1]){
          int c=a[j];
          a[j]=a[j-1];
          a[j-1]=c;
          count++;
        }
      }
    }
    for(int i=0;i<n;i++){
      System.out.print(a[i]);
      if(i!=n-1) System.out.print(" ");
      else System.out.println();
    }
    System.out.println(count);
  }
}



Measured memory_bytes: 26204
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <tuple>

#include <set>
#include <unordered_map>
#include <stack>

using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(x) (x).begin(),(x).end()
using ll = long long;
template<class T>bool chmaxj(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
void YesNo(bool y) { cout << (y ? "Yes" : "No") << endl; } //true==yes


#define INF 21474836

//////////////////////////////////////////////////////////////


int main() {

	int A, B, C, X, Y;
	cin >> A >> B >> C >> X >> Y;
	long long ans = 0;
	if (A + B < C * 2) {
		ans = A * X + B * Y;
	}
	else {
		if (A > C * 2) {
			ans = X * (C * 2);
			if (B > C * 2) {
				if (Y > X)ans += (Y - X) * (C * 2);
			}
			else {
				if (Y > X)ans += (Y - X) * B;
			}
		}
		else if (B > C * 2) {
			ans = Y * (C * 2);
			if (X > Y)ans += (X - Y) * A;	
		}
		else {
			if (X > Y) {
				ans = Y * (C * 2) + (X - Y) * A;
			}
			else {
				ans = X * (C * 2) + (Y - X) * B;
			}
		}
	}

	cout << ans << endl;

	return 0;
}

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

using namespace std;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    long long n,a;
    cin>>n>>a;
    if(n%a==0)
    {
        cout<<n/a<<endl;
    }
    else
        cout<<(n/a)+1<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<P, int> P3;
const ll MOD = ll(1e9)+7;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-11;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()

int main() {
    double x[3], y[3], e[3], l=0.0, s, r = 0.0;
    REP(i,3){
        cin >> x[i] >> y[i];
    }
    REP(i,3){
        e[i] = pow(pow(x[(i+1)%3]-x[i],2)+pow(y[(i+1)%3]-y[i],2),0.5);
        l += e[i];
    }
    s = pow(l*(l/2-e[0])*(l/2-e[1])*(l/2-e[2])/2,0.5);

    REP(i,3){
        r = max(r,2*s/(l+4*s/e[i]));
    }
    printf("%.12lf\n",r);
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <sstream>
#include <vector>
#include <cassert>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <tuple>
#include <regex>
#include <map>
#include <bitset>

using namespace std;
using ull = unsigned long long;
using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

#define EPS (1e-7) 
#define ALL(x) begin(x), end(x)

int main() {
	ll N, K;
	cin >> N >> K;
	cout << (N - K) + 1 << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rrep(i,a,b) for(int i=(int)(a);i>=(int)(b);--i)
#define fore(i,a) for(auto &i:a)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define isin(i,a,b) ((a) <= (i) && (i) < (b))
#define uni(a) (a).erase(unique(all(a)),(a).end())
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)(a).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll  = long long;
using unit= unsigned;
using ull = unsigned long long;
using P   = pair<int,int>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vvi = vector<vi>;
using vp  = vector<P>;
void _main(); int main(){ cin.tie(0); ios::sync_with_stdio(false); _main(); }
template<class T>string join(const v(T)&v){stringstream s;rep(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<class T>inline ostream& operator<<(ostream&o,const v(T)&v){if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v){return o<<v.fi<<","<<v.se;}
template<class T>void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T>void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T>void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T>void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T>bool chmax(T &a, const T &b){ if (a<b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if (b<a){ a = b; return 1; } return 0; }
template<class T>T gcd(T a, T b){ if (b==0){ return a; }else{ return gcd(b, a%b); }}
template<class T>T lcm(T a, T b){ return a / gcd(a, b) * b; }
constexpr double eps = 1e-10;
constexpr int inf = INT_MAX / 2;
constexpr ll infl = 1LL << 60;

double N, D;
bool f(const v(double)& a, const v(double)& b) {
  int t = 0;
  rep(i, 0, D) {
    t += pow(abs(a[i] - b[i]), 2);
  }
  rep(i, 1, 160*100) {
    if (t == i * i) return true;
  }
  return false;
}

void _main() {
  cin >> N >> D;
  v(v(double)) X(N, v(double)(D));
  rep(i, 0, N) rep(j, 0, D) cin >> X[i][j];

  int ans = 0;
  rep(i, 0, N) rep(j, i+1, N) {
    if (f(X[i], X[j])) ++ans;
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define ll long long int
#define ld long double
#define pb push_back
#define pq priority_queue
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vvll vector<vector<ll>>
#define vvi vector<vector<int>>
#define vi vector<int>
#define vll vector<ll>
#define vs vector<string>
#define MODNUM 1000000007
#define lp(i,a,b) for(ll i=a; i<b; i++)
 
using namespace std;
 
ll mex(ll a, ll b, ll m) {
	if(b==0) return 1;
	if(b%2) return a*mex((a*a)%m,(b-1)/2,m)%m;
	else return mex((a*a)%m,b/2,m);
}
 
int x,y;
void exteu(ll a, ll m) {
	if(m==0) { x=1;y=0; }
	else {
		exteu(m,a%m);
		ll temp = x;
		x=y;
		y=temp-(a/m)*y;
	}
}
 
ll fact(ll n) 
{	ll prod=1;
	for(ll i=2; i<=n; i++) {
		prod*=i;
	}
	return prod;
}
 
ll gcd(ll a, ll b) {
	if(b==0) return a;
	return gcd(b, a%b);
}
 
// bool isprime[100001];
// void makesieve() {
// 	memset(isprime, true, sizeof(isprime));
// 	for (int i = 2; i <= sqrt(200000); ++i)
// 	{
// 		if(isprime[i]) {
// 			for (int j = i*i; j <= 200000; j+=i)
// 			{
// 				isprime[j]=false;
// 			}
// 		}
// 	}
// }
// 
// 1 2 4 5 8
void solve() {
	ll n; cin>>n;
	ll p=1, d=1;
	string s = "";
	while(n) {
		ll m = n%26;
		m--;
		if(m<0) {m=25;n--;}
		n/=26;
		s += string(1, (char)('a'+m));
	}
	for (int i = s.length()-1; i >= 0; --i)
	{
		cout<<s[i];
	}
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll TESTS=1;
	// cin >> TESTS;
	// makesieve();
	while(TESTS--) {
		solve();
	}
	return 0;
}


Measured memory_bytes: 3616
#include <iostream>
#include <math.h>

using namespace std;

int main(void){
  int n, x, l[100];
  int i, j, k, sum = 0;
  cin >> n >> x;
  l[0] = 0;
  for(i = 1; i <= n; i++){
    cin >> l[i];
    sum = sum + l[i];
    if(sum > x){
      break;
    }
  }
  cout << i;
  return 0;
}


Measured memory_bytes: 256
import numpy as np
N = int(input())
h = np.array(list(map(int, input().split())))
h_max = max(h)

ans = 0
for i in range(h_max):
    tmp = list(h >= 1)
    a = tmp.index(True)
    count = 0
    for j in range(a, len(tmp)-1):
        if tmp[j] == True and tmp[j+1] == False:
            count += 1
    if tmp[-1] == True:
        count += 1

    ans += count
    h -= 1

print(ans)

Measured memory_bytes: 12508
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
char s[maxn+5]; int k,len;

int main(){
	cin >>s>>k;
	len = strlen(s);
	long long ans = 0;
	int head, tail;
	for(int i=0, j; i<len; i=j){
		for(j=i; j<len; ++j)
			if(s[j] != s[i])
				break;
		ans += (j-i)>>1;
		if(not i) head = j-i;
		if(j == len) tail = j-i;
	}
	if(head == len and tail == len)
		ans = 1ll*k*len>>1;
	else{
		ans = ans*k;
		if(s[0] == s[len-1] and head/2+tail/2 < (head+tail)/2)
			ans += k-1;
	}
	cout << ans;
	return 0;
}

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

int main(){
    string S,T; cin>>S>>T;
    ll N=T.size();
    ll moji=10000;
    for (ll i = 0; i < S.size()-N+1; i++){
        string s=S.substr(i,N);
        //cout<<s<<endl;
        ll cnt=0;
        for(ll j = 0;j < N; j++){
            if(s[j]!=T[j]) cnt++;
        }
        //cout<<cnt<<endl;
        moji=min(moji,cnt);
    }
    cout<<moji<<endl;
}

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

int main(){
    int d, n;
    cin >> d >> n;
    int cnt = 0;
    for(int i=1; i<10000000; i++){
        if(d == 1){
            if(i%100 == 0 && i%10000 != 0 && i%1000000 != 0) cnt++;
        }
        else if(d == 2){
            if(i%10000 == 0 && i%1000000 != 0) cnt++;
        }
        else if(d == 0){
            if(i%100 != 0 && i%10000 != 0 && i%1000000 != 0) cnt++;
        }
        if(cnt == n){
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

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

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

int calc(int n) {
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        auto s = i.to!string;
        if (s.length % 2 == 1) ans++;
    }
    return ans;
}

int calc2(int n) {
    // 桁数が奇数:
    // 1..9
    // 100..999
    // 100000..99999

    int ans = 0;
    ans += max(0, min(n, 9) - 1 + 1);
    ans += max(0, min(n, 999) - 100 + 1);
    ans += max(0, min(n, 99999) - 10000 + 1);
    return ans;
}

void main() {
    int n; scan(n);
    writeln(calc2(n));
}


Measured memory_bytes: 256
using System;
 
namespace Sample
{
  class Sample
  {
    static void Main(string[] args)
    {
    string str=Console.ReadLine();
    for(int i=0;i<str.Length;i++){
      if((i%2)==0){
	Console.Write(str.Substring(i,1));
      }
    }
    }
    
  }

}

Measured memory_bytes: 11092
/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

#include <bits/stdc++.h>
using namespace std;

const bool ready = [](){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(12);
    return true;
}();

const double PI = acos(-1);
using ll= long long;
#define int ll
#define all(v) (v).begin(), (v).end()
#define fori(n) for(int i=0; i<int(n); i++)

#define cini(i) int i; cin>>i;
#define cins(s) string s; cin>>s;
#define cind(d) double d; cin>>d;
#define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; }
#define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; }

using pii= pair<int, int>;
using pdd= pair<double, double>;
using vd= vector<double>;
using vb= vector<bool>;
using vi= vector<int>;
using vvi= vector<vi>;
using vs= vector<string>;

#define endl "\n"

const int MOD=1e9+7;

/* 
 * Lets maintain dp[i]=number of seqs with sum==i
 * Then we can add to all previously found seqs a number
 * to create one with sum==i.
 * so dp[i]=sum(dp[0..i-3]);
 */
void solve() {
    cini(n);

    vi dp(n+1); /* dp[i]= number of seqs so far with sum==i */
    dp[0]=1;

    for(int i=3; i<=n; i++) {
        for(int j=0; j+3<=i; j++) {
            dp[i]+=dp[j];
            dp[i]%=MOD;
        }
    }

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

signed main() {
    solve();
}

// FIRST THINK, THEN CODE
// DO NOT JUMP BETWEEN PROBLEMS


Measured memory_bytes: 3552
#include<bits/stdc++.h>
int X,k,q;
struct ev{
	int x,y,id;
	bool operator<(const ev&e)const{return x<e.x;}
}e[300007];
int ep=0,as[300007];
int main(){
	scanf("%d%d",&X,&k);
	for(int i=0,a;i<k;++i){
		scanf("%d",&a);
		e[ep++]=(ev){a,0,0};
	}
	scanf("%d",&q);
	for(int i=1,a,b;i<=q;++i){
		scanf("%d%d",&a,&b);
		e[ep++]=(ev){a,b,i};
	}
	std::sort(e,e+ep);
	long long mn=0,mx=X,a=0;
	for(int i=0,sgn=-1,t0=0;i<ep;++i){
		int v0=(e[i].x-t0)*sgn;
		if(e[i].id){
			long long v=e[i].y+a;
			if(v<mn)v=mn;
			if(v>mx)v=mx;
			v+=v0;
			if(v<0)v=0;
			if(v>X)v=X;
			as[e[i].id]=v;
		}else{
			mn+=v0,mx+=v0,a+=v0;
			if(mn<0)mn=0;
			if(mx<0)mx=0;
			if(mn>X)mn=X;
			if(mx>X)mx=X;
			t0=e[i].x;
			sgn*=-1;
		}
	}
	for(int i=1;i<=q;++i)printf("%d\n",as[i]);
	return 0;
} 

Measured memory_bytes: 4480
#include <bits/stdc++.h>
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	if (N == 3)
	{
		cout << "2 5 63" << endl;
		return 0;
	}
	else if (N == 4)
	{
		cout << "2 5 20 63" << endl;
		return 0;
	}
	
	int a, b;
	// aは3の倍数を出力する回数
	// bは(2の倍数) && !(3の倍数)を出力する回数
	if (N % 2 == 1)
	{
		a = min((N / 4 - 1) * 4 + 3, 9999);
		b = N - a;
	}
	else
	{
		a = min((N - 1) / 4 * 4, 10000);
		b = N - a;
	}
	for (int i = 1; i <= a; i++)
		cout << 3 * i << " ";

	int cnt = 0, x = 2;
	while (true)
	{
		if (x % 3 == 0)
		{
			x += 2;
			continue;
		}
		else
		{
			cout << x << (cnt != b - 1 ? " " : "");
			if (cnt == b - 1)
				break;
			else
				cnt++;
			x += 2;
		}
	}
}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define fs first
#define fst first
#define sc second
#define snd second
#define sz(X) (int)(X).size()
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define fornr(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define forab(i, a, b) for(int i = int(a); i < int(b); i++)
#define all(X) X.begin(), X.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef double dbl;
typedef long double ld;
typedef vector<int> vi;

const int N = 1e3;
const int LOG = 61;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LLMOD = 1e9 + 7;
const ll LLINF = 1e16;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll a, b;
    cin >> a >> b;
    if ((a + b) % 2) cout << "IMPOSSIBLE\n";
    else cout << (a + b) / 2 << "\n";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	while(a!=0 && c!=0){
		c=c-b;
		if(c<=0){
			cout<<"Yes"<<endl;
			break;
		}
		a=a-d;
		if(a<=0)
		{
			cout<<"No"<<endl;
			break;
		}
		
	}
}

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

int main(){
  
  int A,B;
  cin >> A >> B;
  
  int K = (A+B);
  
  if (K % 2 == 0){
    cout << K /2 << endl;
  }else{
    cout << "IMPOSSIBLE" << endl;
  }
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#define N 2000
#define M 8000010
#define ls x << 1
#define rs x << 1 | 1
#define inf 0x3f3f3f
#define inc(i) (++ (i))
#define dec(i) (-- (i))
#define mid ((l + r) >> 1)
// #define int unsigned __int128
//#define ll long long
#define XRZ 19260817
#define pai acos(-1)
#define debug() puts("XRZ TXDY");
#define mem(i, x) memset(i, x, sizeof(i));
#define Next(i, u) for(register int i = head[u]; i ; i = e[i].nxt)
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout);
#define Rep(i, a, b) for(register int i = (a) , i##Limit = (b) ; i <= i##Limit ; inc(i))
#define Dep(i, a, b) for(register int i = (a) , i##Limit = (b) ; i >= i##Limit ; dec(i))
using namespace std;
inline int read() {
    register int x = 0, f = 1; register char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c 	- 48, c = getchar(); 
    return x * f;
}
inline int read_plus() {
    register int res = 0, ch = getchar();
    while(!isdigit(ch) and ch != EOF) ch = getchar();
    while(isdigit(ch)) res = ((res << 3) + (res << 1) + (ch - '0')) % XRZ, ch = getchar();
    return res;
}	
int dx[10] = {0, 1, 1, 2, 2, -1, -1, -2, -2};
int dy[10] = {0, 2, -2, 1, -1, 2, -2, 1, -1};
int A[N], Ans;
bool cmp(int x, int y) {
	return x < y;
}
signed main() { int n = read(), k = read();
	Rep(i, 1, n) A[i] = read(); sort(A + 1, A + n + 1, cmp);
	Rep(i, 1, k) Ans += A[i]; printf("%d", Ans);
	return 0;
}// 

Measured memory_bytes: 3752
// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>

using namespace std;

#define rep(i, n) for (int i = 0, _n = (int)(n); i < _n; ++i)

const int N = (int) 1e5 + 5, mod = 0;

int pr[N];
long long a[N];
vector<int> p;
map<long long, int> mp;
long long s[N], o[N];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    for (int i = 2; i < N; ++i) if (!pr[i]) {
        for (int j = i; j < N; j += i)
            pr[j] = 0;
        p.push_back(i);
    }
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        long long x = a[i], y = 1, self = 1;
        for (int j : p) {
            if (j * 1ll * j * j > x) {
                break;
            }
            int cnt = 0;
            while (x % j == 0) cnt++, cnt %= 3, x /= j;
            for (int q = 0; q < cnt; ++q)
                self *= j;
            for (int q = 0; q < (3 - cnt) % 3; ++q)
                y *= j;
        }
        self *= x;
        long long sq = sqrt(x);
        int flag = 0;
        for (long long q = sq - 1; q <= sq + 1; ++q)
            if (q * q == x) {
                flag = 1;
                sq = q;
                break;
            }
        if (!flag)
            y *= x * x;
        else
            y *= sq;
        s[i] = self;
        o[i] = y;
        mp[self]++;
        mp[y]--;
    }
    int res = 0;
    for (int i = 0; i < n; ++i) {
        if (mp[s[i]] >= 0) {
            res++;
            mp[o[i]] = -1;
        }
    }
    cout << res;





}



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

#define ms(a,b) memset(a, b, sizeof(a))
#define rep(a,b,c) for(int a = (int)(b); a < (int)(c); a++)
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define m_p(a,b) make_pair(a, b)
#define lson l,mid,o << 1
#define rson mid + 1,r,o << 1 | 1
#define ls o << 1
#define rs o << 1 | 1
#define inf 0x3f3f3f3f

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int,int> pii;

inline bool isdigit(char& ch) {
	return ch >= '0' && ch <= '9';
}
template<class T>
void read(T &x) {
	x = 0;
	ll f = 1;char ch = getchar();
	for (;!isdigit(ch);ch = getchar()) 
		if (ch == '-') f = -1;
	for (; isdigit(ch);ch = getchar())
		x = (x << 1) + (x << 3) + ch - '0';
	x *= f;
}
template<class T>
inline void write(T x) {
	if (x == 0) {putchar('0');return ;}
	if (x < 0) {putchar('-');x = -x;}
	int _stk[65],_top = 0;
	for (;x;x /= 10) _stk[++_top] = x % 10 + 48;
	for (;_top;_top--)putchar(_stk[_top]);
}

const int MAXN = 1e5 + 10;
const ll N = 1e18;
ll arr[MAXN];
int n;
int main () {
	read(n);
	rep(i, 1, n + 1) {
		read(arr[i]);
	}
	sort(arr + 1, arr + 1 + n);
	if (arr[1] == 0) {
		cout << 0;
		return 0;
	}

	ll sum = 1ll;
	rep(i, 1, n + 1) {
		if (sum > N / arr[i]) {
			cout << -1;
			return 0;
		}
		sum *= arr[i];
	}
	cout << sum;
	return 0;
}

Measured memory_bytes: 4380
N,X = map(int,input().split())
L = [int(i) for i in input().split()]
L.append(0)
D=0
for i in range(1,N+1):
    D = D + L[i - 1]
    if D>X:
        i = i-1
        break
    else:
        pass

print(i+1)

Measured memory_bytes: 3060