akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
typedef long long int lli;
using namespace std;
int main()
{
	int n,w1;	
	cin>>n>>w1;
	vector<lli> w(n);
	vector<lli> val(n);
	for(lli i=0;i<n;i++)
	{
		cin>>w[i];
		cin>>val[i];
	}
	vector<vector<lli> >v(n+1,vector<lli>(w1+1));
	for(lli i=0;i<n;i++)
	{
		v[i][0]=0;
	}
	for(lli i=0;i<w1;i++)
	{
		v[0][i]=0;
	}
	for(lli i=1;i<=n;i++)
	{
		for(lli j=1;j<=w1;j++)
		{
			if(j-w[i-1]<0)
			{
				v[i][j]=v[i-1][j];
			}
			else
			{
				v[i][j]=max(v[i-1][j],v[i-1][j-w[i-1]]+val[i-1]);
			}
		}
	}
	cout<<v[n][w1]<<endl;
}


Measured memory_bytes: 80256
import Control.Monad
import Data.Functor

main :: IO ()
main = do
  n <- readLn
  as <- join <$> (replicateM n $ map read . words <$> getLine) :: IO [Int]
  print $ solve as

solve :: [Int] -> Int
solve (a:as) = maxProfit as minBound a
  where
    maxProfit :: [Int] -> Int -> Int -> Int
    maxProfit [] maxProf _ = maxProf
    maxProfit (a:as) maxProf minFx
      = maxProfit as (max maxProf (a - minFx)) (min a minFx)



Measured memory_bytes: 188484
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include "bits/stdc++.h"
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

int main() {
	int a, b; char c;
	cin >> a>>c>>b;
	if (c == '+') {
		cout << a + b;
	}else{
		cout << a - b;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) (x).begin(), (x).end()
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

 
int main() {

    ll x;
    cin >> x;
    ll ans = 0;
    ll i = 100;

    while(1) {
        ans++;
        i = i*1.01;
        if(i>=x) {
            cout<<ans<<endl;
            return 0;
        }
    }

 return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
signed main(){
    int n;cin >> n;
    int ret = 0;
    for(int i = 1;i*i <= n;i++){
        //trace(i,n/i);
        if(n%i == 0){
            int m = i-1;
            
            if(m != 0 && n/m == n%m)ret += m;
            if(i*i != n){
                m = n/i -1;
                if(m != 0 && n/m == n%m)ret += m;
            }
        }

    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 3564
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    String op = sc.next();
    int b = sc.nextInt();
    System.out.println( op.equals("+") ? a+b : a-b);
  }
}

Measured memory_bytes: 23764
#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>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)

const int mod = 1000000007;
struct mint {
ll x; 
mint(ll x=0):x((x%mod+mod)%mod){}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
 }
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
 }
 mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
mint res(*this);
return res+=a;
}
mint operator-(const mint a) const {
mint res(*this);
return res-=a;
}
 mint operator*(const mint a) const {
mint res(*this);
return res*=a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
 mint inv() const {
return pow(mod-2);
 }
  mint& operator/=(const mint a) {
return (*this) *= a.inv();
 }
mint operator/(const mint a) const {
mint res(*this);
return res/=a;
 }
};
struct combination {
vector<mint> fact, ifact;
combination(int n):fact(n+1),ifact(n+1) {
  assert(n < mod);
 fact[0] = 1;
 for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
 ifact[n] = fact[n].inv();
  for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n]*ifact[k]*ifact[n-k];
}
  };

int n;
string s;

mint solve(){
    combination c(n+1);
    mint ans=1;
    int k=0;
    rep(i,2*n){
        if(s[i]=='W'){
            if(k==0)return mint(0);
            if((k&1)==0)
            {
                ans*=k;
                k--;
            }
            else {
                k++;
            }
        }else{
            if((k&1)==0){
                k++;
            }
            else {
                ans*=k;
                k--;
            }
        }
    }
    if(k>0)return mint(0);
    return ans*c.fact[n];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);

cin>>n>>s;
cout<<solve().x<<endl;
return 0;
}

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

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

  int n;
  cin >> n;
  string ans = "No";
  for (int i = 1; i < 10; i++) {
    if (n % i) continue;
    int j = n / i;
    if (j >= 1 && j <= 9) {
      ans = "Yes";
      break;
    }
  }
  cout << ans << '\n';
  return 0;
}

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

using namespace std;

int W, H, x, y;
char map[21][21];

void Move(char c)
{
    if (c == 'U') {
        map[y][x] = '^';
        if (y - 1 >= 0 && map[y - 1][x] == '.') {
            swap(map[y][x], map[y - 1][x]);
            --y;
        }
    }
    else if (c == 'D') {
        map[y][x] = 'v';
        if (y + 1 < H && map[y + 1][x] == '.') {
            swap(map[y][x], map[y + 1][x]);
            ++y;
        }
    }
    else if (c == 'L') {
        map[y][x] = '<';
        if (x - 1 >= 0 && map[y][x - 1] == '.') {
            swap(map[y][x], map[y][x - 1]);
            --x;
        }
    }
    else if (c == 'R') {
        map[y][x] = '>';
        if (x + 1 < W && map[y][x + 1] == '.') {
            swap(map[y][x], map[y][x + 1]);
            ++x;
        }
    }
    else if (c == 'S') {
        int dx = 0, dy = 0;
        if (map[y][x] == '^')
            dy = -1;
        else if (map[y][x] == '>')
            dx = 1;
        else if (map[y][x] == 'v')
            dy = 1;
        else if (map[y][x] == '<')
            dx = -1;

        for (int i = 1; ; ++i) {
            if (x + i * dx < 0 || x + i * dx >= W ||
                y + i * dy < 0 || y + i * dy >= H)
                break;
            if (map[y + i * dy][x + i * dx] == '*') {
                map[y + i * dy][x + i * dx] = '.';
                break;
            }
            if (map[y + i * dy][x + i * dx] == '#')
                break;
        }
    }
}

