akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#define REP(i, n)   for(int i = 0; i < (n); i++)
#define REPS(i, n)  for(int i = 1; i <= (n); i++)
#define RREP(i, n)  for(int i = (n)-1; i >= 0; i--)
#define RREPS(i, n) for(int i = (n); i > 0; i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define mt make_tuple
#define pb push_back

using ll  = long long;
using pi  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vs  = vector<string>;
using vb  = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll  INFL = 1e18;
const double PI = 3.141592653589793;
const double EPS = 1e-9;

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

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int N; cin >> N;
    vi A(N), B(N);
    REP(i, N) cin >> A[i];
    REP(i, N) cin >> B[i];

    vi countA(200001), countB(200001);
    REP(i, N)
    {
        countA[A[i]]++;
        countB[B[i]]++;
    }

    vector<pi> tmp(N);
    REP(i, N) tmp[i] = mp(countA[A[i]], i);
    sort(ALL(tmp));
    vi indexA(N);
    REP(i, N) indexA[i] = tmp[i].second;

/*
    cout << endl;
    REP(i, N) cout << indexA[i] << " ";
    cout << endl;
*/

    priority_queue<pi> q;
    REP(i, 200001) if(countB[i] > 0) q.push(mp(countA[i], i));
    q.push(mp(-1, -1));

    vi ans(N, -1);
    REP(i, N)
    {
        pi most = q.top(); q.pop();
        pi less = q.top(); q.pop();

        if(A[indexA[i]] == most.second)
        {
            if(countB[less.second] == 0 || less.first == -1) break;
            q.push(most);
            ans[indexA[i]] = less.second;
            countB[less.second]--;
            if(countB[less.second] > 0) q.push(less);
        }
        else
        {
            if(countB[most.second] == 0 || most.first == -1) break;
            q.push(less);
            ans[indexA[i]] = most.second;
            countB[most.second]--;
            if(countB[most.second] > 0) q.push(most);
        }
    }

    bool ok = true;
    REP(i, N) if(A[i] == ans[i] || ans[i] == -1) ok = false;

    if(ok)
    {
        cout << "Yes" << endl;
        REP(i, N) cout << ans[i] << " ";
        cout << endl;
        return 0;
    }
    cout << "No" << endl;
}

Measured memory_bytes: 10964
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

struct team{
	int tnum, correct, penalty;
};

bool cmp(struct team lhs, struct team rhs){
	if(lhs.correct != rhs.correct)
		return lhs.correct > rhs.correct;
	else if(lhs.penalty != rhs.penalty)
		return lhs.penalty < rhs.penalty;
	else
		return lhs.tnum < rhs.tnum;
}

int main(){
	int T, P, R;
	int t, q, time;
	string judge;
	int wrong[100][100];
	struct team ans[100];
	int i, j;
	
	while(1){
		cin >> T >> P >> R;
		if(T == 0 && P == 0 && R == 0)
			break;
		
		for(i = 0; i < 100; i++){
			ans[i].tnum = i + 1;
			ans[i].correct = ans[i].penalty = 0;
			for(j = 0; j < 100; j++)
				wrong[i][j] = 0;
		}
		
		for(i = 0; i < R; i++){
			cin >> t >> q >> time >> judge;
			
			if(judge == "WRONG")
				wrong[t - 1][q - 1]++;
			else{
				ans[t - 1].correct++;
				ans[t - 1].penalty += time + wrong[t - 1][q - 1] * 1200;
			}
		}
		
		sort(ans, ans + T, cmp);
		for(i = 0; i < T; i++)
			cout << ans[i].tnum << " " << ans[i].correct << " " << ans[i].penalty << endl;
	}
	
	return 0;
}

Measured memory_bytes: 968
function Main(input) {
  input=input.split("\n");
  if(input[input.length-1]===''){
    input.pop();
  }
  const N=input[0].split(' ')[0]-0;
  const K=input[0].split(' ')[1]-0;
  var key=input[1].split(' ').map(e=>{
    return e-0;
  }).findIndex(e=>{
    return e===1;
  });
  console.log(Math.ceil((N-1)/(K-1)));
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 37624
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(x) (x).begin(),(x).end()
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;

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

    return 0;
}



Measured memory_bytes: 256
function Main(input) {
  input = input.trim().split(" ");
  var A = parseFloat(input[0]);
  var B = parseFloat(input[1]);
  var H = parseFloat(input[2]);
  var M = parseFloat(input[3]);

  var rad = 6;

  var Hrad = H * 5 * rad + (30 * M) / 60;
  var Mrad = M * rad;

  var A2 = Math.pow(A, 2);
  var B2 = Math.pow(B, 2);
  var cos = Math.cos((Hrad - Mrad) * (Math.PI / 180));
  var l = Math.sqrt(A2 + B2 - 2 * A * B * cos);
  console.log(l);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 29748
# -*- coding: utf-8 -*-
from copy import deepcopy
def inpl(): return tuple(map(int, input().split()))

N = int(input())
A = inpl()
L = list(A)
cms = []

if abs(max(L)) > abs(min(L)):
    m = max(L)
    mi = L.index(max(L))
    
    for i in range(1, N):
        if L[i-1] <= L[i]:
            continue
        elif L[i-1] <= L[i] + m:
            cms.append("{} {}".format(mi+1, i+1))
            L[i] += m
            if L[i] > m:
                m = L[i]
                mi = i
        elif L[i-1] <= L[i] + 2*m:
            cms.append("{} {}".format(mi+1, i+1))
            cms.append("{} {}".format(mi+1, i+1))
            L[i] += 2*m
            if L[i] > m:
                m = L[i]
                mi = i
        else:
            print("Error11")
            break
else :
    m = min(L)
    mi = L.index(min(L))
    
    for i in range(N-2, -1, -1):
        if L[i] <= L[i+1]:
            continue
        elif L[i] + m <= L[i+1]:
            cms.append("{} {}".format(mi+1, i+1))
            L[i] += m
            if L[i] < m:
                m = L[i]
                mi = i
        elif L[i] + 2*m <= L[i+1]:
            cms.append("{} {}".format(mi+1, i+1))
            cms.append("{} {}".format(mi+1, i+1))
            L[i] += 2*m
            if L[i] < m:
                m = L[i]
                mi = i
        else:
            print("Error12")
            break

print(len(cms))
if len(cms) > 2*N:
    print("Error2")
for cm in cms:
    print(cm)

Measured memory_bytes: 3444
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i = (s);i<(int)(n);i++)

