akhauriyash/Code-Regression huggingface dataset:
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <utility>
#include <memory>
#include <functional>
#include <deque>
#include <cctype>
#include <ctime>
#include <numeric>
#include <list>
#include <iomanip>
 
#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <forward_list>
 
#define cauto const auto&
#else
 
#endif
 
using namespace std;
 
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll;
typedef vector<vector<long long> > vvll;
 
#define VV(T) vector<vector< T > >
 
template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}
 
template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}
 
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i,n) _rep2((i),0,(n))
#define _rep2(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define fi first
#define se second
#define mkp make_pair
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif
 
#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
 
void mainmain(){
	int n;
	cin>>n;
	ll W;
	cin>>W;
	vector<pll> v(n);
	rep(i,n){
		cin>>v[i].fi>>v[i].se;
	}
	ll base = v[0].fi;
	rep(i,n){
		v[i].fi -= base;
	}
	ll ans = 0;
	rep(ii,1,n+1){
		ll ww = min(W - base*ii,300LL);
		if(ww < 0) break;
		vvll dp;
		initvv(dp,ii+1,ww+1);
		dp[0][0] = 0;
		rep(i,n){
			for(int j=ww; j>=0; j--){
				for(int k=ii-1; k>=0; k--){
					if(j-v[i].fi>=0){
						maxs(dp[k+1][j], dp[k][j-v[i].fi]+v[i].se);
					}
				}
			}
		}
		rep(i,ii+1) rep(j,ww+1){
			maxs(ans, dp[i][j]);
		}
	}
	cout<<ans<<endl;
}
 
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(20);
    mainmain();
}

Measured memory_bytes: 536
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>


typedef long double ld;
typedef long long ll;

using namespace std;

set<int> s;

int main() {
	int x, n, t;
	cin >> x >> n;
	for (int i = 0; i < n; i++) {
		cin >> t;
		s.insert(t);
	}
	int bestdist = 1000;
	int best = -1;
	for (int i = 0; i <= 110; i++) {
		if (s.count(i)) {
			continue;
		}
		if (abs(x - i) < bestdist) {
			best = i;
			bestdist = abs(x - i);
		}
	}
	cout << best << endl;

	return 0;
}


Measured memory_bytes: 3584
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N;
int a[150000];
int b[150000];
int i, j;
queue<pair<int, int> > que;
pair<int, int> p;

int main() {
  vector<int> v[100005];
  int cnt[100000];
  int c[100000];
  int s = 1;
  cin >> N;
  for (i = 0; i < N; i++) {
    cnt[i] = 0;
    c[i] = 0;
  }
  for (i = 0; i < N-1; i++) {
    cin >> a[i] >> b[i];
    cnt[a[i]-1]++;
    cnt[b[i]-1]++;
    v[a[i]].push_back(i);
    v[b[i]].push_back(i);
  }
  int k = 0;
  for (i = 0; i < N; i++) {
    k = max(k, cnt[i]);
  }
  int color = 1;
  for (i = 0; i < N-1; i++) {
    if (a[i] == s) {
      que.push(make_pair(i, b[i]));
      c[i] = color;
      color++;
    }
  }
  while (!que.empty()) {
    color = 1;
    p = que.front();
    que.pop();
    for (i = 0; i < v[p.second].size(); i++) {
      if (color == c[p.first])
        color++;
      int t = v[p.second][i];
      if (a[t] == p.second && c[t] == 0) {
        que.push(make_pair(t, b[t]));
        c[t] = color;
        color++;
      }
      if (b[t] == p.second && c[t] == 0) {
        que.push(make_pair(i, a[i]));
        c[t] = color;
        color++;
      }
    }
  }
  cout << k << endl;
  for (i = 0; i < N-1; i++)
    cout << c[i] << endl;
}


Measured memory_bytes: 7680
#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <vector>
#define pb push_back
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
#define MAXN 200100

int n,m;
bool reach1[MAXN],reachn[MAXN];

int main(){
	ms(reach1); ms(reachn);
	reach1[1] = reachn[n] = 1;
	scanf("%d %d",&n,&m);
	for( int i = 1; i <= m ; i++ ){
		int a,b;
		scanf("%d %d",&a,&b);
		if( a == 1 ) reach1[b] = 1;
		if( b == 1 ) reach1[a] = 1;
		if( a == n ) reachn[b] = 1;
		if( b == n ) reachn[a] = 1;
	}
	for( int i = 1 ; i <= n ; i++ )
		if( reach1[i]  &&  reachn[i] ){
			printf("POSSIBLE\n");
			return 0;
		}
		
	printf("IMPOSSIBLE\n");
	return 0;
}

Measured memory_bytes: 640
N=int(input())
A=[]
for i in range(N):
  #tmp=float(input())*10**9
  inp=input()
  ten=inp.find(".")
  L=len(inp)
  batu=9
  if ten!=-1:
    batu-=L-ten-1
  inp=inp.replace(".","")
  inp=int(inp)
  inp*=10**batu
  A.append(inp)

#print(A)

dat=[[0]*19 for _ in range(19)]  
rui=[[0]*19 for _ in range(19)]

B=[]

for i in range(N):
  dev2,dev5=0,0
  while A[i]%2==0 and dev2<18:
    dev2+=1
    A[i]//=2
  while A[i]%5==0 and dev5<18:
    dev5+=1
    A[i]//=5
  dat[dev2][dev5]+=1
  B.append([dev2,dev5])
  