int main()
{
    int T;

    cin >> T;
    while (T--) {
        cin >> H >> W;

        for (int i = 0; i < H; ++i)
            cin >> map[i];
        for (int i = 0; i < H; ++i)
            for (int j = 0; j < W; ++j)
                if (map[i][j] == '^' || map[i][j] == '>' ||
                    map[i][j] == 'v' || map[i][j] == '<')
                    x = j, y = i;

        string order;
        int num;

        cin >> num;
        cin >> order;

        for (int i = 0; i < num; ++i)
            Move(order[i]);

        // Output
        for (int i = 0; i < H; ++i)
            cout << map[i] << "\n";
        if (T != 0)
            cout << endl;
    }

    return 0;
}

Measured memory_bytes: 1208
#include<stdio.h>
#define N 2500000

int main(void){
  int prime[N],i,j,n;

  for(i=2;i<N;i++)
    prime[i]=0;

  prime[0]=1;
  prime[1]=1;

  for(i=2;i*i<=N;i++){
    if(prime[i]==0){
      for(j=2*i;j<N;j+=i){
	prime[j]=1;
      }
    }
  }

  while(scanf("%d",&n),n){
    int count=0;
    for(i=2;i<=n/2;i++){
      if(prime[i]==0 && prime[n-i]==0)count++;
    }
    printf("%d\n",count);
  }
  return 0;
}

Measured memory_bytes: 9000
#include <iostream>
#include "deque"
#include "vector"
using namespace std;
typedef long long ll;
int main()
{
    ll n,x;
    cin >> n;
    deque<ll> deq;
    for (int i=0;i<n;i++){
        cin >> x;
        if (i%2==0)
        deq.push_back(x);
        else deq.push_front(x);
    }
    bool flag=false;
    if (n%2==0){
        for(int i=0;i<deq.size();i++){
            if (flag) cout << " ";
            flag=true;
            cout << *(i+deq.begin());
        }
    }else {
        for (int i=deq.size()-1;i>=0;i--){
           if (flag) cout << " ";
            flag=true;
          cout << *(i+deq.begin());
    }
    }

    return 0;
}


Measured memory_bytes: 3840
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<map>
using namespace std;
int main() {
    string s;
    cin >> s;
    int flag = 1;
    for(int i=0;i<s.size();i++){
        if(i%2==0){
            if(s.at(i) != 'L'){
                flag = 0;
            }else{
                flag = 1;
                break;
            }
        }else{
            if(s.at(i) != 'R'){
                flag = 0;
            }else{
                flag = 1;
                break;
            }
        }
    }
    cout << (flag == 0 ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
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() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll H, N;
    cin >> H >> N;
    vector<ll> A(N);
    vector<ll> B(N);
    for(ll i = 0; i < N; i++){
        cin >> A[i] >> B[i];
    }
    vector<ll> dp(1100000, LLONG_MAX);

    // 初期条件
    dp[0] = 0;
    // ループ
    for (ll i = 0; i < 110000; i++) {
        for(ll j = 0; j < N; j++) {
            if(dp[i]!=LLONG_MAX)chmin(dp[i + A[j]], dp[i] + B[j]);
        }
    }

    //答え
    ll min_num = LLONG_MAX;
    for(ll i = H; i<H+10000; i++) {
        if(dp[i]!=LLONG_MAX) {
            min_num = min(dp[i], min_num);
        }
    }
    cout << min_num << endl;
    return 0;
}

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

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

using namespace std;

bool solve() {

    cin.tie(0);
    ios::sync_with_stdio(false);

    vector<vector<int>> A(3, vector<int>(3));
    REP(i, 3) REP(j, 3) cin >> A[i][j];
    int N;
    cin >> N;
    set<int> b;
    REP(_, N) {
        int tmp;
        cin >> tmp;
        b.insert(tmp);
    }

    vector<vector<int>> B(3, vector<int>(3)); 
    REP(i, 3) REP(j, 3) {
        B[i][j] = b.count(A[i][j]);
    }

    int all_one;
    
    REP(i, 3) {
        all_one = true;
        REP(j, 3) {
            if (!B[i][j]) {
                all_one = false;
                break;
            }
        }
        if (all_one) {
            return true;
        }
    }

    REP(j, 3) {
        all_one = true;
        REP(i, 3) {
            if (!B[i][j]) {
                all_one = false;
                break;
            }
        }
        if (all_one) {
            return true;
        }
    }

    all_one = true;
    REP(i, 3) {
        if (!B[i][i]) {
            all_one = false;
            break;
        }
    }
    if (all_one) {
        return true;
    }

    all_one = true;
    REP(i, 3) {
        if (!B[2 - i][i]) {
            all_one = false;
            break;
        }
    }
    if (all_one) {
        return true;
    }
    return false;
}

int main() {
    cout << (solve() ? "Yes" : "No") << endl; 
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;


int main(int argc, char *argv[]) {
  // C-style stdio functions should not be used.
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  int N;
  cin >> N;
  double x = (double)N / 1.08;
  int p = floor(x) - 1;
  for (int i = 0; i <= 2; i++) {
    int y = floor((double)(p + i) * 1.08);
    if (y == N) {
      cout << p+i << endl;
      return 0;
    }
  }
  cout << ":(" << endl;
  
  return 0;
}



Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

typedef long long ll;

#define rep(i, a, b) for (ll i = a; i < (ll)b; ++i)
#define digit(a) to_string(a).size()
#define INF 10e12
#define MAX 51000
#define all(x) (x).begin(), (x).end()
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))

