akhauriyash/Code-Regression huggingface dataset:
import heapq


def solve(string):
    n, m, *ab = map(int, string.split())
    ab = sorted([(a, b) for a, b in zip(*[iter(ab)] * 2)])
    hq = []
    index, cap, count = 0, 1, m
    ans = 0
    while index < n:
        _a, _b = ab[index]
        if _a > m:
            break
        if _a <= cap:
            heapq.heappush(hq, -_b)
            index += 1
        else:
            if len(hq) > 0:
                ans += -heapq.heappop(hq)
            count -= 1
            cap += 1
    for _ in range(count):
        if len(hq) > 0:
            ans += -heapq.heappop(hq)
    return str(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))


Measured memory_bytes: 25876
#include <stdio.h>

int main(void) {
	int n;
	int f = 0, i = 0, j = 0;
	int ary[101] = {};
	
	scanf("%d", &n);
	if(n % 4 == 0) f = 1;
	if(n % 7 == 0) f = 1;
	for(i = 4; i < 101; i += 4) {
		if(f == 1) break;
		for(j = 7; j < 101; j += 7) {
			if(n % (i + j) == 0) f = 1;
		}
	}
	printf( f ? "Yes\n" : "No\n");
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include <functional>
#include <limits>
#include <cassert>
#include <bitset>

using namespace std;

/* template */

using ll = long long;

void debug_out() { std::cout << std::endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cout << "debug: "; debug_out(__VA_ARGS__)
#else
#define debug(...) 
#endif

#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define rrep(i, a, n) for (int i = ((int)(n-1)); i >= (int)(a); i--)
#define Rep(i, a, n) for (long long i = (long long)(a); i< (long long)(n); i++)
#define RRep(i, a, n) for (long long i = ((long long)(n-1ll)); i>=(long long)(a); i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}

struct Edge{
    int to;
    ll weight;
    Edge(int t, ll w) : to(t), weight(w){ }
};

struct edge{
    int from;
    int to;
    ll weight;
    edge(int f,int t,ll w) : from(f), to(t), weight(w){ }
};


using Graph = vector<vector<Edge>>;
using graph = vector<vector<int>>;
using edges = vector<edge>;

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;
}

template <class T>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

ll ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}

constexpr ll LNF = 1LL<<50;

constexpr int INF = 1e9+7;

const long double PI=3.14159265358979323846;


vector<int> dx = {1,0,-1,1,-1,0};
vector<int> dy = {1,1,1,0,0,-1};

/* template */

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int x; cin >> x;
    if(x>=30){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
} 

Measured memory_bytes: 3612
def f(level,x):
    if level==0: return x

    if x in [1,0]:
        return 0
    elif x==b[level][0]:
        return b[level][1]
    elif 2<=x<b[level-1][0]+2:
        return f(level-1,x-1)
    elif x==b[level-1][0]+2:
        return b[level-1][1]+1
    elif b[level-1][0]+2<x<b[level][0]:
        return b[level-1][1]+1+f( level-1, x-(b[level-1][0]+2))

N,X=map(int,input().split())
b=[[1,1] for i in range(N+1)]
for i in range(1,N+1):
    b[i][0]=b[i-1][0]*2+3
    b[i][1]=b[i-1][1]*2+1

print(f(N,X))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename Domain, typename Range, typename Function>
Domain tsearch(Domain L, Domain R, const Function& f, bool concave_up = true) {
#ifdef DEBUG
    using actual_type = typename callable_traits<Function>::function_type;
    using expected_type = typename callable_traits<Range(Domain)>::function_type;
    static_assert(is_same<actual_type, expected_type>::value, "tsearch 'f' must be Range(Domain)");
#endif
    while(R - L > 1) {
        Domain M = (L + R) / 2;
        ((concave_up ? f(M) < f(M + 1) : f(M) > f(M + 1)) ? R : L) = M;
    }
    return (concave_up ? f(L) < f(R) : f(L) > f(R)) ? L : R;
}
int main() {
	int n;
	cin >> n;
	vector<ll> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	auto foo = [&](ll b) {
		ll sad = 0;
		for(int i = 0; i < n; i++) {
			sad += abs(a[i] - (b + i));
		}
		return sad;
	};
	ll b = tsearch<ll, ll>(-1'000'000'000ll, 1'000'000'000ll, foo);
	cout << foo(b) << endl;
}

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

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

using namespace std;

typedef long long ll;

int n, a;
int x[50];
ll dp[51][5001];

int main(){
	cin >> n >> a;
	rep(i, n){
		int v;
		cin >> v;
		x[i] = v - a;
	}

	dp[0][2500] = 1;
	rep(i, n){
		rep(j, 5001){
			dp[i + 1][j] = dp[i][j];
			if(j - x[i] >= 0){
				dp[i + 1][j] += dp[i][j - x[i]];
			}
		}
	}

	cout << dp[n][2500] - 1 << endl;
	return 0;
}

Measured memory_bytes: 2176
n,m,c=map(int,input().split())
B=list(map(int,input().split()))
ans=0
for _ in range(n):
    A=list(map(int,input().split()))
    cnt=0
    for i in range(m):
        cnt+=A[i]*B[i]
    if cnt+c>0:
        ans+=1
print(ans)

Measured memory_bytes: 3060
// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> bool get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'&&t!=EOF; t=getchar());
	if(t=='-')neg=true,t=getchar();if(t==EOF)return false;
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;return true;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) (get1(a)&&get1(b))
#define get3(a,b,c) (get1(a)&&get2(b,c))
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

