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


#define ll long long int
#define ld long double
#define mod 1000000007
#define big 1e18+10
#define small -big
#define pb push_back



template <typename T>

void prarr(T a)
{
     cerr << "[ ";
     
     for(auto i : a){
         cerr << i << " ";
     }
     
     cerr << "]" << endl;
}


#define trace(...) _er(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void _er(const char* name, Arg1&& arg1){
	cerr << "[" << name << " : " << arg1 << "]" << endl;
}

template <typename Arg1, typename... Args>

void _er(const char* names, Arg1&& arg1, Args&&... args){
    
	const char* comma = strchr(names + 1, ',');
	cerr << "[" ; cerr.write(names, comma - names) << " : " << arg1 << "] ";
	_er(comma+2, args...);
}






void solve() {
    
    ll n, x, t;
    cin >> n >> x >> t;
    
    ll a = (n + (x - 1)) / x;
    
    cout << (a * t ) << endl;
}


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

    int t=1;
    //cin >> t;

    for(int i = 1; i <= t; i++) {  
   
         solve();
    }


    return 0;
        
}


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

const int N = 1e5 + 5;
int n, a, b, c, dp[N][3];
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a >> b >> c;
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a;
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b;
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + c;
    }
    cout << max(dp[n][0], max(dp[n][1], dp[n][2]));
}

Measured memory_bytes: 1408
#define _GLIBCXX_DEBUG
#include "bits/stdc++.h"
using namespace std;
using Graph = vector<vector<int>>;

typedef long long ll;
typedef long double ld;


#define int long long
#define rep(i, n) for(long long i = 0; i < (n); i++)
#define sqrt(d) pow((long double) (d), 0.50)

const ll INF = 2e9;
const ll large_P = 1e9 + 7;





signed main() {
    string S; cin >> S;
    int N = S.size();

    int res = 0;
    rep(i, N / 2) {
        if (S.at(i) != S.at(N - 1 - i)) res++;
    }

    cout << res << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define Ms(a,b) memset(a,b,sizeof a)
#define db(x) cout<<#x<<"="<<x<<endl;
#define db2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl;
#define db3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl;
using namespace std;
int n;
int main() {
	scanf("%d",&n);
	printf("%lld\n",1ll*(1+n-1)*(n-1)/2);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    int n = 0;
    char m;
    for (int i = 0; i < 4; ++i) {
        cin >> m;
        if (m == '-') {
            --n;
        } else if (m == '+') {
            ++n;
        }
    }
    cout << n << endl;
    return 0;
}

Measured memory_bytes: 256
s = gets.chomp.chars
letters = s.uniq.sort
ans = 100
letters.each do |x|
  str = s.dup
  cnt = 0
  while str.uniq.size > 1
    (0..str.size - 2).each do |i|
      str[i] = x if str[i + 1] == x
    end
    str.pop
    cnt += 1
  end

  ans = cnt if ans > cnt
end
puts ans


Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define N 3005
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
int n,q,a[N],x,y;
int now = 1,las = 0;
ll f[N][N],inv2;
ll qp(ll a,ll b) { ll ret = 1; for(;b;b>>=1,a = a * a % mod) if(b & 1) ret = ret * a % mod; return ret; }


int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i) scanf("%d",a + i);
	inv2 = qp(2,mod - 2);
	ll qpn = qp(2,q);
	for(int i=1;i<=n;++i)
	  for(int j=1;j<=n;++j)
	    if(a[i] > a[j]) f[i][j] = 1;
	while(q--)
	{
		scanf("%d%d",&x,&y);
		swap(now,las);
		for(int i=1;i<=n;++i) 
		{
			if(i == x || i == y) continue;
			f[i][x] = f[i][y] = (f[i][x] + f[i][y]) % mod * inv2 % mod;
			f[x][i] = f[y][i] = (f[x][i] + f[y][i]) % mod * inv2 % mod;
		}
		f[y][x] = f[x][y] = (f[x][y] + f[y][x]) % mod * inv2 % mod;
	}
	ll ans = 0;
	for(int i=1;i<=n;++i)
	  for(int j=i + 1;j<=n;++j)
	     ans = (ans + f[i][j] * qpn % mod) % mod;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 70784
#include<stdio.h>
int main() {
  int n,a,i;
  scanf("%d",&n);
  for (i=0;i<n;i++) {
    scanf("%d",&a);
    if (a%2==0 && a%3!=0 && a%5!=0) {
      printf("DENIED\n");
      return 0;
    }
  }
  printf("APPROVED\n");
}

Measured memory_bytes: 128
#include <stdio.h>

