akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <string.h>

int main() {	
	char X[150][1001];
	char Y[150][1001];
	int figureXY[1001][1001] ;
	int longX, longY;
	int dataSetN;
	int max;
	int i, j, k;
	longX = 0;	longY = 0;

	scanf("%d", &dataSetN);
	for (i = 0; i < dataSetN; i++) {
		scanf("%s", X[i]);
		scanf("%s", Y[i]);
	}

	for (i = 0; i < dataSetN; i++) {
		max = 0;
		longX = strlen(X[i]);
		longY = strlen(Y[i]);
		for (j = 0; j <= longX; j++) {
			figureXY[j][0] = 0;
		}
		for (j = 0; j <= longY; j++) {
			figureXY[0][j] = 0;
		}

		for (j = 1; j <= longX; j++) {
			for (k = 1; k <= longY; k++) {
				if (X[i][j - 1] == Y[i][k - 1]) {
					figureXY[j][k] = figureXY[j - 1][k - 1] + 1;
				}
				else if (figureXY[j - 1][k] >= figureXY[j][k - 1]) {
					figureXY[j][k] = figureXY[j - 1][k];
				}
				else {
					figureXY[j][k] = figureXY[j][k - 1];
				}

				if (figureXY[j][k] > max) {
					max = figureXY[j][k];
				}
			}
		}

		printf("%d\n", max);
	}

	return 0;
}

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

long long s;
long long ans[10] = {0};

void solve();

int main() {
  cin >> s;
  solve();
  for(int i = 0; i < 6; ++i) {
    if(i != 0) cout << " ";
    cout << ans[i];
  }
  cout << endl;
  return 0;
}

void solve() {
  ans[0] = ans[1] = 0;
  ans[2] = (long long)1e9;
  ans[3] = 1;
  ans[5] = s / (long long)1e9 + 1;
  ans[4] = ans[5] * (long long)1e9 - s;
  if(ans[5] > (long long)1e9) {
    --ans[5];
    --ans[3];
  }
}

Measured memory_bytes: 256
// Problem : C - Rally
// Contest : AtCoder - AtCoder Beginner Contest 156
// URL : https://atcoder.jp/contests/abc156/tasks/abc156_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize "trapv"//  WA to RE int!!
#include <bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORR(i,n) for(int i=n;i>=0;i--)
#define pb push_back
#define vint vector<int>
#define sint set<int>
#define mint map<int,int>
#define pint pair< int,int >
#define int long long int 
#define test int tt1234; cin>>tt1234;while(tt1234--)
#define endl "\n"
#define SI(a,n) int a[n];FOR(i,n) cin>>a[i];
#define input(a,n) int n;cin>>n; SI(a,n)
#define all(zz) zz.begin(),zz.end()
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define error(x) cerr << #x <<" is " << x << endl;
#define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
#define precision(x) cout<<fixed<<setprecision(x);
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define present(container, element) (container.find(element)!=container.end())
#define fint fast;test
#define set(a,x) memset(a,x,sizeof(a))
#define L(x)	((x)<<1)
#define R(x)	(((x)<<1)+1)
#define ft first
#define se second
#define MOD 1000000007
using namespace std;
template<typename... T> void rd(T&... args) { ((cin >> args), ...); }
template<typename... T> void pp(T... args) { ((cout << args << " "), ...); cout<<"\n"; }

void solve(){
	int n;
	rd(n);
	vint arr(n);
	for(int & v:arr)rd(v);
	int l=*min_element(all(arr)),h=*max_element(all(arr));
	int ans=INT_MAX;
	for(int i=l;i<=h;i++)	
	{
		int temp=0;
		for(auto v:arr)temp+=((i-v)*(i-v));
		ans=min(ans,temp);
	}
	pp(ans);
	return;	
}


int32_t main() {
    // fint{
    	fast;
    	solve();
    // }
    return 0;
}


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

int main() {
	int N;
	while ( cin >> N ) {
		if ( N == 0 ) {		 
			break;
		}
		typedef pair<double, string> P;
		vector<P> ans;
		while ( N-- ) {
			string l;
			int p;
			cin >> l >> p;
			int t = 0;
			int d = 0;
			for ( int i = 0; i < 5; i++ ) {
				int a;
				cin >> a;
				if ( i <= 2 ) t += a;
				else d += a;
			}
			int f, s, m;
			int sum = 0;
			cin >> f >> s >> m;

			t += d*m;
			sum = f*s*m;
			ans.push_back(P(-((double)(sum-p)/(double)t), l));
		}
		sort(ans.begin(), ans.end());

		for ( int i = 0; i < ans.size(); i++ ) {
			cout << ans[i].second << endl;
		}
		cout << '#' << endl;
	}
	return 0;
}
	



Measured memory_bytes: 3128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[2][11111];
int N,M;
ll P[11111];
ll C[555];
ll E[555];
ll K[11111];
#define INF (11111111111LL)
ll solve(){
  int id = 0;
  fill(dp[0],dp[2],INF);
  dp[0][0] = 0;
  for(int i=0;i<N;i++){
    id = i&1;
    for(int j=0;j<=M;j++){
      int nd = id^1;
      if( dp[id][j] == INF ) continue;
      //      printf("%d %d  =  %lld\n",i,j,dp[id][j]);
      ll m = min((ll)M,j+C[i]);
      dp[nd][m] = min(dp[nd][m],
                      dp[id][j] + E[i]);
      dp[nd][j] = min(dp[nd][j], dp[id][j]);
    }
  }
  id=N&1;
  K[M] = dp[id][M];
  for(int i=M-1;i>-1;i--){
    // cout << K[i+1] << endl;
    K[i] = min(K[i+1],dp[id][i]);
  }
  sort(P,P+M);
  ll res = 0;
  ll sum = 0;
  for(int i=M-1;i>-1;i--){
    sum += P[i];
    int nums = M-i;
    ll ri = sum - K[nums];
    res = max(ri,res);
  }

  return res;

}