int main(){
    long long x;
    cin >> x;
    long long k = 100;
    int sum = 0;
    while(k < x){
        k *= 1.01;
        sum++;
    }
    cout << sum << endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#include <unordered_set>
#include <unordered_map>

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
typedef set<LL> SLL;
typedef unordered_set<LL> USLL;
typedef string STR;

template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
template<class T> void _R(std::vector<T>& v) { for (auto& e : v) { _R(e); } }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;

LL calc_MEX(const std::vector<LL>& v) {
  std::unordered_set<LL> values;
  for (const auto& e : v) {
    values.insert(e);
  }
  for (LL k = 0; k <= (LL)v.size(); ++k) {
    if (values.find(k) == values.end()) {
      return k;
    }
  }
  return v.size();
}

int main() {
  LL n;
  R(n);
  W((1000 - n % 1000) % 1000);
  return 0;
}


Measured memory_bytes: 3784
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<vector>
using namespace std;
using uint = unsigned int;
using ll = long long;
const int M = 1e9 + 7;
const ll MLL = 1e18L + 9;
#pragma unused(M)
#pragma unused(MLL)
#ifdef LOCAL
#include"rprint.hpp"
#else
template <class... T> void printl(T&&...){ }
template <class... T> void printc(T&&...){ }
template <class... T> void prints(T&&...){ }
template <class... T> void printd(T&&...){ }
template <class... T> void printArr(T&&...){ }
#endif

ll solve(ll a, ll b){
    int msba, msbb;
    ll a2 = a, b2 = b;
    while(1){
        msba = msbb = -1;
        for(int i = 0; i < 64; i++){
            if(a2 & (1ll << i)){ msba = i; }
            if(b2 & (1ll << i)){ msbb = i; }
        }
        if(msba != msbb){ break; }
        a2 ^= 1ll << msba;
        b2 ^= 1ll << msba;
    }
    prints(msba, msbb);
    ll upper = (1ll << msbb) - a2;
    // ll upper2 = (1ll << msbb) * 2 - upper;
    ll upper2 = (1ll << msbb) | a2;
    ll range1 = b2 - a2 + 1,
       dupe = max(0ll, b2 - upper2 + 1);
    printd(upper, upper2, range1, dupe);
    bitset<64> bsu(upper2), bsa(a), bsb(b), bs1(range1 + upper - dupe), bs2(68833183630578410ll);
    printd(bsu);
    printd(bsa);
    printd(bsb);
    printd(bs1);
    printd(bs2);
    // cout << range1 + upper - dupe << '\n';
    int msbb2 = 0;
    for(int i = 0; i < 64; i++){
        if((b2 ^ (1ll << msbb)) & (1ll << i)){ msbb2 = i; }
    }
    ll lower = b2 | ((1ll << msbb2) - 1);
    bitset<64> bsl(lower);
    printd(bsl);
    range1 = lower - a2 + 1;
    dupe = max(0ll, lower - upper2 + 1);
    return range1 + upper - dupe;
}

int main(){
    ll a, b;
    cin >> a >> b;
    if(a == b){ cout << 1 << '\n'; return 0; }
    cout << solve(a, b) << '\n';
    return 0;
}


Measured memory_bytes: 888
n = int(input())
arr = [0] * (n + 1)

for x in range(1, 101):
  for y in range(1, 101):
    for z in range(1, 101):
      a = x**2 + y**2 + z**2 + x*z + y*z + x*y
      if a<= n:
        arr[a] += 1
        
for i in range(1,n+1):
    print(arr[i])

Measured memory_bytes: 9224
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fo(i,s,e) for( i=s;i<e;i++)
#define rfo(i,s,e) for(i=s;i>e;i--)
#define LL long long int 
const LL MOD=1e9+7;
#define pb push_back
#define pob pop_back()
#define sp " "
#define ff first
#define ss second
//            When something is important enough, you do it even if the odds are not in your favor.

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    // code goes here
    int t=1;//cin>>t;
    while(t--){
      LL n,i;cin>>n;
      std::map<string, LL> m;
      fo(i,0,n){
        string s;cin>>s;
        sort(s.begin(), s.end());
        m[s]++;
      }
      LL ans=0;
      for(auto x:m){
        ans+=x.ss*(x.ss-1)/2;
      }
      cout<<ans;
    }
    return 0;
}

Measured memory_bytes: 11400
#include <bits/stdc++.h>
using namespace std;
long long a,n,k;
int d[70][200001],i,j,g;
int main()
{
    cin>>n>>k;
    for(i=0;i<n;++i)
	{
    	cin>>a;
    	d[0][i]=a-1;
    }
    for(i=0;i<=60;++i)
    	for(j=0;j<n;++j)d[i+1][j]=d[i][d[i][j]];
    for(i=0;i<=60;++i)if(k&(1LL<<i))g=d[i][g];
    cout<<g+1;
    return 0;
}