for i in range(19):
  for j in range(19):
    for k in range(i+1):
      for l in range(j+1):
        rui[k][l]+=dat[i][j]
  
ans=0
for i in range(N):
  dev2,dev5=B[i]
  t_dev2,t_dev5=18-dev2,18-dev5
  if dev2>=t_dev2 and dev5>=t_dev5:
    ans-=1
  ans+=rui[t_dev2][t_dev5]

print(ans//2)
  
  
    
    

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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int64 n,m,d;
    cin >> n >> m >> d;
    cout << fixed << setprecision(10);
    cout << (double)(n - d) * (d==0?1:2) / (n * n) * (m - 1) << endl;
    return 0;
}

Measured memory_bytes: 256
(let* ((n (read))
       (m (loop :repeat n :collect (read))))
  (princ(loop :for k :from 0 :upto (- n 3)
        :sum(loop :for j :from (1+ k) :upto (- n 2)
                  :sum(loop :for l :from (1+ j) :upto (- n 1)
                            :count (let* ((a (elt m k))
                                          (b (elt m j))
                                          (c (elt m l))
                                          (x (and (not (= a b))
                                                  (not (= a c))
                                                  (not (= b c))
                                                  (< a (+ b c))
                                                  (< b (+ a c))
                                                  (< c (+ a b)))))
                                     x))))))

Measured memory_bytes: 24724
import sys
import numpy as np
import numba
from numba import njit
from numba.types import Omitted
i4 = numba.int32
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353

@njit((numba.types.optional(i8), ) * 2, cache=True)
def seg_f(x, y):
    if x is None:
        return y
    if y is None:
        return x
    return max(x, y)


@njit((i8[:], ), cache=True)
def build(raw_data):
    N = len(raw_data)
    seg = np.zeros(N + N, np.int64)
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
    return seg


@njit((i8[:], i8, i8), cache=True)
def set_val(seg, i, x):
    N = len(seg) // 2
    i += N
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])


@njit((i8[:], i8, i8), cache=True)
def fold(seg, l, r):
    vl = vr = None
    N = len(seg) // 2
    l, r = l + N, r + N
    while l < r:
        if l & 1:
            vl = seg_f(vl, seg[l])
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(seg[r], vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)

def main(XD):
    X, D = XD[::2], XD[1::2]
    N = len(X)
    argsort = np.argsort(X)
    X, D = X[argsort], D[argsort]
    INF = 1 << 60
    X = np.append(X, INF)
    D = np.append(D, 1)
    # i 台目を起動したとき、生き残るはじめてのロボを求める
    dp0 = np.searchsorted(X, X + D)
    seg = build(dp0)
    for n in range(N - 1, -1, -1):
        x = fold(seg, n, dp0[n])
        dp0[n] = x
        set_val(seg, n, x)
    # n 台目より右側での状態の数え上げ
    dp = np.zeros(N + 1, np.int64)
    dp[-1] = 1
    for n in range(N - 1, -1, -1):
        nxt = dp0[n]
        dp[n] = (dp[n + 1] + dp[nxt]) % MOD  # 動かさない、動かす
    return dp[0]

N = int(readline())
XD = np.array(read().split(), np.int64)

print(main(XD))

Measured memory_bytes: 132692
#include<bits/stdc++.h>
using namespace std;
/*
int main(){
  int64_t N;
  cin >> N;
  int p = N / 15;
  //cout << p << endl; OK
  int q = N % 15;
  //cout << q << endl; OK
  int64_t a = 0;
  for(int i=0; i<q+1; i++){
    if(i==1||i==2||i==4||i==7||i==8||i==11||i==13||i==14){
      a += 15*p + i;
    }
  }
  cout << a << endl;
  int64_t ans = p*p*60 + a;
  cout << ans << endl;
}
*/