vector<int> g[2333];
int dist[2333][2333];
int n,k;
void dfs(int x,int cur,int f=0,int d=0)
{
	dist[cur][x]=d;
	for(auto v:g[x])if(v!=f)dfs(v,cur,x,d+1);
}
pii e[2333];
int main()
{
	get2(n,k);
	for(int i=1,u,v;i<n;i++)
	{
		get2(u,v);e[i]=mp(u,v);
		g[u].pb(v);
		g[v].pb(u);
	}
	for(int i=1;i<=n;i++)dfs(i,i);
	int ans=n;
	if(k%2==0)
	{
		for(int i=1;i<=n;i++)
		{
			int now=0;for(int j=1;j<=n;j++)now+=(dist[i][j]>k/2);
			ans=min(ans,now);
		}
	}
	else
	{
		for(int i=1;i<n;i++)
		{
			int u=e[i].ff,v=e[i].ss,now=0;
			for(int j=1;j<=n;j++)now+=(dist[j][u]+dist[j][v]>k);
			ans=min(ans,now);
		}
	}
	printendl(ans);
	return 0;
}

Measured memory_bytes: 18944
N,K=map(int, input().split())

A=list(map(int, input().split()))

p=10**9+7


def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
n = 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p) 階乗のmod
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, n + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)




#最大値として、最小値として何回登場するか

A=sorted(A)
ans=0
for i in range(K-1,N):
    ans+=cmb(i,K-1, p)*A[i]
    ans%=p

for i in range(N-K+1):
    ans-=cmb(N-i-1, K-1, p)*A[i]
    ans%=p

print(ans)

Measured memory_bytes: 105108
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();

		int dist = B - A;
		if (dist % 2 == 0) {
			System.out.println("Alice");
		} else {
			System.out.println("Borys");
		}

	}
}


Measured memory_bytes: 23252
function main()
  
  (N,M) = map(x -> parse(Int,x), split(readline()))
  
  drink = Tuple[]
  
  for i in 1:N
    (A,B) = map(x -> parse(Int,x) ,split(readline()))
    push!(drink, (A,B))
  end
  
  sort!(drink, by= x -> x[1])
  
  check1 = 0
  check2 = 1
  ans = 0
  
  for i in 1:M
    
    check1 += 1
    ans += drink[check2][1]
    
    if check1 == drink[check2][2]
      check1 = 0
      check2 += 1
    end
    
  end
  
  println(ans)
  
end

main()

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

void solve()
{
    int x;
    cin >> x;
    if (x < 1200)
        cout << "ABC" << endl;
    else
        cout << "ARC" << endl;
}

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

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,m,s,g;
vector<pair<int,string> >edge[45];
string dp[45];
struct S{
	int v; string s;
	bool operator <(const S &a)const{
		return s > a.s;
	}
	S(int a,string b){
		v = a; s = b;
	}
};
int a[3005],b[3005]; string c[3005];
int main(){
	while(1){
		scanf("%d%d%d%d",&n,&m,&s,&g);
		if(n==0) return 0;
		for(int i=0;i<n;i++){
			edge[i].clear();
			dp[i] = "1";
		}
		for(int i=0;i<m;i++){
			cin >> a[i] >> b[i] >> c[i];
			edge[b[i]].pb(mp(a[i],c[i]));
		}
		
		priority_queue<S>que;
		que.push(S(g,"")); dp[g] = "";
		while(!que.empty()){
			S t = que.top(); que.pop();
			if(dp[t.v] != "1" && dp[t.v] < t.s) continue;
			if(t.s.size() > 500) continue;
			for(int i=0;i<edge[t.v].size();i++){
				string nex = edge[t.v][i].sc;
				nex += t.s;
				if(dp[edge[t.v][i].fi] == "1" || dp[edge[t.v][i].fi] > nex){
					dp[edge[t.v][i].fi] = nex;
					que.push(S(edge[t.v][i].fi,nex));
				}
			}
		}
		if(dp[s].size() >= 250 || dp[s] == "1") puts("NO");
		else cout << dp[s] << endl;
	}
}

Measured memory_bytes: 5832
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    int cnt = 0;
    for(int i=1; i<=n; i++){
        int t; cin >> t;
        if(i%2 && t%2) cnt++;
    }
    cout << cnt;
}

Measured memory_bytes: 3648
N = input()
K = int(input())

# dp[i][j][k]:問題の条件を満たす数の個数
# i桁目まで決定している。
# 非0の桁がすでにj個ある。
# k=0:i桁目までNと一致。k=1:すでにN以下であることが決まっている。

dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(len(N)+1)]
dp[0][0][0] = 1
for i in range(len(N)):
  n = int(N[i])
  for j in range(4):
    for k in range(2):
      for d in range(10): # d:i+1桁目の数字
        # ni,nj,nk:次の遷移先
        ni = i+1
        nj = j
        nk = k
        if d > 0:
          nj += 1
        if nj > K:
          continue
        if k == 0:
          if d > n:
            continue
          if d < n:
            nk = 1
        dp[ni][nj][nk] += dp[i][j][k]

print(dp[len(N)][K][0]+dp[len(N)][K][1])


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