int main(void)
{
	int weight;
	int g[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
	int gu[10] = {0};
	int i;
	int w;
	
	while (scanf("%d", &weight) != EOF){
		w = weight;
		for (i = 0; i < 10; i++){
			gu[i] = 0;
		}
		for (i = 9; i >= 0; i--){
			if (g[i] <= w){
				gu[i] = 1;
				w -= g[i];
			}
		}
		for (i = 0; i < 10; i++){
			if (gu[i] == 1){
				printf("%d", g[i]);
				weight -= g[i];
				if (weight > 0){
					printf(" ");
				}
			}
		}
		printf("\n");
	}
	
	return (0);
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ll n,x,c=0,f=0;
    cin>>n;
    vector<ll>v;
    for(ll i=1; i<=n; i++)
    {
        cin>>x;
        v.push_back(x);
    }
    for(ll i=0; i<n; i++)
    {
        if(v[i]==1)
        {
            f=1;
            break;
        }
    }
    x=1;
    if(f==1)
    {
        for(ll i=0; i<n; i++)
        {
            if(v[i]!=x)
            {
                c++;
            }
            else if(v[i]==x)
            {
                x++;
            }
        }
        cout<<c<<endl;
    }
    else cout<<-1<<endl;
    return 0;
}


Measured memory_bytes: 2548
def calc(n, arr):
    min = arr[0]
    max = arr[0]
    sum = arr[0]
    for i in range(n - 1):
        target = arr[i + 1]
        if target < min:
            min = target
        if target > max:
            max = target
        sum += target

    return '{} {} {}'.format(min, max, sum)


if __name__ == "__main__":
    n = input()
    arr = list(map(int, input().split()))
    print(calc(int(n), arr))



Measured memory_bytes: 6556
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Dish {
  long a, b, s;
  Dish(long a,long b,long s) : a(a), b(b), s(s) {}
  bool operator<(const Dish &d) const { return s < d.s; }
};

int n, a, b;
vector<Dish> dish;

int main() {
  cin.tie(0); ios_base::sync_with_stdio(false);
  cin >> n;
  for(int i = 0; i < n; ++i) {
    cin >> a >> b;
    dish.emplace_back(a, b, a + b);
  }
  sort(dish.rbegin(), dish.rend());

  long ans = 0;
  for(int i = 0; i < n; ++i) {
    if(i&1) ans -= dish[i].b;
    else ans += dish[i].a;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4724
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = lambda: sys.stdin.readline().rstrip()

N, K = map(int, input().split())
a = list(map(int, input().split()))

#dp[i][j]は残りi個でjが勝つかどうか（j=0 or 1）
dp = [[-1, -1] for _ in range(K+1)]
dp[0] = [0, 0]

for i in range(1, K+1):
    for j in range(2):
        if dp[i][j] > -1:
            continue

        flag = 1
        for x in a:
            if i >= x:
                flag *= dp[i-x][1-j]
        if flag == 0:
            dp[i][j] = 1
        else:
            dp[i][j] = 0
            
print("First" if dp[K][0] else "Second")

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

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

using namespace std;

int main(int argc, char* argv[]){
  string S;
  cin >> S;

  if(S == "ABC"){
    cout << "ARC" << endl;
  } else {
    cout << "ABC" << endl;
  }

  return 0;
}


Measured memory_bytes: 3604
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>
#include <utility>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
#define lol long long
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) setprecision(x+1)
#define abs(x,y) (max(x,y)-min(x,y))
#define SUM(n) ((n)+1)*(n)/2
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = (1e9)+7;
#define all(v) v.begin(),v.end()
using namespace std;
using pii = pair<int,int>;
typedef vector<int> vit;

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

  lol n, k, sum = 0;
  cin >> n >> k;
  while(n != 0){
    n/=k;
    sum ++;
  }
  cout << sum << '\n';
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

string s;

int main(){
	cin>>s;
	if(s[0]=='Y'&&s[1]=='A'&&s[2]=='K'&&s[3]=='I') cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
A = int(raw_input())
B = int(raw_input())
C = int(raw_input())
X = int(raw_input())

ans = 0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            if 500*a+100*b+50*c == X:
                ans += 1 
print ans

Measured memory_bytes: 2568
x1, y1, x2, y2 = map(int, input().split())
vec = [x2 - x1, y2 - y1]

x3, y3 = -vec[1] + x2, vec[0] + y2

x4, y4 = -vec[1] + x1, vec[0] + y1

print(int(x3), int(y3), int(x4), int(y4))


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INFLL (1LL<<62) // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    Init();
    ll n;
    cin >> n;

    // 例外処理
    if(n == 1){
        Yes();
        cout << 2 << endl;
        cout << "1 1" << endl;
        cout << "1 1" << endl;
        return 0;
    }

    // 任意の2つの部分集合の共通部分が1であり、また各要素は2回しか使われないため、
    // 集合のサイズは(k-1)となる。よって、k*(k-1)/2 = nが成立する。
    // 上記が成り立たなければ解は存在しない。
    ll l=0, r=n+1;
    while(r-l > 1){
        ll mid = (r+l)/2;
        if(mid*(mid-1)/2 > n) r = mid;
        else l = mid;
    }
    if(l*(l-1)/2 != n) No();
    else{
        Yes();
        cout << l << endl;
        vvi tri(l, vi(0));
        ll col = 1;
        for(ll i=1; i<=n; i++){
            if(tri[col].size() == col) col++;
            tri[col].push_back(i);
        }

        // 末尾列を出力
        cout << l-1 << " ";
        for(ll i=1; i<=l-1; i++){
            cout << *tri[i].rbegin() << (i == l-1 ? endl : " ");
        }

        // 他のを出力
        for(ll i=1; i<l; i++){
            cout << l-1 << " ";
            ll j = 0, cnt = 0;
            for(; j<tri[i].size(); j++){
                cnt++;
                cout << tri[i][j] << (cnt == l-1 ? endl : " ");
            }
            if(cnt == l-1) continue;
            j--;
            for(col = i+1; col<=l-1; col++){
                cnt++;
                cout << tri[col][j] << (cnt == l-1 ? endl : " ");
            }
        }
    }
}

Measured memory_bytes: 4296
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={0, 1, 0, -1};
int dy[]={-1, 0, 1, 0};


int n,h[405][405],num[405][405];
int ss[][7] = {
	{ 0,0,0,0,0,0,0, },
	{ 0,0,3,5,2,4,0, },
	{ 0,4,0,1,6,0,3, },
	{ 0,2,6,0,0,1,5, },
	{ 0,5,1,0,0,6,2, },
	{ 0,3,0,6,1,0,4, },
	{ 0,0,4,2,5,3,0, },
};

int main(){
	while(true){
		cin >> n;
    	if(n == 0)break;
    	for(int i = 0;i < 400;i++){
      		for(int j = 0;j < 400;j++){
        		h[i][j] = 0;
        		num[i][j] = -1;
      		}
    	}
		for(int ii = 0;ii < n;ii++){
			int t,f;
			cin >> t >> f;
			int s = ss[t][f];
			int side[] = {f,s,7-f,7-s};
			int nmax = -1,rot = -1;
			int x = 200,y = 200;
			bool flag = false;
			for(int k = 0;k < 4;k++){
				if(side[k] >= 4 && side[k] > nmax && h[x][y] > h[x+dx[k]][y+dy[k]]){
					rot = k;
					nmax = side[k];
					flag = true;
				}
			}
			while(flag == true){
				flag = false;
				x = x + dx[rot]; y = y + dy[rot];
				if(rot == 0){
					int f_tmp = f;
					f = t;
					t = 7 - f_tmp;
				}else if(rot == 1){
					int s_tmp = s;
					s = t;
					t = 7 - s_tmp;
				}else if(rot == 2){
					int t_tmp = t;
					t = f;
					f = 7 - t_tmp;
				}else{
					int t_tmp = t;
					t = s;
					s = 7 - t_tmp;
				}
				nmax = -1; 
				rot = -1;
				side[0] = f; side[1] = s; side[2] = 7-f; side[3] = 7-s;
				for(int k = 0;k < 4;k++){
					if(side[k] >= 4 && side[k] > nmax && h[x][y] > h[x+dx[k]][y+dy[k]]){
						rot = k;
						nmax = side[k];
						flag = true;
					}
				}
			}
			h[x][y]++;
			num[x][y] = t;
		}
		int ans[7];
		for(int i = 1;i <= 6;i++) ans[i] = 0;
		for(int i = 0;i < 400;i++){
			for(int j = 0;j < 400;j++){
				if(num[i][j] >= 1) ans[num[i][j]]++;

			}
		}
		cout << ans[1];
		for(int i = 2;i <= 6;i++){
			cout << " " << ans[i];
		}
		cout << endl;
  	}
}


Measured memory_bytes: 4356
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <utility>
#include <map>
#include <climits>
#include <vector>
#include <set>
#include <string>
#include <numeric>

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define flood(arr, c, s) for (int i=0; i<s; i++) arr[i] = c
//#define int long long
using namespace std;

signed main() {
    FAST_IO;
    string s, g;
    cin >> s >> g;
    bool flag=true;
    for (int i=0; i<s.length(); i++) {
        if (s[i] != g[i]) {
            cout << "No";
            exit(0);
        }
    }
    if (g.length()>s.length()) cout << "Yes";
    return 0;
}

Measured memory_bytes: 3128
#include <stdio.h>

int main()
{
    int n, x, a = 0;
    int i, j, k;
    
    while (1) {
        scanf("%d %d", &n, &x);
        if(n == 0 && x == 0)    break;
        
        for (i = 1; i <= n - 2; i++)
        {
            for (j = i + 1; j <= n - 1; j++)
            {
                for (k = j + 1; k <= n; k++)
                {
                    if ((i + j + k) == x && i != j && j != k && k != i)
                    {
                        a++;
                    }
                }
            }
        }
        
        printf("%d\n", a);
        a = 0;
    }
    
    return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define mod 1000000007
#define pii pair<int,int>
#define pll pair<long long,long long>
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007 //998244353
#define ll long long
#define lli long long int
#define vi vector<int>
#define vll vector<long long>
#define vp vector<pair<long long,long long>>
#define vpp vector<pair<pair<long long,long long>,long long>>
#define mp make_pair
typedef std::numeric_limits< double > dbl;
using namespace std;

int main()
{
	IOS;
	string s;
	cin>>s;
	cout<<s;
	if(s[s.size()-1]=='s')
	cout<<"es";
	else
	cout<<"s";
}

Measured memory_bytes: 3656
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

using static Input;
class Program
{
    static string S;
    
    static void INPUT()
    {
        S = NextString();
    }
    static void OUTPUT()
    {
        char prev = ' ';
        var d = false;
        var ans = 0;
        foreach (var c in S)
        {
            if (prev == c && !d)
            {
                prev = ' ';
                d = true;
                continue;
            }

            ans++;
            prev = d ? ' ' : c;
            d = false;
        }

        Console.WriteLine(ans);
    }
    static void Main(string[] args)
    {
#if DEBUG  
        TESTINPUT();
#else
        INPUT();
#endif
        OUTPUT();
    }

    static void TESTINPUT()
    {
        S = "aabbaa";
        S = "aaaccacabaababc";
        S = "aaaaa";
    }
}

public class Input
{
    public const long MOD = 1000000007;
    public const int INF = 1000000007;
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}



Measured memory_bytes: 13268
//daddy's back in town, back to rolling the damn hash yoooo babeeeeees//
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define vi vector <int>
#define L nod<<1
#define R ((nod<<1)|1)
#define int ll
const ll mod = 1000000007;
int n, a[10010], cnt[1000010], ans=1;

int pw(int x, int y){
	if(y==0) return 1;
	int xd=pw(x, y/2);
	return ((xd*xd)%mod)*(y%2 ? x : 1)%mod;
}

int inv(int xd){
	xd%=mod;
	return pw(xd, mod-2);
}

int32_t main(){
	ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	cin>>n;
	for(int i=1, x; i<=n; i++){
		cin>>x;
		a[i]=x;
		for(int p=2; p*p<=x; p++){
			int cur=0;
			while(x%p==0){
				x/=p;
				cur++;
			}
			cnt[p]=max(cur, cnt[p]);
		}
		if(x>1) cnt[x]=max(1LL, cnt[x]);
	}
	for(int i=2; i<=1000000; i++){
		ans*=pw(i, cnt[i]);
		ans%=mod;
	}
	int cur=0;
	for(int i=1; i<=n; i++){
		cur+=inv(a[i]);
		cur%=mod;
	}
	cout<<ans*cur%mod;
}

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

int main(){
    int n,a[200001];
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        a[i]-=i;
    }
    sort(a+1,a+n+1);
    int b=a[(n+1)/2];
    long long ans=0;
    for(int i=1;i<=n;++i){
        ans+=abs(a[i]-b);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1024
x,k,d=map(int, input().split())
x=abs(x)
if x/k >= d:
  print(x-d*k)
elif (k-int(x/d))%2==0:
  print(abs(x-int(x/d)*d))
else:
  print(abs(x-int(x/d)*d-d))


Measured memory_bytes: 9172
import sys
import math

from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())
def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]
def exit():
    import sys
    sys.exit(0)
def perm_sub(li, used):
    if len(li) == len(used):
        return [deque()]
    k = []
    for i in range(len(li)):
        if i in used:
            continue
        used.add(i)
        sub_list = perm_sub(li, used)
        for sub in sub_list:
            sub.appendleft(li[i])
        k.extend(sub_list)
        used.discard(i)
    return k
def perm_li(li):
    return perm_sub(li, set())
def perm_n(n):
    return perm_sub(list(range(n)), set())
def join_i(li, sep=""):
    return sep.join([str(e) for e in li])
def li2n(li):
    n, base = 0, 1
    for i in range(len(li)-1, -1, -1):
        n += li[i] * base
        base *= 10
    return n
def sli2ili(li):
    return [int(s) for s in li] 
def prime_list(n):
    li = [i for i in range(2, n+1)]
    for i in range(len(li)):
        if li[i] >= int(math.sqrt(n)):
            break
        if li[i] == -1:
            continue
        for j in range(i+1, len(li)):
            if li[j] % li[i] == 0:
                li[j] = -1
    return [n for n in li if n != -1]
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while True:
        r = a % b
        if r == 0: return b
        a, b = b, r
def lcm(a, b):
    return int(a * b / gcd(a,b))
def all_subset(li):
    s = []
    n = len(li)
    for bit in range(0, (1<<(n+1))):
        ss = set()
        for i in range(0, n):
            if (bit & (1 << i)):
                ss.add(li[i])
        s.append(ss)
    return s
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)
def mCn(m, n):
    def factorial_ntimes(m, n):
        r = 1
        while n:
            r *= m
            m -= 1
            n -= 1
        return r
    return int(factorial_ntimes(m, n) / factorial(n))

n,m = load_list()
lr = []

lmax = 0
rmin = 10**6
for _ in range(m):
    l, r = load_list()
    lmax = max(lmax, l)
    rmin = min(rmin, r)

print(len(range(lmax, rmin+1)))
    
    


Measured memory_bytes: 46040
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void){
    // Your code here!
    int a = 0;
    char s[11];
    scanf("%s",s);
    for(int i = 0; i < strlen(s); i++)
    {
        a += s[i]-48;
    }
    printf("%s\n",(atol(s)%a == 0)? "Yes":"No");
}


