akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int X = sc.nextInt();
			int Y = sc.nextInt();
			if (X == 0 && Y == 0)
				break;
			int[][] field = new int[X][Y];
			int[][] movable = new int[X][Y];
			for (int i = 0; i < Y; i++)
				for (int j = 0; j < X; j++)
					movable[j][i] = 0;
			for (int i = 0; i < Y; i++)
				for (int j = 0; j < X; j++)
					field[j][i] = sc.nextInt();
			for (int i = Y - 1; i >= 0; i--)
				for (int j = 0; j < X; j++) {
					if (field[j][i] == 0) {
						if (i == Y - 1)
							movable[j][i] = 1;
						else {
							movable[j][i] += movable[j][i + 1];
							if (j > 0 && field[j - 1][i + 1] != 2)
								movable[j][i] += movable[j - 1][i + 1];
							if (j < X - 1 && field[j + 1][i + 1] != 2)
								movable[j][i] += movable[j + 1][i + 1];
						}
					} else if (field[j][i] == 1)
						movable[j][i] = 0;
					else if (field[j][i] == 2) {
						if (i >= Y - 2)
							movable[j][i] = 1;
						else
							movable[j][i] = movable[j][i + 2];
					}
				}
			int result = 0;
			for (int i = 0; i < X; i++)
				result += movable[i][0];
			System.out.println(result);
		}
		sc.close();
	}
}

Measured memory_bytes: 23628
#include<iostream>
#include<vector>
#include<atcoder/convolution>
using atcoder::convolution;

int main(){
  using namespace std;
  using i64 = int64_t;

  int n,m;
  cin>>n>>m;
  vector<i64> a(n),b(m);
  for(auto& ai:a)cin>>ai;
  for(auto& bi:b)cin>>bi;

  auto c = convolution(a,b);
  for(auto itr=begin(c);itr!=end(c);++itr){
    cout<<(*itr)<<"\n "[itr+1!=end(c)];
  }
  
}

Measured memory_bytes: 27280
abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def map_abc(N, S):
    result = ""
    for str_a in S:
        new_index = (abc.find(str_a) + N) % 26
        new_str = abc[new_index]
        result = result + new_str
    return result


if __name__ == "__main__":
    N = int(input())
    S = input()
    print(map_abc(N, S))


Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

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

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

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
int main() {
	long long int n;
	long long int k;
	cin >> n >> k;
	long long int a = n - k + 1;
	long long int b = k - 1;
	COMinit();
	for (long long int i = 0; i < k; i++) {
		long long int ans = 0;
		long long int t = COM(a, i + 1) % MOD;
		long long int f = COM(b, i) % MOD;
		ans = t * f % MOD;
		ans = ans % MOD;
		cout << ans << endl;
	}
}

Measured memory_bytes: 16640
package main

import (
	"fmt"
)