int main(){
  cin >> M >> N;
  for(int i=0;i<M;i++){
    cin >> P[i];
  }
  for(int i=0;i<N;i++){
    cin >> C[i] >> E[i];
  }
  cout << solve() << endl;
}

Measured memory_bytes: 1528
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int N=500;

int n, m, k, u, v, x, y, t, a, b, ans;
char A[N][N], B[N][N], C[N][N];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m;
	for (int i=0; i<n; i++) for (int j=0; j<m; j++){
		cin>>A[i][j];
		B[i][j]=C[i][j]=A[i][j];
	}
	for (int i=0; i<m; i++) B[0][i]=C[n-1][i]='#';
	for (int i=1; i<n-1; i++) for (int j=0; j<m; j++){
		if (j&1) B[i][j]='#';
		else C[i][j]='#';
	}
	for (int i=0; i<n; i++){
		for (int j=0; j<m; j++) cout<<B[i][j];
		cout<<"\n";
	}
	cout<<"\n";
	for (int i=0; i<n; i++){
		for (int j=0; j<m; j++) cout<<C[i][j];
		cout<<"\n";
	}
	
	return 0;
}


Measured memory_bytes: 4400
def solve(a,b):  # fix inputs here
    a = int(a)
    res = int(b[0]) * 100 * a + int(b[2]) * 10 * a + int(b[3]) * 1 * a 
    return res//100

a,b = input().split()
res = solve(a,b)
print(res)

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s,t,f;
    cin>>s>>t;
    int a=s.size();
    f=t.substr(0,a);
    if(f==s)
        cout<<"Yes";
    else
        cout<<"No";
    
    return 0;
}

Measured memory_bytes: 3536
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast") 
#define int long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back 
#define eb emplace_back
#define fn for(int i =0 ;i <n;i++)
#define fn1 for( int i =1;i<=n;i++)
#define fm for(int j =0 ;j <m;j++)
#define fm1 for(int j =1;j<=m;j++)
#define fi first
#define se second
#define endl '\n'
# define PI  3.14159265358979323846
#define MOD 1000000007
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
const int N = 1e3+5;
const int INF = 1e18L;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
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...);
}
char ar[N][N];
int dp[N][N];
int n , m;
inline int add(int x, int y, int mod) {
   if (y >= mod) y %= mod;
   if (x >= mod) x %= mod;
   x  += y;
   return (x >= mod ? x - mod : x);
} 
int solve(int x, int y){
	if(x<0||y<0||x>=n||y>=m||ar[x][y]=='#')return 0;
	if(dp[x][y]!=-1)return dp[x][y];
	if(x==n-1 && y==m-1)return 1;
	int ans =0 ;
	ans = add(ans, solve(x+1,y),MOD);
	ans = add(ans, solve(x,y+1),MOD);
	return dp[x][y]=ans;
}
signed main(){
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	// #endif
	IOS;
	int T=1;
	// cin >> T;
	while(T--){
		cin >> n >> m ;	
		fn{
			fm{
				cin >> ar[i][j];
				dp[i][j]=-1;
			}
		}
		cout << solve(0,0) << endl;
	
	
	}
	cerr << "Time Taken : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
	return 0;
}

Measured memory_bytes: 9216
#include <iostream>
#include <map>
#include <cstring>
using namespace std;

const int size = 1000;
int G[size][size];
int C[size];
map <int, int> M;
int M_index;
bool flag;

void set_index( int a ) 
{
  if ( M.find( a ) != M.end() ) return;
  M[a] = M_index; 
  M_index++;
}

void init()
{
  memset( G, 0, sizeof(G) );
  memset( C, 0, sizeof(C) );
  M.clear();
  flag = false;
}

int main( void ) 
{
  int a, b;
  flag = true;
  while ( cin >> a >> b ) {
    if ( a == 0 && b == 0 ) {
      for ( int i = 0; i < size; i++ ) {
        for ( int j = 0; j < size; j++ ) {
          if ( G[i][j] > 0 ) C[i] += G[i][j];
        }
      }
      bool ok = true;
      int start = M[1], goal = M[2];
      for ( int i = 0; i < size; i++ ) {
        if ( !C[i] ) continue;
        if ( i == start || i == goal ) {
          if ( C[i] % 2 == 0 ) ok = false;
        } else {
          if ( C[i] % 2 != 0 ) ok = false;
        }
      }
      // output
      cout << ( ok ? "OK" : "NG" ) << endl;
      flag = true;
    } else {
      if ( flag ) {
        init();
      }
      set_index( a );
      set_index( b );
      int index_a = M[a], index_b = M[b];
      G[index_a][index_b]++;
      G[index_b][index_a]++;
    }
  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define ll long long
const int mod=1e9+7;
using namespace std;

int main()
{
    //freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
    string s;
    cin>>s;
    s+='~';
    for(int i=0; i<s.size()-2; i++)
    {
        if(s[i]==s[i+1])
        {
            cout<<i+1<<" "<<i+2<<endl;
            return 0;
        }
        if(s[i]==s[i+2])
        {
            cout<<i+1<<" "<<i+3<<endl;
            return 0;
        }

    }
    cout<<-1<<" "<<-1<<endl;
}



Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  Int n,k;
  cin>>n>>k;
  k=(n-1)*(n-2)/2-k;
  if(k<0){
    cout<<-1<<endl;
    return 0;
  }

  using P = pair<Int, Int>;
  vector<P> es;
  for(Int i=1;i<n;i++)
    es.emplace_back(0,i);

  for(Int i=1;i<n;i++)
    for(Int j=1;j<i;j++)
      if(k>0) es.emplace_back(j,i),k--;

  cout<<es.size()<<endl;
  for(auto p:es) cout<<p.first+1<<" "<<p.second+1<<endl;
  return 0;
}


Measured memory_bytes: 512
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int MOD = 10007;
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s = sc.next();
		int[][] dp = new int[n+1][8]; dp[0][1] = 1;
		for (int i=0;i<n;i++) for (int j=1, p = s.charAt(i) != 'J' ? s.charAt(i) != 'O' ? 2 : 1 : 0;j<8;j++) {
			if (((j>>p)&1) == 0 ) continue;
			for (int l=1;l<8;l++) {
				if ((j&l) == 0) continue;
				dp[i+1][j] = (dp[i+1][j] + dp[i][l]) % MOD;
			}
		}
		int sum = 0;
		for (int i=1;i<8;i++) sum = (sum+dp[n][i]) % MOD;
		System.out.println(sum);
	}
}