Measured memory_bytes: 128
n,S,r=int(input()),input(),0
dp1=[0]*n
dp2=[0]*n
d1=set()
d2=set()
cs=[0]*10
for i in range(n):
    dp1[i] = len(d1)
    d1.add(S[i])
for i in range(n):
    j = n-i-1
    dp2[j] = len(d2)
    r += dp1[j]*(dp2[j]-dp2[cs[int(S[j])]])
    d2.add(S[j])
    cs[int(S[j])] = j
print(r)


Measured memory_bytes: 3572
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;

#define sp << " " <<
#define mod 1000000007
#define PI 3.14159265358979323
#define y second
#define x first
#define pb push_back
#define mp make_pair
#define mem(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
#define pqueue priority_queue< ll >
//#define pdqueue priority_queue< ll,vector<ll> ,greater< ll > >
#define codejamDebug(x) cout<<"Case #"<<x<<": ";
#define debug(x) cout<<#x<<" :"<<x<<endl;
#define rep(i,n) for(long long i=0;i<n;i++)
#define f(i,a,b) for(long long i = a; i < b; i++)
#define fd(i,a,b) for(long long i = a; i >=b; i--)
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long int           ll;
typedef long double             ld;
typedef unsigned long long int ull;
typedef vector <int>            vi;
typedef vector <ll>            vll;
typedef pair <int, int>        pii;
typedef pair <ll, ll>          pll;
typedef vector < pii >        vpii;
typedef vector < pll >        vpll;
typedef vector <string>         vs;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//Handle:cyber_rajat