using namespace std;

const long long MOD = 1e9 + 7;

bool is_prime(ll N)
{
    for (ll i = 2; i * i <= N; ++i)
    {
        if (N % i == 0)
            return false;
    }
    return true;
}
int main(void)
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n, tmp = 0;
    cin >> n;

    vector<ll> vec(n);
    rep(i, 0, n) cin >> vec[i], tmp = tmp ^ vec[i];
    rep(i, 0, n) cout << (tmp ^ vec[i]) << " ";
    cout << endl;
}


Measured memory_bytes: 4764
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=1e9+7;
const int size=1e4;
const long inf=1e9;
long modpow(long x,int n,long p){
	int i=0;long res=1;
	while(n>=(1<<i)){
		if(n&(1<<i)) (res*=x)%=p;
		i++;
		x=(x*x)%p;
	}return res;
}
long modfact(long n,long p){//n! mod p
    if(n>=p) return 0;
    long res=1;
    rep(i,1,n+1) (res*=i)%=p;
    return res;
}
long modperm(long n,long r,long p){//nPr mod p
    if( n-r >= p || r%p > n%p) return 0;
    long res=1;
    rep(i,n-r+1,n+1) (res*=i)%=p;
    return res;
}
long modcomb(long n,long r,long p){//nCr mod p
	long temp=modfact(r,p);
  	long x = temp;
	long res=1; int i=0;
	while( (p-2) >= (1<<i) ){
		if( (p-2) & (1<<i) ) (res*=x)%=p;
		i++; x = x * x % p;
	}
    return (res*modperm(n,r,p))%p;
}
int main(){
	int n,a,b;cin>>n>>a>>b;
	long res = (modpow(2,n,mod) + mod - 1)%mod;
	(res += mod - modcomb(n,a,mod)) %= mod;
	(res += mod - modcomb(n,b,mod)) %= mod;
	cout<<res<<endl;
}

Measured memory_bytes: 256
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>
#include <complex>
#define _USE_CMATH_DEFINES

const long INF = (1l << 30);
const long LINF = (1l << 60); //1.15*10^18

long n;

int main(){
    scanf("%ld", &n);
    if(n % 10 == 2 || n % 10 == 4 || n % 10 == 5 || n % 10 == 7 || n % 10 == 9){
        printf("hon\n");
    }else if(n % 10 == 3){
        printf("bon\n");
    }else{
        printf("pon\n");
    }
}


Measured memory_bytes: 3760
#include <bits/stdc++.h>
    using namespace std;
     
    int main() {
      int H,W;
      cin >> H >> W;
      vector<string> S(H);
      vector<vector<int>> Sh(H+2,vector<int>(W+2));//初期化されてる
      int count=0;
      
      for(int i=0;i<H;i++){
        cin >> S.at(i);
      }
      
      for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
          if(S.at(i).at(j)=='#'){
            Sh[i][j]++;
            Sh[i][j+1]++;
            Sh[i][j+2]++;
            Sh[i+1][j]++;
            Sh[i+1][j+2]++;
            Sh[i+2][j]++;
            Sh[i+2][j+1]++;
            Sh[i+2][j+2]++;
          }
        }
      }
      
      for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
          if(S.at(i).at(j)=='#'){
            cout << S.at(i).at(j);
          }else{
            cout << Sh[i+1][j+1];
          }
        }
        cout << endl;
      }
      
    }

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1e9+7;

int main(void){

    int N; cin>>N;
    int cnt=0;
    ll past; cin>>past;
    int maximum=0;
    for (int i = 1; i < N; ++i) {
        ll tmp; cin>>tmp;
        if(tmp<=past){
            cnt++;
            maximum = max(cnt, maximum);
        }else{
            cnt = 0;
        }
        past = tmp;
    }
    cout<<maximum<<endl;
    return 0;
}

Measured memory_bytes: 256
def bubble_sort(args):
    count = 0
    result = args[:]
    l = len(result) - 1
    for i in range(0, l):
        for j in range(l, i, -1):
            if (result[j] < result[j-1]):
                result[j], result[j-1] = result[j-1], result[j]
                count += 1
    return result, count

if __name__ == '__main__':
    n = int(input())
    args = list(map(int, input().split()))[:n]
    r, c = bubble_sort(args)
    print(' '.join(map(str, r)))
    print(c)



Measured memory_bytes: 5600
#include<iostream>
#include<string>
#include<cmath>
#include<iomanip>
using namespace std;
double PI = acos(-1);

