akhauriyash/Code-Regression huggingface dataset:
local mod = 1000000007
local mfl, mce = math.floor, math.ceil
local function bmul(x, y)
  local x0, y0 = x % 31623, y % 31623
  local x1, y1 = mfl(x / 31623), mfl(y / 31623)
  return (x1 * y1 * 14122 + (x1 * y0 + x0 * y1) * 31623 + x0 * y0) % mod
end
local function badd(x, y) return mod <= x + y and x + y - mod or x + y end
local n = io.read("*n")
local invs = {1}
local invsum = {1}
for i = 2, n do
  invs[i] = bmul(mfl(mod / i), mod - invs[mod % i])
  invsum[i] = badd(invsum[i - 1], invs[i])
end
local fact = 1
for i = 2, n do
  fact = bmul(fact, i)
end
local ret = 0
for i = 1, n do
  local a = io.read("*n")
  local mul = 1
  if 1 < i then
    mul = badd(mul, invsum[i])
    mul = badd(mul, mod - 1)
  end
  if i < n then
    mul = badd(mul, invsum[n + 1 - i])
    mul = badd(mul, mod - 1)
  end
  mul = bmul(mul, fact)
  ret = badd(ret, bmul(a, mul))
end
print(ret)


Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define pb push_back
//#define int long long
#define mod 1000000007
#define fi first
#define se second
#define ll long long
#define scan() ll n; cin>>n ; ll a[n]; for(ll i = 0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
#define fast ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(ll i=x;i<y;i++)
using namespace std;
typedef vector<int>vi ;
typedef vector<ll>vll ;
typedef vector<vector<ll> >vvl ;
typedef pair<ll,ll> pll ;
int main()
{
	fast;
	ll n;
	cin>>n;
	ostringstream str1;
	str1 << n; 
	ll count=0;
	string geek = str1.str(); 
	for(ll i=0;i<geek.size();i++)
	{
		if(geek[i]=='7')
		{
			count=1;
			break;
		}
	}
	if(count==0)
		cout<<"No";
	else
		cout<<"Yes";
	return 0;
}


Measured memory_bytes: 3652
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	as := make([]int, n + 1)
	for i := 0; i < n; i++ {
		fmt.Scan(&as[i])
	}

	cnt := 1
	prev := as[0]
	b :=  0 //   > 0,0 , 0 < のどれか判別できれば良い

	for i := 0; i < n; i++ {
		if b * (as[i]- prev) < 0 {
			cnt++
			b = 0
		} else if as[i] - prev != 0 {
			b = as[i] - prev
		}

		prev = as[i]
	}
	fmt.Println(cnt)
}


Measured memory_bytes: 6312
from collections import defaultdict


num_room, num_path = map(int, input().split(' '))

paths = defaultdict(set)
for i in range(0, num_path):
    src, dest = map(int, input().split(' '))
    paths[src].add(dest)
    paths[dest].add(src)

rooms = {1}
route = {}

while rooms:
    new_rooms = set()
    for src in rooms:
        dest_set = paths[src]
        for dest in dest_set:
            if dest in route.keys():
                continue
            route[dest] = src
            new_rooms.add(dest)
    rooms = new_rooms

for i in range(2, num_room+1):
    if i not in route.keys():
        print("No")
        exit(0)

print("Yes")
for i in range(2, num_room+1):
    print(route[i])


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