int main(){
  int N ;
  cin >> N;
  int64_t ans=0;
  for(int i=1; i<N+1; i++){
    if(i%3 != 0 && i%5 != 0){
      ans += i;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3636
import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = readLn >>= putStrLn . solve

solve :: Int -> String
solve x 
    | x `elem` [7,5,3] = "YES"
    | otherwise = "NO"

readLine :: IO [Int]
readLine = unfoldr (fmap (second (maybe B.empty snd . B.uncons)) . B.readInt) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine

Measured memory_bytes: 508
#include <stdio.h>
int menseki(int a, int b)
{
	int c;
	c = a*b;
	return c;
}
int syuu(int a, int b)
{
	int d;
	d = (2*a)+(2*b);
	return d;
}
int main()
{
	int e, f;
	scanf("%d %d", &e, &f);
	printf("%d %d\n", menseki(e, f), syuu(e, f));
	return 0;
}
/*scanf で２つの整数を続けて読み込むには
scanf("%d %d", &a, &b);
と記述します。*/

Measured memory_bytes: 596
#include <stdio.h>

int main(void) {
  int a,b,c,d,g[100][100],t[100],m;
  scanf("%d %d",&a,&b);
  for(c=0;c<a;c++){
   for(d=0;d<b;d++){
     scanf("%d",&g[c][d]);
  }
}
  for(c=0;c<b;c++){
    scanf("%d",&t[c]);
}
  for(c=0;c<a;c++){
  m=0;
  for(d=0;d<b;d++){
    m+=g[c][d]*t[d];
    }
   printf("%d\n",m);
  }
  return 0;
}


Measured memory_bytes: 2140
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
using ll=long long;
#define rep(i,a,b) for(int i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+b,(a).begin()+c // コンテナ a の 要素 b から c へのイテレータ
#define MOD 1000000007
// typedef
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;



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

int a;
string s; 
cin >> a >> s;

if (a >= 3200) {cout << s << "\n"; return 0;}
else {cout << "red" << "\n"; return 0;}

return 0;
}

// 境界，出力文字列 チェック



Measured memory_bytes: 256
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def lcm(a, b):
	return a * b // gcd (a, b)

n = int(input())
l = int(input())

i = 1

while i < n:
    l = lcm(l, int(input()))
    i = i + 1

print(l)


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

int main() {
  string a, b, c;
  cin >> a >> b >> c;
  if(a.at(a.size() - 1) == b.at(0)){
    if(b.at(b.size() - 1) == c.at(0)){
      cout << "YES" << endl;
      return 0;
    }
  }
  cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B,C,X;
  cin >> A >> B >> C >> X;
  int ans = 0;
  
  for (int a=0;a<=A; a++) {
    for (int b=0;b<=B; b++) {
      for (int c=0;c<=C; c++) {
        if( X == a*500 + b*100 + c*50) ans++;
      }
    }
  }

  cout << ans << endl;
  

}


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

int main(){
    string s;
    cin >> s;
    int len_s = s.size();
    int l = 0;
    int r = 0;
    rep(i,len_s){
        if (s[i] == 'A'){
            l = i;
            break;
        }
    }
    repr(i,len_s - 1){
        if (s[i] == 'Z'){
            r = i;
            break;
        }
    }
    cout << r - l + 1 << endl;
}


Measured memory_bytes: 640
import sys
N,M,X=map(int, sys.stdin.readline().split())
C=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]

ans=float("inf")

for n in range(2**N):
    L=[0 for _ in range(M+1)]
    price=0
    for i in range(N):
        if n>>i&1==1:
            for j,x in enumerate(C[i]):
                if j==0:
                    price+=x
                else:
                    L[j]+=x    
        if X<=min(L[1:]):
            ans=min(ans,price)
if ans==float("inf"):
    print -1
else:
    print ans

Measured memory_bytes: 73520
#include<iostream>
#include<vector>
using namespace std;
int n,q;
string s,t,d;
char move(int p){
  for(int i=0;i<q;i++){
    if(s[p]==t[i]){
      if(d[i]=='R') p++;
      else p--;

      if(p==-1) return 'l';
      else if(p==n) return 'r';
    }
  }
  return 'm';
}
int main(){
  int i,j;
  cin>>n>>q;
  cin>>s;
  char c,buf;
  for(i=0;i<q;i++){
    cin>>c;
    t.push_back(c);
    cin>>c;
    d.push_back(c);
  }
  int rp=n-1,lp=0,mp;

  buf=move(0);
  if(buf=='r'){
    cout<<0<<endl;
    return 0;
  }
  else if(buf=='m'){
    lp=-1;
  }
  buf=move(n-1);
  if(buf=='l'){
    cout<<0<<endl;
    return 0;
  }
  else if(buf=='m'){
    rp=n;
  }

  mp=n-1;
  if(lp!=-1){//消える左端を探す
    while(1){
      if(mp-lp==1) break;
      j=(mp+lp)/2;
      buf=move(j);
      if(buf=='l') lp=j;
      else mp=j;
    }
  }

  mp=0;
  if(rp!=n){
    while(1){
      if(rp-mp==1) break;
        j=(mp+rp)/2;
        buf=move(j);
        if(buf=='r') rp=j;
        else mp=j;
      }
  }
  cout<<rp-lp-1<<endl;
  return 0;
}

Measured memory_bytes: 1024
/*input
5 1000000000
6 6 2 6 2
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, m; cin >> n >> m;
    vector<ll> a(n);
    ll lcm;
    for(int i = 0; i < n; i++)
    {
    	int foo; cin >> foo;
    	a[i] = foo/2;
    	if(!i) lcm = a[i];
    	else lcm = (lcm * a[i])/__gcd(lcm, a[i]);
    }
    for(int i = 0; i < n; i++) if(!(lcm/a[i] & 1))
    {
		cout << 0;
		return 0;
    }
    if(m < lcm) cout << 0;
    else cout << (m - lcm)/(2 * lcm) + 1;

    return 0;
}

Measured memory_bytes: 1024
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>

#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

#include <stdexcept>

using namespace std;

//conversion
//------------------------------------------
inline int toint(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class t> inline string tostring(t x) { ostringstream sout; sout << x; return sout.str(); }

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (l" << __line__ << ")" << " " << __file__ << endl

// type alias
using ll = long long;
using ull = unsigned long long;

inline bool isPower2(ull a)
{
	if (a == 0)
	{
		return false;
	}
	return !(a & (a - 1));
}

inline unsigned getMaxEffectiveBit(ull a)
{
	ll index = 0;
	for (; a != 0; a >>= 1)
	{
		++index;
	}
	return index;
}

// computational complexity: o(log(max(a, b))) 
inline ull getGcd(ull a, ull b)
{
	if (b == 0)
	{
		return a;
	}
	return getGcd(b, a % b);
}

// computational complexity: o(log(max(a, b))) 
template<class ll>
inline pair<ll, ll> getBezoutsIdentitySolution(ll a, ll b)
{
	if (b == 0)
	{
		return { 1, 0 };
	}
	auto sol = getBezoutsIdentitySolution(b, a % b);
	return { sol.second, sol.first - (a / b) * sol.second };
}

template<class Integer>
inline Integer getPower(Integer base, unsigned exponential)
{
	Integer res = 1;
	while (exponential >= 1)
	{
		if (exponential & 1)
		{
			res *= base;
		}
		base = base * base;
		exponential >>= 1;
	}

	return res;
}



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

	ll N;
	cin >> N;
	
	vector<ll> As(N);
	ll A;
	ll minusCount = 0;
	for (ll i = 0; i < N; ++i)
	{
		cin >> A;
		if (A <= 0)
		{
			++minusCount;
		}
		As[i] = abs(A);
	}

	sort(As.begin(), As.end());
	ll res = accumulate(As.begin(), As.end(), (minusCount % 2 == 0 ? 0 : -As[0] * 2) );

	cout << res << endl;

	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

#define eps (1e-10)
struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
    Point operator+(Point p) {return Point(x+p.x,y+p.y);}
    Point operator-(Point p) {return Point(x-p.x,y-p.y);}
    Point operator*(double k){return Point(x*k,y*k);}
    double norm(){return x*x+y*y;}
    double abs(){return sqrt(norm());}
    bool operator == (const Point &p) const{
    return fabs(x-p.x)<eps && fabs(y-p.y)<eps;
  }
  double dot(Point p){return x*p.x+y*p.y;}
  double det(Point p){return x*p.y-y*p.x;}
};
bool cmp_x(const Point& p,const Point& q){
  if(p.x!=q.x) return p.x<q.x;
  return p.y<q.y;
}
bool cmp_y(const Point& p,const Point& q){
  if(p.y!=q.y) return p.y<q.y;
  return p.x<q.x;
}
vector<Point> convex_hull(Point* ps,int n){
    sort(ps,ps+n,cmp_x);
    int k=0;
    vector<Point> qs(n*2);
    rep(i,n){
        while(k>1&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<0) --k;
        qs[k++]=ps[i];
    }
    for(int i=n-2,t=k;i>=0;--i){
        while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<0) --k;
        qs[k++]=ps[i];
    }
    qs.resize(k-1);
    return qs;
}
double distance(Point p,Point q){
    return (p-q).abs();
}

Point p[101],q[101];
double PI=acos(-1.0);
double b[101];
int main(){
    int n,xi,yi;
    cin>>n;
    rep(i,n){
        cin>>xi>>yi;
        q[i]=p[i]=Point(xi,yi);
    }
    vector<Point> ans=convex_hull(q,n);
    int m=ans.size();
    rep(i,m){
        Point p1(ans[(i-1+m)%m]-ans[i]),p2(ans[(i+1)%m]-ans[i]);
        double deg=acos(p1.dot(p2)/(p1.abs()*p2.abs()));
        double a=abs(PI-deg)/(PI*2);
        int cur=find(p,p+n,ans[i])-p;
        b[cur]=a;
    }
    rep(i,n) cout<<fixed<<setprecision(12)<<b[i]<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define IOS ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
const ll mininf = -922337203685477;
const ll nax = 1e5+5;
ll n, arr[nax];
	
int main(){
	IOS
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> arr[i];
	}
	sort(arr, arr+n);
	ll fpb=__gcd(arr[0], arr[1]);
	for(int i=2;i<n;i++){
		fpb=__gcd(fpb, arr[i]);
	}
	cout << fpb << '\n';
}


Measured memory_bytes: 4404
n,a,b=map(int,input().split())
s=input()
counta=0
countb=0
for i in range(n):
    if s[i]=="c":
        print("No")
    elif s[i]=="b":
        if counta<a+b and countb<b:
            counta+=1
            countb+=1
            print("Yes")
        else:
            print("No")
    else:
        if counta<a+b:
            counta+=1
            print("Yes")
        else:
            print("No")


Measured memory_bytes: 4016
using System;
using System.Collections.Generic;

namespace ABC_045
{
    class Program
    {
        static void Main(string[] args)
        {
            Queue<string>[] S;
            S = new Queue<string>[3];

            for (int i = 0; i < 3; i++)
            {
                string input = Console.ReadLine();
                S[i] = new Queue<string>();
                for (int j = 0; j < input.Length; j++)
                {
                    S[i].Enqueue(input.Substring(j, 1));
                }
            }

            int target = 0;

            while (true)
            {
                if(S[target].Count == 0)
                {
                    Console.WriteLine((target == 0) ? "A" : (target == 1) ? "B" : "C");
                    break;
                }

                string next = S[target].Dequeue();
                
                target = (next == "a") ? 0 : (next == "b") ? 1 : 2 ;
            }
        }
    }
}


Measured memory_bytes: 2904
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;

int main()
{
    ll n,a,b;
    scanf("%lld %lld %lld",&n,&a,&b);
    if((b-a)%2==0)
    {
        printf("%lld\n",(b-a)/2);
    }
    else
    {
        printf("%lld\n",min((a+b-1)/2,(n-a+n-b+1)/2));
    }
    return 0;
}


Measured memory_bytes: 128
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static string[] s_rd;
T RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T = long)(in string str, T fix = 0) { auto r = str.split.to!(T[]); r[] += fix; return r; }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
long lcm(long x, long y) { return x * y / gcd(x, y); }

long mod = 10^^9 + 7;
//long mod = 998244353;
//long mod = 1_000_003;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{
	auto N = RD;
	auto A = RD;

	writeln(N % 500 <= A ? "Yes" : "No");
	stdout.flush();
	debug readln();
}

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

int main() {
    string s, t, u;
    int a, b;
    cin >> s >> t;
    cin >> a >> b;
    cin >> u;
    if (s == u) {
        cout << a - 1 << " " << b << endl;
    } else {
        cout << a << " " << b - 1 << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

class B {
	int n;
	int k;
	int ans{ 1 };

public:
	void solve()
	{
		cin >> n >> k;

		for (int i{ 0 }; i < n; i++)
		{
			if (i)
				ans *= k - 1;
			else
				ans = k;
		}

		cout << ans << endl;
	}
};


int main()
{
	B solution;
	solution.solve();

	return 0;
}

Measured memory_bytes: 256
from bisect import bisect_right, bisect_left
from collections import Counter, deque
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import groupby, permutations, combinations, product
from sys import stdin, stderr


# 最大公約数（ユークリッドの互除法）
# Python3.5 で math.gcd()が追加され、
# AtCoder環境と最新環境でパッケージが分かれてしまったので、自分で書いておく
def gcd(x, y):
    return x if y == 0 else gcd(y, x % y)


# 拡張ユークリッド互除法
# 正整数x, y について、a*x + b*y == gcd(x,y)なるa,bを返す。
# 特に、互いに素なるx, yについては a*x + b*y == 1 となる a, b。
def exgcd(x, y):
    if y == 0:
        return 1, 0
    a, b = exgcd(y, x % y)
    return b, a - (x // y) * b


# 最小公倍数
def lcm(x, y):
    m = gcd(x, y)
    return (x // m) * (y // m)


def main():
    n, r = [int(x) for x in input().split()]
    if n >= 10:
        return r
    return 100*(10-n) + r


if __name__ == "__main__":
    print(main())

Measured memory_bytes: 3692
#include<bits/stdc++.h>
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int mod = 1000000007;
const int INF = 1001001001;

int main() {
  int x;
  cin >> x;
  string ans;
  if (x >= 30) ans = "Yes";
  else ans = "No"; 

  cout << ans << endl;
}

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;


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

    return 0;
}


Measured memory_bytes: 3552
#include <bits/stdc++.h>
#define ll long long
#define li long int
#define ld long double
#define pl pair<long long, long long>
#define pi pair<int, int>
#define ppl pair<pl, ll>
#define ppi pair<int, pi>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define LLFOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define MOD 1000000007
#define M2 998244353
//std::cout <<setprecision(30) << av << endl;
using namespace std;
ll pre[300000];
ll suf[300000];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    //cin >> t;
    while(t--){
        int hi, k;
        cin >> hi >> k;
        int n = hi+1; // no of numbers

        FOR(i, 0, n+1){
            pre[i]=((ll)(i-1)*(i))/2;
            suf[i]=(ll)hi*i-((ll)(i)*(i-1))/2;
        }
        ll sum=0;
        FOR(i, k, n+1){
            sum=(sum+suf[i]-pre[i]+1)%MOD;
        }
        cout << sum << endl;




    }
}


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

using ll = long long;
using ull = unsigned long long;

#define MOD 1000000007

int main(void) {
    ll N, x;
    ll count = 0;
    vector<ll> A;
    cin >> N >> x;
    A.resize(N);
    for(ll i = 0;i < N;i++) cin >> A[i];
    sort(A.begin(), A.end());
    for(auto &i: A) {
        if(x < i) {
            break;
        } else {
            count++;
            x -= i;
        }
    }
    if(count == N && x) count--;
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int a;
	scanf("%d",&a);
	
	int h,m,s;
	
	h=a/3600;
	a%=3600;
	
	m=a/60;
	a%=60;
	
	s=a;
	
	printf("%d:%d:%d\n",h,m,s);
	
	return 0;

}

Measured memory_bytes: 1020
import java.util.*;

class Main {

    Scanner sc;
    HashMap<String, Integer> itemList;
    HashMap<String, LinkedList<String>> itemComb;

    int solve(String item) {
        int min = Integer.MAX_VALUE;
        int sum = 0;
        if ( !itemList.containsKey(item) )return min;
        min = itemList.get(item);
        if ( !itemComb.containsKey(item) )return min;
        if (itemComb.get(item).isEmpty()) {
            return itemList.get(item);
        }
        for (String str : itemComb.get(item)) {
            sum += solve(str);
            if (sum >= min) return min;
        }
        return sum;
    }

    void run() {
        sc = new Scanner(System.in);

        while (true) {
            int n = sc.nextInt();
            if (n == 0) {
                break;
            }
            itemList = new HashMap<String, Integer>();
            itemComb = new HashMap<String,LinkedList<String>>();
            for (int i = 0; i < n; i++) {
                LinkedList<String> tmp = new LinkedList<String>();
                String item = sc.next();
                itemList.put(item, sc.nextInt());
                itemComb.put(item,tmp);
            }
            int m = sc.nextInt();
            for (int i = 0; i < m; i++) {
                String item = sc.next();
                int num = sc.nextInt();
                LinkedList<String> tmp = new LinkedList<String>();
                for (int j = 0; j < num; j++) {
                    tmp.add(sc.next());
                }
                itemComb.put(item,tmp);
            }
            String q = sc.next();
            System.out.println(solve( q ) );
        }
    }

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

Measured memory_bytes: 13000
fun main(args: Array<String>) {
    val n = readLine()!!

    val ans = when{
        n[0] == n[1] && n[1] == n[2] -> "Yes"
        n[1] == n[2] && n[2] == n[3] -> "Yes"
        else -> "No"
    }

    println(ans)
}

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

using namespace std;

int N, M;

int main() {
	int in, out, totalIn, totalOut, maxSum;

	maxSum = -1;
	cin >> N >> M;
	totalIn = M;
	totalOut = 0;
	for (int i = 0; i < N; ++i) {
		cin >> in >> out;
		totalIn += in;
		totalOut += out;
		if (totalOut > totalIn) {
			cout << "0" << endl;
			return 0;
		}
		maxSum = max(maxSum, totalIn - totalOut);
	}
	cout << max(maxSum, M) << endl;

	return 0;
}


Measured memory_bytes: 3100
#include <stdio.h>
 
int main(void) {
    unsigned long long factoricals[21];
    int i;
    factoricals[0]=1;
    for(i=1;i<=20;i++) {
        factoricals[i]=factoricals[i-1]*i;
    }
    scanf("%d",&i);
    printf("%llu\n",factoricals[i]);
    return 0;
}

Measured memory_bytes: 596
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
	int a1=0,a2=0;
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		if(a>a1)
			a1=a,a2=b;
	}
	printf("%d",a1+a2);
}

Measured memory_bytes: 128
#include <stdio.h>
#include <string.h>


int main (void){
        int N,M,min,now=2,ans=0,M_cnt;
        int a[100001],b[100001],check[100001];
        for (int i = 0; i < 100001; i++) {
                check[i]=0;
        }
        scanf("%d\n",&N);
        scanf("%d\n",&M);
        M_cnt=M;
        for (int i = 0; i < M; i++) {
          scanf("%d\n",&a[i]);
          scanf("%d\n",&b[i]);
        }

        while(1){
          min=100001;
          for (int i = 0; i < M; i++) {
            if(check[i]==0&&min>b[i]){
              min=b[i];
            }
            if(now==min){
              break;
            }
          }
        //  printf("min=%d\n",min );
          ans++;
          now=min+1;
          for (int i = 0; i < M; i++) {
            if(check[i]==0&&min>a[i]&&min<=b[i]){
              check[i]=1;
              M_cnt--;
          //    printf("destory:%d\n",i);
            }
            if(M_cnt==0){
              printf("%d\n", ans);
              return 0;
            }
          }


        }

        return 0;
}


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

int main(){
    int n;
    cin >> n;
    int a[n];
    int ans = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        ans += (a[i] - 1);
    }

    cout << ans << endl;
}

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

using namespace std;

/**
 *  Name: Chris M. Perez
 *  University: Interamerican University Metro Campus
 *
**/

#define endl '\n'
#define MOD 10e18
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define gcd(x , y) __gcd(x , y)
#define all(x) (x).begin() , (x).end()
#define forn(i , a , b) for(int i=(a);i<(b);i++)
#define forrange(j , a , b) for(int j=(a);j<=(b);j++)
#define nestedforn(i , a , b , j , c , d) for(int i=(a);i<=(b);i++) for(int j=(c);j<=(d);j++)
#define sort_all(x) sort(all(x))
#define zeros_at_beginning(x) __builtin_clz(x)
#define zeros_at_end(x) __builtin_ctz(x)
#define ones(x) __builtin_popcount(x)
#define parity_even_or_odd_ones __builtin_parity(x)

typedef vector<int> vi;
typedef pair<int , int> pii;
typedef tuple<int , int , int> tiii;
typedef vector<pii> vpii;
typedef vector<tiii> vtiii;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef long long int lli;

             
inline int input(){
  int n;
  scanf("%d" , &n);
  return n;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;

#ifdef LOCAL_DEFINE
  freopen("input.txt" , "rt" , stdin);
#endif

  int n; cin >> n;
  vector<int> v(2 * n);
  forn(i , 0 , 2 * n) cin >> v[i];
  sort_all(v);
  int k = 0;
  forn(i , 0 , (int)v.size()){
   k += v[i];
   i += 1;
  }
  cout << k << endl;
#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif  
  return 0;
}

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

#define SIZE 200000
using namespace std;
/*
int MaxBenefit(int* R, int size) {
 /*
	int max, temp;

	for (int j = 1; j < size; j++) {
		for (int i = j + 1; i < size; i++) {
			if (j == 1 && i == 2) {
				max = R[i] - R[j];
			}
			temp = R[i] - R[j];
			if (temp > max) {
				max = R[i] - R[j];
			}
		}
	}
	
	int maxv = -200000000;
	int minv = R[0];
	
	for(int i = 0; i < size; i++ ){
	    maxv = max(maxv, R[i] - minv);
	    minv = min(minv, R[i]);
	}

	return maxv;
}
*/

int main() {
	int R[SIZE];
	int n;

	cin >> n;

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

	//cout << MaxBenefit(R, n) << endl;
	int maxv = -2000000000;
	int minv = R[0];
	
	for(int i = 1; i < n; i++ ){
	    maxv = max(maxv, R[i] - minv);
	    minv = min(minv, R[i]);
	}
	
	cout << maxv << endl;
	return 0;
}


Measured memory_bytes: 3856
#include <iostream>

using namespace std;

int bill[2][100];
int n;
bool visited[2][100];
int jump(int, int, int);

main(){
  while(1){
    cin >> n;
    if(n==0) break;
    
    for(int i=0;i<2;i++){
      for(int j=0;j<n;j++){
	cin >> bill[i][j];
      }
    }
    for(int i=0;i<2;i++){
      for(int j=0;j<n;j++){
	visited[i][j]=false;
      }
    }
    int count1=jump(0, 0, 0);
    for(int i=0;i<2;i++){
      for(int j=0;j<n;j++){
	visited[i][j]=false;
      }
    }
    int count2=jump(0, 1, 0);
    if(count1==-1 && count2==-1) cout << "NA" << endl;
    else if(count1<=count2) cout << count1 << endl;
    else cout << count2 << endl;
  }
  return 0;
}

int jump(int count, int b, int h){
  if(bill[b][h]==1){
    while(1){
      if(h==n-1) break;
      if(bill[b][h+1]!=1) break;
      h++;
    }
  }
  else if(bill[b][h]==2){
    while(1){
      if(h==0) break;
      if(bill[b][h]!=2) break;
      h--;
    }
  }

  if(visited[b][h]) return -1;
  visited[b][h]=true;
  
  if(h==n-1) return count;
  if(b==1) b=0;
  else b=1;
  if(h==n-2) return jump(count+1, b, h+1);
  return jump(count+1, b, h+2);
}

Measured memory_bytes: 0
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
#define bn(x) ((1<<x)-1)
#define newline puts("")
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,const vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;



int main() {
  int n,a,b;
  scanf("%d%d%d",&n,&a,&b);
  a -= b;
  vi d(n);
  cin>>d;
  int l = 0, r = INF;
  while (l+1<r) {
    ll c = (l+r)>>1;
    ll t = 0;
    rep(i,n) {
      ll x = max(d[i]-c*b,0ll);
      ll s = (x+a-1)/a;
      t += s;
    }
    if (t <= c) r = c; else l = c;
  }
  cout<<r<<endl;
  return 0;
}






















Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	while(cin >> n >> m, n, m){
		vector<int> h(n + 1), w(m + 1);
		h[0] = 0; w[0] = 0;
		rep(i, 1, n + 1) cin >> h[i];
		rep(i, 1, m + 1) cin >> w[i];
		rep(i, 1, n + 1) h[i] += h[i - 1];
		rep(i, 1, m + 1) w[i] += w[i - 1];
		vector<int> hh, ww;
		rep(i, 0, n + 1){
			rep(j, i + 1, n + 1){
				hh.push_back(h[j] - h[i]);
			}
		}
		rep(i, 0, m + 1){
			rep(j, i + 1, m + 1){
				ww.push_back(w[j] - w[i]);
			}
		}
		sort(all(hh));
		sort(all(ww));
		int ans = 0;
		rep(i, 0, hh.size()){
			ans += upper_bound(all(ww), hh[i]) - lower_bound(all(ww), hh[i]);
		}		
		cout << ans << endl;
	}
}