int main(){
    int n;
    double sum;
    double ave;
    while(cin >> n){
        if(n==0)break;
        double s[n];
        sum = 0;
        for(int i=0;i<n;i++){
            cin >> s[i];
            sum += s[i];
        }
        ave = sum / n;
        double alpha=0;
        for(int i=0;i<n;i++) alpha += pow(s[i] - ave, 2);
        cout << setprecision(10) << sqrt(alpha / n) << endl;
        
    }
    return 0;
}


Measured memory_bytes: 3296
numS = input()
numT = input()
numSsep = [charS for charS in numS]
numTsep = [charT for charT in numT]

if len(numS)+1 !=len(numT):
	print("No")
	exit()

i=0
for i in range(len(numSsep)):
	#print(numSsep[i] ," ?= ", numTsep[i] ) 
	if str(numSsep[i]) != str(numTsep[i]) :
		print("No")
		exit()
	#print("roop",i+1,"th end\n")

print("Yes")	


Measured memory_bytes: 9076
import java.util.Scanner;

public class Main {
	boolean check(char[] a, char[] b) {
		for (int i = 0; i < 8; i++) {
			if (a[i] != '*' && a[i] != b[i]) {
				return false;
			}
		}
		return true;
	}

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

		while (true) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			if ((n | m) == 0) {
				break;
			}

			char[][] c = new char[n][];
			int[] d = new int[n];
			for (int i = 0; i < n; i++) {
				c[i] = sc.next().toCharArray();
				d[i] = sc.nextInt();
			}
			char[][] e = new char[m][];
			for (int i = 0; i < m; i++) {
				e[i] = sc.next().toCharArray();
			}

			int sum = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (check(c[i], e[j])) {
						sum += d[i];
					}
				}
			}

			System.out.println(sum);
		}
	}

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

Measured memory_bytes: 34628
#include <bits/stdc++.h>
using namespace std;
#define fi           first
#define se           second
#define ll           long long
#define pb           push_back
#define mp           make_pair
#define pll          pair<ll,ll>
#define pii          pair<int,int>
#define all(x)       (x).begin(),(x).end()
#define isWorking()  cout<<"Wroking"<<endl
#define FOR(i,x,y)   for(int i=x; i<y; i++)
#define SORT(x)      sort(x.begin(),x.end())
#define PRINT(ok)    cout<<(ok? "YES":"NO")<<endl
#define Fast_Input   ios_base :: sync_with_stdio(false), cin.tie(NULL);
typedef vector < int > VI;
const ll mod= 1e9+7,INF=1e18,mx= 5e6+5,mn=100;
int testCase=1,cas=0;

int main() {
    Fast_Input

    //cin>>testCase;
    while(testCase--){
        int ok=1;
        int n; cin>>n;
        while(n--){
            int k; cin>>k;
            if(k%2==0){
                if(k%3==0 || k%5==0){

                }else ok=0;
            }
        }
    cout<<(ok==1? "APPROVED":"DENIED")<<endl;
    }
    return 0;
}


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

Sum = 0
preSum = 0

a = N -1
b = 1

while True:
  c = a // b
  
  #print([a,b,c])
  
  if c < b:
    Sum = preSum * 2 + b - 1
    break
  elif c == b:
    Sum = preSum * 2 + 1 + b - 1
    break
  else:
    preSum += c - 1 - b + 1
    b += 1
  
  #print(preSum)

print(Sum)

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

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

const int mod = 1000000007;
//const int mod = 998244353;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


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

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int K; cin >> K;
    queue<ll> Q;
    rep(i, 9) Q.push(i+1);
    if (K <= 9) {
        cout << K << endl;
        return 0;
    }
    int k = 9;
    while(1) {
        ll x = Q.front(); Q.pop();
        ll d = x % 10;
        for (int dd = -1; dd <= 1; ++dd) {
            int nd = d + dd;
            if (nd < 0 || nd > 9) continue;
            ll nx = 10 * x + nd;
            k++;
//            cout << nx << endl;
            if (k == K) {
                cout << nx << endl;
                return 0;
            }
            Q.push(10 * x + nd);
        }
    }
}


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

using i64 = long long;
const i64 LLINF = (1LL << 60);

int main()
{
    int N;
    string C;
    map < string, string > trans;
    vector < int > T1, T2;

    cin >> N;
    string ans(2 * N, ' ');
     
    trans["Red"] = "RB";
    trans["Blue"] = "BR";

    int l = 1, r = N + 1;

    cout << "?";
    for ( int i = 1; i <= N; i++ ) cout << " " << i;
    cout << endl;
    fflush(stdout);
    cin >> C;
    if ( C == "-1" ) return ( 0 );

    while ( l + 1 < r ) {
        string S;
        int m = (l + r) / 2;
        cout << "?";
        for ( int i = 0; i < N; i++ ) cout << " " << m + i;
        cout << endl;
        fflush(stdout);
        cin >> S;
        if ( S == C ) l = m;
        else r = m;
        if ( S == "-1" ) return ( 0 );
    }
    ans[l - 1] = trans[C][0];
    ans[l - 1 + N] = trans[C][1];
    
    for ( int i = l + 1; i < l + N; i++ ) T1.push_back(i);
    for ( int i = (l + N) % (2 * N); i != (l - 1); (i += 1) %= (2 * N) ) T2.push_back(i + 1);
    for ( int i = 1; i <= 2 * N; i++ ) {
        string S;
        if ( find(begin(T1), end(T1), i) != T1.end() ) {
            cout << "? " << i;
            for ( auto x : T2 ) cout << " " << x;
            cout << endl;
            fflush(stdout);
            cin >> S;
            if ( S == "Red" ) ans[i - 1] = 'R';
            else ans[i - 1] = 'B';
        } else if ( find(begin(T2), end(T2), i) != T2.end() ) {
            cout << "? " << i;
            for ( auto x : T1 ) cout << " " << x;
            cout << endl;
            fflush(stdout);
            cin >> S;
            if ( S == "Red" ) ans[i - 1] = 'R';
            else ans[i - 1] = 'B';
            if ( S == "-1" ) return ( 0 );
        }
    }
    
    cout << "! " << ans << endl;
    fflush(stdout);
    return ( 0 );
}