int main(int argc, char const *argv[])
{
	sync;
	int n;
	cin >> n;
	int a[n+5];
	rep(i,n){
		cin >> a[i];
	}
	sort(a,a+n);
	ll sum = 0;
	sum += a[n-1];
	ll idx = n-2;
	ll cnt = 2;
	while(cnt < n){
		sum += a[idx];
		cnt++;
		if(cnt >= n){
			break;
		}
		sum += a[idx];
		cnt++;
		if(cnt >= n){
			break;
		}
		idx--;
	}
	cout << sum << endl;
	return 0;
}


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

int main(){
	int a=0,b=0,c;
	for(int i=0;i<8;i++){ scanf("%d",&c); if(i<4) a+=c; else b+=c;}
	printf("%d\n",max(a,b)); 
}

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

int main() {
	vector<int> a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	int k;
	cin >> k;
	
	cout << a[k-1] << endl;
	return 0;
}

Measured memory_bytes: 256
import fractions
from functools import reduce

n = int(input())
lst = [0 for _ in range(n)]
for i in range(n):
    lst[i] = int(input())

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

print(lcm_list(lst))


Measured memory_bytes: 5076
n = int(raw_input())
nums = map(lambda x: int(x) - 1, raw_input().split())
ans = 0
for i in range(len(nums)):
    if nums[i] == i:
        ans += 1
        if i != len(nums) - 1:
            nums[i], nums[i+1] = nums[i+1], nums[i]
print ans


Measured memory_bytes: 11304
# 配列じゃなくて辞書なり連想配列なりハッシュなりを使いましょう おしまい
n, k = map(int, input().split())
h = {}
for _ in range(n):
    a, b = map(int, input().split())
    if a in h:
        h[a] += b
    else:
        h[a] = b

arr = [x for x in h.items()]
arr = list(sorted(arr, key=lambda x: x[0]))
count = 0

for a in arr:
    if count + a[1] >= k:
        print(a[0])
        exit()
    else:
        count += a[1]


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