Measured memory_bytes: 36964
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;

using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}
ll mod = 1e9 + 7;
int main() {
	ll N;
	cin >> N;
	vector<ll> A(N+5);
	A.at(0) = 1;
	A.at(1) = 0;
	A.at(2) = 0;
	for (ll i = 3; i < N + 1; i++) {
		A.at(i) = A.at(i - 1) + A.at(i - 3);
		A.at(i) %= mod;
	}
	cout << A.at(N) << endl;
}

Measured memory_bytes: 3628
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <math.h>
#include <string>
#define ll long long
#define ull unsigned long long
#define make(type,x) type x; cin>>x
#define make2(type,x,y) type x,y; cin>>x>>y
#define fr(x,y) for(long long x=0;x<y;x++)
#define makevec(x,y,n) vector <x> y(n); for(ll i=0;i<n;i++) cin>>y[i]
#define M (ll)1000000007
#define MM (ll) 1e8
#define INF (ll) 1e18

# define IOS ios_base::sync_with_stdio(false); cin.tie(NULL)

using namespace std;

template <typename T>
T modpow(T base, T exp, T modulus) {
  base %= modulus;
  T result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}
bool sortbysec(const pair <ll,ll> &a,const pair <ll,ll> &b){
    return a.second<b.second;
}

struct cmp {
	bool operator() (const pair<int, int> &a, const pair<int, int> &b) const {
		int lena = a.second - a.first + 1;
		int lenb = b.second - b.first + 1;
		if (lena == lenb) return a.first < b.first;
		return lena > lenb;
	}
};