Measured memory_bytes: 724
public class Hello{
    public static void Main(){

        string[] input = System.Console.ReadLine().Split(' ');
        int A = int.Parse(input[0]);
        int B = int.Parse(input[1]);
        int C = int.Parse(input[2]);
        
        if((A == 5 && B == 5 && C == 7) || (A == 5 && B == 7 && C == 5) || (A == 7 && B == 5 && C == 5)){
            System.Console.WriteLine("YES");
        }else{
            System.Console.WriteLine("NO");
        }
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <algorithm>
#include <string>
// #include <vector>
using namespace std;
int main()
{
  int A, B, C, X;
  cin >> A >> B >> C >> X;

  int count = 0;
  for(int i = 0; i <= A; i++)
  for(int j = 0; j <= B; j++)
  for(int k = 0; k <= C; k++){
    if(X == 500*i + 100*j + 50*k) ++count;
  }

  cout << count << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <array>
#include <tuple>
#include <random>

using namespace std;
typedef long long int ll;

#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 all(x) (x).begin(), (x).end()

#define inf 10000000000

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

    ll r, g;
    cin >> r >> g;
    cout << g * 2 - r << endl;
}


Measured memory_bytes: 256
// KALAM
# include <bits/stdc++.h>
# define int long long
# define debug(x) cerr << #x << " = " << x << endl

using namespace std;

const int N = 100000 + 77 , inf = 1000000000 + 77;
int n , m , v , p;
int a[N];
inline int Get(vector < int > X , int t) {
   // each time take t numbers and redice them by 1 , X is sorted
   if(t <= 0)
      return inf;
   long long le = 0 , ri = 1e15;
   int sz = X.size();
   while(ri - le > 1) {
      long long mid = ((le + ri) >> 1);
      long long low = mid , high = 0 , val_low = 0;
      for(int i = sz - 1;i >= 0;-- i) {
         long long x = X[i];
         x = min(x , mid);
         if(low > x) {
            low -= x;
            high += x;
         } else {
            x -= low;
            high = mid;
            ++ val_low;
            swap(low , high);
            low -= x;
            high += x;
         }
      }
      //cout << mid << ' ' << val_low << endl;
      if(val_low >= t)
         le = mid;
      else
         ri = mid;
   }
   return le;
}
int32_t main() {
   //cout << Get({1 , 2 , 10} , 3);
   scanf("%lld %lld %lld %lld" , & n , & m , & v , & p);
   for(int i = 1;i <= n;++ i)
      scanf("%lld" , a + i);
   sort(a + 1 , a + 1 + n);
   int le = 0 , ri = n;
   while(ri - le > 1) {
      int mid = ((le + ri) >> 1);
      if(a[n - p + 1] > a[mid] + m) {
         le = mid;
         continue ;
      }
      vector < int > X;
      int new_v = v - mid - (p - 1);
      for(int i = mid + 1;i <= n - p + 1;++ i)
         X.push_back(a[mid] + m - a[i]);

      if(Get(X , new_v) >= m)
         ri = mid;
      else
         le = mid;
   }
   printf("%lld\n" , n - le);
   return 0;
}


Measured memory_bytes: 2884
s = gets.chomp
t = gets.chomp

n = s.length - t.length + 1
m = t.length

min_count = m
n.times do |i|
  count = 0
  m.times do |j|
    count += 1 if s[i + j] != t[j]
  end
  min_count = count if min_count > count
end

puts min_count


Measured memory_bytes: 14328
LI = lambda: list(map(int,input().split()))
MI = lambda: map(int,input().split())
yes = lambda: print("Yes")
no = lambda: print("No")
I = lambda: list(input())
J = lambda x: "".join(x)
II = lambda: int(input())
SI = lambda: input()
#---khan17---template
a,b,c,d = MI()
while(a > 0 and c >0):
	c-=b
	if c<=0:
		yes()
		break
	a-=d
	if a<=0:
		no()
		break

Measured memory_bytes: 9180
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    int water[] = {10, 20, 30, INT_MAX};
    int value[] = {125, 140, 160};

    for(;;){
        int w;
        cin >> w;
        if(w == -1)
            return 0;

        int ret = 1150;
        for(int i=0; i<3; ++i){
            if(w > water[i]){
                ret += (min(water[i+1], w) - water[i]) * value[i];
            }
        }
        cout << (4280 - ret) << endl;
    }
}

Measured memory_bytes: 0
//----------------------------------------------------------------------
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
//----------------------------------------------------------------------

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;

int main(void) {
    int n;
    cin >> n;
    vector<int> h(n);
    REP(i, n) cin >> h[i];

    for(int i = n - 1; i >0; --i) {
        if(h[i]>=h[i-1]) {
        }else if(h[i] == h[i-1]-1) {
            h[i-1]--;
        }else {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s,t;
	cin>>s; 
	t=s;
	reverse(s.begin(),s.end());//新函数 调转;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='b') s[i]='d';
		else if(s[i]=='d') s[i]='b';
		else if(s[i]=='p') s[i]='q';
		else if(s[i]=='q') s[i]='p';
	}
	if(s==t) cout<<"Yes";
	else cout<<"No";
	return 0;
}

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

using namespace std;

int main() {
    int h, w, i, j, ans;
    cin >> h >> w;
    char t;
    int g[1001][1001];
    int arrs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    vector<pair<int, int> > pts;
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            cin >> t;
            if (t == '.') g[i][j] = 0;
            else {
                g[i][j] = 1;
                pts.push_back(make_pair(i, j));
            }
        }
    }
    ans = 0;
    while (pts.size() != 0) {
        vector<pair<int, int> > newPts;
        for (auto &pt : pts) {
            int x = pt.first, y = pt.second;
            for (int k = 0; k < 4; k++) {
                if (x + arrs[k][0] < 0 || x + arrs[k][0] > h - 1 || y + arrs[k][1] < 0 || y + arrs[k][1] > w - 1
                  || g[x + arrs[k][0]][y + arrs[k][1]] != 0) {
                    continue;
                }
                g[x + arrs[k][0]][y + arrs[k][1]] = 1;
                newPts.push_back(make_pair(x+arrs[k][0], y+arrs[k][1]));
            }
        }
        pts = newPts;
        ans++;
    }
    cout << ans - 1;
    return 0;
}