func main() {
	var s, t string
	fmt.Scan(&s, &t)
	ss := []rune(s)
	ts := []rune(t)
	len := len(ss)
	for i := 0; i < len; i++ {
		flag := true
		for j := 0; j < len; j++ {
			if ss[j] != ts[j] {
				flag = false
				break
			}
		}
		if flag == true {
			fmt.Println("Yes")
			return
		} else {
			first := ss[0]
			for j := 0; j < len-1; j++ {
				ss[j] = ss[j+1]
			}
			ss[len-1] = first
		}
	}
	fmt.Println("No")
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define INF 1000000001
#define ll long long
using namespace std;
using pll = pair<ll, ll>;

int main()
{
  ll N;
  cin >> N;
  vector<pll> red(N);
  vector<pll> blue(N);
  for (ll i = 0; i < N; ++i)
  {
    cin >> red.at(i).first >> red.at(i).second;
  }
  for (ll i = 0; i < N; ++i)
  {
    cin >> blue.at(i).first >> blue.at(i).second;
  }
  sort(red.begin(), red.end(), [] (pll a, pll b){
    return a.second < b.second;
  });
  sort(blue.begin(), blue.end(), [] (pll a, pll b){
    return a.second < b.second;
  });
  vector<pll> pos_red;
  ll cnt = 0;
  ll ans = 0;
  for (ll i = 0; i < N; ++i)
  {
    pll b = blue.at(i);
    ll temp = cnt;
    // cout << "bsecond" << b.second << endl;
    for (ll j = temp; j < N; ++j)
    {
      // cout << "rsecond" << red.at(j).second << endl;
      cnt = j;
      if (b.second > red.at(j).second)
      {
        pos_red.push_back(red.at(j));
      }
      else
      {
        break;
      }
    }
    ll largest_first = -1;
    ll index;
    // cout << "pos_red" << endl;
    // for (ll j = 0; j < pos_red.size(); ++j)
    // {
    //   cout << pos_red.at(j).first << ' ' << pos_red.at(j).second << endl;
    // }
    for (ll j = 0; j < pos_red.size(); ++j)
    {
      if (pos_red.at(j).first < b.first && pos_red.at(j).first > largest_first)
      {
        largest_first = pos_red.at(j).first;
        index = j;
      }
    }
    if (largest_first != -1)
    {
      ans += 1;
      // cout << "pair" << endl;
      // cout << b.first << ' ' << b.second << endl;
      // cout << pos_red.at(index).first << ' ' << pos_red.at(index).second << endl;
      pos_red.erase(pos_red.begin() + index);
    }
    // cout << red.at(i).first << ' ' << red.at(i).second << endl;
  }
  cout << ans << endl;
}


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

int main(){
  
  int N, K;
  string S;
  cin >> N >> K;
  cin >> S;
  
  S.at(K - 1) = S.at(K - 1) + 32;
  cout << S << endl;

  return 0;
}

Measured memory_bytes: 3560
#include <stdio.h>

int c[1000001], time[1000001];

void sort(int, int);
void change(int, int);

main(){
  int tc, m1, m2, m3, m4, s1, s2, s3, s4, n, i;

  while(1){
    scanf("%d", &n);
    if(n==0) break;

    for(i=0;i<n;i++){
      c[i]=time[i]=0;
    }

    for(i=0;i<n;i++){
      scanf("%d", &c[i]);
      scanf("%d %d %d %d %d %d %d %d", &m1, &s1, &m2, &s2, &m3, &s3, &m4, &s4);

      time[i]=60*m1+s1+60*m2+s2+60*m3+s3+60*m4+s4;
    }

    sort(0, n-1);

    printf("%d\n%d\n%d\n", c[0], c[1], c[n-2]);
  }
  return 0;
}

void sort(int right, int left){
  int i, j, n;

  i=right;
  j=left;
  n=time[(right+left)/2];

  while(1){
    while(n>time[i]) i++;
    while(n<time[j]) j--;

    if(i>=j) break;

    change(i, j);
    i++;
    j--;
  }

  if(right<i-1) sort(right, i-1);
  if(j+1<left) sort(j+1, left);
}

void change(int a, int b){
  int temp;

  temp=time[a];
  time[a]=time[b];
  time[b]=temp;

  temp=c[a];
  c[a]=c[b];
  c[b]=temp;
}

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

using ll = long long;

ll n, k, q, p;
std::vector<ll> vec;
int main() {
    std::cin >> n >> k >> q;
    vec.assign(n, 0);
    for (int i = 0; i < q; i++) {
        std::cin >> p;
        vec[--p]++;
    }
    for (int i = 0; i < n; i++) {
        if ((k-q+vec[i]) > 0) {
            std::cout << "Yes" << std::endl;
        }
        else {
            std::cout << "No" << std::endl;
        }
    }
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int MOD = 1000000007;
int INF = numeric_limits<int>::max() / 2;


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

  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  int y = ty - sy, x = tx - sx;
  rep(i,x) cout << 'R';
  rep(i,y) cout << 'U';
  rep(i,x) cout << 'L';
  rep(i,y+1) cout << 'D';
  rep(i,x+1) cout << 'R';
  rep(i,y+1) cout << 'U';
  cout << "LU";
  rep(i,x+1) cout << 'L';
  rep(i,y+1) cout << 'D';
  cout << 'R' << endl;

}

Measured memory_bytes: 256
#include <cstdlib>
#include <iostream>
#include <string>
#include <time.h>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <vector>
#include <functional>
#include <numeric>
#include <cassert>
#include <algorithm>
#include <functional>
//#include "bits/stdc++.h"
using namespace std;
//using namespace std::vector;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)

#define huge 1000000007
typedef long long int ll;
ll gcd(ll a, ll b);

int main(void) {

	ll N = 0;
	ll A = 0;
	ll B = 0;
	ll C = 0;
	ll D = 0;
	ll M = 0;
	//ll T = 0;
	//ll M = 0;
	ll h[1000] = {};
	ll b[100] = {};
	//ll c[100] = {};
	//ll d[100] = {};

	//ll v[3] = {};
	//ll *c, *s, *n;
	string S,T,U[52];
	ll count = 0;
	ll count2 = 0;
	float sum = 0;
	ll min = 1000000000000;
	ll max = 0;
	ll smax = 0;
	ll max2 = 0;
	ll smax2 = 0;
	int tmax = 0;
	int tmax2 = 0;
	//int flag = 0;
	char temp,head;
	//int is = 0;
	bool flag = false;
	
	//char p;


	

	

	//cin >> S;
	
	//b = (ll *)malloc(M * sizeof(ll));
	//vector<pair<int,int>> ch(50);

	cin >> N;
	
	

	

	if(N==22)
	cout << "Christmas Eve Eve Eve" << endl;
	else if(N == 23)
		cout << "Christmas Eve Eve" << endl;
	else if(N == 24)
		cout << "Christmas Eve" << endl;
	else if(N == 25)
		cout << "Christmas" << endl;

	//x = (ll *)malloc((N+1) * sizeof(ll));
	//c = (ll *)malloc((N) * sizeof(ll));
	//cin >> D >> G;
	//vector<pair<int,int>> tr(M);
	//vector<pair<int,int>> qes(Q);
	//sort(c.begin(), c.end());
	
	//cout << c[2] - c[1] << endl;

	
	/*A = N / 1000;
	N %= 1000;
	B = N / 100;
	N %= 100;
	C = N / 10;
	N %= 10;
	D = N;*/
	


	//cin >> N >> M;

	//vector<pair<int,int>> c(M);
	////vector<pair<int, int>> e(M);
	//vector<ll> d(M);

	//rep(i, 0, M) {
	//	cin >> c[i].first >> c[i].second;
	//	//e[i].first = c[i].first;
	//	//e[i].second = c[i].second;

	//}
	////sort(c.begin(), c.end());

	//

	//rep(i, 0, M) {

	//	
	//	
	//	rep(j, 0, M) {
	//		if (c[i].first == c[j].first && c[j].second < c[i].second) {
	//			d[i]++;
	//			//cout << j << endl;
	//		}
	//	}
	//	cout << std::setfill('0') << std::right << std::setw(6) << c[i].first;
	//	cout << std::setfill('0') << std::right << std::setw(6) << d[i]+1 << endl;
	//}

	return 0;

}

ll gcd(ll a, ll b) {
	
	/* 自然数 a > b を確認・入替 */
	if (a<b) {
		ll tmp = a;
		a = b;
		b = tmp;
	}
	ll x = b;
	ll y = a;
	/* ユークリッドの互除法 */
	ll r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}


	return y/b*x;
}



Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a) for(int i=last[a];i;i=next_[i])
using namespace std;