Measured memory_bytes: 52072
#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)


def count_answer(x,y,num_b,num_w):
    # print(used)

    if S[x][y] == "#":
        num_b += 1
    else:
        num_w += 1
    used[x][y] = 1
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1 or next_x >= H or next_y >= W:
            pass
        elif used[next_x,next_y] == 1:
            pass
        elif S[next_x][next_y] != S[x][y]:
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            continue
        num_b = 0
        num_w = 0
        if S[i][j] == "#":
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)


Measured memory_bytes: 203720
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] x = new int[N];
		int[] y = new int[N];
		int[] h = new int[N];
		
		for (int i = 0; i < N; i++) {
			x[i] = sc.nextInt();
			y[i] = sc.nextInt();
			h[i] = sc.nextInt();
		}
		
		for (int posX = 0; posX <= 100; posX++) {
			for (int posY = 0; posY <= 100; posY++) {
				
				int H = -1;
				for (int i = 0; i < N; i++) {
					if (h[i] == 0) continue;
					
					if (H == -1) {
						H = h[i] + Math.abs(posX - x[i]) + Math.abs(posY - y[i]);
					}
					else {
						int tmp = h[i] + Math.abs(posX - x[i]) + Math.abs(posY - y[i]);
						if (tmp != H) {
							H = -2;
							break;
						}
					}
				}
				
				if (H == -2) continue;
				
				for (int i = 0; i < N; i++) {
					if (h[i] != 0) continue;
					
					int tmp = H - Math.abs(posX - x[i]) - Math.abs(posY - y[i]);
					if (tmp > 0) {
						H = -2;
						break;
					}
				}
				
				if (H == -2) continue;
				
				System.out.println(posX + " " + posY + " " + H);
			}
		}

	}

}

Measured memory_bytes: 23380
#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N,M;
    cin >> N >> M;
    int a[N],b[N],c[M],d[M];
    for(int i=0;i<N;i++) cin >> a[i] >> b[i];
    for(int i=0;i<M;i++) cin >> c[i] >> d[i];

    for(int i=0;i<N;i++){
        int mn=400000001,cur=0,ans=0;
        for(int j=0;j<M;j++){
            cur = max(a[i]-c[j], c[j]-a[i]) + max(b[i]-d[j], d[j]-b[i]);
            if(cur < mn){
                mn = cur;
                ans = j+1;
            }
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<pair<ll, ll>> pll;
 
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define popcount(x) __builtin_popcountll(x)
 
const long double PI = acos(-1);
 
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  ll n, m;
  cin >> n >> m;

  cout << (n-1) * (m-1) << endl;
  return 0;
}

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

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        --a[i];
    }
    int ans = 0;
    for (int i = 0; i < n; ++i)
        if (i <a[i] && a[a[i]] == i)
            ++ans;
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		while(true) {

			int middle = in.nextInt();
			int term_end = in.nextInt();
			int retest = in.nextInt();
			int sum = middle + term_end;

			if(middle == -1 && term_end == -1 && retest == -1) {

				break;

			}else if(middle == -1 || term_end == -1) {

				System.out.println("F");

			}else if(sum >= 80) {

				System.out.println("A");

			}else if(sum < 80 && sum >= 65) {

				System.out.println("B");

			}else if(sum < 65 && sum >= 50) {

				System.out.println("C");

			}else if(sum < 50 && sum >= 30) {

				if(retest >=  50) {

					System.out.println("C");

				}else {

					System.out.println("D");

				}

			}else if(sum < 30) {

				System.out.println("F");

			}
		}
	}
}

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

int main(){
  int w, h, x, y, r;
  cin >> w >> h >> x >> y >> r;

  if(x - r < 0 || x + r > w){
    cout << "No" << endl;
  }else if(y - r < 0 || y + r > h){
    cout << "No" << endl;
  }else{
    cout << "Yes" << endl;
  }
  return 0;
}


Measured memory_bytes: 3096
q,h,s,d=map(int,input().split())
n=int(input())
cost=0
if n>=2:
    cost+=n//2*min(q*8,h*4,s*2,d)
    n%=2
if n>=1:
    cost+=n//1*min(q*4,h*2,s)
    n%=1
if n>=0.5:
    cost+=n//0.5*min(q*2,h)
    n%=0.5
if n>=0.25:
    cost+=n//0.25*q
print(cost)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);


const int INF = 1<<30;


int main() {
    int n,m; cin >> n >> m;
    string s; cin >> s;

    // 後ろからのDPテーブルを作成する
    // dp[i] : Nからiに到達するのに必要な最短手数
    // queueを使って計算量を減らしてる
    // queueのサイズ上限としてmにしておく
    // queueにはdp[i]の値がNから順番に入ってる。
    // これやれば、あるi地点を見るときに、queueの先頭にはNからi+mへの最短手数が入ってる。
    // 一回の移動で最大m移動できるので、Nからiへの最短手数は Nからi+mへの最短手数に+1した数となる
    vector<int> dp(n+1, INF);
    dp[n] = 0;
    queue<int> q;
    q.push(0);
    for(int i = n-1; i >= 0; i--) {
        while (true) {
            if(q.size() == 0) {
                cout << -1 << endl;
                return 0;
            }
            if (q.front() != INF && q.size() <= m) break;
            q.pop();
        }
        if(s[i] == '0') dp[i] = q.front() + 1;
        q.push(dp[i]);
    }

    // dpテーブルを使って辞書順最短経路を見ていく
    vector<int> ans;
    // 現在いるマス
    int now = 0;
    // 残りのサイコロ振れる回数
    int rest = dp[0];
    while(now < n) {
        --rest;
        int move = 1;
        // 最初に最短経路数が変わる場所が辞書順最短手順
        while(dp[now+move] != rest) move++;
        ans.push_back(move);
        now += move;
    }
    rep(i, ans.size()) {
        cout << ans[i] << endl;
    }

    return 0;
}



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

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll,ll> lll;