Measured memory_bytes: 18132
#include<iostream>
#include<numeric>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<map>
#include<utility>
#include<cmath>
#include<tuple>
#include<string>
#include<bitset>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
using namespace std;
typedef long long ll;

int main(){
    int n; cin>>n;
    set<string> s;
    for(int i=0;i<n;i++){
        string t; cin>>t;
        s.insert(t);
    }
    cout<<s.size()<<endl;
}

Measured memory_bytes: 19152
#!/usr/bin/env python3

n = int(input())
r = n%10
if r == 2 or r == 4 or r == 5 or r == 7 or r == 9:
    print('hon')
elif r == 0 or r == 1 or r == 6 or r == 8:
    print('pon')
else:
    print('bon')

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

typedef long long ll;

ll N;
vector<pair<ll, ll>> Tasks;

bool solve() {
  ll t = 0;
  for (auto task : Tasks) {
    t += task.second;
    if (t > task.first) return false;
  }
  return true;
}
int main() {
  cin >> N;
  for (ll i = 0; i < N; ++i) {
    ll a, b;
    cin >> a >> b;
    Tasks.push_back(make_pair(b, a));
  }
  sort(Tasks.begin(), Tasks.end());
  cout << (solve() ? "Yes" : "No") << endl;
  return 0;
}


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

using namespace std;

#define REP1(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pow(x) x*x
#define ll long long
static const ll MAX = 1000000;
static const ll INFTY = 1e12;

struct edge {
    ll to;
    char cost;
};

using Graph = vector<vector<int>>;
using _Graph = vector<vector<edge>>;
// 入力
int H, W;
vector<vector<char>> field;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

// 深さ優先探索
vector<bool> seen;
vector<int> colors;

int N;

int main(void){
    
    ll N;
    cin >> N;
    vector<ll> A(N+1), B(N);
    REP(i, N+1)cin >> A[i];
    REP(i, N)cin >> B[i];

    ll ans = 0;

    REP(i, N){
        ll tmp = A[i] - B[i];
        ll tmp2;
        if(tmp < 0) {
            tmp2 = A[i+1] + tmp; 
            if(tmp2 < 0){
                ans += A[i] + A[i+1];
                A[i+1] = 0;
            } else{
                ans += A[i] + A[i+1] - tmp2;
                A[i+1] = tmp2;
            }
            
        }else{
            ans += A[i] - tmp;
        }
        // cout << ans << " ";
    }
    cout << ans << endl;

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


Measured memory_bytes: 1792
card = []
for i in range(3):
    card.append(list(map(int, input().split())))

N = int(input())

result = [[0, 0, 0],[0, 0, 0],[0, 0, 0]]
for _ in range(N):
    b = int(input())
    for i in range(3):
        for j in range(3):
            if b == card[i][j]:
                result[i][j] = 1

judge = 'No'

for i in range(3):
    if result[i][0] * result[i][1] * result[i][2] == 1:
        judge = 'Yes'

for i in range(3):
    if result[0][i] * result[1][i] * result[2][i] == 1:
        judge = 'Yes'

if result[0][0] * result[1][1] * result[2][2] == 1:
    judge = 'Yes'

if result[0][2] * result[1][1] * result[2][0] == 1:
    judge = 'Yes'

print(judge)


Measured memory_bytes: 3064
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
mo = 10**9+7

def main():
	r = II()
	print(2*r*3.14)

if __name__ == '__main__':
	main()

Measured memory_bytes: 9228
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll x,y;
    cin>>x>>y;
    x-=y;
    x=abs(x);
    x=max(x,1LL);
    cout <<((x==1)?"Brown":"Alice")<<endl;
    return 0;
}



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

int main() {
  int N;
  cin >> N;
  
  vector<int> vec(N);
  for(int i = 0; i < N; ++i){
    cin >> vec.at(i);
  }
  
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());
  
  int num = 1;
  for (int i = 1; i < vec.size(); ++i){
  	if (vec.at(i) < vec.at(i-1)){
      num++;
    }
  }
  cout << num << endl;
}


Measured memory_bytes: 256
import numpy as np
n=int(input())
l=list(map(int,input().split()))