Measured memory_bytes: 18792
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>

using namespace std;

typedef long long ll;

int main(){
  int h,w,a,b;
  scanf("%d %d %d %d",&h,&w,&a,&b);
  printf("%d\n",(h-a)*(w-b));
  
  return 0;
}


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

int main(){
	int x,y,z;
	cin>>x>>y>>z;
	if(x==y){
		if(x>z){
			cout<<z<<" "<<x<<" "<<y;
		}else{
			cout<<x<<" "<<y<<" "<<z;
		}
	}else if(y==z){
		if(y>x){
			cout<<x<<" "<<y<<" "<<z;
		}else{
			cout<<y<<" "<<z<<" "<<x;
		}
	}else if(z==x){
		if(z>y){
			cout<<y<<" "<<z<<" "<<x;
		}else{
			cout<<z<<" "<<x<<" "<<y;
		}
	}else if(x<y){
		if(y<z){
			cout<<x<<" "<<y<<" "<<z;
		}else if(x<z&&z<y){
			cout<<x<<" "<<z<<" "<<y;
		}else if(z<x&&z<y){
			cout<<z<<" "<<x<<" "<<y;
		}
	}else if(y<x){
		if(x<z){
			cout<<y<<" "<<x<<" "<<z;
		}else if(y<z&&z<x){
			cout<<y<<" "<<z<<" "<<x;
		}else if(z<y&&z<x){
			cout<<z<<" "<<y<<" "<<x;
		}
	}else if(z<x){
		if(x>y){
			cout<<z<<" "<<x<<" "<<y;
		}else if(z<y&&y<x){
			cout<<z<<" "<<y<<" "<<x;
		}
	}
	cout<<endl;
	return 0;

}

Measured memory_bytes: 1164
n,a,b,c,d = map(int,input().split())
s = input()

from itertools import groupby 

gr = groupby(s)

#AからCへいけるかどうか
for i in range(a-1,c-1):
    if s[i]=='#' and s[i+1]=='#':
        print('No')
        exit(0)
#BからDへいけるかどうか
for i in range(b-1,d-1):
    if s[i]=='#' and s[i+1]=='#':
        print('No')
        exit(0)


if c<b:
    print('Yes')
else:
    if c<d:
        print('Yes')
    else:
        for i in range(b-2,d-1):
            if s[i]=='.' and s[i+1]=='.' and s[i+2]=='.':
                print('Yes')
                exit(0)        
        print('No')


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

namespace AtCorder
{
    class Program
    {
        static void Main(string[] args)
        {

            var NM = ReadSplitInt();
            var n = NM[0];
            var m = NM[1];
            var a = ReadSplitLongLines(m);

            var dp = new long[n + 1];
            var instrusion = new bool[n + 1];

            // 1段目への移動方法数
            dp[0] = 1;

            // 侵入負荷の段数設定（trueが侵入負荷）
            for (long i = 0; i < m; i++)
            {
                instrusion[a[i][0]] = true;
            }

            for (long i = 0; i <= n; i++)
            {
                // 1段か2段先へ移動
                for (long j = 1; j <= 2; j++)
                {
                    if (i + j <= n)
                    {
                        // 侵入不可への移動はできない
                        if (instrusion[i + j] != true)
                        {
                            // i番目からi+j番目への移動
                            dp[i + j] += dp[i];
                            dp[i + j] %= 1000000007;
                        }
                    }
                }
            }
            Console.WriteLine(dp[n]);


            Console.ReadKey();
        }



        #region MyRegion

        public static int ReadInt()
        {
            return int.Parse(Console.ReadLine());
        }

        /// <summary>
        /// 空白区切の数値を取得する
        /// </summary>
        /// <returns>The read split int.</returns>
        public static int[] ReadSplitInt()
        {
            return Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
        }