int main() {
  string S;
  cin >> S;
  int N = S.size();
  int count = 0;
  bool hantei = true;
  for(int i=0;i<N;i++){
    count++;
    if(count % 2 == 0){
      if(S.at(i) == 'R'){
        hantei = false;
        break;
      }
    }else{
      if(S.at(i) == 'L'){
        hantei = false;
        break;
      }
    }
  }
  if(hantei){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
using namespace std;

int main() {
    int h, w, n;
    cin >> h >> w >> n;
    vector<int> a(n);
    rep(i, n)cin >> a.at(i);
    int now = 0;
    rep(i, h){
        vector<int> ans;
        for(int j = 0; j < w; j++){
            if(a.at(now) == 0)now++;
            ans.push_back(now+1);
            a.at(now)--;
        }
        if(i % 2 == 0)reverse(all(ans));
        for(int j = 0; j < w; j++){
            if(j != 0)cout << " ";
            cout << ans.at(j);
        }
        cout << endl;
    }
}


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

int main() {
  int N;
  cin >> N;
  vector<int> p(N);
  for(int i=0; i<N; i++){
    cin >> p.at(i);
  }
  
  int count1 = 0;
  int count2 = 0;
  
  for(int i=0; i<N; i++){
    if(p.at(i) > i+1){
       count1 ++;
    }
  }
  for(int i=0; i<N; i++){
    if(p.at(i) < i+1){
       count2 ++;
    }
  }
  
  //cout << "count:" << count1 << count2 <<endl;
  if(count1 <= 1 && count2 <= 1){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
} 

Measured memory_bytes: 256
n, m = list (map (int, input().split()))
ha = {}
cnt = 0
ans = 0
use = [False for i in range (n + 1)]

for i in range (m) :
    p, s = input().split()
    p = int (p)
    if not use[p] and s == 'AC' :
        cnt += 1
        use[p] = 1;
        ans += ha[p] if p in ha.keys() else 0
        continue
    if use[p] :
        continue
    if not p in ha.keys() :
        ha[p] = 1
    else :
        ha[p] += 1

print (cnt, ans)

Measured memory_bytes: 9904
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

#define int long long

const int N = 1e5 + 7;
const int K = 13;
const int MOD = 1e9 + 7;

int add(int a, int b) {
	return (a + b) % MOD;
}

int dp[N][K];
string s;

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

	cin >> s;
	int n = (int)s.size();
	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int cm = 0; cm < K; cm++) {
			for (int nd = 0; nd < 10; nd++) {
				if (s[i] != '?' && s[i] != nd + '0') continue;
				int nm = (cm * 10 + nd) % K;
				dp[i + 1][nm] = add(dp[i + 1][nm], dp[i][cm]); 
			}
		}
	}
	cout << dp[n][5] << endl;
}


Measured memory_bytes: 10704
S = input()
ans = 0
MOD = 10 ** 9 + 7
la = 0
lp = 0
rc = 0
rp = 0
for c in S:
    if c == 'C':
        rc += 1
    if c == '?':
        rp += 1
for c in S:
    if c == 'C':
        rc -= 1
    if c == '?':
        rp -= 1
    if c == '?' or c == 'B':
        if lp == 0:
            l = la * pow(3, lp, MOD)
        else:
            l = la * pow(3, lp, MOD) + lp * pow(3, lp-1, MOD)
        if rp == 0:
            r = rc * pow(3, rp, MOD)
        else:
            r = rc * pow(3, rp, MOD) + rp * pow(3, rp-1, MOD)
        ans += l*r
        ans %= MOD
    if c == 'A':
        la += 1
    if c == '?':
        lp += 1
print(ans)


Measured memory_bytes: 9164
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string A;cin >> A;
  long long s=0,t=0;
  for (int i=0;i<A.size();i++) {
    if (A[i]=='S') s++;
	else if (s>0) s--;
	else t++;
  }
  cout << s+t << endl;
  
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
 
int main(void){
    int N;
    ll num, sum, ans, MOD;
    vector<ll> A;
    sum = 0;
    ans = 0;
    MOD = 1e9+7;
    
    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> num;
        sum += num;
        A.push_back(num);
    }
    
    for (int i = 0; i < N - 1; i++){
        ll temp;
        sum -= A[i];
        temp = sum % MOD;
        ans += (A[i] * temp) % MOD;
    }
    
    cout << ans % MOD << endl;
    
    return 0;
}

Measured memory_bytes: 5332
//{{{
#include<algorithm>
#include<cmath>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<sys/time.h>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printw) FUNC(printwe) FUNC(printb) FUNC(printbe) FUNC(printd) FUNC(printde) FUNC(printdu);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ return in >> p.first >> p.second; }
template <class T>
istream& operator >> (istream& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }
//}}}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll k, a, b;
    cin >> k >> a >> b;
    if(a + 2 >= b){
        cout << k + 1 << '\n';
        return 0;
    }
    if(a >= k){
        cout << k + 1 << '\n';
        return 0;
    }
    ll rem = k - a + 1;
    cout << a + rem / 2 * (b - a) + rem % 2 << '\n';
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var cookiesT, cookiesA, k int
	fmt.Scan(&cookiesT, &cookiesA, &k)

	if cookiesT >= k {
		cookiesT -= k
	} else {
		cookiesA -= (k - cookiesT)
		cookiesT = 0
		if cookiesA < 0 {
			cookiesA = 0
		}
	}

	fmt.Print(cookiesT)
	fmt.Print(" ")
	fmt.Print(cookiesA)
	fmt.Println("")
}


Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>

int max(int p[],int len){
    int largest = -10000;
    for(int i = 0; i < len; i++){
        if (p[i] > largest){
            largest = p[i];
        }
    }
    printf("%d",largest);
    return 0;
}