arr=np.array(l)
arr2=np.append(np.hstack((0,arr)),0)
differ=sum(abs(np.diff(arr2)))
dif=np.diff(arr2)
for i in range(1,n+1):
    difference=abs(dif[i]+dif[i-1])-abs(dif[i])-abs(dif[i-1])
    print(differ+difference)

   


Measured memory_bytes: 22852
#include<stdio.h>
int  yaku(int a,int b){
  if(b==0)return a;
  int r,t;
  r=a%b;
  t=yaku(b,r);
  return t;
}
int main(){
  int a,b,min,t;
  while(scanf("%d %d",&a,&b)!=EOF){
    if(a<b){
      t=a;
      a=b;
      b=t;
    }
    min=yaku(a,b);
    a/=min;
    printf("%d %d\n",min,a*b);
  }
  return 0;
}

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

long long a, b, c;
int ans;

int main()
{
    cin >> a >> b >> c;
    while(!(a%2+b%2+c%2) && ans++ < 1000){
        int am = a/2, bm = b/2, cm = c/2;
        a = bm+cm; b = am+cm; c = bm+am;
    }
    cout << (ans == 1001 ? -1 : ans) << endl;
    return 0;
}


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

int main(){
  string w;cin>>w;
  int l=w.size();
  vector<int> alpha(26,0);
  for(int i=0;i<l;i++){
    alpha.at(w.at(i)-'a')++;
  }
  
  bool ans=true;
  for(int i=0;i<26;i++){
    if(alpha.at(i)%2!=0){
      ans=false;
      break;
    }
  }
  cout<<(ans?"Yes":"No")<<endl;
}

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

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef long double ld;
typedef pair <ll ,ll> pll;
typedef pair <int ,int> pii;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define print(a) {for (auto iiiiiiiiii : a) cout << iiiiiiiiii << ' '; cout << '\n';}
#define fi first
#define se second
#define all(x) (x).begin() , (x).end()

ll next() {ll x; cin >> x; return x;}

const ll inf = 1e18 , mod = 998244353;
const int intf = 2e9 , maxn = 3e5;
const double PI = 3.141592653589 , eps = 1e-9;

void rec(int id , int n , string &s , char maxc){
    if (id == n){
        cout << s << '\n';
        return;
    }
    for (char c = 'a'; c <= maxc + 1; c++){
        s += c;
        rec(id + 1 , n, s , max(maxc , c));
        s.pop_back();
    }
}

void solve(){
    int n; cin >> n;
    string s = "";
    rec(0 , n , s , 'a' - 1);
}


int main()
{
    #ifdef HERE
        freopen("input.txt" , "r" , stdin);
    #else
        //freopen(".in" , "r" , stdin); freopen(".out" , "w" , stdout);
        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.precision(20);
    #endif

    for (int t = 1; t--;) solve();

    #ifdef HERE
        cout << setprecision(3) << fixed << "\n\nRuntime: " << (long double)(clock()) / CLOCKS_PER_SEC << " s.\n";
    #endif
    return 0;
}
/*

*/


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
int a[200001];
int main(){
  int n,k;
  cin>>n>>k;
  for(int i=0;i<n;i++) cin>>a[i+1],a[i+1]+=a[i];
  int ans=0;
  for(int i=k;i<=n;i++){
    ans=max(ans,a[i]-a[i-k]);
  }
  cout<<fixed<<setprecision(10)<<(double)(ans+k)/2.0;
  return 0;
}

Measured memory_bytes: 1024
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 
#include<bits/stdc++.h>
 
using namespace std;
#define ll long long 
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define ull unsigned long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define ff first
#define ss second
#define fast ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0); 
#define nl "\n"
#define sz(a) (int)(a).size() 
#define all(a) (a).begin(),(a).end()
#define fl(a,x) memset(a,x,sizeof(a));
#define pt(a,x) cout << get<x>(a) << " " ;  
#define mt make_tuple 
#define vec vector
 
#define int long long 
 
const int mod = (int) 1e9 + 7 ;
const int MOD = (int) 998244353 ;
const int INF = (int) 1e18 ;
 
typedef vector<int> vii;
typedef pair<int,int> pii;
typedef vector<pii> vpi;
typedef vector<vector<int> > vv;
 
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
 
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

const int N = 1e5 + 5; 
int dp[105][N]; 

void solve(int test) {
	int n,k; cin >> n >> k ;
	int a[n+1] ; rep(i,1,n+1) cin >> a[i] ;
	rep(i,0,n+1) dp[i][0] = 1 ; 

	for(int i = 1 ; i <=n ; ++i) {
		int ps[k] = {} ; ps[0] = 1; 
		rep(j,1,k+1) {
			 ps[j] = (ps[j-1] + dp[i-1][j]) % mod ; 
		}
		for(int j = 1 ; j <= k ; ++j ) {
			if(j <= a[i]) dp[i][j] = ps[j]; 
			else dp[i][j] = ( ps[j] - ps[j - a[i]] + dp[i-1][j-a[i]] + mod ) % mod ; 
		}
	}

	// rep(i,1,n+1) {rep(j,1,k+1) cout << dp[i][j] << " "; cout <<nl ; }

	cout << dp[n][k] ;
}