        /// <summary>
        /// 空白区切の数値を取得
        /// </summary>
        /// <returns>The read split long.</returns>
        public static long[] ReadSplitLong()
        {
            return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
        }


        public static int[][] ReadSplitIntLines(int n)
        {
            return Enumerable.Range(0, n).Select(x => ReadSplitInt()).ToArray();
        }

        public static long[][] ReadSplitLongLines(int n)
        {
            return Enumerable.Range(0, n).Select(x => ReadSplitLong()).ToArray();
        }

        public static long[][] ReadSplitLongLines(long n)
        {
            var ret = new List<long[]>();
            for (long i = 0; i < n; i++)
            {
                ret.Add(ReadSplitLong().ToArray());
            }

            return ret.ToArray();
        }

        #endregion

    }
}


Measured memory_bytes: 24640
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>
#include <tuple>

#define llong long long
#define rep(i,l,n) for(llong (i)=(l);(i)<(n);(i++))
#define _min(a,b) ((a)<(b)?(a):(b))
#define _max(a,b) ((a)>(b)?(a):(b))
#define _abs(a) ((a)>0?(a):(-(a)))

using namespace std;

int main(){
	int k;
	cin >> k;
	rep(i,0,k) cout << "ACL";
	return 0;
}


Measured memory_bytes: 3596
#include<stdio.h>
int main(void){
    int a;
    
    scanf("%d",&a);
    char b[a+1];

    scanf("%s",&b);

    for(int i=0;b[i];i++){
        if(b[i]==b[i+1]){
            a--;
        }
    }
    
    printf("%d\n",a);

    return 0;
}

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

#define rep(i, s, n) for (Int i = s; i < (Int)(n); i++)
#define rrep(i, n, s) for (Int i = n - 1; i >= s; i--)
#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).end()
 
double EPS = 1e-10;
Int INF = 1e18;
int inf = 1e9;
Int mod = 1e9+7;

Int l[200001];
Int r[200001];

int main() {
    Int n, k, c;
    cin >> n >> k >> c;
    string s;
    cin >> s;
    Int pre = -INF;
    Int cnt1 = 0;
    rep(i, 0, n) {
        if (s[i] == 'o' and i - pre > c) {
            cnt1++;
            l[i] = cnt1;
            pre = i;
        }
    }
    pre = INF;
    Int cnt2 = 0;
    rrep(i, n, 0) {
        if (s[i] == 'o' and pre - i > c) {
            cnt2++;
            r[i] = cnt2;
            pre = i;
        }
    }
    if (cnt1 > k) return 0;
    //rep(i, 0, n) cout << r[i] << " "; cout << endl;
    rep(i, 0, n) {
        if (0 < l[i] and 0 < r[i]) dump(i + 1);
    }
    return 0;
}

Measured memory_bytes: 4996
#include <bits/stdc++.h>
using namespace std;  
typedef long long ll;
int main() {
  ll N;
  cin >> N;
  vector<ll> a1(N),a2(N);
  for (ll i=0;i<N;i++) {
    cin >> a1.at(i);
  }
  for (ll i=0;i<N;i++) {
    cin >> a2.at(i);
  }
  
  for (ll i=1;i<N;i++) {
    a1.at(i) += a1.at(i-1);
  }
  
  a2.at(0) += a1.at(0);
  for (ll i=1;i<N;i++) {
    a2.at(i) += max(a1.at(i),a2.at(i-1));
  }
  
  cout << a2.at(N-1);
}

Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)
#define in(a) scanf("%lld", &(a))
#define ind(a) scanf("%lf", &(a))
#define put(a) printf("%lld\n", (a))
#define putd(a) printf("%.15f\n", (a));
//def   puts(a) printf("%s\n", a) 文字はこっち
//your code here!


int main(void){
    ll N, L[11], MAX=0, sum=0;
    in(N);
    rep(i, N){
        in(L[i]);
        chmax(MAX, L[i]);
        sum += L[i];
    }
    puts(MAX<sum-MAX?"Yes":"No");
    return 0;
}


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


S = [input() for _ in range(H)]
Ans = [[0]*W for _ in range(H)]
cnt = 1
for y, s in enumerate(S):
    for x, c in enumerate(s):
        if c=="#":
            Ans[y][x] = cnt
            cnt += 1

for y in range(H):
    k = 0
    for x in range(W):
        if Ans[y][x] == 0:
            Ans[y][x] = k
        else:
            k = Ans[y][x]
    for x in range(W-1, -1, -1):
        if Ans[y][x] == 0:
            Ans[y][x] = k
        else:
            k = Ans[y][x]

for x in range(W):
    k = 0
    for y in range(H):
        if Ans[y][x] == 0:
            Ans[y][x] = k
        else:
            k = Ans[y][x]
    for y in range(H-1, -1, -1):
        if Ans[y][x] == 0:
            Ans[y][x] = k
        else:
            k = Ans[y][x]

for ans in Ans:
    print(" ".join(map(str, ans)))


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

#define NDEBUG
#include <cassert>


typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define eb  emplace_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair

#define PQ(T) priority_queue<T>
#define RPQ(T) priority_queue<T,vector<T>,greater<T>>

template<class T> inline void amin(T & a, T const & b) { a = min(a, b); }
template<class T> inline void amax(T & a, T const & b) { a = max(a, b); }

inline ll square(ll x) { return x * x; }
inline ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }
template <typename T>
inline T mod(T a, T b) { return ((a % b) + b) % b; }