#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define FOR(i,a,b)  for(int i=(a); i< (b); ++i)
#define RFOR(i,b,a) for(int i=(b);i>=(a);i--)
#define REP(i,a,b)  for(int i=(a); i<=(b); ++i)
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
template<typename T>
void PrArr(const T a[] , int len){
	for(int i = 0;i <= len; i++)cout << a[i] << " ";
	cout << endl;
}
template<typename T>
void PrVec(const vector<T> a){
	for(auto it : a)cout << it << " ";
	cout << endl;
}
const int MAX = 0x7ffffff;
const int MIN = 0xcf;
int test;
void slove()
{
	int n;cin >> n;
	string s;cin >> s;
	int l = 0 , r = s.size() - 1 , ans = 0;
	while(l < r)
	{
		while(s[l] == 'R')l++;
		while(s[r] == 'W')r--;
		if(l < r){
			ans++;
			s[l] = 'R';
			s[r] = 'W';
		}
	}
	cout << ans << endl;
	// int ans = count(s.begin(),s.begin() + count(s.begin(),s.end(),'R') , 'W'); 
}	// cout << ans << endl;
int main()
{
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed; // 在iomanip中
#endif
	SIS;slove();
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

Measured memory_bytes: 3796
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using P = pair<ll,ll>;
constexpr ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template<class T> inline void chmin(T& a, T b){
    if (a > b){
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(12);
    ll H,W;
    cin >> H >> W;
    ll Cx,Cy,Dx,Dy;
    cin >> Cx >> Cy >> Dx >> Dy;
    vector<string> S(H);
    REP(i,H)cin >> S[i];
    vector<vector<ll>> dist(H,vector<ll>(W,-1));
    queue<P> did;
    queue<P> que;
    que.push(mp(Cx-1,Cy-1));
    S[Cx-1][Cy-1] = 'p';
    for(ll i = 0;;i++){
        if(que.empty())break;
        // BFS 開始 (キューが空になるまで探索を行う)
        while (!que.empty()) {
            P v = que.front(); // キューから先頭頂点を取り出す
            que.pop();
            did.push(v);
            if(v.F!=0)if(S[v.F-1][v.S] == '.'){
                que.push(mp(v.F-1,v.S));
                S[v.F-1][v.S] = 'p';
            }
            if(v.S!=0)if(S[v.F][v.S-1] == '.'){
                que.push(mp(v.F,v.S-1));
                S[v.F][v.S-1] = 'p';
            }
            if(v.F!=H-1)if(S[v.F+1][v.S] == '.'){
                que.push(mp(v.F+1,v.S));
                S[v.F+1][v.S] = 'p';
            }
            if(v.F!=W-1)if(S[v.F][v.S+1] == '.'){
                que.push(mp(v.F,v.S+1));
                S[v.F][v.S+1] = 'p';
            }
        }
        while(!did.empty()){
            P v = did.front();
            did.pop();
            dist[v.F][v.S] = i;
            for(ll k = max(v.F-2,(ll)0);k < min(v.F+3,H);k++){
                for(ll l = max(v.S-2,(ll)0);l < min(v.S+3,W);l++){
                    if(S[k][l] == '.'){
                        que.push(mp(k,l));
                        S[k][l] = 'p';
                    }
                }
            }
        }
    }
    cout << dist[Dx-1][Dy-1] << "\n";
}

Measured memory_bytes: 12588
#include <stdio.h>
typedef long long ll;
int n;
int ans = 0;
void dfs(ll num, int use) {
	if (num > n) {
		return;
	}
	if (use == 7) {
		ans++;
	}
	dfs(num * 10 + 3, use | 1);
	dfs(num * 10 + 5, use | 2);
	dfs(num * 10 + 7, use | 4);
	return;
}
int main() {
	scanf("%d", &n);
	dfs(0, 0);
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <sstream>
#include <stack>
#include <time.h>
#include <vector>
#include <complex>
#include <map>
#include <set>
#include <iomanip>
#include <math.h>
#include <stdlib.h>
#include <list>
#include <utility>
#include <memory>
#include <cstring>
#include <fstream>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <ios>
using namespace std;
using namespace std;
#define mkp make_pair
void read(string &s){
	s="";char ch=getchar();
	for (;ch>'z' || ch<'a';ch=getchar());
	for (;ch>='a' && ch<='z';s+=ch,ch=getchar());
}
typedef long long ll;
const ll MOD1=1e9+7,MOD2=1e9+9;
const ll hasha=48,hashb=53;
ll wt=0,tw=0;
string s,t;
ll num1[32000004],num2[32000004];
ll hash1[32000004],hash2[32000004];
int dp[32000004];
int ans=0;
pair<ll,ll> hashit(int x){
	if (x<t.size()) return mkp(hash1[x],hash2[x]);
	return mkp((hash1[x]-hash1[x-t.size()]*num1[t.size()]%MOD1+MOD1)%MOD1,(hash2[x]-hash2[x-t.size()]*num2[t.size()]%MOD2+MOD2)%MOD2);
}
int main(){	
 	read(s);read(t);
   	while(s.size()<t.size()*2) s=s+s;
    s=s+s;
    s=s+s;
    s=s+s;
    num1[0]=num2[0]=1;
   	for(int i=1;i<s.size();i++)
    	num1[i]=num1[i-1]*hasha%MOD1,num2[i]=num2[i-1]*hashb%MOD2; 
    hash1[0]=hash2[0]=s[0]-'a'+1;
    for(int i=1;i<s.size();i++)
    	hash1[i]=(hash1[i-1]*hasha+s[i]-'a'+1)%MOD1,hash2[i]=(hash2[i-1]*hashb+s[i]-'a'+1)%MOD2;
	wt=tw=t[0]-'a'+1;
    for(int i=1;i<t.size();i++)
    	wt=(wt*hasha+t[i]-'a'+1)%MOD1,tw=(tw*hashb+t[i]-'a'+1)%MOD2;
  	pair<ll,ll> od=mkp(wt,tw);
    for(int i=0;i<s.size();i++){
    	dp[i]=0;
    	pair<ll,ll> o=hashit(i);
    	if (i>=t.size() && od==hashit(i))dp[i]=dp[i-t.size()]+1;
    	ans=max(ans,dp[i]);
	}
    if(ans+1>=s.size()/t.size()){
    	puts("-1");return 0;
	}
	cout<<ans;
}

Measured memory_bytes: 588460
#include <cstdio>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
 
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vl;

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
 
#define ALL(a) (a).begin(),a.end()
#define MAXE(a) *max_element(ALL(a))
#define MINE(a) *min_element(ALL(a))

int main(){
  ll a,b;
  cin >> a >> b;
  ll c = a+b;
  if(c<a-b)c=a-b;
  if(a<a*b)c=a*b;
  cout << c << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int n;
    scanf("%d",&n);
    int i;
    char c;
    char *p = "Three\0";
    for(i=0;i<n;i++){
        scanf("%c",&c);
        if(c=='Y')p="Four\0";
    }
    printf("%s",p);
    return 0;
}


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

bool ok(int N) {
  for(int i = 0; i <= 100/4; i++) {
    for(int j = 0; j <= 100/7; j++) {
      if(4*i+7*j == N) return true;
    }
  }
  return false;
}

int main () {
  int N;
  cin >> N;

  cout << (ok(N) ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
h, w, d = map(int, input().split())
num_dict = [[] for _ in range(h * w)]
for i in range(h):
    num_list = [int(i) for i in input().split()]
    for j, num in enumerate(num_list):
        num_dict[num - 1] = (i + 1, j + 1)
accum_list = [0 for _ in range(h * w)]
for i in range((h * w) - d - 1, -1, -1):
    accum_list[i] += (abs(num_dict[i + d][0] - num_dict[i][0]) +
                      abs(num_dict[i + d][1] - num_dict[i][1]) + accum_list[i + d])
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(accum_list[l - 1] - accum_list[r - 1])

Measured memory_bytes: 14848
from collections import deque
s=deque(list(input()))
p=deque()
for i in range(len(s)):
    w=s.popleft()
    if w=="0":
        p.append("0")
    elif w=="1":
        p.append("1")
    else:
        if len(p)==0:
            continue
        else:
            p.pop()

for i in range(len(p)):
    print(p[i],end="")
        




Measured memory_bytes: 3316
#include <stdio.h>
#include <limits.h>
#include <math.h>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

#define VARIABLE(x) cerr << #x << "=" << x << endl
#define BINARY(x) static_cast<bitset<16> >(x);
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)
#define if_range(x, y, w, h) if (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))

const int INF = 100000000;
typedef double D;
const double EPS = 1e-8;
const double PI = 3.14159;
int dx[4]={-1, 0, 1, 0}, dy[4]={0, -1, 0, 1};
using namespace std;
typedef pair<int, int> P;

/** Problem2243 : Step Step Evolution **/
int main()
{
	string s;
	while (cin>>s) {
		if (s=="#") break;
		
		int idx[10] = {-1, 0, 1, 2, 0, 1, 2, 0, 1, 2};
		
		// first left
		int ansL = 0;
		int r=0, l=idx[s[0]-'0'];
		bool nl = false;
		for (int i=1; i<s.size(); i++) {
			int a = s[i]-'0';
			
			if (!nl) {
				if (idx[a] >= l) {
					r = idx[a];
					nl = true;
				} else {
					l = idx[a];
					ansL++;
					nl = false;
				}
			} else {
				if (idx[a] <= r) {
					l = idx[a];
					nl = false;
				} else {
					r = idx[a];
					ansL++;
					nl = true;
				}
			}
			//cout << ansL << " " << l << " " << r << endl;
		}
		
		// first right
		int ansR = 0;
		l=0, r=idx[s[0]-'0'];
		nl=true;
		for (int i=1; i<s.size(); i++) {
			int a = s[i]-'0';
			if (!nl) {
				if (idx[a] >= l) {
					r = idx[a];
					nl = true;
				} else {
					l = idx[a];
					ansR++;
					nl = false;
				}
			} else {
				if (idx[a] <= r) {
					l = idx[a];
					nl = false;
				} else {
					r = idx[a];
					ansR++;
					nl = true;
				}
			}
			//cout << ansR << " " << l << " " << r << endl;
		}

		cout << min(ansL,ansR) << endl;
		//cout << ansL << " " << ansR << endl;
	}
}

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

int main()
{
  int N;
  cin >> N;
  string w;
  map<string,int> mp;
  rep(i,N) {
    cin >> w;
    sort(w.begin(),w.end());
    mp[w]++;
  }
  ll ans=0;
  for(auto& p : mp){
    int count = p.second;
    ans +=(ll)count * (count-1)/2;
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 11136
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)

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

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

typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//定数
#define INF 1000000000 //10^9:極めて大きい値,∞
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

int main(){
    int a;
    cin>>a;
    int x=a^1;
    cout<<x<<endl;
    return 0;
}

Measured memory_bytes: 3584
import bisect
N = int(input())
S = list(map(int,input().split()))
Q = int(input())
T = list(map(int,input().split()))

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return True
    return False

ans = 0
for t in T:
    if index(S,t):
        ans+=1

        
print(ans)



Measured memory_bytes: 16744
#include <iostream>
#include <string>
using namespace std;
 
int main(){
  int goal, from, to;
  int i;
  bool out_flag = false;
  cin >> goal >> from >> to;

  for(i=from; i<=to; i++){
    if (i%goal == 0){
      out_flag = true;
      break;
    }
  }
  if(out_flag){
    cout << "OK" << endl;
  }
  else{
    cout << "NG" << endl;
  }
}

Measured memory_bytes: 3128
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pi pair<ll,ll>
#define all(X) X.begin(),X.end()

// for pair comparison function(ascending order) use return (i1.ff < i2.ff);

/* string operations :
   str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
   str.substr (x) : returns a substring str[x],... end of string
   str.find(qtr) : returns the first occurenece of qtr in str */

const int M = (1<<20)+5;
const int md = 1e9+7;

ll pwr(ll a,ll n,ll m)
{
	ll p=1;
	while(n>0)
	{
		if(n%2==1)
			p=(p*a)%m;
		a=(a*a)%m;
		n=n/2;
	}
	return p;
}

ll ar[M],cnt[M];

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

	ll n,ans = 0,tmp = 0,i;

	cin >> n;
	for(i=1;i<=n;++i)
	{
		cin >> ar[i];
		cnt[ar[i]]++;	
	}

	for(i=1;i<=n;++i)
	{
		ans += (cnt[i]*(cnt[i]-1))/2;
	}

	for(i=1;i<=n;++i)
	{
		tmp = ans;
		ans -= (cnt[ar[i]]*(cnt[ar[i]]-1))/2;
		cnt[ar[i]]--;
		ans += (cnt[ar[i]]*(cnt[ar[i]]-1))/2;
		cout << ans << "\n";
		cnt[ar[i]]++;
		ans = tmp;
	}
	return 0;
}


Measured memory_bytes: 5248
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
a = 0
for i in str(n):
    a += int(i)
if int(n) % a == 0:
    print("Yes")
else:
    print("No")


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

using namespace std;

int main()
{
	int k, t;
	cin >> k >> t;
	int m = 0;
	for (int i = 0; i < t; i++)
	{
		int a;
		cin >> a;
		m = max(m, a);
	}
	cout << max(0, 2 * m - k - 1) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int a[3][3];
    bool app[3][3];
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            cin>>a[i][j];
            app[i][j] = false;
        }
    }
    int n; cin>>n;
    int b[n];
    for(int i=0;i<n;i++) cin>>b[i];
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<n;k++){
                if(a[i][j]==b[k]) app[i][j]=true;
            }
        }
    }
    string ans="No";
    for(int i=0;i<3;i++){
        if(app[i][0]&&app[i][1]&&app[i][2]) ans="Yes";
    }
    for(int i=0;i<3;i++){
        if(app[0][i]&&app[1][i]&&app[2][i]) ans="Yes";
    }
    if(app[0][0]&&app[1][1]&&app[2][2]) ans="Yes";
    if(app[0][2]&&app[1][1]&&app[2][0]) ans="Yes";
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
n,k = map(int,input().split())
s = input()