struct c_h {
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        x ^= FIXED_RANDOM;
        return x ^ (x >> 16);
    }
};

ll calcpow(ll x, ll y)
{
    ll temp;
    if(y == 0)
        return 1;
    temp = calcpow(x, y / 2);
    if (y % 2 == 0)
        return temp * temp;
    else
    {
        if(y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b,a%b);

}
ll egcd(ll a, ll b, ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1;
    ll y1;
    ll g=egcd(b,a%b,x1,y1);
    x=y1;
    y=x1-y1*(a/b);
    return g;
}


bool isprime(ll a){
bool flag=1;
for(ll i=2;i*i<=a;i++){
    if(a%i==0) {flag=0; break;}
}
return flag;
}

ll dx8[8]={1,0,-1,0,1,-1,1,-1};
ll dy8[8]={0,1,0,-1,1,-1,-1,1};
ll dx4[4]={0,0,1,-1};
ll dy4[4]={1,-1,0,0};



int main(){
    IOS;
    double ans=0;
    make2(ll,n,k);
    for(ll i=1;i<=n;i++){
        if(i>=k) ans+=1.0/(double)n;
        else{
            ll p=ceil((double)log2((double)k/(double)i));
            ans+=1.0/(n*calcpow(2ll,p));
        }
    }
    cout<<setprecision(10)<<ans<<endl;


    return 0;
}


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

using namespace std;
using ll =long long;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//Write From this Line

int main()
{
	int K;
	cin >> K;
	string s;
	cin >> s;

	if(K >= s.size()) cout << s << endl;
	else cout << s.substr(0,K) <<"..." << endl;
}


Measured memory_bytes: 3588
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    cout << fixed << setprecision(10);
    deque<char> deq;
    string s;
    cin >> s;
    for(auto u : s){
        deq.push_back(u);
    }
    int q;
    cin >> q;
    int rev = 0;
    rep(i,q){
        int t;
        cin >> t;
        if(t == 1) rev ^= 1;
        else{
            int f;
            char ss;
            cin >> f >> ss;
            if(f == 1){
                if(rev == 1) deq.push_back(ss);
                else deq.push_front(ss);
            }else{
                if(rev == 1) deq.push_front(ss);
                else deq.push_back(ss);
            }
        } 
    }
    /*
    cout << "end" << endl;
    for(auto u : deq) cout << u << endl;
    cout << endl;*/
    if(rev == 1){
        reverse(deq.begin(),deq.end());
    }
    for(auto u : deq) cout << u;
    cout << endl;
    return 0;
}

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