int main() {
    int N;
	string S;
	cin >> N >> S;
	int r=0, b=0;
	for(int i=0; i<N; ++i){
	    if(S[i]=='R') ++r;
	    else ++b;
	}
	cout << (r>b ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){
	int a_point,b_point,i,a_card,b_card,n;
	while(0==0){
		scanf("%d",&n);
		if(n==0) break;
		a_point=0;
		b_point=0;
		for(i=0;i<n;i++){
			scanf("%d %d",&a_card,&b_card);
			if(a_card>b_card) a_point+=(a_card+b_card);
			else if(a_card<b_card) b_point+=(a_card+b_card);
			else {
				a_point+=a_card;
				b_point+=b_card;
			}
		}
		printf("%d %d\n",a_point,b_point);
	}
	return 0;
}

Measured memory_bytes: 1028
function check(A,K,N,M)
	dp=[false for _=1:K]
	dp[1]=true
	for i=1:N
		if i==M continue end
		for j=K:-1:A[i]+1
			dp[j]|=dp[j-A[i]]
		end
	end
	flag=false
	for i=max(1,K-A[M]+1):K
		flag|=dp[i]
	end
	flag
end
function main()
	N,K=map(x->parse(Int,x),split(readline()))
	A=sort(map(x->parse(Int,x),split(readline())))
	L=0
	R=N+1
	while R-L>1
		M=div(L+R,2)
		if check(A,K,N,M)
			R=M
		else
			L=M
		end
	end
	println(L)
end
main()


Measured memory_bytes: 117124
N = int(input())
isopen = []
profit = []

for i in range(N) :
    isopen.append(list(input().split()))
    
for i in range(N) :
    profit.append(list(map(int, input().split())))
    
# permutation of available open periods 
perms = []
def perm(s, idx) :
    if idx == 10 :
        if s != "0000000000" :
            perms.append(s)
    else :
        perm(s + "0", idx + 1)
        perm(s + "1", idx + 1)
        
perm("", 0)

def doand(s1, s2) :
    cnt = 0
    for i in range(10) :
        if s1[i] == s2[i] == "1" :
            cnt += 1
            
    return cnt 

max_cost = -10**20

for p in perms :
    cost_over = 0
    # for each branch
    for i in range(N) : 
        # bit AND for current permutation and branch -> fetch count
        numsame = doand(p, "".join(isopen[i]))
        
        # fetch profit based on count for branch 
        cost_over += profit[i][numsame]
    
    max_cost = max(max_cost, cost_over)
    
print(max_cost)

Measured memory_bytes: 3188
A, B, K = map(int, input().split())

if 2 * K >= B - A + 1:
    for i in range(A, B+1):
        print(i)
else:
    for i in range(A, A+K):
        print(i)
    for i in range(B-K+1, B+1):
        print(i)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define Would
#define you
#define please


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

	
	int X, A, B;
	cin >> X >> A >> B;
	
	if (abs(X - A) < abs(X - B)) co("A");
	else co("B");

	Would you please return 0;
}

Measured memory_bytes: 256
function Main(input){
  var inp = input.split('\n');
  var inp1 = [];

// N, l, r を取得
  for(var i = 0; i < inp.length; i++){
    inp1.push(inp[i].split(' ').map((n) => { return parseInt(n)}));
  }

  var N = inp1[0][0];
  var l = [];
  var r = [];
  for(var i = 1; i < inp1.length; i++){
    l.push(inp1[i][0]);
    r.push(inp1[i][1]);
  }

// 
  var f = []; // 素数ならば true を格納する配列
  for(var i = 2; i <= 100000; i++){  
    if(!f[i]){
      for(var j = i + i; j <= 100000; j += i){
        f[j] = true;
      }
    }
  }

  var c = [];
  for(var i = 0; i <= 100001; i++) c[i] = 0; // 配列cを0で埋める

  for(var i = 3; i <= 100000; i += 2){ // 奇数のうち、'2017に似た数を配列cにリスト
    if(!f[i] && !f[(i + 1) / 2]){
      c[i]++;
    }
  }
  for(var i = 3; i <= 100000; i++){  // 配列cの、その添字までの和を上書き
    c[i] += c[i - 1];
  }

//  while(N--){
  for(var i = 0; i < N; i++){
    console.log(c[r[i]] - c[l[i] - 1]);
  }

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

Measured memory_bytes: 68224
#include <iostream>
using namespace std;
 
int main(){
  bool is_prime[51000];
 
  is_prime[0]=is_prime[1]=false;
  for(int i=2;i<51000;i++){
    is_prime[i] = true;
  }
 
  for(int i=2;i*i<51000;i++){
    if(is_prime[i]){
      for(int j=i*i;j<51000;j=j+i){
        is_prime[j] = false;
      }
    }
  }
 
  while(true){
    int n;
    cin >> n;
 
    if(cin.eof())
        break;
 
    int high = n;
    int low = n;
 
    while(1){
      high = high+1;
      if(is_prime[high]){
        break;
      }
    }
 
    while(1){
      low = low-1;
      if(is_prime[low]){
        break;
      }
    }
 
    cout << low << " " << high << endl;
  }
 
  return 0;
}


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

#define rep(i,n) for(int i=0;i<(n);++i)
#define loop(i,b,n) for(int i=b;i<(n);++i)
#define each(e,v) for(auto &&e : v)

#define all(v) (v).begin(),(v).end()
#define sz(v) (int)v.size()

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const double EPS = 1e-9;
const ll MOD = 1e+9 + 7;

template<typename A,typename B> inline void chmin(A &a,B b){ if(a>b) a=b; }
template<typename A,typename B> inline void chmax(A &a,B b){ if(a<b) a=b; }
template <typename T> inline void print(const T& x) { cout << x << endl; }

int main() {
    int n;
    cin >> n;

    vector<int> a(n,0);
    rep(i,n) cin >> a[i];

    int count = 0;
    rep(i,n){
        if(i%2==0 && a[i]%2==1) ++count;
    }
    print(count);

    return 0;
}


Measured memory_bytes: 3588
import java.util.*;
import java.io.*;

public class Main{
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] s = br.readLine().split(" ");
    int a = Integer.parseInt(s[0]);
    int b = Integer.parseInt(s[1]);
    int c = Integer.parseInt(s[2]);
    
    if(b / a > c){
      System.out.println(c);
    }else{
      System.out.println(b / a);
    }
  }
}