int32_t main() {
 
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif   

    fast;
	int t=1;
	// cin>>t;
	rep(i,1,t+1) {
		solve(i) ;
	}
 
	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}

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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;
/*
0-index
functionの中を書いて使う
宣言の時に単位元を書く
*/
template<typename T>
struct segtree{
	int n;
	vector<T> dat;
	T ZERO;
	function<T(T,T)> func;
	segtree(int n_, function<T(T,T)> func_, T zero):func(func_), ZERO(zero){
	  n = 1;
	  while(n < n_)n*=2;
	  dat.resize(2*n);
	  for(int i = 0;i < 2*n;i++)dat[i] = ZERO;
	}
	void update(int k, T a){
	  k += n - 1;dat[k] = a;
	  while(k > 0){
		k = (k-1)/2;
		dat[k] = func(dat[k*2+1],dat[k*2+2]);
	  }
	}

	void set(int k, T a) {
		k += n - 1;dat[k] = a;
	}

	void build(){
		for(int i = n - 2;i >= 0;i--){
			dat[i] = func(dat[2 * i + 1], dat[2 * i + 2]);
		}
	}

	T get(int k){return dat[k+n-1];}

	T que(int a,int b){
		T L = ZERO,R = ZERO;
		int A = a + n - 1;
		int B = b + n - 1;
		while(A < B){
			if((A & 1) == 0)L = func(L,dat[A++]);
            if((B & 1) == 0)R = func(dat[--B],R);
            A = A >> 1;
            B = B >> 1;
		}
		return func(L,R);
	}
};


int getmin(string str){
	char c = str[0];
	bool isFirst = true;
	int cou = 0;
	int ret = INF;
	REP(i, str.size()){
		if(str[i] == c)cou++;
		else {
			if(isFirst && cou % 2 == 0)cou++;
			if(cou % 2)ret = min(ret, cou);
			isFirst = false;
			cou = 0;
		}
	}

	return ret;
}

ll n, m, k, ans;
string str;

bool oneKind(string str){
	REP(i, str.size())if(str[0] != str[i])return false;
	return true;
}

void solveA(){
	ll ans = 0;
	segtree<ll> seg(n, [](ll a, ll b){return (a + b) % MOD;}, 0);
	seg.update(0, 1);

	for(ll i = 2;i < n;i++){
		ll l = max(0LL, i - k - 1);
		ll r = i - 1;
		seg.update(i, seg.que(l, r));
	}
	REP(i, n-1){
		if(n - (i + 1) <= k){
			//cout << "pass " << seg.get(i) * (n - i) % MOD << endl;
			ans = (ans + seg.get(i) * (n - i) % MOD) % MOD;
		}
	}
	ans = (ans + 1) % MOD;
	cout << ans << endl;
}

void solveB(){
	ll ans = 0;
	segtree<ll> seg(n, [](ll a, ll b){return (a + b) % MOD;}, 0);
	seg.update(0, 1);

	for(ll i = 2;i < n;i++){
		if(i % 2)continue;
		ll l = max(0LL, i - k - 1);
		ll r = i - 1;
		seg.update(i, seg.que(l, r));
	}

	//REP(i, n)cout << seg.get(i) << " ";cout << endl;
	REP(i, n-1){
		if(n - (i + 1) <= k && ((n - (i + 1)) % 2)){
			//cout << "pass " << seg.get(i) * (n - i) % MOD << endl;
			ans = (ans + seg.get(i) * (n - i) % MOD) % MOD;
		}
	}
	cout << ans << endl;
}

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

	cin >> n >> m >> str;
	k = getmin(str);


	if(oneKind(str)){
		solveA();
	}
	else {
		solveB();
	}

	return 0;
}


Measured memory_bytes: 4816
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
int n;
bool num[123456 * 2 + 1];
vector<int> prime;
void serchPrime(){

  for(int i = 2; i < 123456 * 2 + 1 ; i++){
    if(!num[i]){
      prime.push_back(i);
      for(int k = 1; i * k <= 123456 * 2 ; k++){
        num[i * k] = true;
      }
    }
  }
}

void solve(){
  int res = 0;
  for(int i = 0; i < prime.size(); i++){
    if(n < prime[i] && prime[i] <= 2*n){
      res ++;
    }
  }
  cout << res << endl;
}

int main(){
  serchPrime();
  while(true){
    cin >> n;
    if(n == 0) break;
    solve();
  }

  return 0;
}



Measured memory_bytes: 3440
using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = int.Parse(Console.ReadLine());
            int b = int.Parse(Console.ReadLine());
            int h = int.Parse(Console.ReadLine());

            Console.WriteLine((a + b) * h / 2);
        }
    }
}

Measured memory_bytes: 11092
#include <stdio.h>

int main(void){

  int n, i, j, k, a[100], co = 0, c;

  scanf("%d", &n);

  for(i = 0; i < n; i++){
    scanf("%d", &a[i]);
  }

  for(i = 0; i < n-1; i++){
    for(j = 0; j < n-i-1; j++){
      if(a[j] > a[j+1]){
	k = a[j];
	a[j] = a[j+1];
	a[j+1] = k;
	co++;
      }
    }
  }

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

  return 0;
}

Measured memory_bytes: 600
#!/usr/bin/ruby
a=(gets.to_i+1).times.map{gets.split[1].to_i.times.map{v,r=gets.split.map(&:to_f);[v*r,r]}.transpose.map{|e|e.reduce(:+)}.reduce(:/)}
puts a.pop+0.0000001<a.max ? :YES: :NO

Measured memory_bytes: 2940
from math import floor, sqrt
INF = 10 ** 20


def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n // b) + (n % b)