sp = []
if s[0]=='0':
  sp.append(0)

count=0
for si in s:
  if count==0:
    flag = si
    count=1
  elif flag == si:
    count+=1
  else:        
    sp.append(count)
    flag = si
    count=1
if count>0:
  sp.append(count)
if s[-1]=='0':
  sp.append(0)

ss=[0]
ss.append(sp[0])
count = 0
for spi in sp[1:]:
  ss.append(ss[-1]+spi)  

ans = 0
for left in range(0,len(ss),2):
  right = left+2*k+1
  if right >= len(ss): #!!
    right = len(ss)-1
  ans = max(ans,ss[right]-ss[left])    

print(ans)  

Measured memory_bytes: 8700
N=int(input())
num=0
result=0
min=10000000000
for i in range(N):
  a,b=map(int,input().split())
  if a>b:
    if b<min:
      min=b
      num=1
  result+=a

if num ==0:
  print(0)
else:
  result-=min
  print(result)
  

Measured memory_bytes: 3060
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;
int main()
{
    int a,b;

    while(1){
        cin >> a >> b;
        if(a==0 && b==0) break;
        else if(a > b){
          printf("%d %d\n",b,a);
          
        } 
        else{
          printf("%d %d\n",a,b);  
        }


    }







    return 0;
}