Measured memory_bytes: 22612
#include<iostream>
#include<stdio.h>
#include<vector>
#include<stdlib.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<queue>
#include<cmath>
using namespace std;
vector<bool> p(1111111,true);
void furui(){
  for(int i=2;i<=1111;i++){
    if(!p[i])continue;
    for(int j=2*i;j<1111111;j+=i)p[j]=false;
  }
}

int main(){
  long long n, m;
  cin >> n >> m;
  if(n==1){
    cout << m << endl;
    return 0;
  }
  furui();
  vector<long long> a;
  int i=2;
  while(m>1){
    if(m%i==0){
      a.push_back(i);
      m/=i;
    }else{
      p[i]=false;
      i++;
      for(;!p[i]&&i<1111111;i++);
      if(i==1111111){
        a.push_back(m);
        break;
      }
    }
  }
  long long cnt=1,l=a.size(),ans=1;
  for(int i=1;i<l;i++){
    if(a[i-1]==a[i])cnt++;
    else cnt=1;
    
    if(cnt%n==0)ans*=a[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
int Min(int a,int b){
    if(a<=b)return a;
    return b;
}
int main()
{   int q,h,s,d,n;
    scanf("%d%d%d%d%d",&q,&h,&s,&d,&n);
    long min=Min(8*q,Min(4*h,Min(2*s,d)));
    long ans;
    if(min==d&&n%2==1){
        ans=n/2*min+Min(4*q,Min(2*h,s));
    }else{
        ans=min*n/2;
    }
    printf("%ld",ans);

    return 0;
}


Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll mod =1e9 + 7;
ll size;

int main(){
	ll a , b , n;
	cin >> a >> b >> n;
	ll temp = n/b;
	if(temp == 0){
		
				cout << floor(double(a*n)/b) - a * floor(double(n)/b) << endl;
	}
	else{
		
		cout << floor(double(a*(temp*b-1))/b) - a * floor(double(temp*b-1)/b) << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3868
A,B = map(int,input().split())
count = 0
for a in range(A//10000,B//10000+1):
    for b in range(10):
        for c in range(10):
            p = a * 10001 + b * 1010 + c * 100
            if p >= A and p <= B:
                count += 1
print(count)

Measured memory_bytes: 2940
def inpl(): return list(map(int, input().split()))

N = int(input())
T = inpl()
A = inpl()

OK = True
D = [0]*N
D[0] = 1

for i in range(1, N):
    if T[i-1] < T[i]:
        D[i] = 1

if D[-1] and (A[-1] != T[-1]):
    OK = False
else:
    D[-1] = 1

for i in range(N-2, -1, -1):
    if A[i] > A[i+1]:
        if D[i] and (A[i] != T[i]):
            OK = False
        else:
            if A[i] > T[i]:
                OK = False
            D[i] = 1

ans = OK
MOD = 10**9 + 7
for i in range(N):
    if D[i] == 0:
        ans = ans * min(A[i], T[i]) % MOD
print(ans*1)

Measured memory_bytes: 19012
D,G=map(int,input().split())
PC=[list(map(int,input().split())) for i in range(D)]
ans=10**18
import math
for i in range(2**D):
  _i=i
  j=0
  s=[]
  _ans=0
  g=0
  while i>0:
    if i%2==1:
      _ans+=PC[j][0]
      g+=(PC[j][0]*100*(j+1)+PC[j][1])
      s.append(j)
    j+=1
    i=i//2
  if g>=G:
    ans=min(ans,_ans)
  else:
    j=D-1
    while j in s:
      j-=1
    if j>-1 and G-g<=(PC[j][0]-1)*100*(j+1):
      _ans+=math.ceil((G-g)/100/(j+1))
      ans=min(ans,_ans)
print(ans)
      

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

typedef long long ll;

ll N, K;
vector<ll> A;
vector<ll> P;
vector<bool> V;
ll I;
ll Res;

ll solve() {
  if (K < I) return P[K];
  return P[I + (K - I) % (P.size() - I)];
}
int main() {
  cin >> N >> K;
  A.resize(N);
  for (ll i = 0; i < N; ++i) {
    ll a;
    cin >> a;
    --a;
    A[i] = a;
  }
  V.resize(N);
  ll now = 0;
  while (!V[now]) {
    V[now] = true;
    P.push_back(now);
    now = A[now];
  }
  for (ll i = 0;; ++i) {
    if (P[i] == now) {
      I = i;
      break;
    }
  }
  cout << solve() + 1 << endl;
  return 0;
}


Measured memory_bytes: 6920
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int n,m;
char c[55][55];
int ans[55][55];
int dx[]={-1,0,1};
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			rep(k,3){
				rep(l,3){
					if(k==1&&l==1)continue;
					if(c[i+dx[k]][j+dx[l]]=='#')ans[i][j]++;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(c[i][j]=='#')cout<<'#';
			else cout<<ans[i][j];
		}
		cout<<endl;
	}				
	return 0;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
a = list(map(int, input().split()))
grid = [[0,0] for x in range(n)]
for i in range(n):
    for j in range(i):
        if a[j] < a[i]:
            grid[i][0]+=1
    for j in range(i, n):
        if a[j] < a[i]:
            grid[i][1]+=1

mod = 1000000007
ans = 0
for i in range(n):
    ans += k * (2*grid[i][1] + (k-1)*grid[i][1]) // 2
    ans %= mod
    ans += (k-1) * (2*grid[i][0] + (k-2)*grid[i][0]) // 2
    ans %= mod
print(ans)


            


Measured memory_bytes: 9368
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds; 
#define test() int t;cin>>t;for(int test=1;test<=t;test++)
#define T pair<int, int>
#define ordered_set tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define MOD 1000000007
#define pb push_back 
#define ins insert
#define fast(); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ld long double
#define endl '\n'
int m(int a) {
    return ((a%MOD)+MOD)%MOD;
}
int p(int a, int b) {
    if (b==0) return (int)1;
    int x = p(a, b>>1);
    if (b & 1) return m(x*m(a*x));
    return m(x*x);
}
signed main(){
    fast();
    int n;
    cin >> n;
    int ans = 0;
    for(int i=1; i<=n; i++){
        if(i%3 != 0 && i%5 != 0)    ans += i;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3612
#include <iostream>
#include <cstdio>

using namespace std;

int n;
int a[505];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        int cnt = 0, ii = i;
        while(ii % 2 == 0)
        {
            ii /= 2;
            cnt++;
        }
        a[i] = cnt + 1;
    }
    for(int i = n - 1; i >= 1; i--)
    {
        for(int j = 1; j <= i; j++)
        {
            printf("%d ", a[j]);
        }
        puts("");
    }
    return 0;
}


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

int main(void) {
    long long N;
    cin >> N;
    vector< long long > x(N), y(N);
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
    }
    vector< long long > d(N);
    for (int i = 0; i < N; i++) {
        d[i] = x[i] + y[i];
    }
    sort(d.begin(), d.end());
    long long cand[2];
    cand[0] = d[N - 1] - d[0];
    vector< long long > e(N);
    long long xmax = 0;
    for (int i = 0; i < N; i++) {
        xmax = max(xmax, x[i]);
    }
    for (int i = 0; i < N; i++) {
        e[i] = xmax - x[i] + y[i];
    }
    sort(e.begin(), e.end());
    cand[1] = e[N - 1] - e[0];
    printf("%lld\n", max(cand[0], cand[1]));
    return 0;
}


Measured memory_bytes: 9532
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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

const ll mod=1e9+7;

int main(){
    ll x;
    cin >> x;
    if(360%x==0){
        cout << 360/x << endl;
        return 0;
    }
    else{
        ll d=gcd(360,x);
        cout << 360/d << endl;
    }
} 

Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>

#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

int64_t kRem = 1000000007;

using namespace std;

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

	int n, m; cin >> n >> m;
	vector<int> blocks(m);
	for (auto& block : blocks) {
		cin >> block;
	}

	vector<int64_t> scores(n + 1);
	scores[0] = 1;
	auto it = blocks.begin();
	if (it != blocks.end() && *it == 1) {
		scores[1] = 0;
		it++;
	}
	else {
		scores[1] = 1;
	}

	FOR_LE(i, 2, n) {
		if (it != blocks.end() && *it == i) {
			scores[i] = 0;
			it++;
			continue;
		}

		scores[i] = scores[i - 1] + scores[i - 2];
		scores[i] %= kRem;
	}

	cout << scores[n] << endl;

	return 0;
}


Measured memory_bytes: 1408
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <memory.h>
#include <set>
#include <cmath>
#define fio ios::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ll _pow(ll a, ll b) {
	ll ans = 1;
	for (ll i = 0; b >> i; i++) {
		if ((b >> i) & 1) ans *= a;
		a *= a;
	}
	return ans;
}
int main(void) {
	int a, b; scanf("%d %d", &a, &b);
	if (!(b%a)) {
		printf("%d\n", a + b);
	}
	else {
		printf("%d\n", b - a);
	}
	return 0;
}

Measured memory_bytes: 256
import queue

q = queue.Queue()

N,M = map(int,input().split())
AB = []
dic = {}
for _ in range(M):
    AB = list(map(int,input().split()))
    dic.setdefault(AB[1], []).append(AB[0])
    dic.setdefault(AB[0], []).append(AB[1])

cnt = 1
ans = [0] * N

for i in range(len(dic[1])):
    ans[dic[1][i] - 1] = 1
    q.put(dic[1][i])

while q.empty() == False:
    current_number = q.get()
    for i in range(len(dic[current_number])):
        if ans[dic[current_number][i] - 1] == 0:
            ans[dic[current_number][i] - 1] = current_number
            q.put(dic[current_number][i])

print("Yes")
for i in range(1,N):
    print(ans[i])

Measured memory_bytes: 38420
#include<bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef unordered_map<int,int> umii;
typedef unordered_map<ll,ll> umll;
 
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define bs(v,val) binary_search(v.begin(),v.end(),val)
#define mod 1000000007
#define ff first
#define ss second
#define fi(n) for(int i=0;i<n;i++)
#define fj(n) for(int j=0;j<n;j++)
#define all(v) v.begin(),v.end()
#define pb push_back
#define m_p make_pair
#define endl '\n'
 
ll power(ll x, ll y, ll p)
{  
    ll res = 1;
    x = x % p;  
    if (x == 0) return 0;
    while (y > 0){  
        if (y & 1)  res = (res*x) % p;  
        y = y>>1;
        x = (x*x) % p;  
    }  
    return res;  
}
ll modInverse(ll n, ll p)
{
    return power(n, p-2, p); 
}
// ********** CODE STARTS HERE ****************//

void solve()
{
	int n;
	cin>>n;
	vi a(n);
	fi(n)cin>>a[i];
	ll money = 1000, invest = 0;
	for(int i=1; i<n; i++)
	{
		if(a[i] > a[i-1])
		{
			invest = money/a[i-1];
			money -= invest*a[i-1];
			money += invest*a[i];
			invest = 0;
		}
	}
	cout<<money;
}

int main()
{
	fastio;
	int T;
//    cin>>T;
//    while(T--)
        solve();
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define ll long long
#define mp make_pair
using namespace std;
ll vsum[114514],rvl[114514],lvl[114514];
int main(){
	ll n,c;
	cin>>n>>c;
	vector<ll> x,v;
	x.pb(0);
	v.pb(0);
	for(int i=0;i<n;i++){
		ll tmpx,tmpv;
		cin>>tmpx>>tmpv;
		x.pb(tmpx);
		v.pb(tmpv);
	}
	x.pb(c);
	v.pb(0);
	vsum[1] = v[1];
	for(int i=1;i<n;i++){
		vsum[i+1] = vsum[i] + v[i+1];
	}
	for(int i=1;i<=n;i++){
		lvl[i] = vsum[i]-x[i];
		rvl[i] = (vsum[n] - vsum[i-1]) - (c-x[i]);
	}
	for(int i=1;i<=n;i++){
		if(lvl[i]<lvl[i-1])lvl[i]=lvl[i-1];
	}
	for(int i=n;i>=1;i--){
		if(rvl[i]<rvl[i+1])rvl[i]=rvl[i+1];
	}
	ll ans = 0;
	// 0 -> L -> 0 -> R
	for(int i=0;i<=n;i++){
		ll tmp = vsum[i] - 2*x[i];
		tmp += rvl[i+1];
		if(tmp>ans)ans = tmp;
	}
	for(int i=n+1;i>=1;i--){
		ll tmp = (vsum[n] - vsum[i-1]) - 2*(c-x[i]);
		tmp += lvl[i-1];
		if(tmp>ans)ans=tmp;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4460
# https://atcoder.jp/contests/abc118/tasks/abc118_c

def main():
    N = int(input())
    A = list(map(int, input().split()))  # 体力

    while True:
        A.sort()

        before_min = A[0]
        after_min = before_min
        for i in range(1, N):
            A[i] = (A[i] % A[0]) if A[i] % A[0] != 0 else A[i]
            after_min = min(after_min, A[i])

        # print(A)
        if before_min == after_min:
            print(before_min)
            exit()

main()


Measured memory_bytes: 14224
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long llong;
const int INF = 0x3f3f3f3f;
const int MAXN = 200005;

int A[MAXN], L[MAXN/2], R[MAXN/2];

llong merge(int left, int mid, int right){
	int n1 = mid - left, n2 = right - mid;
	for(int i = 0; i < n1; i++)	L[i] = A[left+i];
	for(int i = 0; i < n2; i++)	R[i] = A[mid+i];
	L[n1] = R[n2] = INF;
	int i, j;
	llong v = 0;
	i = j = 0;
	for(int k = left; k < right; k++){
		if(L[i] <= R[j])
			A[k] = L[i++];
		else{
			v += n1 - i;
			A[k] = R[j++];
		}
	}
	return v;
}

llong mergeSort(int left, int right){
	llong v1, v2, v3;
	if(left + 1 < right){
		int mid = (left + right) / 2;
		v1 = mergeSort(left, mid);
		v2 = mergeSort(mid, right);
		v3 = merge(left, mid, right);
		return v1 + v2 + v3;
	}
	else	
		return 0;
}

int main(){
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)	scanf("%d", A + i);
	llong  ans = mergeSort(0, n);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4780
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast","no-stack-protector","unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx")
//#include<bits/extc++.h>
//using namespace __gnu_pbds;
using namespace std;
#define int long long
#define F(i,L,R) for(int i=L;i<R;++i)
#define FE(i,L,R) for(int i=L;i<=R;++i)
#define getI(a) scanf("%lld",&a)
#define getII(a,b) scanf("%lld%lld",&a,&b)
#define getIII(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define VgetI(n) int (n); scanf("%lld",&(n))
#define VgetII(n,m) int (n),(m); scanf("%lld%lld",&(n),&(m))
#define VgetIII(n,m,k) int (n),(m),(k); scanf("%lld%lld%lld",&(n),&(m),&(k))
#define debug(x) cout<<(#x)<<"="<<x<<"\n";
#define qq cout<<"QQ\n";
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define f first
#define s second
#define INF 2000000000
main(){
	int x;
	while(~getI(x)){
		int now=100,ans=0;
		while(now<x) now*=1.01,ans++;
		printf("%lld\n",ans);
	}
}

Measured memory_bytes: 3820
import numpy as np

N = int(input())
a = list(map(int,input().split()))


def calc_total_cost(t,list):
    total_cost=0
    for i in range(len(list)):
        total_cost += (t-list[i])**2
    return total_cost


t = round(np.mean(a))



c1 = calc_total_cost(t,a)
c2 = calc_total_cost(t+1,a)
print(int(min(c1,c2)))

Measured memory_bytes: 12504
n, yen = list(map(int, input().split()))

for x in range(n+1):
  for y in range(n+1):
    z = n - x - y
    if z < 0:
      continue
    r = (10000*z) + (5000*x) + (1000*y)
    if r == yen:
      print(z, x, y)
      exit()
print(-1, -1, -1)

Measured memory_bytes: 3060
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
ans = B[A[0]-1]
for i in range(N-1):
  ans += B[A[i+1]-1]
  if(A[i+1] == A[i] + 1):
    ans += C[A[i]-1]
print(ans)

Measured memory_bytes: 3064
using System;
class Program
{
    static void Main(string[] args)
    {
        string[] str = Console.ReadLine().Split(' ');//2つ以上のスペース区切り入力の取得
        int N = int.Parse(str[0]);

        string[] strHeight = Console.ReadLine().Split(' ');//2つ以上のスペース区切り入力の取得
        string[] results = new string[N];

        int count = 0;
        for( int i = 0; i < N; i++ )
        {
            int each = int.Parse(strHeight[i]);
            results[each - 1] = (i + 1).ToString();
        }

        foreach (var kekka in results)
        {
            Console.Write(kekka);
            Console.Write(" ");
        }
        //Console.Read();
    }
}

Measured memory_bytes: 27996
s = '1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51'.split(', ')
k = int(input())
print(int(s[k-1]))


Measured memory_bytes: 2940