def main():
    n = int(input())
    s = int(input())

    ans = INF
    # 1桁
    if n == s:
        ans = min(ans, n + 1)

    # 2桁
    for p in range(1, int(sqrt(n)) + 1):
        q = s - p
        b = (n - q) // p
        if 2 <= b and f(b, n) == s:
            ans = min(ans, b)

    # 3桁以上
    for b in range(2, int(sqrt(n)) + 1):
        if f(b, n) == s:
            ans = min(ans, b)

    print(-1 if ans == INF else ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
import java.util.*;

public class Main {

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

		// 入力
		int N = sc.nextInt();
		int[] v = new int[N];
		for (int i = 0; i < N; i++) {
			v[i] = sc.nextInt();
		}
		Arrays.sort(v);
		double ave = v[0];
		for (int i = 1; i < N; i++) {
			ave = (ave+v[i])/2;
		}
		System.out.println(ave);
	}

	// ユークリッドの控除法(最大公約数を求める)
	private static long gcd(long a, long b) {
		if (b == 0) {
			return a;
		}
		return gcd(b, a % b);
	}

	// 複数の最大公約数を求める
	private static long gcdex(long param[]) {
		long g = gcd(param[0], param[1]);
		for (int i = 1; i < param.length-1; i++) {
			g = gcd(g, param[i+1]);
		}
		return g;
	}

	// 最小公倍数を求める
	private static long lcm(long a, long b) {
		return (a * b) / gcd(a, b);
	}

	//
	private static long all(long n, long count, int N) {
		if (count == N) {
			return count;
		}
		return all(1, count, N);
	}

}

Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
struct{
	char suit;
	int num;
}typedef Card;

bool isStable(Card* a1,Card* a2,int n){
	for(int i = 0;i < n;i++){
		if(a1[i].suit != a2[i].suit)
			return false;
	}
	return true;
}

void printArray(Card* a,int n){
	for(int i = 0;i < n;i++){
		cout << a[i].suit << a[i].num << flush;
		if(i != n - 1){
			cout << " " << flush;
		}else{
			cout << endl;
		}
	}
}

void selectionSort(Card* a,int n){
	int minI;
	Card v;
	for(int i = 0;i < n;i++){
		minI = i;
		for(int j = i;j < n;j++){
			if(a[minI].num > a[j].num){
				minI = j;
			}
		}
		v = a[i];
		a[i] = a[minI];
		a[minI] = v;
	}
	printArray(a,n);
}

void bubbleSort(Card* a,int n){
	bool isTraded = true;
	Card v;
	for(int j = 0; j < n; j++){
		for(int i = n - 1;i >= j + 1;i--){
			if(a[i].num < a[i - 1].num){
				v = a[i];
				a[i] = a[i - 1];
				a[i - 1] = v;
			}
		}
	}
	printArray(a,n);
}

int main(){
	int n;
	cin >> n;
	Card* a1 = new Card[n];
	for(int i = 0; i < n;i++){
		cin >> a1[i].suit >> a1[i].num;
	}
	Card* a2 = new Card[n];
	memcpy(a2,a1,n * sizeof(a1[0]));

	bubbleSort(a1,n);
	cout << "Stable" << endl;
	selectionSort(a2,n);
	if(isStable(a1,a2,n)){
		cout << "Stable" << endl;
	}else{
		cout << "Not stable" << endl;
	}
}



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

#define ll long long
#define ar array
#define ld long double
#define endl "\n"
#define fori(i,k,n) for(int i = k;i<n; i++)
const int mxN=1e3;
ll w, h, l, u, r, d;

void fastio(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main(){
    fastio();
    int n;
    cin>>n;
    vector<int> a(n);
    fori(i,0,n)cin>>a[i];
    map<int,int> mp;
    for(int i = 0; i<n; i++){
        mp[a[i]]++;
    }
    for(int i = 1; i<=n; i++){
        if(mp.find(i)!=mp.end())cout<<mp[i]<<endl;
        else cout<<0<<endl;
    }
}

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

#define rp(i, k, n) for (int i = k; i < n; i++)
typedef long long ll;
typedef double ld;



template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF = 1ll << 60;
const ll MOD = 1e9 + 7ll;
const double PI=3.14159265358979323846;


// dijkstra法ライブラリここから-----------------------------------------------------------------------------//

const int MAX_V = 500009;
typedef pair<int, ll> P;
vector<P> d(MAX_V);  // 結果格納　intは親　到達不可能なら-1, inf
vector< vector <P> > graph(MAX_V);


void dijkstra(int s) {
    priority_queue< P, vector<P>, greater<P> > que;
    for(int i = 0; i < d.size(); ++i) {
        d.at(i) = P(-1, INF);
    }
    que.push(make_pair(s, 0ll));
    d.at(s) = P(s, 0);
    while(!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.first;
        if(p.second > d.at(v).second) continue;
        for(int i = 0; i < graph.at(v).size(); ++i) {
            P edge = graph.at(v).at(i);
            if(d.at(edge.first).second > d.at(v).second + edge.second) {
                d.at(edge.first).second = d.at(v).second + edge.second;
                d.at(edge.first).first = v;
                que.push(make_pair(edge.first, d.at(edge.first).second));
            }
        }
    }
}

// dijkstra法ライブラリここまで-----------------------------------------------------------------------------//


int main() {
    int N, M; cin >> N >> M;
    rp(i, 0, M) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--; v--;
        graph.at(u).emplace_back(v+N, 1ll);
        graph.at(u+N).emplace_back(v+2*N, 1ll);
        graph.at(u+2*N).emplace_back(v, 1ll);
    }

    int S, T; cin >> S >> T;
    S--; T--;
    dijkstra(S);
    if(d.at(T).first == -1) cout << -1 << endl;
    else cout << d.at(T).second / 3ll << endl;
    return 0;
}

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