int main()
{
    int a,b;


    scanf("%d", &a);
    scanf("%d", &b);

    int kkk[3];

    kkk[0] = a+b;
    kkk[1] = a-b;
    kkk[2] = a*b;

    max(kkk,3);


    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

signed main(){

	lli n;
	cin>>n;

	vector<double> p(n);
	REP(i,0,n)cin>>p[i];

	double dp[3010]={0};
	dp[0]=1.0;

	for(lli i=1;i<=n;i++){
		for(lli j=i;j>=0;j--){
			dp[j] = dp[j] * (1.0-p[i-1]) ;
			if(j>0)dp[j] += dp[j-1]*p[i-1];
		}
	}
	lli target = n/2+1;
	double ans=0;
	REP(i,target,n+1)ans += dp[i];

	printf("%.10lf\n",ans);


	return 0;
}

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

// #define multitest 1
#ifdef WIN32
#define db(...) ZZ(#__VA_ARGS__, __VA_ARGS__);
#define pc(...) PC(#__VA_ARGS__, __VA_ARGS__);
template <typename T, typename U>
ostream &operator<<(ostream &out, const pair<T, U> &p)
{
	out << '[' << p.first << ", " << p.second << ']';
	return out;
}
template <typename Arg>
void PC(const char *name, Arg &&arg)
{
	std::cerr << name << " { ";
	for (const auto &v : arg)
		cerr << v << ' ';
	cerr << " }\n";
}
template <typename Arg1>
void ZZ(const char *name, Arg1 &&arg1)
{
	std::cerr << name << " = " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void ZZ(const char *names, Arg1 &&arg1, Args &&... args)
{
	const char *comma = strchr(names + 1, ',');
	std::cerr.write(names, comma - names) << " = " << arg1;
	ZZ(comma, args...);
}
#else
#define db(...)
#define pc(...)
#endif

using ll = long long;
#define f first
#define s second
#define pb push_back
const long long mod = 1000000007;
auto TimeStart = chrono::steady_clock::now();

const int nax = 2e5 + 10;

void solve()
{
	int n;
	cin >> n;
	long double a, sum = 0;
	while (n--)
	{
		cin >> a;
		sum += 1 / a;
	}
	cout << fixed << setprecision(9) << 1/sum;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
#ifdef multitest
	cin >> t;
#endif
	while (t--)
		solve();
#ifdef WIN32
	cerr << "\n\nTime elapsed: " << chrono::duration<double>(chrono::steady_clock::now() - TimeStart).count() << " seconds.\n";
#endif
	return 0;
}

Measured memory_bytes: 256
// oh, the less I know the better
// corner cases // int vs ll // cin vs scanf // clear structures // statement // doublesz
#include <bits/stdc++.h>
#define endl '\n'
#define fst first
#define snd second
#define pb push_back
#define sz(x) int(x.size())
#define REP(i,n) for(int i = 0; i < int(n); ++i)
#define trace(x) cout << #x << " = " << x << endl
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int N = 2e5+20, MOD = 1e9+7;

template<typename T, T mod>
struct Tint{
	T val;
	Tint(): val(0){}
	Tint(long long x){ x %= mod; if(x < 0) x += mod; val = x; }
	// basic operations
	Tint& operator += (Tint oth){ val += oth.val; if(val >= mod) val -= mod; return *this; }
	Tint& operator -= (Tint oth){ val -= oth.val; if(val < 0) val += mod; return *this; }
	Tint& operator *= (Tint oth){ val = (long long)(val) * oth.val % mod; return *this; }
	Tint operator + (Tint oth) const{ return Tint(*this) += oth; }
	Tint operator - (Tint oth) const{ return Tint(*this) -= oth; }
	Tint operator * (Tint oth) const{ return Tint(*this) *= oth; }
};

using Mint = Tint<int,MOD>;

Mint fact[N], ifact[N];

Mint bpow(Mint x, ll p){
	Mint ans;
	for(ans = 1; p; p >>= 1, x = x*x)
		if(p&1) ans = ans * x;
	return ans;
}

void build(){
	fact[0] = ifact[0] = 1;
	for(int i = 1; i < N; ++i){
		fact[i] = fact[i-1] * i;
		ifact[i] = bpow(fact[i],MOD-2);
	}
}

Mint comb(ll n, ll k){ return fact[n] * ifact[k] * ifact[n-k]; }
Mint ways(ll x, ll y){ return comb(x+y,x); }

int main(){

	fastio;
	build();
	int h,w,n;
	cin >> h >> w >> n;
	vector<ii> pts(n);
	for(int i = 0; i < n; ++i){
		cin >> pts[i].fst >> pts[i].snd;
		pts[i].fst--; pts[i].snd--;
	}
	pts.pb(ii(h-1,w-1));
	sort(pts.begin(),pts.end());

	vector<Mint> dp(sz(pts),1);
	for(int i = 0; i < sz(dp); ++i){
		dp[i] = ways(pts[i].fst,pts[i].snd);
		for(int j = 0; j < i; ++j){
			if(pts[j].fst <= pts[i].fst && pts[j].snd <= pts[i].snd){
				dp[i] -= ways(pts[i].fst-pts[j].fst, pts[i].snd-pts[j].snd) * dp[j];
			}
		}
	}

	cout << dp.back().val << endl;

	return 0;
}


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

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

    ll i,j,k,l,m,n,w,x,y,z,p,q,tmp,sum=0;
    string str;
    cin>>str;
    ll maxx=0;
    rep(i,str.length()){
        if(str[i]=='A'||str[i]=='C'||str[i]=='G'||str[i]=='T'){
            sum++;
            maxx=max(sum,maxx);
        }else{
            sum=0;
        }
    }
    cout<<maxx<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define N 100000
#define A 0
#define B 1
#define C 2
#define DONE 3
 
long long dp[N + 2][5];
int a[N + 2];
int b[N + 2];
int c[N + 2];
int n;

long long solve(int x, int type){
    if (x > n){
        return type == DONE;
    }

    if (dp[x][type] != -1){
        return dp[x][type];
    }

    if (type == A){
        return dp[x][type] = solve(x + 1, type) + solve(upper_bound(b + 1, b + 1 + n, a[x]) - b, type + 1);
    }

    if (type == B){
        return dp[x][type] = solve(x + 1, type) + solve(upper_bound(c + 1, c + 1 + n, b[x]) - c, type + 1);
    }

    if (type == C){
        return dp[x][type] = solve(x + 1, type) + solve(x + 1, type + 1);
    }

    return dp[x][type] = solve(x + 1, type);
}
 
int main(){
	int i;

    scanf("%d", &n);

    for (i = 1; i <= n; i++){
        scanf("%d", a + i);
    }

    for (i = 1; i <= n; i++){
        scanf("%d", b + i);
    }

    for (i = 1; i <= n; i++){
        scanf("%d", c + i);
    }

    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);
    sort(c + 1, c + 1 + n);
    memset(dp, -1, sizeof(dp));

    printf("%lld\n", solve(1, 0));

	return 0;
} 

Measured memory_bytes: 14720
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<deque>
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pii;
typedef pair<pii, ll>pi3;
ll mod = 1000000007;
int main()
{
	string a, b, c;
	cin >> a >> b >> c;
	//cout << 800 * x - 200 * (x / 15) << endl;
	printf((a[a.size()-1]==b[0]&&b[b.size()-1]==c[0]) ? "YES\n" : "NO\n");
}

Measured memory_bytes: 256
s=input()
li = list(s)
a=[]
b=[]
for i in range(len(li)):
  if i%2 == 0:
    a.append(li[i])
  else:
    b.append(li[i])

if 'L' in a or 'R' in b:
  print('No')

else:
  print('Yes')

Measured memory_bytes: 3060
s=list(map(int,input()))
k=int(input())
ans=0
num=0

for i in range(len(s)):
    if s[i]!=1:
        ans=s[i]
        break
    else:
        num+=1
        if num==k:
            ans=s[i]
            break
        else:
            pass

print(ans)


Measured memory_bytes: 2940
N = int(input())
dic = {}
for c in "MARCH":
    dic[c] = 0
myset = set(list("MARCH"))
for _ in range(N):
    c = input()[0]
    if c in myset:
        dic[c] += 1

res = 0
for i in range(5-2):
    for j in range(i+1, 5-1):
        for k in range(j+1, 5):
            res += dic["MARCH"[i]] * dic["MARCH"[j]] * dic["MARCH"[k]]
print(res)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>a
#define pb push_back
#define sz(x) int(x.size())

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
ll lcm(ll a, ll b){
  return a*b/gcd(a,b);
}

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

class UnionFind{
public:
  vi Parent;
  UnionFind(int n){
    Parent = vi(n,-1);
  }

  int root(int a){
    if(Parent[a] < 0) return a;
    else return Parent[a] = root(Parent[a]);
  }

  int size(int a){
    return -Parent[root(a)];
  }

  bool merge(int a, int b){
    a = root(a);
    b = root(b);
    if(a == b) return false;

    if(size(a) < size(b)) swap(a,b);
    Parent[a] += Parent[b];
    Parent[b] = a;

    return true;
  }
};

class Factrial{
public:
  vl Fac;
  Factrial(int MAX){
    Fac = vl(MAX+1);
    rep(i,MAX) {
      if(i == 0) Fac[i+1] = 1;
      else Fac[i+1] = ((i+1)*Fac[i])%MOD;
    }
  }
};

int main(){
  int H, A; cin >> H >> A;
  cout << (H+A-1)/A << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <map>
using namespace std;
typedef long long ll;

// #define DEBUG

template <typename T>
T my_pow_with_mod(T x, T a, T mod = 1e9 + 7)
{
    ll ans = 1;
    ll b = x;
    while (a)
    {
        if (a & 1)
            ans *= b;
            ans %= mod; 
        a = a >> 1;
        b = b * b;
        b %= mod;
    }
    return ans;
}

template <typename T>
void prime_factorization(T n){
    vector<pair<T, T>> a;
    T counter, p;
    T m = sqrt(n) + 1;
    p = n;
    for (T i = 2; i <= m; i++){
        counter = 0;
        while (n % i == 0){
            counter++;
            n /= i;
        }
        if (counter)
            a.push_back(make_pair(i, counter));

        if (n == 1)
            break;
    }
    if (n != 1)
        a.push_back(make_pair(n, 1));

    cout << p << ":";
    for (int i = 0; i < a.size(); i++){
        for (int j = 0; j < a[i].second; j++){
            cout  << " "<< a[i].first;
        }
    }
    cout << endl;

}

int main()
{

#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif
    int n;
    cin >> n;
    prime_factorization(n);
    return 0;
}

// getline(cin,s);
// a = strtok(s, ",");  ","で分解
// for (int i = 0; i < n; i++)


Measured memory_bytes: 3108
#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
vector<int>x[1000000], B[1000000]; int a[300000], b[300000], l[1000000], r[1000000], X[1000000], Y[1000000], n, m;
map<pair<int, int>, int>M;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>Q;
map<pair<int, int>, int>used;
vector<pair<int, int>>Vec;
void add_edge() {
    for (int i = 1; i <= n; i++)sort(B[i].begin(), B[i].end());
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < B[i].size(); j++) { Vec.push_back(make_pair(B[i][j], i)); }
    }
    sort(Vec.begin(), Vec.end()); for (int i = 0; i < Vec.size(); i++) { M[Vec[i]] = i + 1; X[i + 1] = Vec[i].first; Y[i + 1] = Vec[i].second; }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < B[i].size() - 1; j++) {
            x[M[make_pair(B[i][j], i)]].push_back(M[make_pair(B[i][j + 1], i)]);
        }
    }
    for (int i = 0; i < m; i++) {
        x[M[make_pair(a[i] * 2, b[i])]].push_back(M[make_pair(a[i] * 2 + 1, b[i] + 1)]);
        x[M[make_pair(a[i] * 2, b[i] + 1)]].push_back(M[make_pair(a[i] * 2 + 1, b[i])]);
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) { B[i].push_back(0); B[i].push_back(500000); }
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
        B[b[i]].push_back(a[i] * 2); B[b[i]].push_back(a[i] * 2 + 1);
        B[b[i] + 1].push_back(a[i] * 2); B[b[i] + 1].push_back(a[i] * 2 + 1);
    }
    add_edge();
    for (int i = 0; i < 1000000; i++) { l[i] = 1000000; r[i] = 0; }
    for (int i = 1; i <= n; i++) { Q.push(make_pair(0, M[make_pair(0, i)])); l[M[make_pair(0, i)]] = i; r[M[make_pair(0, i)]] = i; }
    while (!Q.empty()) {
        int a1 = Q.top().second; Q.pop();
        for (int i = 0; i < x[a1].size(); i++) {
            if (X[a1] >= X[x[a1][i]] || used[make_pair(a1, x[a1][i])] == 1)continue;
            Q.push(make_pair(X[x[a1][i]], x[a1][i])); used[make_pair(a1, x[a1][i])] = 1;
            l[x[a1][i]] = min(l[x[a1][i]], min(l[a1], Y[x[a1][i]]));
            r[x[a1][i]] = max(r[x[a1][i]], max(r[a1], Y[x[a1][i]]));
        }
    }
    for (int i = 1; i <= n; i++) { 
        if (i >= 2)cout << ' '; 
        cout << r[M[make_pair(500000, i)]] - l[M[make_pair(500000, i)]] + 1;
    }
    cout << endl;
    return 0;
}

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