long double solve(int N, int K){
    vi dp(K+1, -1);
    dp[K] = 0;
    for (int k=K-1; k>=1; --k) {
        if (k*2 > K) { dp[k]=1; continue; }
        dp[k] = dp[k*2] + 1;
    }
    vector<long double> r(21);
    r[0] = 1;
    for (int i=1; i<=20; ++i) {
        r[i] = r[i-1] * 0.5;
    }

    long double acc = 0;
    rep1(i,N){
        int t = (i >= K)? 0 : dp[i];
        acc += r[ t ];
    }
    acc /= N;
    return acc;
}

int main() {
    int n,k; cin >> n >> k;
    printf("%.12Lf\n", solve(n,k));
    return 0;
}


Measured memory_bytes: 640
/*|In The Name of Allah|*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<pair<int,int> > vii;
typedef map<int, int> mii;
typedef map<string, int> msi;
typedef pair<int, int> pii;
#define el	'\n'
#define lp(i,n) for(int i = 0;i < int(n);i++)
#define rlp(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rng(i,a,b) for(int i = int(a);i <= int(b);i++)
#define mp(x,y)  	make_pair((x),(y))
#define pb(x)    	push_back((x))
#define all(v)  	((v).begin()),((v).end())
#define sz(x)  		((int) (x).size())
#define bits(a) 	__builtin_popcountll(a)
#define fr first
#define sc second
#define pii pair<int, int>
#define sortva(v) sort(all(v))
#define sortvd(v) sort(v.rbegin(),v.rend())
#define sortaa(a,n) sort(a,a+n)
#define sortad(a,n) sort(a,a+n),reverse(a,a+n)
#define SS stringstream
#define ll long long
#define clr(x, y) memset(x, y, sizeof(x))
#define foreach(it,x) for(__typeof__((x).begin()) it = (x).begin(); it != (x).end(); ++it)
int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
ll gcd(ll a, ll b){if (a == 0)return b;return gcd(b % a, a);}



void MisSiOn_ImPosSiBlE(){
//freopen("portals.in", "r", stdin);
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

}


int const N = 5e5 + 9, mod = 1e9+7 , oo = 0x3f3f3f3f;
//------------------------------------------------------------------------------------



int n;
ll res,arr[N];
int main()
{
    MisSiOn_ImPosSiBlE();

    vi v;
    int m;
    cin>>m>>n;
    m--;
    lp(i,n)cin>>arr[i];
    sort(arr,arr+n);
    for (int i=1;i<n;i++){
        v.push_back(arr[i]-arr[i-1]);
    }


    sortvd(v);
    lp(i,v.size()){
    if (m)m--;
    else{
        res+=v[i];
    }
    }

    cout<<res;




















/*
*/
    return 0;
}


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

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

  vector<int> nodes[100001];
  vector<int> signposts(n + 1, -1);

  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    nodes[a].push_back(b);
    nodes[b].push_back(a);
  }

  queue<int> next_rooms;
  next_rooms.push(1);

  while (!next_rooms.empty()) {
    int signpost = next_rooms.front();
    next_rooms.pop();

    for (int room : nodes[signpost]) {
      if (signposts[room] == -1) {
        signposts[room] = signpost;
        next_rooms.push(room);
      }
    }
  }

  cout << "Yes" << endl;

  for (int i = 2; i <= n; i++) {
    cout << signposts[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 10116
n,k = map(int, raw_input().split(' '))
r,s,p = map(int, raw_input().split(' '))
seq = raw_input()

import collections
q,i = collections.deque(), 0
while(i < len(seq)):
	u = q.popleft() if len(q) == k else [0,0,0]
	q.append( [ max(u[1], u[2]) + (r if seq[i]  == 's' else 0) ,max(u[0], u[2]) + (s if seq[i]  == 'p' else 0) ,max(u[0], u[1]) + (p if seq[i]  == 'r' else 0)])
	i +=1
print sum([max(cc) for cc in q] or [0])


Measured memory_bytes: 43932
#include <iostream>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <iomanip>
#include <cstdio>

using namespace std;

void trace(int A[], int N) {
	int i;
	for (int i = 0; i < N; ++i) {
		if (i > 0)printf(" ");
		printf("%d", A[i]);
	}
	printf("\n");
}

void insert(int A[], int N) {
	int j, i, v;
	for(i = 1;i<N;++i){
		v = A[i];
		j = i - 1;
		while (j >= 0 && A[j] > v) {
			A[j + 1] = A[j];
			j--;
		}
		A[j + 1] = v;
		trace(A, N);
	}
}

int main() {
	int w, s;
	cin >> s >> w;

	if (s <= w) {
		cout << "unsafe" << endl;
	}
	else {
		cout << "safe" << endl;
	}

	return 0;
}

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

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

map<int, vector<P> > mp;

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

  while(1) {
    int a, b, c;
    cin >> a >> b >> c;
    if(!a) break;
    mp[a].pb(P(b, c));
  }

  int l;
  cin >> l;
  rep(i, 0, l) {
    int h[10001] = {};
    rep(j, 1, m + 1) cin >> h[j];
    rep(j, 1, n + 1) {
      int kyu = 0;
      rep(k, 0, mp[j].size()) {
        kyu += h[mp[j][k].first] * mp[j][k].second;
      }
      cout << kyu;
      if(j == n) cout << endl;
      else cout << " ";
    }
  }
}

Measured memory_bytes: 4804