akhauriyash/Code-Regression huggingface dataset:
def gcd(a, b):
  if b == 0:
    return a
  else:
    return gcd(b, a % b)
import collections
K = int(input())
ans = 0
cnt = collections.defaultdict(int)
# count the number of combination of a, b
for a in range(1, K + 1):
  for b in range(1, K + 1):
    cnt[gcd(a, b)] += 1
for c in range(1, K + 1):
  for gcd_of_ab in cnt.keys():
    ans += gcd(gcd_of_ab, c) * cnt[gcd_of_ab]
print(ans)

Measured memory_bytes: 9452
#include <stdio.h>
int main(){
	int N,K;
	scanf("%d %d",&N,&K);
	double sum=0;
	for(int i=1;i<=N;i++){
		int num=i;
		int cnt=0;
		while(num<K){
			num*=2;
			cnt++;
		}
		sum+=1/(double)(1<<cnt);
	}
	printf("%.15lf",sum/(double)N);
}

Measured memory_bytes: 128
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  cout << (d == 1) << endl;
  return 0;
}

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

int main(){
    string s;
    cin>>s;
    vector<int> a(s.size(),0);
    vector<bool> b(s.size(),false);
    for(int i=0;i<s.size()-1;i++){
        if(s[i]=='R'&&s[i+1]=='L'){
            b[i+1]=true;
        }
    }
    int r_count=0,l_count=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='R'){
            r_count++;
        }else{
            if(b[i]){
                int j=i;
                while(s[j]=='L'){
                    l_count++;
                    if(j==s.size()){
                        break;
                    }
                    j++;
                }
                int l=r_count/2+(l_count+1)/2;
                a[i]=l;
                int r=r_count+l_count-l;
                a[i-1]=r;
                r_count=0;
                l_count=0;
            }
        }
    }
        
    for(int i=0;i<s.size();i++){
        cout<<a[i];
        if(i==s.size()-1){
            cout<<endl;
        }else{
            cout<<' ';
        }
    }

}

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

int main() {
    int n,k; cin >> n >> k;
    vector<int> a(n);
    rep(i,n) cin >> a[i];

    vector<vector<ll>> dp(n + 1,vector<ll>(k + 2,0));
    rep(i,n + 1) dp[i][1] = 1;

    rep(i,n) {
        int m = a[i];
        rep(j,k + 1) {
            dp[i][j + 1] += dp[i][j];
            dp[i][j + 1] %= MOD;
        }
        for (int j = 1; j < k + 1; j ++ ) {
            dp[i + 1][j + 1] = dp[i][j + 1] - dp[i][max(j - m,0)] + MOD;
            dp[i + 1][j + 1] %= MOD;
        }
    }

    cout << dp[n][k + 1] <<  endl;
}

Measured memory_bytes: 80256
#include <bits/stdc++.h>
using namespace std;
const int N = 105;

int main() {
    int n , m , d ;
    cin >> n >> m >> d;
    if (d % 2 == 1) {
        for (int i = 0 ; i < n ; ++ i) {
            for (int j = 0 ; j < m ; ++ j) {
                putchar("RG"[(i + j) & 1]);
            }
            puts("");
        }
    } else {
        int l = d + d;
        for (int i = 0 ; i < n ; ++ i) {
            for (int j = 0 ; j < m ; ++ j) {
                int p = (i + j) % l;
                int w = (i - j % l + l) % l;
                putchar("RGBY"[(p < d) * 2 + (w < d)]);
            }
            puts("");
        }
    }


}


Measured memory_bytes: 512
n,m,k=map(int,input().split())
al=list(map(int,input().split()))
bl=list(map(int,input().split()))
a=[0]
b=[0]
for i in range(n):
    a.append(a[i]+al[i])
for i in range(m):
    b.append(b[i]+bl[i])
ans=0
j=m
for i in range(n+1):
    if a[i]>k:
        break
    while b[j]>k-a[i]:
        j-=1
    ans=max(ans,i+j)
print(ans)