#define println(msg) cout << msg << endl
#define yes_or_no(flag) if (flag) { println("Yes"); } else { println("No"); }
#define sort_vec(vec) sort(vec.begin(), vec.end())
#define rsort_vec(vec) sort(vec.rbegin(), vec.rend()) // greater<int>()
int sum_of_digits(int n) {
  int sum = 0;
  for (; n > 0; n /= 10) { sum += (n % 10); }
  return sum;
}

int main() {
  // 入力
  int N, M;
  cin >> N >> M;

  vector<pair<int, int>> vp(M);
  for (int i = 0; i < M; i++) {
    cin >> vp.at(i).first >> vp.at(i).second;
  }
  
  // 計算
  vector<int> V(N);
  for (auto &v : V) {
    v = 0;
  }
  
  for (int i = 0; i < M; i++) {
    V.at(vp.at(i).first - 1)++;
    V.at(vp.at(i).second - 1)++;
  }
  
  // 出力
  for (int i = 0; i < N; i++) {
    println(V.at(i));
  }
}


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

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

int main() {

	int N;
	int t[110000], x[110000], y[110000];
	int dift, difx, dify;
	int i;
	bool ans;

	cin >> N;
	t[0] = 0; x[0] = 0; y[0] = 0;
	REP(i, N){
		cin >> t[i+1] >> x[i+1] >> y[i+1];
	}

	REP(i, N){
		dift = (t[i+1]-t[i]);
		difx = abs(x[i+1]-x[i]);
		dify = abs(y[i+1]-y[i]);
		if( dift < ( difx + dify ) ){
			cout << "No" << endl;
			return 0;
		}
		//cout << ( difx + dify ) % 2 << endl;
		if( dift % 2 != (( difx + dify ) % 2) ){
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;
	return 0; 
}

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define ALL(A) (A).begin(),(A).end()
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)

const ll mod = 1e9+7;
const ll INF = 2*1e18;
const int inf = 1e9+7;

using namespace std;

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N,K;
	cin >> N >> K;
	ll ans = 0;
	for(int b=K+1;b<=N;b++){
		ll p = N/b;
		ans += p*max(0LL,(ll)b-K);
		ans += max(0LL,N%(ll)b-K+1);
	}
	if(K==0)ans -=N;
	cout << ans << endl;
}

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

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  if (a == b && b == c) cout << 1 << endl;
  else if (a != b && b != c && c != a) cout << 3 << endl;
  else cout << 2 << endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        String S = sc.next();
        String ans = "No";
        sc.close();
        try {
            Integer.parseInt(S.substring(0,A));
            Integer.parseInt(S.substring(A+1));
            if (S.length() == A+B+1){
                if (S.charAt(A) == '-'){
                    ans = "Yes";
                }
            }
        }
        catch(NumberFormatException e){
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 23764
N=int(input())
S=input()

r,g,b=0,0,0
for s in S:
    if s=='R': r+=1
    elif s=='G': g+=1
    else: b+=1


ng=0
for i in range(N):
    for j in range(i+1,N):
        k=j+(j-i)
        if k>=N: continue
        if S[i]!=S[j] and S[j]!=S[k] and S[i]!=S[k]:
            ng+=1

ans=r*g*b
print(ans-ng)


Measured memory_bytes: 9208
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<random>
using namespace std;

//fixed << setprecision(10)
#define PI 3.141592653589793
#define Yes(a) a ? "Yes" : "No";
#define YES(a) a ? "YES" : "NO";
#define rep(i,n) for(int i=0;i<n;i++)

int gcd(int a,int b) {
	if (a < b) {
		int tmp = a;
		a = b;
		b = tmp;
	}
	int r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

map<int, int> prime;
void Prime(long long int n) {
	for (int i = 2; i <= n; i++) {
		int count = 0;
		while (n % i == 0) {
			count++;
			n /= i;
		}
		if (count != 0) {
			prime.insert(make_pair(i, count));
		}
	}
}

int main() {
	string str;
	cin >> str;

	int n = str.size();
	vector<int> num(n + 1,0);
	long long int sum = 0;

	for (int i = 0; i < n; i++) {
		if (str[i] == '<') {
			num.at(i + 1) = num.at(i) + 1;
		}
	}
	for (int i = n-1; i >=0; i--) {
		if (str[i] == '>') {
			num.at(i) = max(num.at(i), num.at(i+1) + 1);
		}
	}

	for (int i = 0; i <= n; i++) {
		sum += num.at(i);
	}
	/*
	for (int i = 0; i <= n; i++) {
		cout << num.at(i) << " ";
	}cout << endl;
	*/
	cout << sum << endl;
}

Measured memory_bytes: 2820
#include<stdio.h>

int main(void){
    int W,H,x,y,r;
    
    scanf("%d",&W);
    scanf("%d",&H);
    scanf("%d",&x);
    scanf("%d",&y);
    scanf("%d",&r);
    
    if((x+r>W||x-r<0)||(y+r>H||y-r<0)){
        printf("No\n");
    }else{
        printf("Yes\n");
    }
    
    return 0;
}


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

int main() {
	long n,m,i,j,ans,cur,res,a,b,v,w,t;
	cin >> a >> v >> b >> w >> t;
	if(w>=v || abs(v-w)*t<abs(b-a)){
		cout << "NO" << endl; return 0;
	}else{
		cout << "YES" << endl; return 0;
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 3624
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
typedef long long ll;
typedef long double ld;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF (1LL<<60)
#define MOD1 1000000007
#define MAX_N (1 << 17)


void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a=c;}
ll max2(ll a,ll b){return a>=b?a:b;}
ll min2(ll a,ll b){return a>=b?b:a;}
ll minn(ll n, ll a[n]){ll b=INF;rep(i,0,n) b=min2(b,a[i]);return b;}
ll maxn(ll n, ll a[n]){ll b=-INF;rep(i,0,n) b=max2(b,a[i]);return b;}
ll ABS(ll a){return a>=0?a:(-a);}
ll POW(ll a, ll b){ll c=1;rep(i,0,b) c*=a;return c;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

/*nをa進数にしたときの、i桁目の数*/
ll placenai(ll n, ll a, ll i){return i==1?n%a:placenai(n/a,a,i-1);}

ll x[3]={0,0,0};

ll dfs(ll a, ll n, ll dig){
    // if(a==0) return dfs(a*10+3,n,dig)+dfs(a*10+5,n,dig)+dfs(a*10+7,n,dig);
    // printf("%lld ",a);
    if(a>n) return 0;
    rep(i,0,dig){
        if(placenai(a,10,i+1)==3) x[0]=1;
        if(placenai(a,10,i+1)==5) x[1]=1;
        if(placenai(a,10,i+1)==7) x[2]=1;
    }
    ll c=x[0]+x[1]+x[2];
    // printf("%lld\n",c);
    rep(i,0,3) x[i]=0;
    return ( c==3?1:0 ) + dfs(a*10+3,n,dig+1)+dfs(a*10+5,n,dig+1)+dfs(a*10+7,n,dig+1);
}


int main(void){
    // char ;
    ll n;
    scanf("%lld",&n);
    printf("%lld\n",dfs(0,n,0));
    return 0;
}


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

using namespace std;

int main(){
	int ary_morning[10] , ary_after[20];
	int sum[10] , ans[10];
	string str[10];

	for(int i = 0; i < 9; i++){
		cin >> str[i] >> ary_morning[i] >> ary_after[i];
		sum[i] = ary_morning[i] + ary_after[i];
		ans[i] = (ary_morning[i] * 200) + (ary_after[i] * 300); 
	}for(int i = 0; i < 9; i++){
		cout << str[i] << " " << sum[i] << " " << ans[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 3184
#include <iostream>
#include <cassert>
#include <climits>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <limits>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

long long int INF = 1e18;
long long int mod = 1000000007;
double Pi = 3.1415926535897932384626;

vector<ll> G[500005];
vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop

int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
ll bit[500005];
//↓,→,↑,←

#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(15)<<x<<endl;
#define pu(x) cout<<x;
#define re(i,n) for(i=0;i<n;i++);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define deba(x) cout<< #x << " = " << x <<endl

ll rui(ll abc,ll bed){
    //abcのbed乗を計算する
    if(bed==0){return 1;}
    else{
        ll ced = rui(abc,bed/2);
        ced *= ced;
        ced %= mod;
        if(bed%2==1){ced*=abc; ced%=mod;}
        return ced;
    }
}
ll gcd(ll number1,ll number2){
	if(number1 > number2){
		swap(number1,number2);
	}
	if(number1 == 0 || number1 == number2){
		return number2;
	}else{
		return gcd(number2 % number1,number1);
	}
}

ll i,j,k,ii,jj,r,l;
ll n,num,sum,ans;
ll a,b,c,d,e,g,h;
ll x[500005],y[500005],z[500005];
bool dp[10000];
char s[500005];

ll bitsum(ll i){
	ll s = 0;
	while(i>0){
		//p("hoi");
		s += bit[i];
		i -= i & -i;
	}
	return s;
}
void bitadd(ll b,ll x){
	while(b <= n){
		//p("hoi");
		bit[b] += x;
		b += b & -b;
	}
}

void solve(ll c){
	a = n;
	b = 0;
	for(i=0;i<n;i++){
		if(s[i] == c){
			dp[i] = true;
		}else{
			dp[i] = false;
		}
	}
	bool dame;
	while(1){
		dame = false;
		for(i=0;i<a;i++){
			if(!dp[i])dame = true;
		}
		if(!dame){
			ans = min(ans,b);
			break;
		}
		for(i=0;i<a-1;i++){
			if(dp[i] || dp[i+1])dp[i] = true;
		}
		a--;
		b++;
	}
}


int main(){
	cin >> s;
	ans = INF;
	n = strlen(s);
	for(k='a';k<='z';k++){
		solve(k);
	}
	p(ans);
	return 0;
}

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

int main() {
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == '?') s[i] = 'D';
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 3700
import java.util.Scanner;

public class Main implements Runnable {

    public static void main(String[] args) {
        new Thread(null, new Main(), "", 128 * 1024 * 1024).start();
    }

    public void run() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), C = sc.nextInt();
        int[] s = new int[100000], t = new int[100000], c = new int[100000];
        for (int i = 0; i < N; i++) {
            s[i] = sc.nextInt();
            t[i] = sc.nextInt();
            c[i] = sc.nextInt();
        }

        int[] ss = new int[200002], tt = new int[200002];
        for (int i = 1; i <= C; i++) {
            for (int j = 0; j < 200002; j++) {
                tt[j] = 0;
            }
            for (int j = 0; j < N; j++) {
                if (c[j] == i) {
                    tt[s[j] * 2 - 1]++;
                    tt[t[j] * 2]--;
                }
            }
            for (int j = 1; j < 200002; j++) {
                tt[j] += tt[j - 1];
            }
            for (int j = 0; j < 200002; j++) {
                if (tt[j] > 0) {
                    ss[j]++;
                }
            }
        }
        int max = 0;
        for (int i = 0; i < 200002; i++) {
            max = Math.max(max, ss[i]);
        }
        System.out.println(max);
    }
}

Measured memory_bytes: 96352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define ALL(n) begin(n),end(n)
#define IN(a, x, b) (a<=x && x<b)
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
template<class T> inline T CHMAX(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T CHMIN(T & a, const T b) { return a = (a > b) ? b : a; }

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);

int main()
{
    INIT;
    int n;
    cin >> n;
    int count = 0;
    vector<int> h(n);
    REP(i,n){
        cin >> h.at(i);
    }
    for(int i = 1; i < n; i++){
        int ma = h.at(i-1);
        for(int j = 0; j < i; j++){
            ma = max(ma, h.at(j));
            
        }
        if(ma <= h.at(i)) count++;
    }
    cout << count + 1 << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;


class Solve{
	static int INF = 10000;
	
	 public void solve() {
		 Scanner sc = new Scanner(System.in) ;
		 int n = sc.nextInt();
		 int k = sc.nextInt();
		 String str = sc.next();
		 StringBuilder sb = new StringBuilder(str);
		 if(str.charAt(k-1)=='A') {
			 sb.replace(k-1, k, "a");
		 }else if(str.charAt(k-1)=='B') {
			 sb.replace(k-1, k, "b");
		 }
		 else if(str.charAt(k-1)=='C') {
			 sb.replace(k-1, k, "c");
		 }
		 System.out.println(sb);

	}
}





public class Main {

	public static void main(String[] args) {

		Solve s= new Solve();
		s.solve();

	}
}


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

int main(){
    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;
    bool if_can_make_water[F / 100];
    fill(if_can_make_water, if_can_make_water + F / 100, false);
    for(int a = 0; a * A <= F / 100; a++){
        for(int b = 0; a * A + b * B <= F / 100; b++){
            if(a || b){
                if_can_make_water[a * A + b * B - 1] = true;
            }
        }
    }
    bool if_can_make_sugar[F + 1];
    fill(if_can_make_sugar, if_can_make_sugar + F + 1, false);
    for(int c = 0; c * C <= F; c++){
        for(int d = 0; c * C + d * D <= F; d++){
            if_can_make_sugar[c * C + d * D] = true;
        }
    }
    int ans_all = 100 * A, ans_sugar = 0;
    double ans_concentration = 0.0;
    for(int i = 0; i < F / 100; i++){
        for(int j = 0; j <= F; j++){
            if(if_can_make_water[i] && if_can_make_sugar[j] && i * 100 + j + 100 <= F){
                double concentration = j / (i * 100.0 + j + 100.0) * 100;
                if(ans_concentration < concentration && j <= E * (i + 1)){
                    ans_all = i * 100 + j + 100;
                    ans_sugar = j;
                    ans_concentration = concentration;
                }
            }
        }
    }
    cout << ans_all << " " << ans_sugar << endl;
    
}


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


int main() {
	
	int a, b, cnt = 0;
	cin >> a >> b;
	for(int i=a; i<=b; i++){
		string s;
		s = to_string(i);
		reverse(s.begin(), s.end());
		if(stoi(s)==i) cnt++;
	}
	cout << cnt << endl;
	
	
	return 0;
}

Measured memory_bytes: 256
H,W = map(int,input().split())

N = int(input())

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

dp = [[0]*W for _ in range(H)]

strate = True
w = 0
h = 0
dp[0][0] = 1

for key,value in enumerate(a):
    if key == 0:
        count = 1
        if value == 1:
            continue       
    else:
        count = 0

    while count < value:
        count += 1
        if strate:
            if w < W-1:
                w += 1
            elif w == W-1:
                strate = False
                h += 1
        else:
            if 0 < w:
                w -= 1
            elif w == 0:
                strate = True
                h += 1

        dp[h][w] = key+1
                
for aa in dp:
    print(*aa)

Measured memory_bytes: 74200