int main()
{
    int a[4],k;
    while(cin>>a[0]>>a[1]>>a[2]>>k)
    {
        sort(a,a+3);
        int t=a[0]+a[1];
        for(int i=1;i<=k;i++){
            a[2]*=2;
        }
        t+=a[2];
        cout<<t<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define PI 3.14159265
#define seive_len 1000001

bool seive[seive_len];
int primeSeive[seive_len];

typedef long long int lli;

lli gcd(lli a, lli b) {
  if(b == 0)
    return a;
  return gcd(b, a%b);
}

lli lcm(lli a, lli b) {
  lli gcd_ = gcd(a, b);
  lli lcm_ = (a*b)/gcd_;
  return lcm_;
}

lli fastPower(lli a, lli b) {
  lli res=1;
  while(b > 0) {
    if(b&1)
      res *= a;
    a *= a;
    b >>= 1;
  }
  return res;
}

lli fastPowerM(lli a, lli b, lli mod) {
  a %= mod;
  lli res = 1;
  while(b) {
    if(b%2 == 1)
      res = (res*a)%mod;
    a = (a*a)%mod;
    b >>= 1;
  }
  return res;
}

void multiply(lli a[][2], lli b[][2], int mod) {
  int res[2][2];
  memset(res, 0, sizeof(res));
  for(int i=0;i<2;i++) {
    for(int j=0;j<2;j++) {
      for(int k=0;k<2;k++) {
        res[i][j] += a[i][k]*b[k][j]%mod;
      }
    }
  }
  for(int i=0;i<2;i++)
    for(int j=0;j<2;j++)
      a[i][j] = res[i][j];
}

void matrixExpo(lli a[][2], lli n, int mod) {
  if(n == 0 || n == 1)
    return;
  lli b[][2] = {{1,1}, {1,0}};
  matrixExpo(a, n/2, mod);
  multiply(a, a, mod);
  if(n%2)
    multiply(a, b, mod);
}

void makeSeive() {
  for(int i=2;i*i<=seive_len;i++) {
    if(seive[i]) {
      for(int j=i*i;j<=seive_len;j+=i)
        seive[j] = false;
    }
  }
}

void makePrimeSeive() {
  for(int i=1;i<seive_len;i++)
    primeSeive[i] = i;
  for(int i=4;i<seive_len;i+=2)
    primeSeive[i] = 2;
  for(int i=3;i*i<seive_len;i++) {
    if(primeSeive[i] == i) {
      for(int j=i*i;j<seive_len;j+=i) {
        if(primeSeive[j] == j)
          primeSeive[j] = i;
      }
    }
  }
}

bool isPrime(lli n) {
  for(int i=2;i<=sqrt(n);i++) {
    if(n%i == 0)
      return false;
  }
  return true;
}

void getInput(vector<lli>& a, int n) {
  lli x;
  for(int i=0;i<n;i++) {
    cin >> x;
    a.push_back(x);
  }
}

void replaceSpace(string& s) {
  for(int i=0;s[i];i++) {
    if(s[i] == ' ')
      s.replace(i, 1, "%20");
  }
}


void testCase() {
  lli i, d, t, s;
  cin >> d >> t >> s;
  if(t*s >= d)
    cout << "Yes";
  else
    cout << "No";
}

int main() {
	int t=1;
	// cin >> t;
  // makePrimeSeive();
  // FILE* fp;
  // fp = fopen("out.txt", "w");
	for(int i=1;i<=t;i++) {
    // fprintf(fp, "Case #%d:\n", i);
    // cout << "Case #" << i << ":" << ' ';
		testCase();
    cout << '\n';
	}
	return 0;
}


Measured memory_bytes: 3680