int read() {
	char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	int x=ch-'0';
	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

const int N=1e6+5,inf=1e9;

struct pty{int x,y,id;}a[N],b[N];
bool cmpx(pty a,pty b) {return a.x<b.x;}
bool cmpy(pty a,pty b) {return a.y<b.y;}

int last[N],now[N],next_[N],t[N],l,cnt;
void add(int x,int y) {
	t[++l]=y;next_[l]=last[x];last[x]=l;
}

int n,tot;
void init() {
	n=read();tot=2*n;
	fo(i,1,n) {
		a[i].x=read();a[i].y=read();a[i].id=i;
		b[i].x=a[i].x;b[i].y=a[i].y;b[i].id=i;
	}
}

int rootx,rooty,le[N],ri[N];
void build(int &v,int l,int r,int flag) {
	if (l==r) {
		v=(flag==1)?(a[l].id+n):b[l].id;
		return;
	}
	v=++tot;
	int mid=l+r>>1;
	build(le[v],l,mid,flag);
	build(ri[v],mid+1,r,flag);
	add(v,le[v]);add(v,ri[v]);
}

void link(int v,int l,int r,int x,int y,int z) {
	if (x>y) return;
	if (l==x&&r==y) {add(z,v);return;}
	int mid=l+r>>1;
	if (y<=mid) link(le[v],l,mid,x,y,z);
	else if (x>mid) link(ri[v],mid+1,r,x,y,z);
	else link(le[v],l,mid,x,mid,z),link(ri[v],mid+1,r,mid+1,y,z);
}

void prepare() {
	sort(a+1,a+n+1,cmpx);
	build(rootx,1,n,1);
	sort(b+1,b+n+1,cmpy);
	build(rooty,1,n,2);
	fo(i,1,tot) now[i]=last[i];cnt=l;
}

int dfn[N],low[N],stack[N],cl[N],tmp,top,id;
bool vis[N],in[N];
void tarjan(int x) {
	vis[x]=in[x]=1;dfn[x]=low[x]=++tmp;stack[++top]=x;
	rep(i,x)
		if (!vis[t[i]]) {
			tarjan(t[i]);
			low[x]=min(low[x],low[t[i]]);
		} else if (in[t[i]]) low[x]=min(low[x],dfn[t[i]]);
	if (low[x]==dfn[x]) {
		stack[top+1]=0;++id;
		for(;stack[top+1]!=x;top--) {
			in[stack[top]]=0;
			cl[stack[top]]=id;
		}
	}
}

bool check(int mid) {
	int lx,rx;
	fo(i,1,tot) last[i]=now[i];l=cnt;
	lx=1,rx=1;
	fo(i,1,n) {
		while (lx<i&&a[i].x-a[lx].x>=mid) lx++;
		while (rx<=n&&a[rx].x-a[i].x<mid) rx++;
		link(rootx,1,n,lx,i-1,a[i].id);
		link(rootx,1,n,i+1,rx-1,a[i].id);
	}
	// xuan x ban x
	lx=1,rx=1;
	fo(i,1,n) {
		while (lx<=n&&b[i].y-a[lx].x>=mid) lx++;
		while (rx<=n&&a[rx].x-b[i].y<mid) rx++;
		link(rootx,1,n,lx,rx-1,b[i].id+n);
	}
	// xuan y ban x
	lx=1,rx=1;
	fo(i,1,n) {
		while (lx<=n&&a[i].x-b[lx].y>=mid) lx++;
		while (rx<=n&&b[rx].y-a[i].x<mid) rx++;
		link(rooty,1,n,lx,rx-1,a[i].id);
	}
	// xuan x ban y
	lx=1,rx=1;
	fo(i,1,n) {
		while (lx<i&&b[i].y-b[lx].y>=mid) lx++;
		while (rx<=n&&b[rx].y-b[i].y<mid) rx++;
		link(rooty,1,n,lx,i-1,b[i].id+n);
		link(rooty,1,n,i+1,rx-1,b[i].id+n);
	}
	// xuan y ban y
	
	tmp=top=id=0;
	fo(i,1,tot) vis[i]=cl[i]=dfn[i]=low[i]=0;
	fo(i,1,tot) if (!vis[i]) tarjan(i);
	fo(i,1,n) if (cl[i]==cl[i+n]) return 0;
	return 1;
}

void solve() {
	int l=0,r=inf;
	while (l<r) {
		int mid=l+r>>1;
		if (check(mid)) l=mid+1;
		else r=mid;
	}
	printf("%d\n",l-1);
}

int main() {
	init();
	prepare();
	solve();
	return 0;
}

Measured memory_bytes: 29952
#include<iostream>
#include<cmath>
#include<vector>
#include<string>

using namespace std;

/*static*/ const string mark [4]={"S","H","C","D"};         //???????????????????????????

int main(){
  int member[4][13]={};                  //??????????????????????±????????????????
  int i,j;                            //??????????????°??????
  int n,b;                   //n?????\??????????????????????????°???????´??????????????????????????????????????´?
  string a;                  //a??¨??????string???????????§????????????

  cin >> n;                         //??\??????????????????????????°?????\???

  for(i=0;i<n;i++){
    cin >> a >> b;                 //??????????????????????????\???
    if(a=="S")  member[0][b-1]=1;   //?????£????????????????????¨?????????????????????????????????1?????????
    else if(a=="H")  member[1][b-1]=1;
    else if(a=="C")  member[2][b-1]=1;
    else if(a=="D")  member[3][b-1]=1;
  }



  for(i=0;i<4;i++){
    for(j=0;j<13;j++){
      if(member[i][j]== 0){                //?????£??????????????????????????¢?´¢
        cout << mark[i] << ' ' << j+1 << endl;         //?????£??????????????????????????¨???
      }
    }
  }
return 0;
}

Measured memory_bytes: 1212
#include <stdio.h>
#include <math.h>
 
int main(void)
{
  long int i, j, k, a, b=0, g=0, r=0, result = 0;
  char n[4001];
  
  scanf("%ld", &a);
  scanf("%s", n);
  for( i = 0; i < a; i++ ){
    if( n[i] == 'B' ) b++;
    if( n[i] == 'G' ) g++;
    if( n[i] == 'R' ) r++;
  }
  
  result = b*g*r;
  
  for( i = 0; i < a; i++ ){
    for( j = i+1; j < a; j++ ){
      k = (2*j)-i;    
        if( k < a && n[i] != n[j] && n[j] != n[k] && n[k] != n[i] ){
          result--; 
      }       
    }         
  }
  
  printf("%ld\n", result);
  return 0;
}

Measured memory_bytes: 1708
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <cstdlib>
#include <math.h>

using namespace std;

typedef long long ll;
#define rep(i, n) for(long (i) = 0; (i) < (long) (n); (i)++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,a,b) for(long i=(a);i<(b);i++)
#define rrep1(i,a,b) for(long i=(a);i<=(b);i++)
#define rrrep(i,a,b) for(long i=(a);i>=(b);i--)
#define define pb push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define X first
#define Y second
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vector<int> >
#define vpl vector<pair<long, long> >
#define vppl vector<pair<long, pair<long, long> > >

const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
const ll LINF = 1e18;

int printYes() {
    cout << "Yes" << endl;
    return 0;
}

int printNo() {
    cout << "No" << endl;
    return 0;
}

int ans;

int printAns() {
    cout << ans << endl;
    return 0;
}


int pow(int x) {
	if (x == 0) {
		return 1;
	}
	else {
		return pow(x - 1) * 2;
	}
}

int main(int argc, char const *argv[])
{
    int c;
    cin >> c;
    if (c >= 1000) {
        cout << "ABD";
    } else
    {
        cout << "ABC";
    }
    return 0;
}


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

void solve(long long N, long long K){
    int ans = 0;
    REP(i, 31) {
        if (pow(K, i) > N) {
            ans = i;
            break ;
        }
    }
    cout << ans << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    solve(N, K);
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include<list>
#include<vector>
#include<stack>
#include<queue>

using namespace std;
int main()
{
    int n,q;
    cin>>n>>q;
    list<int> li[n];
    int tp1,tp2,a;
    while(q--){
        cin>>tp1>>tp2;
        switch(tp1){
        case 0:
            cin>>a;
            li[tp2].insert(li[tp2].end(),a);
            break;
        case 1:
            for(list<int>::iterator it=li[tp2].begin();it!=li[tp2].end();it++){
                if(it!=li[tp2].begin())cout<<" ";
                cout<<*it;
            }
            cout<<"\n";
            break;
        case 2:
            cin>>a;
            li[a].splice(li[a].end(),li[tp2]);
            break;
        }
    }
}

//list<int> lit;
//list<int>::iterator it;
//int main()
//{
//    lit.clear();
//    int t,tp,a;
//    it=lit.begin();
//    cin>>t;
//    while(t--){
//        cin>>tp;
//        switch(tp){
//        case 0:
//            cin>>a;
//            lit.insert(it,a);
//            break;
//    case 1:
//            cin>>a;
//            if(a<0){
//                while(a++){
//                    if(it!=lit.end())it++;
//                }
//            }
//            else if(a>0){
//                while(a--){
//                    if(it!=lit.begin())it--;
//                }
//            }
//        break;
//    case 2:
//        lit.erase(--it);
//        break;
//        }
//    }
//    lit.reverse();
//    for(it=lit.begin();it!=lit.end();it++){
//
//        cout<<*it<<"\n";
//    }
//}



Measured memory_bytes: 18740
#include<iostream>
#include<string.h>
#include<vector>

using namespace std;

bool student[1000][1260];

int main(){
	while(true){
		memset(student,0,sizeof(student));
		int n,m;
		cin >> n >> m;
		if(n == 0 && m == 0) break;
		int r;
		cin >> r;
		
		vector<int> iodata[1000][2];
		int user[10000];
		int num = 0;
		memset(user,-1,sizeof(user));
		for(int i = 0;i < r;i++){
			int t,a,b,f;
			cin >> t >> a >> b >> f;
			if(user[b] == -1){
				user[b] = num;
				num++;
			}
			iodata[user[b]][f].push_back(t);
		}
		
		for(int i = 0;i < num;i++){
			for(int j = 0;j < iodata[i][1].size();j++){
				for(int k = iodata[i][1][j];k < iodata[i][0][j];k++){
					student[i][k] = 1;
				}
			}
		}
		
		int q;
		cin >> q;
		for(int i= 0;i < q;i++){
			int ts,te,c;
			cin >> ts >> te >> c;
			if(user[c] == -1){
				cout << 0 << endl;
			}else{
				int time = 0;
				for(int j = ts;j < te;j++){
					if(student[user[c]][j] == 1) time++;
				}
				cout << time << endl;
			}
		}
	}
	
	return 0;
}


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

int main() {
  int N , K ;
  cin >> N >> K ;

  // ここにプログラムを追記
  int a ,i;
  a=1;
  for(i=1;i<=N;i++){
    if(a<K){
      a=a*2;
      continue;
    }
    if(a>=K){
      a=a+K;
    }
  }
  cout << a << endl;
    
  
  
  
      
  
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <cmath>
#include <iomanip>

using namespace std;

int main() {
    int N;
    string S;
    cin >> N;
    cin >> S;
    int answer=0;
    char last='A';

    for(auto& c : S){
        if(c!=last)
            answer++;
        last=c;
    }

    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 512
using System;

namespace Kyopuro
{
    class Program
    {
        static void Main(string[] args)
        {

            int N = int.Parse(Console.ReadLine());
            int i;
            int count;

            string[] st = Console.ReadLine().Split(' ');

            long ans=0;
            long[] num = new long[N];

            for (i = 0; i < N; i++)
            {
                num[i] = long.Parse(st[i]);
            }
            count = CountMinus(num, N);


            for (i = 0; i < N; i++)
            {
                num[i] = Math.Abs(long.Parse(st[i]));
            }

            Array.Sort(num);

            if (ExistZero(num, N))
            {
                for (i = 0; i < N; i++)
                {
                    ans += Math.Abs(num[i]);
                }
            }
            else if (count == 1)
            {
                ans = num[0] * -1;
                for (i = 1; i < N; i++)
                {
                    ans += Math.Abs(num[i]);
                }
            }
            else
            {
                for (i = 0; i < N; i++)
                {
                    ans += Math.Abs(num[i]);
                }
            }
            Console.WriteLine(ans);
        }





        static int CountMinus(long[] numlist, int N)
        {
            int count = 0;
            int i;

            for (i = 0; i < N; i++)
            {
                if(numlist[i] < 0)
                {
                    count++;
                }
            }
            return count%2;
        }

        static bool ExistZero(long[] numlist, int N)
        {
            bool isExist = false;
            int i;

            for (i = 0; i < N; i++)
            {
                if (numlist[i] == 0)
                {
                    isExist = true;
                }
            }
            return isExist;
        }


    }
}

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

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define odd(x) ((x) % (2))
#define fastio ios_base::sync_with_stdio(false), cin.tie(0);
#define fileio freopen("template.in", "r", stdin), freopen("template.out", "w", stdout);
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const ll MOD = 1e9 + 7;

int main() {
    fastio;
    //fileio;
        
    int streak = 0;
    int best = 0;
    string s;
    cin >> s;
    FOR(i, 0, 3) {
        if (s[i] == 'S') {
            best = max(best, streak);
            streak = 0;
        } else {
            streak++;
        }
    }
    best = max(best, streak);
    cout << best << "\n";
    return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
const long long MOD = 1e9+7;
//aのMODbでの逆元
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
//nCk
long long combi(int n,int k){
    k = min(k,n-k);
    long long p = 1;
    for(int i = n;i>=n-k+1;i--){
        p*=i;
        p%=MOD;
    }
    for(int i = 0;i<k;i++){
        p*=modinv((i+1),MOD);
        p%=MOD;
    }
    return p;
}
long long power(long long n,int x,long long MOD){
    long long a = 1;
    long long b = x;
    while(n>0){
        if(n%2==1){
            a*=b;
            a%=MOD;
        }
        n/=2;
        b = b*b;
        b%=MOD;
    }
    return a;
}
int main(){
    long long n,a,b;
    cin >> n >> a >> b;
    long long ans = power(n,2,MOD) -1;
    long long tmp = 0;
    tmp+=combi(n,a);
    tmp+=combi(n,b);
    ans-=tmp;
    ans%=MOD;
    if(ans<0) ans+=MOD;
    cout << ans << endl;
}

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

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

    int R, G, B, N;
    cin >> R >> G >> B >> N;

    long long res = 0;
    for (int r=0; r<=N; r+=R) {
        for (int g=0; r+g<=N; g+=G) {
            if ((N - r - g) % B == 0) {
                res ++;
            }
        }
    }

    cout << res << endl;

    return 0;
}

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


int main() {

    int n, m;
    cin >> n >> m;
    int a[55], b[55];
    for (int i = 0; i < m; ++i) {
        cin >> a[i] >> b[i];
    }
    int sum[55];
    for (int i = 0; i < n; ++i) {
        sum[i] = 0;
    }
    for (int i = 0; i < m; ++i) {
        sum[a[i]-1] += 1;
        sum[b[i]-1] += 1;
    }
    for (int i = 0; i < n; ++i) {
        cout << sum[i] << endl;
    }
    return 0;
}

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

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}

void code() {
    ll n,d;
    cin>>n>>d;
    ll ans=0;
    vector<ll> A(n);
    for(ll i=0; i<n; i++) {
        ll x,y;
        cin>>x>>y;
        if(x*x+y*y <= d*d)
            ans++;
    }


    cout << ans << "\n";
}

signed main() {
    std::ios_base::sync_with_stdio(false);
    ll t=1;
    // cin>>t;
    for(ll i=0; i<t; i++) {
        code();
    }
}


Measured memory_bytes: 4844
// 2011/04/02 Tazoe

#include <iostream>
#include <string>
using namespace std;

int main()
{
	int cnt = 0;

	while(!cin.eof()){
		string str;
		getline(cin, str);
		if(str.empty())
			continue;

		bool pal = true;
		for(int i=0, j=str.size()-1; i<=j; i++, j--)
			if(str[i]!=str[j]){
				pal = false;
				break;
			}

		if(pal)
			cnt++;
	}

	cout << cnt << endl;

	return 0;
}

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

int main() {
	int a, b;
	cin >> a >> b;
	if (b%a == 0) cout << a + b << endl;
	else cout << b - a << endl;
}

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

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

	if (a == b)
	{
		if (a == c)
		{
			cout << "No" << endl;
		}
		else
		{
			cout << "Yes" << endl;
		}
	}
	else if (b == c)
	{
		if (a == b)
		{
			cout << "No" << endl;
		}
		else
		{
			cout << "Yes" << endl;
		}
	}
	else if (a == c)
	{
		if (a == b)
		{
			cout << "No" << endl;
		}
		else
		{
			cout << "Yes" << endl;
		}
	}
	else
	{
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cassert>
#include <complex>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <sstream>
#include <ctime>
#include <cctype>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <deque>
#include <stack>
#include <memory.h>
using namespace std;
typedef long long ll;
#define mp make_pair
int n;
int cnt[4];
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		string tmp;
		cin>>tmp;
		if(tmp=="AC"){
			cnt[0]++;
		}
		if(tmp=="WA"){
			cnt[1]++;
		}
		if(tmp=="TLE"){
			cnt[2]++;
		}
		if(tmp=="RE"){
			cnt[3]++;
		}
	}
	cout<<"AC x "<<cnt[0]<<endl;
	cout<<"WA x "<<cnt[1]<<endl;
	cout<<"TLE x "<<cnt[2]<<endl;
	cout<<"RE x "<<cnt[3]<<endl;
	return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
                    
using namespace std;
struct Point{       
  double x,y;       
};                  
void Koch(int,Point,Point);
                    
int main(){         
 int num;           
 Point p1,p2;       
 cin >> num;        
 /*?????????*/         
 p1.x  = 0;         
 p1.y = 0;          
 p2.x = 100;        
 p2.y = 0;          
 printf("%.8f %.8f\n",p1.x,p1.y);
 Koch(num,p1,p2);   
 printf("%.8f %.8f\n",p2.x,p2.y);
 return 0;          
}                   
                    
                    
void Koch(int num, Point p1, Point p2){
  Point p3,p4,p5;   
  double rad;       
  if( num == 0){    
    return;         
  }                 
  rad = M_PI*60.0 / 180.0;/*??????*/
  p3.x = (2.0 * p1.x + 1.0* p2.x) / 3.0;
  p3.y = (2.0 * p1.y + 1.0 * p2.y) / 3.0;
  p4.x = (1.0 * p1.x + 2.0* p2.x) / 3.0;
  p4.y = (1.0 * p1.y + 2.0 * p2.y) / 3.0;
  p5.x = (p4.x - p3.x)*cos(rad) - (p4.y - p3.y)*sin(rad) + p3.x;
  p5.y = (p4.x - p3.x)*sin(rad) + (p4.y - p3.y)*cos(rad) + p3.y;
                    
  Koch(num-1, p1, p3);
  printf("%.8f %.8f\n",p3.x,p3.y);
  Koch(num-1, p3, p5);
  printf("%.8f %.8f\n",p5.x,p5.y);
  Koch(num-1, p5, p4);
  printf("%.8f %.8f\n",p4.x,p4.y);
  Koch(num-1,p4,p2);                                                                                                                                                                          
}

Measured memory_bytes: 3204
i=0,j,a[10];main(y){for(;i<=9;)scanf("%d",&a[i++]);for(i=0;i<=8;i++)for(j=i+1;j<=9;j++){if(a[i]<a[j]){y=a[i];	a[i]=a[j];a[j]=y;}}for(i=0;i<3;)printf("%d\n",a[i++]);exit(0);}

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

#define ll long long int
#define watch(x) cout << (#x) << " is " << (x) << endl
#define f(i,x,n)  for(int i=x;i<n;i++)
#define FASTIO cin.tie(0); cout.tie(0);
#define eb(x) emplace_back(x)
#define mp(a,b) make_pair(a,b)
#define sz(a) int((a).size())
#define mod 1000000007
#define tr(c,i) for(typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)

//MIN-MAX
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))

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

//For sort by second
bool cmp(const pair<int,int> &a)
{ return a.first<a.second; }

//Tree
/* const int MAXN = 1e5 + 5;
vector<ll> adj[MAXN];*/

//ModPower
ll modpower(ll a,ll b,ll c)
{
	ll res=1;
	while(b)
	{
		if(b&1LL)
			res=(res*a)%c;
		a=(a*a)%c;
		b>>=1;
	}
	return res;
}

int main()
{
	FASTIO;

	ll n,k;
	 cin>>n>>k;

	 //dp[i]->denote the number of ways to distribute i candies.
	 vector<ll>dp(k+1);
	 dp[0]=1;

	 for(ll child=0;child<n;child++)
     {
         ll upto;
          cin>>upto;
          vector<ll>fake(k+1);
        for(ll tot_candy=k;tot_candy>=0;tot_candy--)
        {
            ll temp=dp[tot_candy];
            ll l=tot_candy+1;
            ll r=tot_candy+min(upto,k-tot_candy);
            if(l<=r)
            {
                fake[l]=(fake[l]+temp)%mod;

                if(r!=k)
                {
                    fake[r+1]=(fake[r+1]-temp);
                    if(fake[r+1]<0)
                        fake[r+1]+=mod;
                }

            }


        }
         ll pref_sum=0;
        for(ll i=0;i<=k;i++)
        {
            pref_sum=(pref_sum+fake[i])%mod;
            dp[i]= (dp[i]+pref_sum)%mod;
        }

     }

     cout<<dp[k]%mod<<"\n";;




	return 0;
}













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

int main(){
    int w1=0,h1=0,w2,h2,n,i;
    cin >> w2 >> h2 >> n;
    int a[n];
    for (i=0;i<n;i++){
        int x,y;
        cin >> x >> y >> a[i];
        if (a[i] == 1){
            if(x > w1){
                w1 = x;
            }
        }
        if (a[i] == 2){
            if (x < w2){
                w2 = x;
            }
        }
        if (a[i] == 3){
            if (y > h1){
                h1 = y;
            }
        }
        if (a[i] == 4){
            if (y < h2){
                h2 = y;
            }
        }
    }

    int num = (w2 - w1) * (h2 - h1);
    if (w2 < w1 || h2 < h1){
        cout << 0;
    }
    else{
        cout << num;
    }
}



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

#define rep(i,n) for(ll i=0;i<ll(n);i++)
#define YESNO(T) if(T){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define yesno(T) if(T){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}
#define YesNo(T) if(T){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}

const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
const double pi = 3.14159265358979;



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

    ll a,b,x;
    cin >> a >> b >> x;

    cout << (b/x) - ((a+x-1)/x) + 1 << endl;
}