Measured memory_bytes: 47372
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define FOR(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REVERSE(c) reverse(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define LB(c, x) lower_bound(c.begin(), c.end(), x)
#define UB(c, x) upper_bound(c.begin(), c.end(), x)
#define LI(c, x) distance(c.begin(), LB(c, x))
#define UI(c, x) distance(c.begin(), UB(c, x))

// functions
template <class T> T ceil(T a, T b) {
    return (a + b - 1) / b;
}
template <class T> T round(T a, T b) {
    return (a + b / 2) / b;
}
template <class T> T gcd(T a, T b) {
    return b ? gcd(b, a % b) : a;
}
template <class T> T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}
template <class T> bool amax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Q;
    string s;
    cin >> N >> Q >> s;
    vector<char> t(Q), d(Q);
    REP(i, Q) {
        cin >> t[i] >> d[i];
    }
    int res = N;
    // 左側に落ちるゴーレムの中で最も右にあるもの
    int l = 0, r = N - 1;
    while (l <= r) {
        int mid = (l + r) / 2, now = mid;
        REP(i, Q) {
            if (s[now] != t[i]) {
                continue;
            }
            if (d[i] == 'L') {
                now--;
            } else {
                now++;
            }
            if (now < 0) {
                break;
            }
        }
        if (now < 0) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    res -= l;
    // 右側に落ちるゴーレムの中で最も左にあるもの
    l = 0, r = N - 1;
    while (l <= r) {
        int mid = (l + r) / 2, now = mid;
        REP(i, Q) {
            if (s[now] != t[i]) {
                continue;
            }
            if (d[i] == 'L') {
                now--;
            } else {
                now++;
            }
            if (now >= N) {
                break;
            }
        }
        if (now >= N) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    res -= N - l;
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 976
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define ArraySizeOf(array)     (sizeof(array) / sizeof(array[0]))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define REV(i,n) for(int i=n-1;i>0;i--)
#define _GLIBCXX_DEBUG
int INF = 1e9 + 7;
unsigned NthDayOfWeekToDay(unsigned n, unsigned dow, unsigned dow1)
{
    unsigned day;
    if (dow < dow1) dow += 7;
    day = dow - dow1;
    day += 7 * n - 6;
    return day;
}
unsigned DayToWeekNumber(unsigned day)
{
    return (day - 1) / 7 + 1;
}
unsigned AnotherDayOfWeek(unsigned day, unsigned day0, unsigned dow0)
{
    return (dow0 + 35 + day - day0) % 7;
}
using namespace std;
signed main() {
    int a, b; cin >> a >> b;
    cout << (a % (b * 2 + 1) == 0 ? a / (b * 2 + 1) : a / (b * 2 + 1) + 1) << endl;
}

Measured memory_bytes: 3592
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
int main(void){
    int x,ans=0;
    scanf("%d",&x);
    while (x>=500){
        x-=500;
        ans+=1000;
    }
    while (x>=5){
        x-=5;
        ans+=5;
    }
    printf("%d",ans);
    return 0;
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

// Problem Specific Parameter:

ll dp[55][2];

int main(void){
	int n,p;
	cin >> n >> p;
	
	dp[0][0]=1LL;
	rep(i,n){
		int a;
		cin >> a;
		rep(j,2){
			const int nj = (j+a)%2;
			dp[i+1][j]+=dp[i][j];
			dp[i+1][nj]+=dp[i][j];
		}
	}

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

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int nex[26];
bool app[26],aft[26];
int main(){
	int n;
	cin>>n;
	for(int u=0;u<n;u++){
	string s;
	cin>>s;
	for(int i=0;i<26;i++)app[i]=false,nex[i]=114514,aft[i]=false;
	for(int i=0;i<s.size();i++){
		if(s[i]>='a'&&s[i]<='z')app[s[i]-'a']=true;
	}
	for(int i=0;i<s.size()-1;i+=3){
		if(s[i+1]=='-'){
			nex[s[i]-'a']=s[i+3]-'a';
			aft[s[i+3]-'a']=true;
		}
		else{
			nex[s[i+3]-'a']=s[i]-'a';
			aft[s[i]-'a']=true;
		}
	}
	int t=0;
	while(true){
		if(app[t]&&!aft[t])break;
		t++;
	}
	while(true){
		char z=t+'a';
		cout<<z;
		t=nex[t];
		if(t==114514)break;
	}
	cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()		//sort(all(vi S)) sort(all(string S))
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }

using P = pair<int, int>;		//P.first, P.second
typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9+7;
const int INF = 1e9;

int main() {
	int A,B,C;
	cin>>A>>B>>C;
	int ans;
	if(B + C <= A){
		ans = 0;
	}
	else{
		ans = C - (A-B);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007
#define endl "\n"
typedef long long ll;
using namespace std;

const int N = 55;
pair<int, int> xs[N], ys[N];
int np[N][N][N];
int n, kkk;

int main() {
    ios::sync_with_stdio(false);
    cout.precision(10);
    cin >> n >> kkk;
    for(int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        xs[i] = make_pair(x, y);
        ys[i] = make_pair(y, x);
    }
    sort(xs + 1, xs + n + 1);
    sort(ys + 1, ys + n + 1);
    for(int i = 1; i <= n; i++) {
        swap(ys[i].first, ys[i].second);
    }
    ll ans = 1LL << 62;
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j++) {
            for(int k = 1; k <= n; k++) {
                for(int p = 1; p <= n; p++) {
                    int x = xs[p].first, y = xs[p].second;
                    if(x >= xs[i].first && x <= xs[j].first && y == ys[k].second) {
                        np[i][j][k]++;
                    }
                }
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j++) {
            for(int k = 1; k <= n; k++) {
                int cur = 0;
                for(int l = k; l <= n; l++) {
                    cur += np[i][j][l];
                    ll area = (ll)(xs[j].first - xs[i].first) * (ys[l].second - ys[k].second);
                    if(cur >= kkk && area < ans) {
                        ans = area;
                        break;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
typedef long long int ll;
using namespace std;
#define P 1000000007
#define rep(i,n) for(i=0;i<n;++i)
#define repp(i,a,n) for(i=a;i<n;++i)
#define repr(i,a,n) for(i=a;i>=n;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

vector<ll> adj,pos,used;

ll temp,k,v,flag;

void dfs(ll u)
{
    temp++;
    if(k==temp)
    {
        cout << u ;
        flag=1;
        return ;
    }
    used[u]=1;
    pos[u]=temp;
    if(used[adj[u]]==1)
    {
        v=u;
        return ;
    }
    dfs(adj[u]);
    return ;
    
}

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    temp=0;
    ll t,m,n,i,f=0,j,ans=0;
    temp=0;
    cin >> n >> k ;
    adj.resize(n+1);
    adj.resize(n+1);
    used.assign(n+1,0);
    pos.resize(n+1);
    rep(i,n) cin >> adj[i+1];
    pos[1]=0;
    used[1]=1;
    flag=0;
    dfs(adj[1]);
    if(flag==1)
    {
        return 0;
    }
    k-=pos[v];
    //cout << v << " " << k << endl ;
    ll cylength=pos[v]-pos[adj[v]]+1;
    t = k%cylength ;
    //t+=pos[adj[v]];
    //v=adj[v];
    for(i=0;i<t;++i)
    {
        v=adj[v];
    }
    cout << v ;
    return 0;
}

Measured memory_bytes: 7892
#include<stdio.h>

int main(){
  int a,b,c,n,i,r;

  do{
    scanf("%d %d %d",&a,&b,&c);
    if(a==0&&b==0&&c==0) break;
    a*=a; b*=b; c*=c;
    scanf("%d",&n);
    for(i=0;i<n;i++){
      scanf("%d",&r);
      r*=r; r*=4;
      if((a+c)<r||(a+b)<r||(b+c)<r){
	printf("OK\n");
      }else{
	printf("NA\n");
      }
    }
  }while(1);
  return 0;
}

Measured memory_bytes: 0
import Data.List

factorize :: Int -> [Int]
factorize n = aux n 2
  where
    aux 1 _ = []
    aux n k
      | n `mod` k == 0 = k : aux (n`div`k) k
      | otherwise = aux n (k+1)


main :: IO ()
main = do
  n <- readLn :: IO Int

  let t = map (\xs -> (head xs, length xs)) $ group $ sort $ concat $ map factorize [1..n]

  let
    d2 = filter ((>=2) . snd) t
    d4 = filter ((>=4) . snd) t
    d14 = filter ((>=14) . snd) t
    d24 = filter ((>=24) . snd) t
    d74 = filter ((>=74) . snd) t
    
  print $ length d74 +
    (length $ concat $ map (\(x,_) -> filter ((/=x) . fst) d2) d24) +
    (length $ concat $ map (\(x,_) -> filter ((/=x) . fst) d4) d14) +
    (length $ concat $ map (\(x,y) -> filter ((\a -> a/=x && a/=y) . fst) d2) [(x,y) | (x,_)<-d4, (y,_)<-d4, x<y])



Measured memory_bytes: 636
#include <bits/stdc++.h>
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 long long INF = 1LL<<60;

int main() {
    int H, N;
    cin >> H >> N;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];
    
    vector<vector<long long>> dp(N+1, vector<long long>(H+1, INF));
    dp[0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= H; ++j) {
            chmin(dp[i+1][j], dp[i][j]);
            if (j-A[i] >= 0) chmin(dp[i+1][j], dp[i+1][j-A[i]] + B[i]);
            else chmin(dp[i+1][j], dp[i][0] + B[i]);
        }
    }
    cout << dp[N][H] << endl;
}

Measured memory_bytes: 78592
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(ll i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using ll = int64_t;
using vecint = vector<ll>;
constexpr ll MOD = 1000000007;

ll pm(ll x, ll i) {
  if (i == 0) return 1;
  if ((i % 2) == 1) return (pm(x, i-1) * x) % MOD;
  ll h = pm(x, i/2);
  return (h * h) % MOD;
}

int main()
{
  string s,t;
  cin>>s>>t;
  int n = s.size();
  int m = t.size();
  stringstream ss;
  REP(i,(m+n-1)/n+1) {
    ss<<s;
  }
  string ks = ss.str();
  ll h = 0, th = 0;
  REP(i,m) {
    h *= 31415;
    h += ks[i];
    h %= MOD;
    th *= 31415;
    th += t[i];
    th %= MOD;
  }
  ll coeff = pm(31415, m);
  vector<bool> v(n, false);
  REP(i,n) {
    if (h == th) {
      v[i] = true;
    }
    h *= 31415;
    h %= MOD;
    h += (MOD - ks[i]) * coeff;
    h %= MOD;
    h += ks[i+m];
    h %= MOD;
  }
  vecint len(n, -1);
  bool ok = false;
  REP(i,n) {
    if (len[i] < 0) {
      if (!v[i]) {
        len[i] = 0;
        continue;
      }
      FOR(j,1,n+1) {
        ll idx = (i+j*m) % n;
        if (len[idx] >= 0) {
          REP(k,j) {
            ll idx2 = (i+k*m) % n;
            len[idx2] = len[idx] + (j - k);
          }
          break;
        } else if (!v[idx]) {
          REP(k,j+1) {
            ll idx2 = (i+k*m) % n;
            len[idx2] = j - k;
          }
          break;
        } else if (idx == i) {
          ok = true;
          break;
        }
      }
      if (ok) break;
    }
  }
  if (ok) {
    cout<<-1<<endl;
  } else {
    cout<<*max_element(ALL(len))<<endl;
  }
  return 0;
}


Measured memory_bytes: 8204
N=int(input())
A=list(map(int,input().split()))
sumA=0
sumB=[0]
for i in range(N):
    sumB.append(sumB[i]+A[i])
    i=i+1
for j in range(N-1):
    sumA=sumA+(A[j]*(sumB[N]-sumB[j+1]))%(10**9+7)
    j=j+1
print(sumA%(10**9+7))

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

int main() {
    int a,b,m;
    cin>>a>>b>>m;
    
    int min_a = 100001;
    int min_b = 100001;
    int min_sum = 200002;
    int x[a],y[b],za[m],zb[m],zc[m];
    
    for(int i=0;i<a;++i){
        cin>>x[i];
        min_a = min(min_a,x[i]);
    }

    for(int i=0;i<b;++i){
    cin>>y[i];
    min_b = min(min_b,y[i]);
    }
    
    for(int i=0;i<m;++i){
        cin>>za[i]>>zb[i]>>zc[i];
        min_sum = min(min_sum, x[za[i]-1]+y[zb[i]-1]-zc[i]);
    }
    
    min_sum = min(min_sum, min_a + min_b);
    
    cout<<min_sum<<endl;
    
	return 0;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
#define ll long long int
#define FF first
#define SS second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define pss printf
#define MOD 1000000007
#define INF 1e18
#define eps 0.00001
#define endl '\n'
#define debug(n1) cout<<n1<<endl
const int N = 1e5;  // limit for array size
ll n;  // array size

int main(){
	int k;cin>>k;
	if(k%2==0){
		cout<<(k/2)*(k/2)<<endl;
	}
	else{
		cout<<(k/2)*(k/2+1)<<endl;
	}
	return 0;
}

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

int main(void) {
	int N;
	scanf("%d", &N);
	vector<int> H(N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &H[i]);
	}
	bool ans = true;
	bool isLower = false;
	for (int i = 1; i < N; i++) {
		if (H[i - 1] - H[i] > 1) {
			ans = false;
			break;
		} else if (H[i - 1] - H[i] == 1) {
			if (isLower) {
				ans = false;
				break;
			}
			isLower = true;
		} else if (H[i - 1] - H[i] < 0){
			isLower = false;
		}
	}

	printf(ans ? "Yes" : "No");
	return 0;
}


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

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

    ll ans = 0;
    ans += b/x - a/x;
    if (a%x == 0) ans++;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define ll long long int
using namespace std;
//vec.back()
main()
{
  ll n;
  cin>>n;
  ll he[n]={0};
  ll dp[n]={0};
  for(ll i=0;i<n;++i)
  {
    cin>>he[i];
    if(i>1)
    {
      dp[i]=min((dp[i-2]+abs(he[i-2]-he[i])),(dp[i-1]+abs(he[i-1]-he[i])));
    }  
    else if(i==1) dp[1]=abs(he[1]-he[0]);            
  }
  cout<<dp[n-1];              
  
}

Measured memory_bytes: 1792
n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
a.append(-1)

count=1
ans=0

for i in range(0,n):
    if a[i+1]==a[i]:
        count += 1
    else:

        if count > a[i]:
            ans += count - a[i]
        elif count < a[i]:
            ans += count

        count = 1

print(ans)


Measured memory_bytes: 14084
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#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;
const double pi = acos(-1);
const double eps = 1e-10;

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

int main(){
    int n; cin>>n;
    vector<int> w(n), sumw(n+1, 0);
    for(int i=0; i<n; i++){
        cin>>w[i];
        sumw[i + 1] = sumw[i] + w[i];
    }

    int ans = 1e9;
    for(int i=1; i<n; i++){
        ans = min(ans, abs(sumw[n] - sumw[i] - sumw[i]));
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include<cstring>
#include<string>
#include<stack>
#include<math.h>
#include<stdlib.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
typedef pair<int, pii > piii;
typedef pair<double, double> pdd;
typedef pair<int, char> pic;
typedef priority_queue<pii, vector<pii>, greater<pii> > RPQ;
#define mk make_pair
#define INF (1 << 30)
#define INFL (1ll << 60ll)
#define mod 1000000007

int N, x[60], y[60], ans = INFL;

signed main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> x[i] >> y[i];
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            int p = x[i] - x[j];
            int q = y[i] - y[j];
            int res = 0;
            for(int k = 0; k < N; k++){
                int a = 1;
                for(int r = 0; r < N; r++){
                    if(x[k] - x[r] == p && y[k] - y[r] == q && k != r){
                        a = 0;
                    }
                }
                res += a;
            }
            ans = min(ans, res);
        }
    }
    cout << ans << endl;

    return 0;
}

/*

*/

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

/*
 * @title BinaryIndexedTree
 */
template<class Operator> class BinaryIndexedTree {
	using TypeNode = typename Operator::TypeNode;
	size_t depth;         
	size_t length;
	size_t num;
	vector<TypeNode> node;
public:
	
	//[0,N) constructed, inplace [0,1) + [1,N+1)
	//you can ignore inplace offset
	BinaryIndexedTree(const size_t num) : num(num) {
		for (depth = 1,length = 1; length < num; depth++,length *= 2);
		node.resize(length+1, Operator::unit_node);
	}
 
	//[idx,idx+1) update 
	void update(size_t idx, TypeNode var) {
		assert(0 <= idx && idx < length);
		for (++idx; idx <= length; idx += idx & -idx) node[idx] = Operator::func_node(node[idx],var);
	}

	//[0,idx) get
	TypeNode get(size_t idx) {
		TypeNode ret = Operator::unit_node;
		for (idx = min(length,idx); idx > 0; idx -= idx & -idx) ret = Operator::func_node(ret,node[idx]);
		return ret;
	}

	//return [0,length]
	int binary_search(TypeNode var) {
		if(!Operator::func_check(node.back(),var)) return num;
		TypeNode ret = Operator::unit_node;
		size_t off = 0;
		for(size_t idx = length; idx; idx >>= 1){
			if(off + idx <= length && !Operator::func_check(Operator::func_node(ret,node[off+idx]),var)) {
				off += idx;
				ret = Operator::func_node(ret,node[off]);
			}
		}
		return min(off,num);
	}

	void print() {
		cout << "{ " << get(1);
		for(int i = 1; i < length; ++i) cout << ", " << get(i+1);
		cout << " }" << endl;
	}
};

template<class T> struct NodePrefixSumPointAdd {
	using TypeNode = T;
	inline static constexpr TypeNode unit_node = 0;
	inline static constexpr TypeNode func_node(const TypeNode& l,const TypeNode& r){return l+r;}
	// Binary Search for first index where func_check is true
	inline static constexpr bool func_check(TypeNode nodeVal,TypeNode val){return val <= nodeVal;}
};

template<class TypeNode> struct NodeUpdatePrefixGcd {
	TypeNode unit_node = 0;
	TypeNode func_node(TypeNode l,TypeNode r){return ((r == 0) ? l : func_node(r, l % r));}
	// Binary Search for first index at where func_check is true
	bool func_check(TypeNode nodeVal,TypeNode var){return var == nodeVal;}
};

//verify https://atcoder.jp/contests/chokudai_S001/tasks/chokudai_S001_j
//verify https://atcoder.jp/contests/abc130/tasks/abc130_d

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int N,Q; cin >> N >> Q;
	BinaryIndexedTree<NodePrefixSumPointAdd<long long>> bit(N);
	for(int i=0;i<N;++i) {
		int a; cin >> a; bit.update(i,a);
	}
    while(Q--){
        int t,l,r; cin >> t >> l >> r;
        if(t) cout << bit.get(r)-bit.get(l) << "\n";
        else bit.update(l,r);
    }
    return 0;
}


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

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;

int main() {
    int X, A, B;
    cin >> X >> A >> B;
    cout << (X - A) % B << endl;
    return 0;
}

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

int m,n,summ,sumn,sum;


int main()
{
	scanf("%d%d",&m,&n);
	
	summ=(m-1)*m*0.5;
	sumn=(n-1)*n*0.5;
	
	sum=summ+sumn;
	
	printf("%d",sum);

	return 0;
}

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

public class Main {

	final static long MOD = 1000000007L;
	public static String[] Ws = null;
	public static int wsIndx = 0;
	public static BufferedReader in = null;
	public static ArrayList<int[]> list = new ArrayList<>();
	public static void main(String[] args) throws Exception {

		int N =nextInt();
		int M =nextInt();

		int[] a = new int[M];

		int[] b = new int[M+1];

		int now = -1;
		for(int i=0;i<M;i++){
			a[i]=nextInt();
			b[i]=a[i]-now-1;
			if(i!=0&&a[i]-1==a[i-1]){
				System.out.println(0);
				return;
			}
			now=a[i];
		}
		b[b.length-1]=N-now;

		long ans = 1;
		long[] dp = new long[N+2];
		Arrays.fill(dp, 0);
		dp[0]=1;
		dp[1]=1;
		for(int i=0;i<b.length;i++){

			for(int k=2;k<b[i];k++){
				dp[k]=dp[k-2]+dp[k-1];
				dp[k]%=MOD;
			}
			ans=ans*dp[b[i]-1]%MOD;
		}
		System.out.println(ans);
	}


	public static String[] toStringArray(String s) {
		String[] tmp = new String[s.length()];
		char[] c = s.toCharArray();
		for (int i = 0; i < tmp.length; i++) {
			tmp[i] = String.valueOf(c[i]);
		}
		return tmp;
	}

	public static String concatStringArray(String[] s){
		StringBuffer sb = new StringBuffer();
		for(String x:s){
			sb.append(x);
		}
		return sb.toString();
	}

	public static void check() throws Exception{
		if(in == null){
			in = new BufferedReader(new InputStreamReader(System.in));
		}
		if(Ws==null || Ws.length<=wsIndx){
			Ws = in.readLine().split(" ");
			wsIndx=0;
		}
	}
	public static int nextInt()throws Exception{
		check();
		return Integer.parseInt(Ws[wsIndx++]);
	}

	public static long nextLong()throws Exception{
		check();
		return Long.parseLong(Ws[wsIndx++]);
	}

	public static String nextString()throws Exception{
		check();
		return Ws[wsIndx++];
	}

	public static int[] nextInts()throws Exception{
		check();
		int[] tmp = new int[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Integer.parseInt(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static long[] nextLongs()throws Exception{
		check();
		long[] tmp = new long[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Long.parseLong(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static String[] nextStrings()throws Exception{
		check();
		wsIndx=Ws.length;
		return Ws;
	}


}

Measured memory_bytes: 29908
import java.io.*;

class Main{
	public static void main(String args[])throws IOException{
		BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
		String[] str = buf.readLine().split(" ");
		String direction = buf.readLine();
		int[] num = new int[6];

		for(int i=0; i<6; i++){
			num[i] = Integer.parseInt(str[i]);
		}
		Saikoro sk = new Saikoro(num,direction);
		System.out.println(sk.getSide());
	}	
}
class Saikoro{
	char c;
	int tmp;
	int value=0;

	public Saikoro(int[] num, String direction){
		for(int i=0; i<direction.length(); i++){
			c = direction.charAt(i);
			switch (c) {
	        case 'N':
	            tmp = num[0];
	            num[0] = num[1];
	            num[1] = num[5];
	            num[5] = num[4];
	            num[4] = tmp;
	            
	            break;
	        case 'W':
	        	tmp = num[0];
	            num[0] = num[2];
	            num[2] = num[5];
	            num[5] = num[3];
	            num[3] = tmp;         
	            break;
	        case 'E':
	        	tmp = num[0];
	            num[0] = num[3];
	            num[3] = num[5];
	            num[5] = num[2];
	            num[2] = tmp;
	            break;
	        case 'S':
	        	tmp = num[0];
	            num[0] = num[4];
	            num[4] = num[5];
	            num[5] = num[1];
	            num[1] = tmp;
	            break;
	        default:
			}
			value = num[0];
		}
	}
	public int getSide(){
		return value;
	}

}

Measured memory_bytes: 24476
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#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;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const ll INFLL = 1001001001001001001;  // > 10^18
const int MOD = (int)1e9 + 7;
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

int main() {

    int x,y; cin >>x>>y;

    if (x == 2 || y == 2) {
        cout << "No" << endl;
    } else if ( x == 4 || x == 9 || x == 6 ||x == 11) {
        if (y == 4 || y == 9 || y == 6 ||y == 11) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        } 
    } else if (y == 4 || y == 9 || y == 6 ||y == 11) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    } 

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define rrep(i,a) for(int i=(int)a-1;i>=0;--i)
#define REP(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RREP(i,a,b) for(int i=(int)a-1;i>=b;--i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;
typedef std::vector<long long> vl;
typedef std::vector<std::vector<long long>> vvl;
#define out(x) cout<<x<<"\n";
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;
 
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;
}


ll gcd(ll n, ll m) {
    ll tmp;
    while (m!=0) {
        tmp = n % m;
        n = m;
        m = tmp;
    }
    return n;
}
 
ll lcm(ll n, ll m) {
    return abs(n) / gcd(n, m)*abs(m);//gl=xy
}

using namespace std;

void solve()
{
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int t = 0;
	while (1)
	{
		if(t==0){
			c -= b;
			if(c<=0){
				cout << "Yes";
				return;
			}
		}
		else{
			a -= d;
			if(a<=0){
				cout << "No";
				return;
			}
		}
		t ^= 1;
	}
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(15);
    solve();
    return 0;
}


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

using lli = int64_t;
using vi = vector<lli>;

lli f(vi& v, int n, int fl)
{
    lli ans = 0;

    for(lli i = 0, s = 0; i < n; i++, fl = !fl)
    {
        s += v[i];

        if(!fl && s >= 0) ans += s - (-1), s = -1;
        else
        if(fl && s <= 0) ans += 1 - s, s = 1;
    }

    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);

    int n; cin >> n;

    vi v(n);

    for(int i = 0; i < n; i++) cin >> v[i];

    lli ans = min(f(v, n, 0), f(v, n, 1));

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

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main() {
    ll t1,t2,a1,a2,b1,b2;
    cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;
    ll c1=t1*a1,c2=t1*b1,d1=t2*a2,d2=t2*b2;
    if (c1+d1==c2+d2){
        cout << "infinity" << endl;
        return 0;
    }
    if (c1>c2){
        if (c1+d1>c2+d2){
            cout << 0 << endl;
            return 0;
        }
        ll p=c2+d2-c1-d1,m=c1-c2;
        ll ans=(m/p)*2+1;
        if (m%p==0) ans--;
        cout <<  ans << endl;
    }
    else{
        if (c1+d1<c2+d2){
            cout << 0 << endl;
            return 0;
        }
        ll p=c1+d1-c2-d2,m=-c1+c2;
        ll ans=(m/p)*2+1;
        if (m%p==0) ans--;
        cout <<  ans << endl;
    }
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		sc.close();

		if (a + b + c >= 22) {
			System.out.println("bust");
		} else {
			System.out.println("win");
		}
	}
}


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

int main()
{
    int n=0,m=0;
    cin >> n >> m;
    int A[n][m]={}, b[m]={}, Ans[n]={};
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; j++){
            cin >> A[i][j];
        }
    }
    for(int i=0;i<m;++i){
        cin >> b[i];
    }
    
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; j++){
            Ans[i] += A[i][j] * b[j];
        }
    }
    
    for(int i=0; i<n; ++i){
        cout << Ans[i] << endl;
    }
}



Measured memory_bytes: 3128
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}
 
void No(){
	cout<<"No"<<endl;
	exit(0);
}

int N;
vector<int> G[100100];
ll dp[100100][2];

void dfs(int u, int v) {
    dp[u][0] = 1LL;
    dp[u][1] = 1LL;
    for(auto to : G[u]) {
        if(to == v) continue;
        dfs(to, u);
        dp[u][0] = dp[u][0] * (dp[to][0] + dp[to][1]) % mod;
        dp[u][1] = dp[u][1] * dp[to][0] % mod;
    }
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
    cin >> N;
    rep(i, N - 1) {
        int x, y; cin >> x >> y;
        x --; y --;
        G[x].pb(y);
        G[y].pb(x);
    }
    dfs(0, -1);
    ll ans = dp[0][0] + dp[0][1];
    cout << (ans % mod + mod) % mod << endl;
	return 0;
}

Measured memory_bytes: 14208
/*ex4_3
series2*/

# include <stdio.h>
int getHeight(int east,int west);
int main(void){
    //各文字の箱を作って読み取り
    int east,west;
    scanf("%d %d", &east,&west);
    int height=getHeight(east,west);

    printf("%d\n",height);
    return 0;
}

int getHeight(int east,int west){
   //diffは西側の塔の図っている部分の西からの位置を示す
    int diff=west-east-1;
    //西側の本来の塔の高さは1からdiffを足したもの
    int west_height = diff*(diff+1)/2;
    return west_height-east;
}


Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main(){
    int x,y,mem;
    for (int i = 0; i < 4000; i++){
        cin >> x >> y;
        if(x>y){
            mem = x;
            x = y;
            y = mem;
        }else if(x==0 && y==0){
            break;
        }
        cout << x << " " << y << endl;
    }
}



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

int main() {
	int a, b, c, A, B, C;
	cin >> a >> b >> c;
	int x[3] = { A,B,C };
	// a = max //
	if (a < b && a < c) {
		A = a;
		if (b < c) {
			B = b;
			C = c;
		}
		else {
			B = c;
			C = B;
		}
	}
	else {
		// b = max //
		if (b < a && b < c) {
			A = b;
			if (a < c) {
				B = a;
				C = c;
			}
			else {
				B = c;
				C = a;
			}
		}
		// c = max //
		else {
			A = c;
			if (a < b) {
				B = a;
				C = b;
			}
			else {
				B = b;
				C = a;
			}
		}
	}
	cout << A << " " << B << " " << C << endl;
	return 0;
}

Measured memory_bytes: 3120
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <bitset>
using namespace std;
typedef long long ll;
const int maxn = 105;

int f[maxn][10];
int n,a[maxn];

int main() {
#ifdef suiyuan2009
  freopen("in.cpp","r",stdin);
#endif
  cin>>n;
  for(int i=1; i<=n; i++)cin>>a[i];
  memset(f,-1,sizeof(f));
  f[0][0]=0;
  for(int i=0; i<n; i++)
    for(int j=0; j<10; j++) {
      if(f[i][j]==-1)continue;
      f[i+1][j]=max(f[i+1][j],f[i][j]);
      f[i+1][(j+a[i+1])%10]=max(f[i+1][(j+a[i+1])%10],f[i][j]+a[i+1]);
    }
  int ret=0;
  for(int i=1; i<10; i++)ret=max(ret,f[n][i]);
  cout<<ret<<endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int x = sc.nextInt();
		int t = sc.nextInt();
		int m=0;
		int ans=0;
		
		while(0<N) {
			N = N - x;
			m++;
		}
		ans = t*m;
		System.out.println(ans);
		sc.close();
		
	}

}


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

using namespace std;
vector<int> prime;
bool isPrime[250000];

void PrimeCalc()
{
	memset(isPrime, 1, sizeof(isPrime));
	isPrime[0] = isPrime[1] = false;
	for(int i = 2; i < 250000; ++i)
	{
		if(isPrime[i])
		{
			prime.push_back(i);
			for(int j = 2 * i; j < 250000; j += i)
			{
				isPrime[j] = false;
			}
		}
	}
}

void solve()
{
	PrimeCalc();
	int n;
	while(cin >> n, n)
	{
		int ans = 0;
		int pos = 0;
		while(prime[pos] < n + 1)
		{
			++pos;
		}
		for(int i = pos; prime[i] <= 2 * n; ++i)
		{
			++ans;
		}
		cout << ans << endl;
	}
}

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

Measured memory_bytes: 1592
using System;

class Program
{
  Scanner cin;

  void myon()
  {
    cin = new Scanner();

    int N = cin.nextInt();
    int Q = cin.nextInt();

    var uf = new UnionFind(N);
    for (int i = 0; i < Q; i++)
    {
      int T = cin.nextInt();
      int X = cin.nextInt();
      int Y = cin.nextInt();

      if (T == 0)
      {
        uf.unite(X, Y);
      }
      else
      {
        Console.WriteLine(uf.is_same(X, Y) ? 1 : 0);
      }
    }
  }

  static void Main(string[] args)
  {
    new Program().myon();
  }
}


class UnionFind
{
  int[] data;

  public UnionFind(int sz)
  {
    data = new int[sz];
    for (int i = 0; i < sz; i++)
    {
      data[i] = -1;
    }
  }

  public bool unite(int x, int y)
  {
    x = find(x);
    y = find(y);

    if (x == y) return false;

    if (data[x] > data[y])
    {
      int buf = x;
      x = y;
      y = buf;
    }

    data[x] += data[y];
    data[y] = x;

    return true;
  }

  public int find(int k)
  {
    if (data[k] < 0) return k;
    return data[k] = find(data[k]);
  }

  public int size(int k)
  {
    return -data[find(k)];
  }

  public bool is_same(int x, int y)
  {
    return find(x) == find(y);
  }
}

class Scanner
{
  string[] s;
  int i;
  readonly char[] cs = new char[] { ' ' };

  public Scanner()
  {
    s = new string[0];
    i = 0;
  }

  public string next()
  {
    if (i < s.Length) return s[i++];
    string st = Console.ReadLine();
    while (st == "") st = Console.ReadLine();
    s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
    if (s.Length == 0) return next();
    i = 0;
    return s[i++];
  }

  public int nextInt()
  {
    return int.Parse(next());
  }

  public double nextDouble()
  {
    return double.Parse(next());
  }
}



Measured memory_bytes: 9416
#include <stdio.h>

int main(void){

  char x,y;
	scanf("%c %c", &x, &y);
	if (x < y) {
		printf("<\n");
	} else if (y < x) {
		printf(">\n");
	} else {
		printf("=\n");
	}

  return 0;
}

Measured memory_bytes: 128
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int p = sc.nextInt();
        int q = sc.nextInt();
        int r = sc.nextInt();

        System.out.print(Math.min(Math.min(p + q, q + r), p + r));
    }

}

Measured memory_bytes: 21460
// template version 1.3
// {{{ define basic macro
using namespace std;
#include <iostream>
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)(b-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define sum(v) accumulate(all(v), 0LL)
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define ten(n) ((int)1e##n)
template<class T, size_t N> size_t sza(const T (&array)[N]) { return N; }
template<class T> inline void chmax(T &a, const T &b) { if(a < b) a = b; }
template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }
template<class T=int> T in() {T x; cin>>x; return (x);}

struct Fast {
  Fast(){
    std::cin.tie(0);
    ios::sync_with_stdio(false);
  }
} fast;

// dump macro
#ifdef PCM
  #include "dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
#endif

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;
template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};
#define fi first
#define se second

// }}}
// varible setting{{{

#define infile "../test/sample-1.in"
#define int long long
#define INF 1000000000000000000LL
// #define INF 2147483647
#define MOD 1000000007LL

// }}}

int solve(){
  int n;cin>>n;
  dump(n);
  int a[n],b[n],c[n];
  rep(i, n) cin>>a[i];
  rep(i, n) cin>>b[i];
  rep(i, n) cin>>c[i];
  sort(a, a+n);
  sort(b, b+n);
  sort(c, c+n);
  dump_1d(a,n);
  dump_1d(b,n);
  dump_1d(c,n);

  int res = 0;
  rep(i, n){
    int y = b[i];
    int p = lower_bound(a, a+n, y)-a;
    int q = n-(upper_bound(c, c+n, y)-c);
    dump(y,p,q);
    res += p*q;
  }

  cout << res << endl;

  return 0;
}

signed main() { //{{{
#ifdef INPUT_FROM_FILE
  std::ifstream in(infile);
  std::cin.rdbuf(in.rdbuf());
#endif
  solve();
  return 0;
} //}}}


Measured memory_bytes: 2560
import itertools

def test():
    n = input()
    N = int(n)
    ans = 0
    for i in range(1,len(n)+1):
        for j in itertools.product(["3","5","7"],repeat=i):
            s="".join(j)
            v = int(s)
            if "3" in s and "5" in s and "7" in s and v <= N:
                ans += 1
    print(ans)


if __name__ == "__main__":
    test()


Measured memory_bytes: 3060
#[allow(unused_imports)]
use std::cmp;
use std::io::Write;

// Input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    let s = {
      use std::io::Read;
      let mut s = String::new();
      std::io::stdin().read_to_string(&mut s).unwrap();
      s
    };
    let mut iter = s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
}

macro_rules! input_inner {
  ($iter:expr) => {};
  ($iter:expr, ) => {};

  ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
    let $var = read_value!($iter, $t);
    input_inner!{$iter $($r)*}
  };
}