int main() {
    string S;
    cin >> S;
    int N = S.size() - 1;
    if(S.at(N) == '2' || S.at(N) == '4' || S.at(N) == '5' || S.at(N) == '7' || S.at(N) == '9'){
        cout << "hon" << endl;
    }
    else if(S.at(N) == '0' || S.at(N) == '1' || S.at(N) == '6' || S.at(N) == '8'){
        cout << "pon" << endl;
    }
    else{
        cout << "bon" << endl;
    }
}


Measured memory_bytes: 3624
import sys

import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]


def main():

    n = int(input())
    str_n = str(n)
    #print(str_n)
    ngs = ['3','5','7']
    #a = list(product(ngs, repeat=len(str_n)))
    #print(a)
    ans = ''
    count = 0
    for i in range(1,len(str_n)+1):
        for j in list(product(ngs, repeat=i)):
            #print(j)
            for k in j:
                ans += k
            #print(ans)
            ngs_and_ans = set(ngs) & set(ans)
            if int(ans) <= n and len(ngs_and_ans) == 3:
                count += 1
            ans = ''
    print(count)


if __name__ == '__main__':
    main()


Measured memory_bytes: 16500
import java.util.Scanner;

public class Main {


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
			int sx  = sc.nextInt();
			int sy  = sc.nextInt();
			int tx  = sc.nextInt();
			int ty  = sc.nextInt();
		sc.close();
		for(int i = sx ; i < tx ; i++){

			System.out.print("R");
		}
		for(int i = sy ; i < ty ; i++){

			System.out.print("U");
		}

		for(int i = sx ; i < tx ; i++){

			System.out.print("L");
		}
		for(int i = sy ; i < ty ; i++){

			System.out.print("D");
		}
		int sx2 = sx-1;
		int sy2 = sy-1;
		int tx2 = tx+1;
		int ty2 = ty+1;


		System.out.print("D");

		for(int i = sx; i < tx2 ; i++){

			System.out.print("R");
		}
		for(int i = sy2; i < ty ; i++){

			System.out.print("U");
		}

		System.out.print("LU");
		for(int i = sx2; i < tx ; i++){

			System.out.print("L");
		}
		for(int i = sy; i < ty2 ; i++){

			System.out.print("D");
		}

		System.out.print("R");

		//System.out.println(m);
	}
}

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

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

//

fn run() {
    input! {
        n: usize,
        a: [usize; n],
        b: [usize; n],
    }
    let m = 50;
    for (&a, &b) in a.iter().zip(b.iter()) {
        let mut dp = vec![false; m + 1];
        dp[a] = true;
        for i in (1..(m + 1)).rev() {
            for j in 0..(m + 1) {
                dp[j % i] |= dp[j];
            }
        }
        if !dp[b] {
            println!("-1");
            return;
        }
    }
    let mut cond = vec![true; m + 1];
    for i in (1..(m + 1)).rev() {
        cond[i] = false;
        let mut ok = true;
        for (&a, &b) in a.iter().zip(b.iter()) {
            let mut dp = vec![false; m + 1];
            dp[a] = true;
            for i in (1..(m + 1)).rev() {
                if !cond[i] {
                    continue;
                }
                for j in 0..(m + 1) {
                    dp[j % i] |= dp[j];
                }
            }
            if !dp[b] {
                ok = false;
                break;
            }
        }
        if !ok {
            cond[i] = true;
        }
    }
    let mut ans = 0u64;
    for i in 1..(m + 1) {
        if cond[i] {
            ans += 1 << i as u64;
        }
    }
    println!("{}", ans);
}

fn main() {
    run();
}


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

using namespace std;

int const NMAX = 3e3 - 1;
int n;
long double heads[1 + NMAX], tails[1 + NMAX];
long double dp[1 + NMAX][1 + NMAX];

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> heads[i];
    tails[i] = 1.0 - heads[i];
  }
  dp[0][0] = 1.0;
  for(int i = 1; i <= n; i++) {
    dp[i][0] = tails[i] * dp[i-1][0];
  }
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
      dp[i][j] = tails[i] * (dp[i-1][j]) + heads[i] * (dp[i-1][j-1]);
    }
  }
  long double ans = 0;
  int x = (n+1)/2;
  for(int j = x; j <= n; j++) {
    ans += dp[n][j];
  }
  cout << setprecision(9) << ans;
}


Measured memory_bytes: 140928
import sys

X = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

lis = make_divisors(X)

for i in range(len(lis)):
    A = 0
    B = 0
    dis = lis[i]
    for i in range(-2000,200):
        A = i
        B = A - dis
        if A ** 5 - B ** 5 == X:
            print(A, B)
            sys.exit()
        else:
            continue



Measured memory_bytes: 9460
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <algorithm>
using namespace std;

int W, H;
vector<pair<int, int> > cost_list;