Measured memory_bytes: 3060
function abc100_a()

	# STEP.01
	# get the number of the slice of cake
	A, B = Base.parse.( Base.split( Base.readline( Base.STDIN ) ) )

	# STEP.02
	# output the result
	if A <= 8 && B <= 8
		Base.println( Base.STDOUT, "Yay!")
	else
		Base.println( Base.STDOUT, ":(" )
	end

end

#==================================================================================================#

Main.abc100_a()

Measured memory_bytes: 121164
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <utility>
#include <climits>
#include <vector>
#include <map>
using namespace std;

#define ll long long int
const int MOD = 1000000007;//10^9+7

int max(int a, int b) {

	if (a > b)return a;
	else return b;

}
//aとbの大きい方

int min(int a, int b) {

	if (a < b)return a;
	else return b;

}
//aとbの小さい方

int avd_i(int a, int b) {

	if (a > b)return a - b;
	else return b - a;

}
double avd_d(double a, double b) {

	double re;
	if (a > b)re = a - b;
	else re = b - a;
	return re;

}
//aとbの差の絶対値

ll calc(ll a, ll b, ll p) {

	if (b == 0) {

		return 1;

	}
	else if (b % 2 == 0) {

		ll d = calc(a, b / 2, p);
		return ((d%p)*(d%p)) % p;

	}
	else {

		return ((a%p)*calc(a, b - 1, p) % p) % p;

	}

}
//pは素数,aのb乗をpで割った余り

ll CMOD(ll n, ll r, ll p) {

	ll a = 1, b = 1, c = 1, re;
	for (int i = 1; i <= n; i++) {

		a *= i;
		a = a%p;

	}
	for (int i = 1; i <= r; i++) {

		b *= i;
		b = b%p;

	}
	for (int i = 1; i <= n - r; i++) {

		c *= i;
		c = c%p;

	}
	b = calc(b, p - 2, p);
	c = calc(c, p - 2, p);
	re = ((a%p)*(b%p)) % p;
	re = ((re%p)*c%p) % p;

	return re;

}
//pは素数,(nCr)%p