Measured memory_bytes: 3644
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


@mt
def slv(N, A):
    q = []
    lc = [0]*(N+1)
    for i in range(N):
        heapq.heappush(q, A[i])
        lc[0] += A[i]
    for i in range(N, 2*N):

        a = heapq.heappushpop(q, A[i])
        lc[i-N+1] = lc[i-N] + A[i] - a

    q = []
    rc = [0] * (N+1)
    for i in range(3*N-1, 2*N-1, -1):
        heapq.heappush(q, -A[i])
        rc[N] += A[i]
    for i in range(2*N-1, N-1, -1):
        a = -heapq.heappushpop(q, -A[i])
        rc[i-N] = rc[i-N+1] + A[i] - a

    return max(map(lambda x: x[0]-x[1], zip(lc, rc)))


def main():
    N = read_int()
    A = read_int_n()

    print(slv(N, A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 41528
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int MOD =1e9+7;
using ll=long long;

int main(){
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    map<int, ll> sa, wa;
    set<ll> S;
    rep(i,n){
        sa[(i+1) + a[i]]++;
        wa[(i+1) - a[i]]++;
        S.insert((i+1) + a[i]);
    }
    ll ans = 0;
    for(auto x: S){
        ans += sa[x]*wa[x];
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 47764
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		/* A問題
		Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int T = sc.nextInt();

        int cntBiscuit = 0;

        int time = A;

        for(int i = 2 ; time <= T ; i++) {
        	time = A * i;

        	cntBiscuit += B;
        }

        System.out.println(String.valueOf(cntBiscuit));
        */

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		int[] intValue = new int[N];
		for(int i = 0 ; i<N ; i++) {
			intValue[i] = sc.nextInt();
		}

		int[] intCost = new int[N];
		for(int i = 0 ; i<N ; i++) {
			intCost[i] = sc.nextInt();
		}

		int maxValue = 0;

		for(int i = 0 ; i < N ; i++) {
			if (intValue[i] > intCost[i]) {
				maxValue += intValue[i] - intCost[i];
			}
		}

		System.out.println(String.valueOf(maxValue));
	}

}

Measured memory_bytes: 22868
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <queue>
using namespace std;



int main() {

  vector<long long> frq(pow(10, 5)+1, 0);
  long long N, K, a, b;
  cin >> N >> K;

  for (int i = 0; i < N; ++i) {
    cin >> a >> b;
    frq[a] += b;
  }

  for (int i = 1; i < frq.size(); ++i) {
    K -= frq[i];
    if(K <= 0){
      cout << i << endl;
      return 0;
    }
  }

  return 0;
}



Measured memory_bytes: 1024
#include <stdio.h>
int main()
{
    long long int a, b, c, d, m, n, o, p;
    scanf("%lld %lld %lld %lld", &a, &b, &c, &d);

    m = a*c;
    n = a*d;
    o = b*c;
    p = b*d;
    if(m >= n && m >= o && m >= p)
    {
        printf("%lld\n", m);
    }
    else if(n >= m && n >= o && n >= p)
    {
        printf("%lld\n", n);
    }
    else if(o >= m && o >= n && o >= p)
    {
        printf("%lld\n", o);
    }
    else
    {
        printf("%lld\n", p);
    }
    return 0;
}

Measured memory_bytes: 1708
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  int n,m;
  cin>>n>>m;
  int sum = 0;
  rep(i,m){
    int a;
    cin>>a;
    sum+=a;
  }
  if(sum>n)cout<<-1<<endl;
  else cout<<n-sum<<endl;
  return 0;
}


Measured memory_bytes: 3632
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    a = LI()
    ans = 0
    for i in range(n-1):
        if a[i + 1] < a[i]:
            ans += a[i] - a[i + 1]
            a[i+1] = a[i]
        # print(a[i+1],a[i])
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 110796
#include<bits/stdc++.h>
using namespace std;
long long n,l[90];
int main()
{
	cin>>n;
	l[0]=2;l[1]=1;
	for(int i=2;i<=n;i++)
	  l[i]=l[i-1]+l[i-2];
	cout<<l[n];
	return 0;
}

Measured memory_bytes: 256
H,W,K = map(int,input().split())
a = []
for _ in range(H):
    a.append(input())
answer = [[0 for _ in range(W)] for _ in range(H)]

def sumC(arr):
    s = 0
    for c in arr:
        if c == '#':
            s += 1
    return s

blockIndex = 1

def processNotEmptyRow(i,s):
    global blockIndex
    update = False
    k = 0
    for j in range(W):
        if update:
            blockIndex += 1
            update = False
        answer[i][j] = blockIndex
        if a[i][j] == '#' and k < s - 1:
            update = True
            k += 1
    blockIndex += 1

def processEmptyRow(i,direction):
    global answer
    for j in range(W):
        answer[i][j] = answer[i + direction][j]

sums = [0 for _ in range(H)]

for i in range(H):
    s = sumC(a[i])
    sums[i] = s
    if s > 0:
        processNotEmptyRow(i,s)
        notEmptyRowIndex = i

k = notEmptyRowIndex - 1
while k >= 0:
    if sums[k] == 0:
        processEmptyRow(k, 1)
    k -= 1
k = notEmptyRowIndex + 1
while k < H:
    if sums[k] == 0:
        processEmptyRow(k, -1)
    k += 1

for r in answer:
    print(" ".join(map(str,r)))

Measured memory_bytes: 7272
n = int(input())
a, b = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
cnt = [0,0,0]
for i in range(n):
    if p[i] <= a:
        cnt[0] += 1
    elif p[i] >= b+1:
        cnt[2] += 1
    else:
        cnt[1] += 1

print(min(cnt))

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#define ll long long
#define INF (1<<30)
using namespace std;
int dx[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };
int dy[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
struct Castle {
	int h;
	int w;
	int times;
};
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	ll H, W; cin >> H >> W;
	vector<vector<char>> sand(H, vector<char>(W));
	vector<vector<int>> m(H, vector<int>(W, 0));
	queue<Castle> q;
	for (int i = 0; i < H;i++) for (int j = 0; j < W;j++) cin >> sand[i][j];
	for (int i = 0; i < H;i++) {
		for (int j = 0; j < W;j++) {
			if (sand[i][j] == '.') m[i][j] = INF;
			else {
				for (int k = 0; k < 8;k++) {
					int vi = i + dx[k];
					int vj = j + dy[k];
					if (sand[vi][vj] == '.')m[i][j]++;
				}
				if (m[i][j] >= sand[i][j] - '0') {
					q.push({ i,j,1 });
				}
			}
		}
	}
	int ret = 0;
	while (!q.empty()) {
		Castle cas = q.front(); q.pop();
		ret = cas.times;
		for (int k = 0; k < 8;k++) {
			int vi = cas.h + dx[k];
			int vj = cas.w + dy[k];
			if (m[vi][vj] >= sand[vi][vj] - '0')continue;
			m[vi][vj]++;
			if (m[vi][vj] >= sand[vi][vj] - '0') q.push({ vi,vj,ret + 1 });
		}
	}
	cout << ret << endl;
}

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

using namespace std;

const int MAX_N = 1e5 + 5;

int arr [MAX_N];

int main () {
  ios::sync_with_stdio(false);

  int n, c, k;
  cin >> n >> c >> k;

  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  sort(arr, arr + n);

  int ans = 0;
  int cur_t = -1, cap = 0;
  for (int i = 0; i < n; i++) {
    if (cur_t < arr[i]) {
      ans++;
      cur_t = arr[i] + k;
      cap = 1;
    } else {
      cap++;
    }

    if (cap == c) {
      cur_t = -1;
      cap = 0;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>

using namespace std;
using namespace boost::adaptors;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;

int main()
{
  int n;
  cin>>n;
  vecint b(n-1);
  for(auto& v : b) cin>>v;
  int sum = b.front() + b.back();
  for(int i:boost::irange(0, n-2)) {
    sum += min(b[i], b[i+1]);
  }
  cout<<sum<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long a[2002];
int main()
{
    long long t,i,k,n,x,y=1,z=1,s=1,j;
    cin>>n;

    a[0]=1;
    for(i=3;i<=n;i++)
    {
          for(j=3;j<=i;j++)
          {
              a[i]+=a[i-j];
              a[i]%=1000000007;
          }
    }

    cout<<a[n]<<endl;

    return 0;
}


Measured memory_bytes: 3644
G, N = [int(_) for _ in input().split(" ")]
ret = ()
T = [-1]*(G+1)
T[0] = 1
T[1] = 1
for i in range(N):
  t = int(input())
  T[t] = 0

for i in range(2, G+1):
	if T[i] == -1:
		T[i] = (T[i-1] + T[i-2]) % 1000000007

print (T[G])


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

#define PI 4*atan(1);

int main(){
  int sum;
  while(cin >> sum && sum){
    int p = 0, tmp;
    for(int i =0; i < 9; i++){
      cin >> tmp;
      p += tmp;
    }
    cout << sum - p << endl;
  }
}

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

int A[1005];

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

    int N; cin >> N;
    string S; cin >> S;

    for(int i = 0; i <= 999; i++) {
        int flag1 = 1e9, flag2 = 1e9;
        for(int j = 0; j < N; j++) {
            if(S[j] == i/100 + '0' && flag1 == 1e9) {
                flag1 = j;
                continue;
            }
            if(S[j] == (i/10)%10 + '0' && j > flag1 && flag2 == 1e9) {
                flag2 = j;
                continue;
            }
            if(S[j] == i%10 + '0' && j > flag2) {
                A[i] = 1;
                break;
            }
        }
    }

    int ans = 0;
    for(int i = 0; i <= 999; i++) {
        if(A[i] == 1) ans++;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 384
N,D,X = map(int,input().split())

"""
・玉の位置は無視できる
・等差数列なので左右反転して平均化→完全等間隔に帰着
・ひとつ取り去ったあとの平均化→それも完全等間隔の定数倍
・すべての間隔が1であるN区間の場合の期待値を求める
"""

x = .5
for n in range(2,N+1):
    x += .5 + x/n

answer = x * (2*D+X*(2*N-1))
print(answer)

Measured memory_bytes: 3060
#if 0

#endif

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

int X, Y, S;
int tax(int rate, int priceWithoutTax) {
  return priceWithoutTax + int(floor(priceWithoutTax * rate * 0.01));
}
int solve() {
  int maximum = 0;
  for (int i=1; i<S; ++i)
    for (int j=i; j<S; ++j)
      if (tax(X,i)+tax(X,j) == S)
        maximum = max(maximum, tax(Y,i)+tax(Y,j));
  return maximum;
}

int main() {
  while (cin >> X >> Y >> S && X>0) {
    cout << solve() << endl;
  }
}



Measured memory_bytes: 3104
def selection_sort(A):
    steps = 0
    N = len(A)
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if A[minj][0] > A[j][0]:
                minj = j
        if i != minj:
            steps += 1
        A[minj], A[i] = A[i], A[minj]

    # [print(A[idx], end=' ') if idx != len(A) - 1 else print(A[idx]) for idx in range(len(A))]
    # print(steps)
    return A


def bubbleSort(A):
    steps = 0
    flag = 1
    completed_idx = 0
    while flag:
        flag = 0
        for i in range(len(A) - 1, completed_idx, -1):
            if A[i - 1][0] > A[i][0]:
                A[i - 1], A[i] = A[i], A[i - 1]
                steps += 1
                flag = 1
        completed_idx += 1

    # for e in A[:-1]:
    #     print(e, end=' ')
    # print(A[-1])
    # print(steps)
    return A

d = dict()
N = int(input())
A = [(int(elem[1:]), elem[0]) for elem in input().split()]

for elem in A:
    if elem[0] not in d:
        d[elem[0]] = elem[1]
    else:
        d[elem[0]] += elem[1]

is_stable = True
A_bubble = bubbleSort(A[:])
st = A_bubble[0][1]
cur_val = A_bubble[1][0]
prev_val = A_bubble[0][0]
for e in A_bubble[1:]:
    cur_val = e[0]
    if cur_val != prev_val:
        if st != d[prev_val]:
            is_stable = False
            break
        st = ''
    st += e[1]
    prev_val = cur_val
[print(A_bubble[idx][1] + str(A_bubble[idx][0]), end=' ') if idx != len(A_bubble) - 1 else print(A_bubble[idx][1] + str(A_bubble[idx][0])) for idx in range(len(A_bubble))]
print('Stable' if is_stable else 'Not stable')

is_stable = True
A_slt = selection_sort(A[:])
st = A_slt[0][1]
cur_val = A_slt[1][0]
prev_val = A_slt[0][0]
for e in A_slt[1:]:
    cur_val = e[0]
    if cur_val != prev_val:
        if st != d[prev_val]:
            is_stable = False
            break
        st = ''
    st += e[1]
    prev_val = cur_val

[print(A_slt[idx][1] + str(A_slt[idx][0]), end=' ') if idx != len(A_slt) - 1 else print(A_slt[idx][1] + str(A_slt[idx][0])) for idx in range(len(A_slt))]
print('Stable' if is_stable else 'Not stable')
#
# 5
# H4 C9 S4 D2 C3


Measured memory_bytes: 5628