int main() {
	scanf("%d %d", &W, &H);
	for (int i = 0; i < W; i++) {
		int tmp;
		scanf("%d", &tmp);
		cost_list.push_back(make_pair(tmp, 0));
	}

	for (int i = 0; i < H; i++) {
		int tmp;
		scanf("%d", &tmp);
		cost_list.push_back(make_pair(tmp, 1));
	}

	sort(cost_list.begin(), cost_list.end());

	H++; W++;

	long long ans = 0;
	for (int i = 0; i < cost_list.size(); i++) {
		if (cost_list[i].second == 1) {
			ans += (long long)cost_list[i].first * W;
			H--;
		} else {
			ans += (long long)cost_list[i].first * H;
			W--;
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 2420
#include <iostream>

using namespace std;
int main()
{
    int color;int n;int a;
    cin>>n >>color >>a;
    a=color-1;
    
    if (n==1)
    {
        cout<<color;
    }
    if (n>1)
    {
        for (int i=0; i<n-1; i++)
        {
            color = color * a;
        }
        cout<<color;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)

int main() {
    int n; cin >> n;
    vector<string> s(n);
    rep(i,n) cin >> s[i];
    map<string,int> m;
    for(string si : s){
        m[si] = 1;
    }

    int ans = m.size();
    cout << ans << endl;
}


Measured memory_bytes: 25176
#include <stdio.h>
int main(void){
    // Your code here!
    int N,K,ans=0;
    int i,j;
    int h[100000];
    scanf("%d%d",&N,&K);
    for(i=0;i<N;i++){
        scanf("%d",&h[i]);
        if(h[i]>=K)ans++;
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 512
iN,iA =[int(x) for x in input().split()]
aX = [int(x) - iA for x in input().split()]

#解法2そのまま

iMX = max(aX + [iA])
iULim = iN*iMX
iULim2 = 2*iULim

#y0..yjから0枚以上選んだ合計をt-iN*iMXにするような選び方の総数
dp = [[0]*(iULim2 + 1) for _ in range(iN+1)]
for j in range(0,iN+1):
    for t in range(0,iULim2):
        if j == 0 and t == iULim :
            dp[j][t] = 1
        elif  t - aX[j-1] < 0 or t - aX[j-1] > iULim2:
            dp[j][t] = dp[j-1][t]
        elif  0 <= t - aX[j-1] <= iULim2:
            dp[j][t] = dp[j-1][t] + dp[j-1][t-aX[j-1]]
        else:
            dp[j][t] = 0
print(dp[iN][iN*iMX] -1 )


Measured memory_bytes: 5236
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<climits>

#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
const int INF = INT32_MAX / 3;
const ll MOD = 1e9 + 7;

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


/******************************************************************************************/

vector<int> G[200005];
int cost[200005];
int flag[200005];
int ans[200005];

void solve() {

	
	

	
	queue<pii> que;
	que.push(pii(0, cost[0]));
	ans[0] = cost[0];

	while (!que.empty()) {

		
		pii tmp = que.front();
		que.pop();
		flag[tmp.first] = 1;

		//cout << "now =" << tmp.first << endl;

		for (auto itr : G[tmp.first]) {

			if (flag[itr] == 0) {
				//まだ訪れていない
				ans[itr] = tmp.second + cost[itr];
				flag[itr] = 1;
				que.push(pii(itr, tmp.second + cost[itr]));
			}
		}
	}
}

int main() {

	int n, q;
	cin >> n >> q;
	
	for (int i = 0; i < n-1; i++)
	{
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		if (a > b) {
			swap(a, b);
		}

		G[a].push_back(b);
		G[b].push_back(a);
	}

	for (int i = 0; i < q; i++)
	{
		int p, x;
		cin >> p >> x;
		p--;
		cost[p] += x;
	}


	solve();
	

	for (int i = 0; i < n; i++)
	{
		if (i == 0) {
			cout << ans[i];
		}
		else
		{
			cout << " " << ans[i];
		}
	}
	cout << endl;


	return 0;
}


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

using namespace std;

int main() {
	int N,cnt=0;
	string S;
	cin >> N >> S;
	for (size_t i = 0; i < N-2; i++)
	{
		if (S.substr(i,3)=="ABC")
		{
			cnt++;
		}
	}
	cout << cnt;
	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

signed main(){
	int n,a[200000],xo = 0,sum = 0,ans = 0,r = 0;
	cin >> n;
	for(int i = 0;i < n;i++) cin >> a[i];
	for(int i = 0;i < n;i++){
		while(r < n && sum == xo){
			sum += a[r];
			xo ^= a[r];
			r++;
		}
		if(sum != xo){
			r--;
			sum -= a[r];
			xo ^= a[r];
		}
		ans += r - i;
		sum -= a[i];
		xo ^= a[i];
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second

int n, a, b;

int main() {
    cin >> n >> a >> b;
    cout << min(a, b) << ' ' << max(0, a + b - n);
}

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

ll A, B, C;

ll rec (ll a, ll b, ll c, ll n) {
    if (a%2==1 || b%2==1 || c%2==1) {
        return n;
    }
 
    if (a == b && b == c) {
        return -1;            
    }
 
    rec((b+c)/2, (c+a)/2, (a+b)/2, n+1);
}

int main() {
    cin >> A >> B >> C;

    cout << rec(A, B, C, 0) << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
int main() {
    int N[2];
    cin >> N[0] >> N[1];
    int grid[100][100];

    for(int y = 0; y < 100; y++) {
        for(int x = 0; x < 100; x++) {
            grid[y][x] = x < 50;
        }
    }

    for(int i = 1; i < N[0]; i++) {
        grid[2 * (i / 24)][2 * (i % 24) + 1] = 0;
    }
    for (int i = 1; i < N[1]; i++) {
        grid[2 * (i / 24)][2 * (i % 24) + 50 + 1] = 1;
    }

    cout << "100 100" << endl;
    for(int i = 0; i < 100; i++) {
        for(int j = 0; j < 100; j++) {
            cout << (grid[i][j] ? '#' : '.');
        }
        cout << endl;
    }
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  set<string> S;
  for (int i = 0; i < N; i++) {
    string str;
    cin >> str;
    S.insert(str);
  }
  cout << S.size() << endl;
}

Measured memory_bytes: 19180