int main() {

	int N, a[100005], count[100005], countm1 = 0, ans = 0;

	for (int i = 0; i < 100005; i++) {

		count[i] = 0;

	}

	cin >> N;
	for (int i = 0; i < N; i++) {

		cin >> a[i];
		if (a[i] == 0) {

			countm1++;
			count[0]++;
			count[1]++;

		}
		else {

			count[a[i] - 1]++;
			count[a[i]]++;
			count[a[i] + 1]++;

		}

	}
	ans = countm1;
	for (int i = 0; i < 100005; i++) {

		ans = max(ans, count[i]);

	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
using namespace std;
int main(void){
  vector<int>num(4,0);
  for(int i=0;i<4;i++){
    cin >> num[i];
  }
  
  vector<int>check(10,0);
  for(int i=0;i<4;i++){
    check[num[i]]++;
  }
  
  if(check[1] == 1 && check[4] == 1 && check[7] == 1 && check[9] == 1)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
using namespace std;
int main(void)
{
	int a, i = 0, j;
	char bet, c[1001];

	for (;;)
	{
		scanf("%c", &bet);
		a = bet;
		if (a == 10)
		{
			break;
		}
		c[i] = a - 3;
		if (a == 65)
		{
			a = 88;
			c[i] = a;
		}

		if (a == 66)
		{
			a = 89;
			c[i] = a;
		}

		if (a == 67)
		{
			a = 90;
			c[i] = a;
		}
		i++;
	}
	for (j = 0; j < i; j++)
	{
		printf("%c", c[j]);
	}
	printf("\n");
	return 0;
}

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

#define ris   return *this
#define tmplt template<class T
#define dbgo  debug& operator<<
tmplt > struct rge { T b, e; };
tmplt > rge<T> range(T i, T j) { return rge<T>{i, j}; }
struct debug {
#ifdef LOCAL
~debug(){cerr<<endl;}
tmplt > dbgo(T x){cerr<<boolalpha<<x;ris;}
tmplt, class C > dbgo(pair<T, C> x){ris<<"("<<x.first<<", "<<x.second<<")";}
tmplt > dbgo(rge<T> x){*this<<"[";for(auto it=x.b;it!=x.e;it++){*this<<", "+2*(it==x.b)<<*it;}ris<<"]";}
tmplt > dbgo(vector<T> x){ris<<range(x.begin(),x.end());}
#else
tmplt > dbgo(const T&){ris;}
#endif
};
#define nav(...) << "[ " << #__VA_ARGS__ ": " << (__VA_ARGS__) << " ] "
using ll = long long;

#define forn(i, n) for(int i = 0; i < int(n); i++)
#define ford(i, n) for(int i = n-1; i >= 0; i--) 

template<typename T> 
void min_self(T& a, T b) { 
    a = min(a, b); 
}
template<typename T>
void max_self(T& a, T b) { 
    a = max(a, b); 
}

void test_case() {
    
    ll a, b;
    cin >> a >> b;
    if(a > b) swap(a, b);
    if(b - a <= 1) {
        cout << 2*a-2 << '\n';
    } else {
        ll p = a*b-1;
        ll lo = 0, hi = b;
        while(lo < hi) {
            ll mid = lo + (hi - lo + 1)/2;
            if(mid*mid < p+1) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        if(lo * (lo+1) >= p+1) {
            cout << 2*lo-2 << '\n';
        } else {
            cout << 2*lo-1 << '\n';
        }
    }
    
}

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

    int tc;
    cin >> tc;
    while(tc--) {
        test_case();
    }
}













// Don't worry, you're getting better

// Read statement carefully
// Solve on paper first!
// Make your infinity big enough
// Overflows (long long)

// Author: blondie


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

using namespace std;

const long long MOD = 1e9 + 7;

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

void solve()
{
    long long n, m;
    cin >> n >> m;

    vector<vector<char> > grid(n, vector<char>(m, 0));
    vector<vector<long long> > dp(n, vector<long long>(m, 0));
    dp[0][0] = 1;
    for(long long i = 0; i < n; ++i)
        for(long long j = 0; j < m; ++j)
            cin >> grid[i][j];

    for(long long i = 0; i < n; ++i)
    {
        for(long long j = 0; j < m; ++j)
        {
            for(long long k = 0; k < 2; ++k)
            {
                long long x = i + dx[k], y = j + dy[k];
                if(x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == '.')
                    dp[i][j] = (dp[i][j] + dp[x][y]) % MOD;
            }

            dp[i][j] %= MOD;
        }
    }

    cout << dp[n - 1][m - 1] % MOD << '\n';
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //srand (time(0));

    solve();
}






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

char get_type(string d[]) {
  for (int i = 0; i < 8; i++) {
    for (int j = 0; j < 8; j++) {
      if (d[i][j] == '1') {
        if (i + 3 < 8 && d[i + 3][j] == '1') return 'B';
        if (j + 3 < 8 && d[i][j + 3] == '1') return 'C';
        if (i + 2 < 8 && j - 1 >= 0 && d[i + 2][j - 1] == '1') return 'D';
        if (i + 2 < 8 && j + 1 < 8 && d[i + 2][j + 1] == '1') return 'F';
        if (i + 1 < 8 && j + 2 && d[i + 1][j + 2] == '1') return 'E';
        if (i + 1 < 8 && j + 1 && d[i + 1][j + 1] == '1') return 'A';
        return 'G';
      }
    }
  }
  return '-';
}

int main() {
  string d[8];
  while (getline(cin, d[0])) {
    for (int i = 1; i < 8; i++) {
      getline(cin, d[i]);
    }
    cout << get_type(d) << endl;
    getline(cin, d[0]);
  }
}


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

int main() {
    string S;
    cin >> S;
    bool frag = true;
    if (S[0] != 'A') {
        cout << "WA" << endl;
    }
    else {
        int cntC = 0;

        for (int i = 2; i < S.size()-1; i++) {
            if (S[i] == 'C') {
                cntC++;
            }
            else if (S[i] >= 'A' && S[i] <= 'Z') {
                cout << "WA" << endl;
                frag = false;
                break;
            }
        }
        if (cntC != 1 && frag) {
            cout << "WA" << endl;
            frag = false;
        }
        else if (S[1] >= 'a' && S[1] <= 'z'&& S[S.size()-1] >= 'a' && S[S.size()-1] <= 'z') {
            cout << "AC" << endl;
        }
        else{
            cout << "WA" << endl;
        }
    }
    
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    double w, h, x, y;
    cin >> w >> h >> x >> y;
    int f;
    if(w/2.0==x&&h/2.0==y) f=1;
    else f=0;
    double ans = w*h/2.0;
    printf("%.7lf %d\n",ans,f);
    return 0;
}

Measured memory_bytes: 3796
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define str string
#define fi first
#define se second
#define pb push_back
#define SET(a, b) memset(a, b, sizeof(a))
#define eps 1e-6
#define pi atan(1) * 4
#define mod 1000000007
#define inf 1000000000
#define llinf 1000000000000000000
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
#define FORl(i, a, b) for (ll i = (a); i <= (b); i++)
#define FORDl(i, a, b) for (ll i = (a); i >= (b); i--)
using namespace std;
map<string, int> freq;
string vd[4] = {"AC", "WA", "TLE", "RE"};
int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  FOR(i, 1, t) {
    string S;
    cin >> S;
    freq[S]++;
  }
  FOR(i, 0, 3) {
    printf("%s x %d\n", vd[i].c_str(), freq[vd[i]]);
  }
  return 0;
}

Measured memory_bytes: 3756
package main

import (
	"fmt"
	"os"
)

const (
	x = 500
	y = 100
	z = 50
)

func main() {
	var a, b, c, d int
	fmt.Scan(&a)
	fmt.Scan(&b)
	fmt.Scan(&c)
	fmt.Scan(&d)

	if x*a+y*b+z*c < d {
		fmt.Println("0")
		os.Exit(0)
	}

	counter := 0
	for i := 0; i <= a; i++ {
		for j := 0; j <= b; j++ {
			for k := 0; k <= c; k++ {
				if x*i+y*j+z*k == d {
					counter++
				}
			}
		}
	}
	fmt.Println(counter)

}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e16;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 2510;
constexpr ll nx[8] = {1,0,-1,0,-1,-1,1,1};
constexpr ll ny[8] = {0,1,0,-1,-1,1,-1,1};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,K;
    cin >> n >> K;
    vector<ll> h(n);
    cins(all(h));
    ll dp[n+1][n+1][n+1]; // dp[何回目][操作の回数][何連続]
    rep(i,n+1) rep(j,n+1) rep(k,n+1) dp[i][j][k] = INF;
    dp[0][0][0] = 0;
    rep(i,n){
        rep(j,n){
            rep(k,n){
                if (i < k || j < k || i < j) continue;
                chmin(dp[i+1][j+1][k+1],dp[i][j][k]);
                ll plus;
                if (i == k) plus = h[i];
                else plus = (h[i-k-1] < h[i] ? h[i] - h[i-k-1] : 0);
                chmin(dp[i+1][j][0],dp[i][j][k]+plus);
            }
        }
    }
    ll ans = INF;
    rep(j,K+1){
        rep(k,j+1){
            chmin(ans,dp[n][j][k]);
        }
    }
    PRINT(ans);
}


Measured memory_bytes: 213376
from collections import defaultdict
n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
cnt_d, cnt_t = defaultdict(int), defaultdict(int)
for dif in d:
    cnt_d[dif] += 1

for t_dif in t:
    cnt_t[t_dif] += 1

for k, v in cnt_t.items():
    if v > cnt_d[k]:
        print("NO")
        exit()

print("YES")

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

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

    int a;
    map<int, int> count_map;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        ++count_map[a];
    }

    int ans = 0;
    for (pair<int, int> element : count_map) {
        if (element.first > element.second) {
            ans += element.second;
        }
        if (element.first < element.second) {
            ans += element.second - element.first;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4736
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
#include <map>
#include <cmath>
#include <math.h>
#include <cstdio>
#include <iomanip>
typedef  long long ll;
using namespace std;


int main(void) {
	ll n, k;
	cin >> n >> k;
	ll p;
	vector<long double> E(n), S(n + 1);
	for (int i = 0; i < n; i++) 
	{
		cin >> p;
		E[i] = (double)( p + 1 ) / 2;
	}

	S[0] = 0;
	for (int i = 0; i < n ; i++)
	{
		S[i + 1] = E[i] + S[i];
	}

	long double ans = S[0];
	for (int i = 0; i <= n - k; i++)
	{
		ans = max(ans, S[i + k] - S[i]); 
	}
	
	cout << fixed;
	cout << setprecision(8) << ans << endl;

	return 0;
}

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

typedef pair<int,int> P;

int main() {
  int n;
  while(cin >> n && n) {
    int a[n];
    for(int i=0; i<n; i++) cin >> a[i];
    int s=a[0];
    vector<P> ans;
    for(int i=1; i<n; i++) {
      if(a[i]-1!=a[i-1]) {
	ans.push_back(P(s,a[i-1]));
	s=a[i];
      }
    }
    ans.push_back(P(s,a[n-1]));
    
    for(int i=0; i<ans.size(); i++) {
      if(i!=0) cout << " ";
      if(ans[i].first==ans[i].second) cout << ans[i].first;
      else {
	cout << ans[i].first << "-" << ans[i].second;
      }
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 1200
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
double pi = 3.141592653589793;
ll mod = 1000000007;
ll INF = 1000000001;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;



int main(){
	string s;
	cin>>s;
	char pre = s[0];
	int ans=0;
	REP(i,1,s.size()){
		if(pre=='0'){
			if(s[i]==pre)
				ans++;
			pre='1';
		}
		else{
			if(s[i]==pre)
				ans++;
			pre='0';
		}
	}
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 512
#include <iostream>      // cout, endl, cin
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <list>          // list
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <cctype>        // isupper, islower, isdigit, toupper, tolower
#include <math.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)


int main()
{
    int N;
    cin >> N;
    map<string, int> mp;

    rep(i, N)
    {
        pair<string, string> pr; 
        cin >> pr.first >> pr.second;
        if(pr.first == "insert")
        {
            mp[pr.second] = 1;
        }
        else
        {
            if(mp.count(pr.second))
            {
                cout << "yes" << endl;
            }
            else
            {
                cout << "no" << endl;
            }
        }
    }
}


Measured memory_bytes: 36456
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

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

res = 0
div = make_divisors(M)
for x in div:
  if M // x >= N: res = max(res, x)
print(res)

Measured memory_bytes: 39152
/*######################################################
#########~~~~~####~~~~###~~##~~##~~##~~##~~##~~#########
#########~~##~~##~~##~~##~~~#~~##~~~#~~##~~##~~#########
#~~~~~~##~~~~~###~~~~~~##~~#~~~##~~#~~~##~~##~~##~~~~~~#
#########~~######~~##~~##~~##~~##~~##~~##~~##~~#########
#########~~######~~##~~##~~##~~##~~##~~###~~~~##########
######################################################*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

#pragma GCC optimize("O3")
#define rtn return
#define endl '\n'
#define F first
#define S second
#define mt make_tuple
#define pb push_back
#define int long long
#define value_at find_by_order
#define index_of order_of_key
#define fill(a, v) memset(a,v,sizeof(a))
#define copy(a, b) memcpy(b,a,sizeof(a))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i, n) for(int i=0;i<(int)n;++i)
#define per(i, n) for(int i=(int)n-1;i>=0;--i)
#define rep1(i, n) for(int i=1;i<=(int)n;++i)
#define per1(i, n) for(int i=(int)n;i>=1;--i)
#define loop(i, begin, end) for(int i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cerr << name << " = " << arg1 << '\n';
}
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...);
}
#else
#define trace(...)
#endif

typedef string str;
typedef long double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pll;
typedef vector<int> vll;
typedef vector<pll> vpll;
typedef vector<db> vdb;

template<class T, class V> void remin(T &a, V b) { a > b ? a = b : a = a; }
template<class T, class V> void remax(T &a, V b) { a < b ? a = b : a = a; }
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e18;
const db EPS = 1e-15;
const int MOD = 1e9 + 7;
const int N = 1e5 + 7;

int n;
int a[N + N];

int32_t main() {
  FAST_IO;
  cin >> n;
  rep(i, n)
    cin >> a[i];
  int want = -1;
  rep(i, n) {
    if (a[i] - 2 == want) {
      ++want;
    }
  }
  if (want == -1) {
    cout << -1 << '\n';
    rtn 0;
  }
  want += 1;
  cout << n - want << '\n';
  rtn 0;
}


Measured memory_bytes: 1792
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>
#include <set>
#include <map>

using namespace std;

typedef long long ll;

int main()
{
  int n, x, y;
  cin >> n >> x >> y;
  x--;
  y--;
  vector<int> num(n);
  for (int l = 0; l < n; ++l) for (int r = l + 1; r < n; ++r) {
    vector<vector<int>> g(4, vector<int>(4));
    vector<int> c = vector<int>({l, r, x, y});
    for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j) {
      g[i][j] = abs(c[i] - c[j]);
    }
    g[2][3] = 1;
    for (int t = 0; t < 4; ++t) for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j) {
      if (g[i][j] > g[i][t] + g[t][j]) g[i][j] = g[i][t] + g[t][j];
    }
    num[g[0][1]]++;
  }
  for (int i = 1; i < n; ++i) cout << num[i] << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <sstream>
#include <fstream>

using namespace std;

#define A first
#define B second
#define all(x) (x).begin(), (x).end

typedef long long ll;
constexpr int MOD = 1000000007;

void solve() {
  int N;
  cin >> N;
  vector<vector<double>> dp(N, vector<double>(N + 1));
  vector<double> A(N);
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }
  dp[0][0] = 1 - A[0];
  dp[0][1] = A[0];
  for(int i = 1; i < N; i++){
    for(int j = 0; j < N; j++){
      dp[i][j] += dp[i - 1][j] * (1 - A[i]);
      dp[i][j + 1] += dp[i - 1][j] * A[i];
    }
  }
  double ans = 0;
  for(int i = N / 2 + 1; i <= N; i++){
    ans += dp[N - 1][i];
  }
  cout << fixed << setprecision(10) << ans;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  T = 1;
  //cin >> T;
  while(T--){
    solve();
  }
}

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

#define rep(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define rng(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define rbf(i, v) for (auto& (i) : (v))
#define All(x) (x).begin(),(x).end()
#define cAll(x) (x).cbegin(),(x).cend()
#define COL(x) cout << x << endl
#define CO(x) cout << x
//#define int long long

template<typename T> inline constexpr auto square(T x) { return (x) * (x); }

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

const int MOD = 1000000007;
const int INF = INT_MAX;

signed main()
{
	int N;
	cin >> N;

	int ans = N * N * N;
	COL(ans);

	return 0;
}

Measured memory_bytes: 256
A=int(input())
B=int(input())
C=int(input())
X=int(input())
M=0
for a in range(A+1):
  for b in range(B+1):
    for c in range(C+1):
      if (500*a+100*b+50*c)==X :
        M+=1      
print(M)

Measured memory_bytes: 3060
from collections import defaultdict
import itertools


def resolve():
    n = int(input())
    d = defaultdict(list)
    for _ in range(n):
        s = input()
        d[s[0]].append(s)
    print(sum([len(d[c1]) * len(d[c2]) * len(d[c3]) for c1, c2, c3 in itertools.combinations(["M", "A", "R", "C", "H"], 3)]))


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 55000
while True:
    X=int(input())
    if X>0:
        x=1000-X
        a=x//500
        b=x%500//100
        c=x%500%100//50
        d=x%500%100%50//10
        e=x%500%100%50%10//5
        f=x%500%100%50%10%5
        print(a+b+c+d+e+f)
    else:
        break


Measured memory_bytes: 5588
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string   { sc.Scan(); return sc.Text() }
func scanRunes() []rune    { return []rune(scanString()) }
func scanInt() int         { a, _ := strconv.Atoi(scanString()); return a }
func scanInt64() int64     { a, _ := strconv.ParseInt(scanString(), 10, 64); return a }
func scanFloat64() float64 { a, _ := strconv.ParseFloat(scanString(), 64); return a }

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = scanInt()
	} 
	return res
}

func debug(a ...interface{}) { fmt.Fprintln(os.Stderr, a...) }

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//•*¨*•.¸¸♪main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)
func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1001001)

	a := scanInt()
	b := scanInt()
	k := scanInt()
	for i := a;; i-- {
		if a%i == 0 && b%i == 0 {
			k--
		}
		if k == 0 {
			fmt.Fprintln(wr, i)
			return
		}
	}
}


Measured memory_bytes: 640
N = int(input())
A = list(map(int, input().split()))
even = lambda x: True if x % 2 == 0 else False
div2 = lambda x: x/2
isContinue = True
c = 0
while isContinue:
    for i, v in enumerate(A):
        if even(v):
            A[i] = div2(v)
        else:
            isContinue = False
    if isContinue:
        c += 1
print(c)

Measured memory_bytes: 3060
/* ex4_2
   UMAboogie */

#include<stdio.h>
#include<math.h>
#define PI 3.14159265358979 //円周率を定義

int main(void){
  int length_h, length_m, hour, minute;
  scanf("%d %d %d %d", &length_h, &length_m, &hour, &minute); //時針の長さと分針の長さと時間と分を入力

  double angle_h = hour * PI / 6 + minute * PI / 360; //時針が進む角度を計算
  double angle_m = minute * PI / 30; //分針が進む角度を計算
  double angle_bet = fabs(angle_h - angle_m); //時針と分針の間の角度を計算

  double answer = sqrt(length_h*length_h + length_m*length_m - 2*length_h*length_m*cos(angle_bet)); //余弦定理を用いて2本の針の端点の距離を計算
  printf("%.10f",answer); //答えを出力
  return 0;
}

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    ll A, B;
    cin >> A >> B;
    ll cnt = 0;
    REP(i,A,B+1) {
        if(i/10000==i%10 && (i/1000)%10==(i/10)%10) ++cnt;
    }
    PR(cnt);

    return 0;
}

/*



*/

Measured memory_bytes: 3556
def main(n,a,b):
    ans=0
    while True:
        cnt=0
        for i in range(n):
            m=a[(i-1)%n]+a[(i+1)%n]
            if m<a[i] and b[i]<a[i]:
                a[i]-=b[i]
                cnt+=a[i]//m
                a[i]%=m
                a[i]+=b[i]
        if cnt==0:break
        ans+=cnt
    if a==b:
        print(ans)
    else:
        print(-1)
if __name__=='__main__':
    n=int(input())
    b=list(map(int,input().split()))
    a=list(map(int,input().split()))
    main(n,a,b)


Measured memory_bytes: 40292
A, B, C, X, Y = map(int, input().split(" "))
if A + B < 2 * C:
    print(X * A + Y * B)
else:
    if A < 2 * C and X > Y:
        print(Y * 2 * C + (X - Y) * A)
    elif B < 2 * C and X < Y:
        print(X * 2 * C + (Y - X) * B)
    else:
        print(max(X, Y) * 2 * C)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
const int INF = 1001001001;

int main(){
    int d, g;
    cin >> d >> g;
    vector<int> p(d), c(d);
    rep(i, d) cin >> p[i] >> c[i];
    int ans = INF;
    rep(i, 1<<d) {
        vector<bool> comp(d);
        int score = g;
        int num = 0;
        rep(j, d) {
            if (i>>j&1) {
                comp[j] = true;
                score -= (c[j]+100*(j+1)*p[j]);
                num += p[j];
            }
        }
        int index = d-1;
        //debug(score);
        while (score>0 && index>=0) {
            if (comp[index]) {
                index--;
                continue;
            }
            int v = min(score, 100*(index+1)*(p[index]-1));
            score -= v;
            num += (v-1)/(100*(index+1))+1;
            index--;
        }
        if (score<=0) {
            chmin(ans, num);
        }
    }
    
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256