macro_rules! read_value {
  ($iter:expr, ( $($t:tt),* )) => {
    ( $(read_value!($iter, $t)),* )
  };

  ($iter:expr, [ $t:tt ; $len:expr ]) => {
    (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  };

  ($iter:expr, chars) => {
    read_value!($iter, String).chars().collect::<Vec<char>>()
  };

  ($iter:expr, usize1) => {
    read_value!($iter, usize) - 1
  };

  ($iter:expr, $t:ty) => {
    $iter.next().unwrap().parse::<$t>().expect("Parse error")
  };
}

fn main() {
  let out = std::io::stdout();
  let mut out = std::io::BufWriter::new(out.lock());
  macro_rules! puts {
    ($($format:tt)*) => (write!(out,$($format)*).unwrap());
  }
  input! {
    i: i64,
    o: i64,
    _t: i64,
    j: i64,
    l: i64,
    _s: i64,
    _z: i64,
  }

  let mut ans = o + (i / 2) * 2 + (j / 2) * 2 + (l / 2) * 2;
  match (i % 2, j % 2, l % 2) {
    (1, 1, 1) => {
      ans += 3;
    },
    (0, 1, 1) => {
      if i >= 2 {
        ans += 1;
      }
    },
    (1, 0, 1) => {
      if j >= 2 {
        ans += 1;
      }
    },
    (1, 1, 0) => {
      if l >= 2 {
        ans += 1;
      }
    },
    _ => (),
  }

  puts!("{}\n", ans);
}


Measured memory_bytes: 4352