const ll MOD = 1000000007;
const ll INF = 1e9+5;
const double eps = 1e-7;
const double PI = acos(-1.0);

#define FOR(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define RFOR(i,a,b) for(long long i = (long long)(a); i >= (long long)(b); i--)
#define ull unsigned long long
#define deb(x )     cerr << #x << " = "<< x << endl;
#define endl    "\n"
#define coud(a,d) cout << fixed << showpoint << setprecision(d) << a;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define fill(x, y) memset(x, y, sizeof(y))
#define all(x) (x).begin(), (x).end()
#define bitcount(x) __builtin_popcount(x)
#define cps CLOCKS_PER_SEC
#define verify(x) if(x >= MOD) x -= MOD;

inline void debug_vi(vi a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
inline void debug_vll(vll a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
inline void print_case(int tn) {cout<<"Case #"<<tn<<": ";}

template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

template<typename T>
using maxpq = priority_queue<T>;
/*----------------------------------------------------------------------*/

//return x^y mod p
ll power(ll x,ll y, ll p)
{
    ll res = 1;     
    x = x % p; 
 
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
 
        y = y>>1; // y = y/2
        x = (x*x) % p;  
    }
    return res;
}

int main(){
    std::ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int n,k; cin>>n>>k;
    ll res = 0;
    ll cnt[k + 1];
    RFOR(i, k, 1) {
        cnt[i] = power(k / i, n, MOD);
        for(int j = 2*i; j <= k; j += i) {
            cnt[i] = (cnt[i] - cnt[j] + MOD)%MOD;
        }
        res += (cnt[i] * i)%MOD;
        res %= MOD;
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 4376
n=int(input());A=list(map(int,input().split(' ')))
B=[]
i = 0
while i < n:
    B.append((A[i],i))
    i += 1
B.sort()
klist = [0]*n
total = 0;count = 1;value = B[0][0];k_temp = [B[0][1]]
i = 1
while i < n:
    if value == B[i][0]:
        count += 1
        k_temp.append(B[i][1])
    else:
        t = count*(count-1)//2
        if t != 0:
            total += t
            diff = t - (count-1)*(count-2)//2
            for p in k_temp:
                klist[p] = -1*diff
        count = 1
        k_temp = [B[i][1]]
        value = B[i][0]
    i += 1
if count != 1:
    t = count*(count-1)//2
    total += t
    diff = t - (count-1)*(count-2)//2
    for p in k_temp:
        klist[p] = -1*diff
for k in klist:
    print(k+total)

Measured memory_bytes: 44672
from math import gcd, ceil
N,M = map(int,input().split())
A = list(map(int,input().split()))
A = [a//2 for a in A]
B = 1

for a in A:
  B*=a//gcd(B,a)
  
for a in A:
  if B//a%2==0:
    print(0)
    exit()

print(ceil((M//B)/2))

Measured memory_bytes: 20132
#include<stdio.h>
 
#define min(a,b) (a < b ? a : b)
 
int main(void){
  long long int L, R;
  int m = 2019;
  scanf("%lld %lld", &L, &R);
  long long int ans = 1000000000;
  int cnt = 0;
  int cnt_1 = 0;
  int t = 0;
  for(long long int i = L; i < R; i++){
    if(cnt_1 > 5000) break;
    cnt = 0;
    for(long long int j = i + 1; j <= R; j++){
      if(cnt > 5000) break;
      t = min( (i * j) % m, ans);
      if( t != ans){
        //printf("%lld %lld\n", i , j);
        ans = t;
      }
      //printf("%d\n", ans);
      cnt++;
      //printf("%d\n", j);
    }
    cnt_1++;
    //printf("%d\n", i);
  }
  printf("%lld", ans);
  return 0;
}

Measured memory_bytes: 128
fun main(args:Array<String>) {
    val (a,b) = readLine()!!.split(" ").map { it.toInt() }
    if(a > 0) {
        println("Positive")
    } else if(b < 0) {
        if((b-a+1) % 2 == 0) {
            println("Positive")
        } else {
            println("Negative")
        }
    } else {
        println("Zero")
    }
}

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

int judge(int num) {
    bool f[3] = {false};
    while(num) {
        int tmp = num % 10;
        if(tmp == 3) f[0] = true;
        else if(tmp == 5) f[1] = true;
        else if(tmp == 7) f[2] = true;
        num /= 10;
    }
    if(f[0] && f[1] && f[2]) return 1;
    else return 0;
}

int solve(int N, int num) {
    if(num > N) return 0;
    int ans = 0;
    ans += judge(num);
    if((long long)num * 10 < N) {
        ans += solve(N, num * 10 + 3);
        ans += solve(N, num * 10 + 5);
        ans += solve(N, num * 10 + 7);
    }
    return ans;
}

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

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

int main(void)
{
    bool is[101] = {0};
    int n;
    scanf("%d", &n);
    while (n--) {
        int d;
        scanf("%d", &d);
        is[d] = true;
    }
    int cnt = 0;
    for (int i = 0; i < 101; i++)
        if (is[i]) cnt++;
    printf("%d\n", cnt);
}


Measured memory_bytes: 128
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#define ll long long
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long

#define INF 999999999

using namespace std;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
// input
int h,w;
string field[50];
int nums[52][52];


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

    REP(i,h){
        cin >> field[i];
    }

    for(int i = 1;i < h+1;i++){
        for(int j = 1;j < w+1;j++){
            if(field[i-1][j-1] == '#'){
                nums[j-1][i-1]++;
                nums[j-1][i]++;
                nums[j-1][i+1]++;
                nums[j][i-1]++;
                nums[j][i+1]++;
                nums[j+1][i-1]++;
                nums[j+1][i]++;
                nums[j+1][i+1]++;
            }
        }
    }

    for(int i = 1;i < h+1;i++){
        for(int j = 1;j < w+1;j++){

            if(field[i-1][j-1]=='#'){
                cout << '#';
            }
            else{
                cout << nums[j][i];                
            }
        }
        cout << "\n";
    }

}

Measured memory_bytes: 256
/**
 *  author: Behradm
 *  Created: 2020.07.25 16:19:18
 *  In The Name Of God
**/
#include <bits/stdc++.h>

using namespace std;

int main() {   
  ios::sync_with_stdio(false);
  cin.tie(0);      
  int x;
  cin >> x;
  if (x >= 400 && x <= 599) {
    cout << 8 << '\n';
    return 0;
  }
  if (x >= 600 && x <= 799) {
    cout << 7 << '\n';
    return 0;
  }
  if (x >= 800 && x <= 999) {
    cout << 6 << '\n';
    return 0;
  }
  if (x >= 1000 && x <= 1199) {
    cout << 5 << '\n';
    return 0;
  }
  if (x >= 1200 && x <= 1399) {
    cout << 4 << '\n';
    return 0;
  }
  if (x >= 1400 && x <= 1599) {
    cout << 3 << '\n';
    return 0;
  }
  if (x >= 1600 && x <= 1799) {
    cout << 2 << '\n';
    return 0;
  }
  if (x >= 1800 && x <= 1999) {
    cout << 1 << '\n';
    return 0;
  }
  return 0;
}
  

Measured memory_bytes: 3632
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
#define ll long long
ll p[3005];
int main()
{
    ll n;
    cin >> n;
    ll sum = 0;
    for (int i = 1; i <= n; i++)
        cin >> p[i], sum += p[i];
    cout << sum - n << endl;

    return 0;
}


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

int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), r = b.size(),ans = r, pc;
    for(int i=0; i<=n-r; i++){
        pc=0;
        for(int k=0,j=i; k<r; k++, j++)
            if(a[j]!=b[k]) pc++;

        ans = min(ans, pc);
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 3600
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.IntSet as IS
import Data.Tuple (swap)
import Data.Function (on)
import Data.List (sortBy)

main :: IO ()
main = do
  n <- unsafeTextToInt <$> T.getLine :: IO Int
  as <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  let
    as' = VU.fromList as :: VU.Vector Int
    f :: Tree Int -> V.Vector Int
    f = (V.replicate n 0 V.//) . flatten . pure . f' (0, IS.empty)
      where
        f' :: (Int, IS.IntSet) -> Tree Int -> Tree (Int, Int)
        f' (l, s) (Node i ts) = Node (i, l') (map (f' (l', s')) ts)
          where
            x = as' VU.! i :: Int
            (l', s') = fmap (IS.insert x) . maybe (succ l, s) ((,) l . flip IS.delete s) $ IS.lookupGE x s
  uvs <- sequence . replicate (pred n) $ unsafeListToPair . map (pred . unsafeTextToInt) . T.words <$> T.getLine :: IO [(Int, Int)]
  let
    tree = makeTree n uvs :: Tree Int
  V.mapM_ print . f $ tree

data Tree a = Node a [Tree a]

makeTree :: Int -> [(Int, Int)] -> Tree Int
makeTree n uvs = Node 0 . map (makeTree' 0) $ t V.! 0
  where
    t = V.accum (flip (:)) (V.replicate n []) . ((++) <$> id <*> map swap) $ uvs :: V.Vector [Int]
    makeTree' :: Int -> Int -> Tree Int
    makeTree' i j = Node j (map (makeTree' j) (filter (/= i) $ t V.! j))

flatten :: [Tree a] -> [a]
flatten (Node x ts : tss) = x : flatten (ts ++ tss)
flatten _                 = []

unsafeListToPair :: [Int] -> (Int, Int)
unsafeListToPair [x, y] = (x, y)

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 142280
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Main m = new Main();
		m.run();
	}

	Scanner sc = new Scanner(System.in);

	void run() {

		for(;;){
			
			
			int w = sc.nextInt();
			int h = sc.nextInt();
			
			if(w == 0 && h == 0){
				break;
			}
			
			int map[][] = new int[h+2][w+2];
			
			
			for(int i =0 ; i < h ;i++){
				for(int j= 0; j< w;j++){
					map[i+1][j+1] = sc.nextInt();
				}
			}
			
			int count = 0;
			
			for(int i = 1;i < h+1; i++){
				for(int j = 1 ;j  < w+1; j++){
					if(map[i][j] == 1){
						count++;
						label(map,i,j,count);
					}
				}
			}
			
			System.out.println(count);
		}
		
	}
	
//	int dx[] = {1,-1,0,0};
//	int dy[] = {0,0,1,-1};
	int dx[] = {1,-1,0,0,1,1,-1,-1};
	int dy[] = {0,0,1,-1,1,-1,1,-1};
	void label(int[][] map,int i,int j,int count){
//		System.out.println(i+" "+j);
		if(map[i][j] <= 0){
			return;
		}
		
		map[i][j] = -count;
		for(int k =0;k < dx.length; k++){
			label(map,i+dx[k],j+dy[k],count);
		}
		
	}
}



Measured memory_bytes: 44956
n = int(input())
s = [input() for i in range(n)]

a = 0
b = 0
c = 0
d = 0

for i in range(n):
    if s[i] == "AC":
        a += 1
    if s[i] == "WA":
        b += 1
    if s[i] == "TLE":
        c += 1
    if s[i] == "RE":
        d += 1

print("AC x", a)
print("WA x", b)
print("TLE x", c)
print("RE x", d)

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

bool x[5000000];

int main(){
	memset(x,false,sizeof(x));
	int n,q,y[20],z[5000],power[21],a[20],sum;
	power[0]=1;
	for(int i=1;i<=20;i++){
		power[i]=power[i-1]*2;
	}
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>y[i];
	}
	for(int i=0;i<power[n];i++){
		sum=0;
		for(int j=0;j<n;j++){
			a[j]=(i/power[j])%2;
			if(a[j]==1){
				sum += y[j];
			}
		}
		x[sum]=true;
	}
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>z[i];
		if(x[z[i]]==true){
			cout<<"yes"<<endl;
		}
		else{
			cout<<"no"<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 6052
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 100005;

#define int long long

typedef long long LL;

int n, m;
LL k;
int x[maxn];
int cf[maxn];
int one[maxn];
int ans[maxn];
int tmp[maxn];

inline void zh()
{
	for(int i = 1; i < n; ++i)
		tmp[i] = one[one[i]];
	for(int i = 1; i < n; ++i)
		one[i] = tmp[i];
}

inline void zh2()
{
	for(int i = 1; i < n; ++i)
		tmp[i] = ans[one[i]];
	for(int i = 1; i < n; ++i)
		ans[i] = tmp[i];
}

inline void pow(LL k)
{
	for(int i = 1; i < n; ++i)
		ans[i] = i;
	for(; k; zh(), k >>= 1)
		if(k & 1)
			zh2();
}

inline void getone()
{
	scanf("%lld", &n);
	for(int i = 1; i <= n; ++i)
	{
		scanf("%lld", &x[i]);
		one[i] = i;
	}
	scanf("%lld%lld", &m, &k);
	for(int i = 1, a; i <= m; ++i)
	{
		scanf("%lld", &a);
		swap(one[a - 1], one[a]);
	}
	pow(k);
	for(int i = 1; i < n; ++i)
		cf[i] = x[i + 1] - x[i];
//	for(int i = 1; i < n; ++i)
//		printf("%lld ", cf[i]);
//	puts("");
	for(int i = 1; i < n; ++i)
		tmp[i] = cf[ans[i]];
//	for(int i = 1; i < n; ++i)
//		printf("%lld ", tmp[i]);
//	puts("");
	printf("%lld.0\n", x[1]);
	for(int i = 2; i <= n; ++i)
	{
		x[i] = x[i - 1] + tmp[i - 1];
		printf("%lld.0\n", x[i]);
	}
}

signed main()
{
//	freopen("a.in", "r", stdin);
//	freopen("a.out", "w", stdout);
	getone();
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

Measured memory_bytes: 5248
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vp;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin() , v.end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }
const ll INF=99999999999999;
const ll MOD=1000000007;
 
int main() {
  ll n;
  cin >> n;
  set<ll> s;
  rep(i,n){
    ll x;
    cin >> x;
    s.insert(x);
  }
  cout << s.size();
    
 return 0;
}


Measured memory_bytes: 256
import itertools

X = int(input())

limit = 10 ** 13
check = [0]
now = 1
add = 1
while add < limit:
    add = now ** 5
    minus_add = add * -1
    check.append(add)
    check.append(minus_add)
    now += 1
new_array = sorted(check)
len_new_array = len(new_array)
check_combi = list(itertools.combinations(range(len(new_array)), 2))
for x in check_combi:
    # print(x[0], x[1])
    if new_array[x[0]] - new_array[x[1]] == X:
        print(x[0] - (len_new_array - 1) // 2, x[1] - (len_new_array - 1) // 2)
        break
    if new_array[x[1]] - new_array[x[0]] == X:
        print(x[1] - (len_new_array - 1) // 2, x[0] - (len_new_array - 1) // 2)
        break


Measured memory_bytes: 90264
N=int(input())



from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


from collections import defaultdict
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

count=1
D=defaultdict(int)
for i in range(1,N+1):
    f=factorization(i)
    for t in f:
        num,con=t
        D[num]+=con
threes=0
fives=0
num_15=0
num_25=0
num_75=0

for v in D.values():
    if v>=2:
        threes+=1
    if v>=4:
        fives+=1
    if v>=14:
        num_15+=1
    if v>=24:
        num_25+=1
    if v>=74:
        num_75+=1
#3*5*5
ans=(threes-fives)*fives*(fives-1)//2
if fives>=3:
    #ans+=cmb(fives, 3)
    ans+=fives*(fives-1)*(fives-2)//2
#75*1

ans+=num_75
#5*15

ans+=num_15*(fives-1)
#3*25
ans+=num_25*(threes-1)
print(ans)
#print(D)
#print(threes, fives, num_15, num_25, num_75)
#print(factorization(32400))

Measured memory_bytes: 3684
z[9999],a,b,c;f(x,y){fflush(!printf("? %d %d\n",x,y));scanf("%s",&b);b=b=='Y';}main(i){if(scanf("%d%d",&a,&b),a<=b){puts("Impossible");return;}for(i=a+=b;~--i;)!c||f(i,z[c-1])?(z[c++]=i):c--;for(c=*z,i=a;~--i;)z[i]=f(c,i);for(printf("! "),i=0;i<a;)printf("%d",z[i++]);}

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

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

	int x=0;
	for(int i=a; i<=b; i++){
		
		if(c%i == 0){
			x++;
		}
	}
	cout << x << endl;
	return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <cassert>
#include <random>

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

using namespace std;
typedef long long int ll;
const int INF = 1000000000;
const double PI = acos(-1);
const ll mod = 1000000007;

int main()
{
    ll x, k, d;
    cin >> x >> k >> d;

    if (k <= abs(x) / d) {
        cout << abs(x) - k * d << endl;
        return 0;
    }

    k -= abs(x) / d;
    if (k % 2 == 0) {
        cout << abs(x) % d << endl;
    }
    else {
        cout << d - (abs(x) % d) << endl;
    }
    return 0;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	int a,b,c; cin>>a>>b>>c;
	if(a+b>=c) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
	return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <cstdlib>
#include <vector>
using namespace std;
int main(){
  int t;
  
  scanf("%d",&t);
  
  int arr[t];
  for(int i=0;i<t;i++){
    scanf("%d",&arr[i]);
  }
  int dp[t];
  for(int i=0;i<t;i++){
  	dp[i]=10e4;
  }
  dp[0]=0;
  dp[1]=abs(arr[1]-arr[0]);
//  cout<<dp[0]<<endl;
//  cout<<dp[1]<<endl;
  for (int i=2;i<t;i++){
  	
    dp[i]=min(abs(arr[i]-arr[i-1])+dp[i-1],abs(arr[i]-arr[i-2])+dp[i-2]);
//    cout<<dp[i]<<endl;
  }
  cout<<dp[t-1];
  	
}

Measured memory_bytes: 4472
#include<bits/stdc++.h>
// Begin Header {{{
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i,n) for(ll i=0; i<n; i++)
#define loop(i, j, n) for(ll i=j; i<n; i++)
#define all(x) (x).begin(), (x).end()
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
const long double PI = acos(-1);
// }}} End Header
bool judge(ll t){
	ll k=1;
	while(k*k<=t){
		if(k*k == t) return true;
		k++;
	}
	return false;
}

int main() {
	ll n;
	cin >> n;
	while(n>0){
		if(judge(n)){
			cout << n << endl;
			return 0;
		}
		n--;
	}
	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;
typedef struct _data {
	int x;
	int y;
} data;

int  main()
{
	int n,m;
	cin >> n >> m;
	vector<int> city(n);
	int a,b;
	rep(i, m)
	{
		cin >> a >> b;
		city.at(a-1)++;
		city.at(b-1)++;
	}
	rep(i, n)
		cout << city.at(i) << endl;
	return (0);
}


Measured memory_bytes: 256
n = int(input())
  
def fibonacci(n):
  if n <= 1:
    dp[n] = 1
    return 1
  if dp[n] != -1:
    return dp[n]
  else:
    dp[n] = fibonacci(n-1)+fibonacci(n-2)
    return dp[n]
dp = [-1]*(n+1)
fibonacci(n)
print(dp[-1])


Measured memory_bytes: 5600
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            new Program().Solve(new MyInputStream(Console.In, ' '));
            Console.Out.Flush();
        }

        public void Solve(MyInputStream cin)
        {
            var N = cin.ReadInt();
            var M = cin.ReadInt();
            var cnt = new int[N];
            Enumerable.Range(0, M).ToList().ForEach(i => {
                cnt[cin.ReadInt() - 1]++;
                cnt[cin.ReadInt() - 1]++;
            });
            cnt.ToList().ForEach(WriteLine);
        }
    }

    public class MyInputStream
    {
        private readonly System.IO.TextReader _stream;
        private char separator = ' ';
        private Queue<string> inputStream;
        public MyInputStream(System.IO.TextReader s, char separator = ' ')
        {
            this.separator = separator;
            this._stream = s;
            inputStream = new Queue<string>();
        }
        public string Read()
        {
            if (inputStream.Count != 0) return inputStream.Dequeue();
            string[] tmp = _stream.ReadLine().Split(separator);
            for (int i = 0; i < tmp.Length; ++i)
                inputStream.Enqueue(tmp[i]);
            return inputStream.Dequeue();
        }
        public string ReadLine() { return _stream.ReadLine(); }
        public int ReadInt() { return int.Parse(Read()); }
        public long ReadLong() { return long.Parse(Read()); }
        public double ReadDouble() { return double.Parse(Read()); }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read(); return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt(); return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong(); return ret;}
    }
}

Measured memory_bytes: 13396
#include <iostream>

#define ll long long
#define MOD 1000000007
#define REP(i,n) for(int i = 0; i < n; i++)

using namespace std;

//Step0: 繰り返し二乗法
ll iterative_pow(ll n, ll p, ll mod){
    ll ans = 1;

    while(p > 0){
        if((p & 1) == 1){
            ans = ans * n % mod;
        }
        n = n * n % mod;
        p >>= 1;
    }

    return ans;
}

//nCr mod "mod"を計算
ll nCr(ll n, ll r, ll mod){
    //Step1: 分子xと分母yを用意
    ll x = 1, y = 1;

    //Step2: 分子の計算　n(n-1)(n-2)...(n-r+1)を実装
    REP(i,r){
        x = x * (n - i) % mod;
    }

    //Step3: 分母の計算　a^-1 = a^(p-2) mod pを利用
    for(int i = 1; i <= r; i++){
        y = y * iterative_pow(i, mod-2, mod) % mod;
    }

    //Step4: Step2とStep3より，x*yを返せば良い
    return x * y % mod;
}

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

    ll ans = iterative_pow(2, n, MOD) - 1 % MOD;
    ll min = nCr(n, a, MOD) + nCr(n, b, MOD) % MOD;
  
    cout << (((ans - min) % MOD) + MOD) % MOD;
    
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
# 整数の入力

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

N, M = map(int, input().split())
war = []
for i in range(M):
    war.append(get_list())
war.sort()

cnt = 1
west, east = war[0]
# スペース区切りの整数の入力
for i in range(1, len(war)):
    west_chk, east_chk = war[i]
    if west_chk < east and east <= east_chk:
        pass
    elif east <= west_chk:
        cnt += 1
        east = east_chk
    elif east_chk < east:
        east = east_chk
        
print(cnt)




Measured memory_bytes: 27876
#include"bits/stdc++.h"
#define int long long
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define itr(i,x) for(auto i=(x).begin();i!=(x).end();++i)
#define All(x) (x).begin(),(x).end()
#define gridif(a,x,b) if((a)<=(x)&&(x)<(b))

using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
const int mod=1000000007;

int digitsum(int n,int b){
	if(b<2) return -1;
	if(n<b) return n;
	return digitsum(n/b,b)+n%b;
}
int mpow(int a,int x);
int m_inv(int n);
vector<int> split(int n,int a);
string xal_number(int n,int x);
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int lcm(int x,int y){return x*y/gcd(x,y);}
class Factorial{
private:
	vector<int> fac;
public:
	Factorial(int N){
		fac.push_back(1);
		rep(i,N) fac.push_back(fac[i]*(i+1)%mod);
	}
	int fact(int a){return fac[a];}
	int ifac(int a){return m_inv(fac[a]);}
	int cmb(int n,int r);
};
struct UnionFind {
    vector<int> par; // 親ノード
    UnionFind(int n = 1) { init(n);}
    void init(int n = 1) {
        par.resize(n);
        rep(i,n) par[i] = -1;
    }
    int root(int x) {
        if (par[x] <0) return x;
        else return par[x] = root(par[x]);      
    }
    int size(int x){ return -par[root(x)];}
    bool issame(int x, int y) {return root(x)==root(y);}
    bool connect(int x, int y);
};

signed main(){
	int N,K;
	cin>>N>>K;
	vector<int> a(N);
	rep(i,N) cin>>a[i];
	sort(All(a));
	int inf=1<<20;
	
	//dp[i][j]=i番目のカードまでで総和をjにできるか
	int l=-1,r=N;
	while(l<r-1){//不必要なカードの最後尾を探す
		Graph dp(N+1,vector<int>(K,0));
		dp[0][0]=1;
		int out=(l+r)/2;
		if(a[out]>=K){//必要ならば右を寄せる
			r=out;
			continue;
		}
		rep(i,N) rep(j,K){
			if(j-a[i]>=0)dp[i+1][j]=max(dp[i][j-a[i]],dp[i][j]);
			dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
			if(i==out) dp[i+1][j]=dp[i][j];
		}
		rep(i,a[out]) if(dp[N][K-a[out]+i]==1) r=out;
		if(r!=out) l=out;
		
	}
	cout<<r<<endl;
}

Measured memory_bytes: 195928
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,r) RFOR(i,0,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define lower(a,x) lower_bound(all(a), x) - a.begin();
#define COUNT(a,x)  upper_bound(all(a), x) - lower_bound(all(a), x);
#define MCOUNT(a,x,y) upper_bound(all(a), y) - lower_bound(all(a), x);
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end());
#define scan(x) scanf("%lld",&x);
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
typedef set<ll> SET;
typedef double D;
const ll inf = 5555555555555555555;
const ll mod = 1000000007;
const D pi = acos(-1);
const D eps = 1e-10;

ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, tmp = 0, ma = 0, mi = 0;
string s;
bool ok, flag;
ll dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
ll ddx[9] = { 1,-1,0,0,1,1,-1,-1,0 }, ddy[9] = { 0,0,1,-1,1,-1,1,-1,0 };
#pragma endregion
#define MAX 111111

bool red[MAX];
ll ball[MAX];
int main(void) {
  ll x, y;
  cin >> n >> m;
  rep(i, n) {
	red[i] = false;
	ball[i] = 1;
  }
  red[0] = true;

  rep(i, m) {
	scan(x) scan(y);
	x--; y--;
	if (red[x]) red[y] = true;
	ball[y]++;
	ball[x]--;
	if (!ball[x]) red[x] = false;
  }

  rep(i, n) if (red[i]) ans++;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1152
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long L;

long long a[334514];
int main(){
	int n;
	cin >> n;
	for (int i = 0; i < n*3; i++)cin >> a[i];
	sort(a, a + n+n+n);
	L ans = 0;

	for (int i = n; i<3*n;i+=2)ans += a[i];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
inline ll read(){
	ll res=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+ch-'0';ch=getchar();}
	return res*f;
}
void write(ll x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10|'0');
}
int h,w,a,b;
signed main(){
	h=read(),w=read(),a=read(),b=read();
	for(int i=1;i<=b;i++){
		for(int j=1;j<=w;j++) if(j<=a) cout<<"1";else cout<<"0";
		cout<<endl;
	}
	for(int i=1+b;i<=h;i++){
		for(int j=1;j<=w;j++) if(j<=a) cout<<"0";else cout<<"1";
		cout<<endl;
	}
	return 0;
}


Measured memory_bytes: 1280