akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <array>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>
#include <stack>
#include <utility>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <bitset>
#include <random>
#include <functional>
#include <sstream>
#include <iomanip>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back

typedef long long LL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef vector<LL> VL;

int main() {
	int a, b, c; cin >> a >> b >> c;
	cout << min(b / a, c) << endl;
}

Measured memory_bytes: 256
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,j,n) for(int i = j; i < n; i++)
#define RFOR(i,j,n) for(int i = j-1; i >= n; i--)
#define PREC(n) fixed << setprecision(n)
#define print_array(v) REP(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; } value
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define _LIBCPP_DEBUG 0
using namespace std;
int64_t MOD = 1000000007;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  cout << (n+1)/2 << endl;
}

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

int main() {
  int N;
  cin >> N;
  
  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    if (s == "Y") {
      cout << "Four" << endl;
      return 0;
    }
  }
      cout << "Three" << endl;
      return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<vector<int>> graph;
vector<long long> ans;
vector<bool> used;
 
int main() {
    cin >> n >> q;
    graph = vector<vector<int>>(n);
    ans = vector<long long>(n, 0);
    used = vector<bool>(n, false);
    for(int i = 0; i < n-1; ++i) {
        long long a, b;
        cin >> a >> b;
        a--; b--;
        graph.at(a).push_back(b);
        graph.at(b).push_back(a);
    }

    queue<long long> que;
 
    for(int i = 0; i < q; ++i) {
        long long p, x;
        cin >> p >> x;
        p--;
        ans.at(p) += x;
    }

    que.push(0);
    used.at(0) = true;

    // 上から見ていくからusedが必要
    while(!que.empty()) {
        long long first = que.front();
        que.pop();
        int len = graph.at(first).size();
        for(int j = 0; j < len; ++j) {
            int next = graph.at(first).at(j);
            if(!used.at(next)) {
                ans.at(next) += ans.at(first);
                used.at(next) = true;
                que.push(next);
            }
        }
    }
 
    for(int i = 0; i < n; ++i) {
        cout << ans.at(i) << " ";
    }
    cout << endl;
}

Measured memory_bytes: 17140
#include <bits/stdc++.h>
// #include <math.h>
// #include <cmath>
// #include <vector>
// #include <utility> 
// #include <unordered_map>
// #include <map>
// #include <string>

using namespace std;
typedef long long int lli;

#define M_PI_H  3.14159265358979323846/2  /* pi by two*/
#define rep(i, start, end) for(int i = start; i < end; i++) 
#define repr(i, start, end) for(int i = start; i >= end; i--)   //INCLUSIVE



int main() 
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
	
		char s; cin>>s;

		if(s >= 'a'){
			cout<<"a";
		} else {

			cout<<"A";
		}
	
    return 0;
}

Measured memory_bytes: 3600
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <iomanip>

typedef long double ld;
typedef long long ll;

using namespace std;


/* TEMPLATE ENDS HERE */

#define MAXN (1 << 20)

vector<pair<int, int> > a[MAXN];
int n, m;
int v[MAXN];
int d[MAXN];

bool dfs(int cur, int pos) {
	if (v[cur]) {
		return (d[cur] == pos);
	}
	v[cur] = 1;
	d[cur] = pos;
	bool ret = true;
	for (auto& e: a[cur]) {
		ret &= dfs(e.first, pos + e.second);
	}
	return ret;
}

int main() {
	cout << fixed << setprecision(12);	
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int l, r, d;
		cin >> l >> r >> d;
		a[l].push_back(make_pair(r, d));
		a[r].push_back(make_pair(l, -d));
	}
	for (int i = 1; i <= n; i++) {
		if (v[i]) {
			continue;
		}
		if (!dfs(i, 0)) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}


ll MOD = ((ll)1e9 + 7);

struct mod {
	ll x;

	mod(ll tx = 0) {
		x = tx;
		x %= MOD;
	}
	
	mod& operator=(const ll & tx) {
		x = tx % MOD;
		return *this;
	}
	
	mod& operator=(const mod & m2) {
		x = m2.x;
		return *this;
	}

	mod operator+(const mod& m2) const {
		return mod((x + m2.x) % MOD);
	}

	mod& operator+=(const mod& m2) {
		x += m2.x;
		x %= MOD;
		return *this;
	}

	mod operator-(const mod & m2) const {
		return mod((x - m2.x + MOD) % MOD);
	}

	mod& operator-=(const mod & m2) {
		x -= m2.x;
		x = (x + MOD) % MOD;
		return *this;
	}

	mod operator*(const mod & m2) const {
		return mod((x * m2.x) % MOD);
	}

	mod& operator*=(const mod & m2) {
		x *= m2.x;
		x %= MOD;
		return *this;
	}

	mod mypow(ll k) const {
		mod ret = 1;
		mod cur = x;
		while (k) {
			if (k & 1) {
				ret *= cur;
			}
			cur *= cur;
			k >>= 1;
		}
		return ret;
	}

	mod inv() const {
		return mypow(MOD - 2);
	}

	mod operator/(const mod & m2) const {
		return (*this) * m2.inv();
	}

	mod& operator/=(const mod & m2) {
		x *= m2.inv().x;
		x %= MOD;
		return *this;
	}

	bool operator<(const mod & m2) const {
		return x < m2.x;
	}
};

ostream &operator<<(ostream & os, const mod & m) {
	return os << m.x;
}



Measured memory_bytes: 38028
#昔のコピペ
s = input()
n = len(s)
p = 2019

c = 0
mm = {}
r = 0
mten = 1
for i in range(n - 1, -1, -1):
    ch = int(s[i])
    r = (r + ch * mten) % p
    mten = (mten * 10) % p
    if r in mm:
        c += mm[r]
        mm[r] += 1
    else:
        mm[r] = 1
    if r == 0:
        c += 1

print(c)

Measured memory_bytes: 68240
#include <bits/stdc++.h>
using namespace std;
int n,a,b;
int rez;
int hui;
int c;
int d;
int suma(int g){
    while(g>0){
        hui+=g%10;
        g/=10;
    }
    return hui;
}
int main(){
    cin >> n >> a >> b;
    for(int i=1;i<=n;i++){
        c=i;
        d=i;
        if(suma(i)>=a){
            hui=0;
            if(suma(c)<=b){
                rez+=d;
            }
        }
        hui=0;
    }
    cout<<rez;
}

Measured memory_bytes: 256
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def make_divisors(n): # 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

N = ir()
D = make_divisors(N)
answer = 10 ** 12
for d in D:
    e = N // d
    result = (d - 1) + (e - 1)
    if result < answer:
        answer = result

print(answer)


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

int main()
{
    int N;
    cin >> N;
    vector<int> W(N);
    for (int i = 0; i < N; i++)
        cin >> W[i];

    int s,s1,s2;
    s=0;
    for (int i = 0; i < N; i++)
        s+=W[i];

    s1=0;
    for (int i = 0; i < N; i++){
        s1 += W[i];
        if ((s - s1 - s1) <= W[(i + 1)] || ( s - s1 - s1)<=0)
        {
            cout << abs(s - s1 - s1);
            break;
        }
    }

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
class Main {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		double radius = scanner.nextDouble();
		double pi = 3.141592653589;
		double are = radius*radius*pi;
		double cir = 2*radius*pi;
		String area = String.format("%.8f", are);
		String circ = String.format("%.8f", cir);
		
		System.out.println(area+" "+circ);
	}	
}

Measured memory_bytes: 28152
s = input()
t = input()
max = 10**100
now = t[0]
cnt1 = 0
cnt2 = 0

for i in t:
	if s.find(i)==-1:
		print("-1")
		exit(0)

while True:
	temp = s[:]
	if cnt2 == len(t):
		print(cnt1)
		break
	if max == 0:
		print("-1")
		break
	while True:
		num = temp.find(now)
		if num != -1:
			cnt2+=1
			cnt1+=num+1
			if cnt2 < len(t):
				now = t[cnt2]
			else:
				break
			temp = temp[num+1:]
			continue
		else:
			cnt1+=len(temp)
			break
	max-=1


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

int main() {
  vector<int> p={1};
  for(int i=2;i<=31;i++){
    int D=i*i;
    while(D<=1000){
      p.push_back(D);
      D*=i;
    }
  }
  sort(p.begin(), p.end());
reverse(p.begin(), p.end());
  int a,x;
  cin>>x;
  while(true){
    if(p.at(a)<=x){
      cout<<p.at(a)<<endl;
      break;
    }
    a++;
  }
  
    

}




Measured memory_bytes: 256
# -*- coding: utf-8 -*-


def main():
    import sys
    input = sys.stdin.readline

    k, n = map(int, input().split())
    a = list(map(int, input().split()))
    ans = a[-1] - a[0]

    for i in range(n):
        if (i + 1) < n:
            dist = a[i] + (k - a[i + 1])
            ans = min(ans, dist)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 25924
import java.util.*;
class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int a=sc.nextInt();
    int[] bcd=new int[3];
    int t=a;
    for(int i=2;i>=0;i--){
      bcd[i]=t%10;
      t=t/10;
    }
    a=t%10;
    for(int i=0;i< 1<<3;i++){
      int sum=a;
      String[] pm=new String[3];
      for(int j=0;j<3;j++){
        if((1&(i>>j))==1){
          sum=sum-bcd[j];
          pm[j]="-";
        }
        else{
          sum=sum+bcd[j];
          pm[j]="+";
        }
      }
      if(sum==7){
        System.out.print(a);
        for(int j=0;j<3;j++){
          System.out.print(pm[j]+bcd[j]);
        }
        System.out.println("=7");
        break;
      }
    }
    sc.close();
  }
}


Measured memory_bytes: 39212
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
int const INF = 1001001001;


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

ll N;
cin >> N;

ll cur = 0;
rrep(i,N) {
    cur += i;
    if(N <= cur) {
        rrep(j,i) {
            if(j == cur - N) continue;
            cout << j << endl;
        }
        return 0;
    }
}

return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <functional>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define v_exists(elem, v) find(v.begin(),v.end(),elem)!=v.end()

using namespace std;

int main(){

  int N,T;
  scanf("%d %d", &N, &T);

  int m=1001;

  rep(i, N){
    int c,t;

    cin >> c;
    cin >> t;

    if(t<=T && c<m){
      m = c;
    }
  }

  if(m == 1001){
    cout << "TLE" << endl;
    return 0;
  }

  cout << m << endl;
  return 0;

}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
using ll = long long;
using ull = unsigned long long;
using namespace std;
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
//max_element

int H, W, K;
int X1, Y1, X2, Y2;
bool C[1000010];
int result[4000010];
bool used[4000010];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};


int Ind(int x, int y)
{
	return x + y * W;
}

int Ind(int x, int y, int d)
{
	return x * 4 + y * W * 4 + d;
}

bool IsIn(int x, int y)
{
	return 0 <= x && x < W && 0 <= y && y < H;
}


//---------- ダイクストラ pair<index,len> ----------
void dijkstra()
{
	result[Ind(X1, Y1, 0)] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; //len, index
	q.push(pair<int, int>(0, Ind(X1, Y1, 0)));

	while (q.size() > 0)
	{
		int len, index;
		tie(len, index) = q.top();
		q.pop();
		if (used[index]) continue;
		used[index] = true;

		int cd = index % 4;
		int x = (index / 4) % W;
		int y = (index / 4) / W;

		int rd = (cd + 1) % 4;
		int rlen = ceil(len / (double)K) * K;
		int rindex = Ind(x, y, rd);
		result[rindex] = rlen;
		q.push(pair<int, int>(rlen, rindex));

		int nx = x + dx[cd];
		int ny = y + dy[cd];
		if (IsIn(nx, ny) && !C[Ind(nx, ny)])
		{
			int nindex = Ind(nx, ny, cd);
			result[nindex] = len + 1;
			q.push(pair<int, int>(len + 1, nindex));
		}
	}
}



signed main()
{
	cin >> H >> W >> K;
	cin >> Y1 >> X1 >> Y2 >> X2;
	Y1--;
	X1--;
	Y2--;
	X2--;
	REP(y, H)
	{
		string s;
		cin >> s;
		REP(x, W)
		{
			C[Ind(x, y)] = (s[x] == '@');
		}
	}

	for (int i = 0; i < 4000010; i++)
	{
		result[i] = INT64_MAX;
	}

	dijkstra();

	int m = INT_MAX;
	for (int d = 0; d < 4; d++)
	{
		int res = result[Ind(X2, Y2, d)];
		m = min(m, res);
	}

	if (m == INT_MAX)
	{
		cout << -1 << endl;
	}
	else
	{
		cout << ceil(m / (double)K) << endl;
	}
}



Measured memory_bytes: 42632
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int n = sc.nextInt();
		int k = sc.nextInt();
		double result = 0;

		for (int i = 1; i <= n; i++) {
			if (i >= k) {
				result += (n - k + 1) ;
				break;
			}
			int pow = calcPow(i, k);
			//i1つだけ足す
			result += (1 / Math.pow(2, pow)) ;

			// System.out.print(pow + " ");
			// System.out.println(result);
		}

		System.out.println(result/n);

	}

	// 2の何乗以下かを返す
	private static int calcPow(int n, int k) {
		for (int i = 0; i <= 18; i++) {
			if (n >= k) {
				return i;
			}
			n = n * 2;
		}
		return 0;
	}
}


Measured memory_bytes: 23124
package main

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

func main() {
	n := readInt64()

	if n == 0 {
		fmt.Println(0)
		os.Exit(0)
	}
	if n < 10 {
		fmt.Println(n)
		os.Exit(0)
	}

	N := getNumberOfDigits(n)
	maxnum := int64(0)
	for i := 1; i < N; i++ {
		digitVal := getDigitValue(n, i)
		if digitVal != 9 {
			n = n - ((int64(digitVal) + 1) * int64(math.Pow(10.0, float64(i-1))))
		}

		// fmt.Println(i, ":", n)
		maxnum = max(maxnum, calcDigitsSum(n))
	}

	fmt.Println(maxnum)
}

func getNumberOfDigits(n int64) int {
	cnt := 0
	for {
		cnt++
		n = int64(n / 10)
		if n == 0 {
			break
		}
	}
	return cnt
}

func getDigitValue(n int64, idx int) int {
	cnt := 0
	for {
		cnt++
		ret := n % 10
		n = int64(n / 10)
		if idx == cnt {
			return int(ret)
		}
		if n == 0 {
			fmt.Println("Error@getDigitValue")
			break
		}
	}
	return -1 // invalid value
}

func calcDigitsSum(n int64) int64 {
	sum := int64(0)
	for {
		sum += n % 10
		n = int64(n / 10)
		if n == 0 {
			break
		}
	}
	return sum
}

func max(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

func readInt64() int64 {
	var a int64
	fmt.Scan(&a)
	return a
}

func readInt64Line() []int64 {
	var sc = bufio.NewScanner(os.Stdin)
	sc.Scan()
	line := sc.Text()
	vals := strings.Split(line, " ")
	var vec []int64
	for _, v := range vals {
		n, err := strconv.ParseInt(v, 10, 64)
		if err != nil {
			panic(err)
		}
		vec = append(vec, n)
	}
	return vec
}

func sumInt64Array(arr []int64) int64 {
	var sum int64
	for _, val := range arr {
		sum += val
	}
	return sum
}

// 3141592653589793


Measured memory_bytes: 640
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

using namespace std;

string b[10] = {"MAR", "MAC", "MAH", "MRC", "MRH",
                "MCH", "ARC", "ARH", "ACH", "RCH"};

int main() {
  int n;
  cin >> n;
  vector<string> names(n);
  for (int i = 0; i < n; i++)
    cin >> names[i];
  map<char, int> mp;
  for (int i = 0; i < n; i++) {
    mp[names[i][0]]++;
  }
  long long ans = 0;
  for (int i = 0; i < 10; i++) {
    long long a = 1;
    for (int j = 0; j < 3; j++)
      a *= mp[b[i][j]];
    ans += a;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 6144
#include <stdio.h>
int main(void){
  int N;
  double v[51];
  int i;
  int j;
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%lf",&v[i]);
  }
  int tmp;
  for(i=0;i<N;i++){
    for(j=i+1;j<N;j++){
      if(v[i]>v[j]){
        tmp=v[i];
        v[i]=v[j];
        v[j]=tmp;
      }
    }
  }
  double s=v[0];
  for(i=1;i<N;i++){
    s=(s+v[i])/2.0;
  }
  printf("%lf",s);
  return 0;
}

Measured memory_bytes: 1748
def merge(A, left, mid, right):
    global count
    inf = 10 ** 9
    L = A[left:mid] + [inf]
    R = A[mid:right] + [inf]

    i = 0
    j = 0
    for k in range(left, right):
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

n = int(input())
A = list(map(int, input().split()))
count = 0
mergeSort(A, 0, n)

print(' '.join(list(map(str, A))))
print(count)


Measured memory_bytes: 66704
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}
template<class T> struct Fenwick {
    int n;
    T* d;
    Fenwick() : n(0), d(NULL) {}
    Fenwick(int n_) : n(n_) {
	d = new T[n_]();
    }
    Fenwick(const Fenwick &y) : n(y.n) {
	d = new T[n];
	memcpy(d, y.d, sizeof (T) * n);
    }
    ~Fenwick() {
	delete[] d; d = NULL;
	n = 0;
    }
    friend void swap(Fenwick &x, Fenwick &y) {
	swap(x.n, y.n); swap(x.d, y.d);
    }
    Fenwick& operator=(Fenwick y) {
	swap(*this, y);
	return *this;
    }
    inline void add(int i, const T &x) {
	for (; i<n; i|=i+1) d[i] += x;
    }
    inline T sum(int r) {
	T s = T();
	for (; r; r&=r-1) s += d[r-1];
	return s;
    }
    T sum(int l, int r) {
	return sum(r) - sum(l);
    }
};

int N;
int A[3][100011];
bool use[100011];

int calc(const VI &v) {
    int inv = 0;
    Fenwick<int> F(N);
    EACH (e, v) {
	inv ^= F.sum(*e, N);
	F.add(*e, 1);
    }
    return inv&1;
}

void MAIN() {
    scanf("%d", &N);
    REP (t, 3) REP (i, N) {
	scanf("%d", A[t]+i);
	A[t][i]--;
    }

    vector<pair<int, int> > X;
    REP (i, N) {
	int a = A[0][i], b = A[1][i], c = A[2][i];
	if (a % 3 == 0 && b == a+1 && c == a+2) {
	    int x = a/3;
	    use[x] = true;
	    X.emplace_back(x, 1);
	} else if (c % 3 == 0 && b == c+1 && a == c+2) {
	    int x = c/3;
	    use[x] = true;
	    X.emplace_back(x, -1);
	}
    }

    int cnt = 0;
    REP (i, N) if (use[i]) cnt++;

    bool yes = (cnt == N);
    if (yes) {
	int neg[2] = {};
	VI E, O;
	REP (i, N) {
	    if (i%2 != X[i].first%2) yes = false;

	    int sgn = X[i].second;
	    if (i % 4 >= 2) sgn = -sgn;
	    if (X[i].first % 4 >= 2) sgn = -sgn;
	    if (sgn == -1) neg[i&1] ^= 1;
	    
	    if (i%2) O.push_back(X[i].first);
	    else E.push_back(X[i].first);
	}

	int inv[2] = {};
	inv[0] = calc(E);
	inv[1] = calc(O);

	if (yes) {
	    yes = (neg[0] == inv[1] && neg[1] == inv[0]);
	}
    }

    puts(yes? "Yes": "No");
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 3444
#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N,M = map(int, input().split())
    A = list(map(int, input().split()))
    s = sum(A)
    if s > N:
        print(-1)
    else:
        print(N-s)

main()


Measured memory_bytes: 9996
#include<stdio.h>
int main(){
    int N,i,sum;
    sum = 0;
    scanf("%d",&N);
    if(N>=1 && N<=100){
        for(i = 1;i<=N;i++){
            sum = sum+i;
        }
    }
    printf("%d\n",sum);
    return 0;
}


Measured memory_bytes: 128
using System;
using System.Linq;

class B
{
	static void Main()
	{
		var h = Console.ReadLine().Split().Select(int.Parse).ToArray();
		Console.WriteLine(Enumerable.Range(1, h[0]).Reverse().Where(i => h[0] % i == 0 && h[1] % i == 0).ElementAt(h[2] - 1));
	}
}


Measured memory_bytes: 13396
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();
        int k = scan.nextInt();
        int out = 0;
        if(k <= a){
            out = k;
        }else if(k <= b){
            out = a;
        }else{
            out = a;
            out -= k - a - b;
        }
        System.out.println(out);
    }
}

Measured memory_bytes: 26924
S = input()
flag1 = False
if S[0] == "A":
    S=S.replace("A","",1)
    if "C" in S[1:-1]:
        S = S.replace("C", "", 1)
        if S.islower():
            print("AC")
        else:
            print("WA")
    else:
            print("WA")
else:
            print("WA")

Measured memory_bytes: 3064
#include"bits/stdc++.h"
using namespace std;

#define ll long long int
#define watch(x) cout << (#x) << " is " << (x) << endl
#define f(i,x,n)  for(int i=x;i<n;i++)
#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define eb(x) emplace_back(x)
#define mp(a,b) make_pair(a,b)
#define sz(a) int((a).size())
#define mod 1000000007
#define tr(c,i) for(typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define inf LLONG_MAX
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }


void seethis(vector<ll>vect)
{
    for(ll x:vect)
        cout<<x<<" ";
    cout<<"\n";
}

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...);
}
//LCM
int lcm(int a, int b) {  return a * (b / __gcd(a, b)); }

//For sort by second
bool cmp(const pair<int,int> &a)
{ return a.first<a.second; }

//Tree
/* const int MAXN = 1e5 + 5;
vector<ll> adj[MAXN];*/

//ModPower
ll modpower(ll a,ll b,ll c)
{
	ll res=1;
	while(b)
	{
		if(b&1LL)
			res=(res*a)%c;
		a=(a*a)%c;
		b>>=1;
	}
	return res;
}

int main()
{
	FASTIO;
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
	ll n;
		cin>>n;

	string ans="";

	while(n)
	{
		int digit= n%26;

		if(digit==0)
		{
			ans.push_back('z');
			n=n/26-1;
		}
		else
		{
			char ch= 'a'+digit-1;
			ans.push_back(ch);
			n/=26;
		}
	}
	reverse(ans.begin(),ans.end());
	cout<<ans<<"\n";


	
	return 0;
}

Measured memory_bytes: 3652
import sys;input=lambda:sys.stdin.readline().rstrip();aint=lambda:int(input());ints=lambda:list(map(int,input().split()))
import math;floor,ceil=lambda x:int(math.floor(x)),lambda x:int(math.ceil(x))
from functools import reduce;gcd=lambda*x:reduce(math.gcd,x);lcm=lambda*x:reduce(lambda x,y:(x*y)//gcd(x,y),x,1)
from collections import deque
Yes=lambda b:print("Yes"if b else"No");YES=lambda b:print("YES"if b else"NO")
is_even=lambda x:True if x%2==0 else False

def is_palindrome(s):
  n=len(s);b=True
  for i in range(int(0.5*n)):
    if s[i]!=s[n-i-1]:b=False
  return b

def main():
  n=aint();a=ints();flg=0
  for num in a:
    if num%2==0 and num%3!=0 and num%5!=0:
      flg+=1
      break
  print("APPROVED"if flg==0 else"DENIED")
  
if __name__ == '__main__':
    main()

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

int main()
{
  int N;
  cin >> N;
  map<string, int> mp;
  long long int ans = 0;
  for (int i = 0; i < N; i++)
  {
    string S;
    cin >> S;
    sort(S.begin(), S.end());
    mp[S]++;
    if (mp[S] > 1)
      ans += mp[S] - 1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 11136
from math import hypot
from collections import deque

N, K, *XYC = map(int, open(0).read().split())
XYC = list(zip(*[iter(XYC)] * 3))

Q = deque([(0, 0, 1000.0)])

ans = float("inf")
while Q:
    X, Y, r = Q.popleft()
    if ans * 0.9999995 > sorted(c * hypot(max(abs(X - x) - r, 0), max(abs(Y - y) - r, 0)) for x, y, c in XYC)[K - 1]:
        ans = min(ans, sorted(c * hypot(X - x, Y - y) for x, y, c in XYC)[K - 1])
        for dx, dy in [(-0.5, -0.5), (-0.5, 0.5), (0.5, -0.5), (0.5, 0.5)]:
            Q.append((X + dx * r, Y + dy * r, r / 2))

print(ans)

Measured memory_bytes: 4080
package main

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

var (
	readString func() string
	readBytes  func() []byte
	stdout     *bufio.Writer
)

func init() {
	readString, readBytes = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) (func() string, func() []byte) {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), math.MaxInt32)
	r.Split(bufio.ScanWords)

	f1 := func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
	f2 := func() []byte {
		return []byte(f1())
	}
	return f1, f2
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 10, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readFloat64() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func eprintln(args ...interface{}) (int, error) {
	return fmt.Fprintln(os.Stderr, args...)
}

func eprintf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(os.Stderr, f, args...)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func min64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func max64(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func abs64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func gcd64(a, b int64) int64 {
	if b == 0 {
		return a
	}
	return gcd64(b, a%b)
}

// readString() string
// readInt() int
// readInt64() int64
// readFloat64() float64

// -----------------------------------------------------------------------------

func main() {
	defer stdout.Flush()
	N := readInt()
	println((N - 1) / 2)
}

// -----------------------------------------------------------------------------


Measured memory_bytes: 640
print([1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51][int(input())-1])


Measured memory_bytes: 2940
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val list = readLine()!!.split(" ").map { it.toInt() }.toMutableList()
    var k = 0
    var l = 1

    for (i in 0 until n) {
        if (list[i] != l) {
            k++
        } else {
            l++
        }
    }
    if (k == n) {
        println(-1)
    } else {
        println(k)
    }
}

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

int X, Y, W, H, N, T;

int main() {
	cin >> T;
	
	for(int i = 0; i < T; i++) {
		vector<pair<int, int> > cat;
		cin >> X >> Y >> W >> H;
		cin >> N;
		int ans = 0;

		for(int j = 0; j < N; j++) {
			pair<int, int> tmp;
			cin >> tmp.first >> tmp.second;
			cat.push_back(tmp);
		}

		for(int j = 0; j < N; j++) {
			if((X <= cat[j].first && cat[j].first <= X + W)
					&& (Y <= cat[j].second && cat[j].second <= Y + H))
				ans++;
		}

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

Measured memory_bytes: 1196
#include<iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main()
{
   double a,b,c,d;
   double tmp,e;
   cin>>a>>b>>c>>d;
   tmp=(c-a)*(c-a)+(d-b)*(d-b);
   e=sqrt(tmp);
   cout<<fixed<<setprecision(15)<<e<<endl;
    return 0;
}


Measured memory_bytes: 3280
#ifdef Dhiraj
    #include "D:/dhiraj/Programming/debug.h"
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define d(...) 11
    #define cerr if(0) cerr
#endif

// Macro --------------------------------------------------------------------

#define ll                  long long int
#define FOR(i, a, b, s)     for(ll i = (a); ((s) > 0 ? i < (b) : i > (b)); i += (s))
#define FOR1(b)             FOR(i, 0, b, 1)
#define FOR2(i, b)          FOR(i, 0, b, 1)
#define FOR3(i, a, b)       FOR(i, a, b, (a) <= (b) ? 1 :-1)
#define FOR4(i, a, b, s)    FOR(i, a, b, s)
#define GET5(a, b, c, d, e, ...) e
#define FORC(...)           GET5(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)
#define loop(...)           FORC(__VA_ARGS__)(__VA_ARGS__)
#define all(x)              x.begin(), x.end()
#define rall(x)             x.rbegin(), x.rend()
#define endl                '\n'

// Template -----------------------------------------------------------------

// multiple input
template <typename... T> 
inline void inp(T&... args) {
    ((cin >> args), ...);
}
// scan vector
template <typename T> 
inline istream& operator >>(istream &in, vector<T> &a) {
    for(auto &x : a) in >> x;
    return in;
}
// scan pair
template <typename T, typename U> 
inline istream& operator >>(istream &in, pair<T, U> &a) {
    in >> a.first >> a.second; 
    return in;
}

// Solve --------------------------------------------------------------------

void solve(int &T)
{
    ll n, k;
    cin >> n >> k;
    
    vector<ll> a(n);
    cin >> a;

    map<ll, ll> m;
    m[0] = 1;

    vector<ll> pre(n + 1);
    pre[0] = 0;

    for(ll i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + a[i - 1];
    }

    ll ans = 0;
    ll l = min(n, k - 1);

    for(ll i = 0; i < l; i++)
    {
        ll x = (pre[i + 1] - (i + 1)) % k;
        ans += m[x];
        m[x]++;
    }
    for(ll i = l; i < n; i++)
    {
        ll sm = (pre[i - l] - (i - l)) % k;
        m[sm]--;

        sm = (pre[i + 1] - (i + 1)) % k;
        ans += m[sm];
        m[sm]++;
    }
    cout << ans << endl;
}

// Main ---------------------------------------------------------------------

int main()
{
    #ifdef Dhiraj
        freopen("D:/dhiraj/Programming/i1.txt", "r", stdin);
        freopen("D:/dhiraj/Programming/o1.txt", "w", stdout);
        // freopen("D:/dhiraj/Programming/e1.txt", "w", stderr);
    #endif

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

    int t = 1;
    for(int i = 1; i <= t; i++) {
        cerr << "Case #" << i << "\n";
        solve(i);
    }
    return 0;
}

Measured memory_bytes: 18792
#include <iostream>

using namespace std;

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

    int h, m, s;
    s = S%60;
    m = (S-s)%3600/60;
    h = (S - m*60 -s)/3600;
    cout << h << ":" << m << ":" << s << endl;
    return 0;
}


Measured memory_bytes: 3092
#include <stdio.h>

int main(){

  int N;
  char c1;
  char c2 = '\n';

  while ((c1 = getchar()) != '\n') {
    if(c1 == c2){
      printf("Bad\n");
      return 0;
    }
    c2 = c1;
  }
  printf("Good\n");

  return 0;
}


Measured memory_bytes: 128
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>
#include <map>

typedef long long ll;
#define rep(i, a, n) for(int i = a; i<n; i++)
#define ALL(a) begin(a), end(a)
#define mii map<int, int>
#define msi map<string, int>
#define vi vector<int>
#define vl vector<ll>
#define MOD 1000000007
#define INF 1e9
#define showVector(v) rep(i,0,v.size()){p(v[i]);p(" ")} pl("")
#define p(s) std::cout << s ;
#define pl(s)  std::cout << s << endl;
using namespace std;

// 素数判定 O(√n)
bool is_prime(int n){
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0) return false;
    }
    return true;
}

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

}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main() {
    int K, X;
    cin >> K >> X;
    if (500*K>=X) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define pb push_back
#define INF 1000000005
#define LINF 1000000000000000005

int n,m,x,y,t[100005],dp[100005],ans;

vector <int> g[100005];

queue <int> q;

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> x >> y;
        g[x].pb(y);
        t[y]++;
    }
    for(int i=1;i<=n;i++){
        if(t[i]==0) dp[i]=1,q.push(i);
    }
    while(q.sz){
        int s=q.front();
        q.pop();
        for(int i : g[s]){
            dp[i]=max(dp[i],dp[s]+1);
            t[i]--;
            if(!t[i]) q.push(i);
        }
    }
    for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
    cout << ans-1;
}


Measured memory_bytes: 6528
def num2alpha(num):
    if num<=26:
        return chr(64+num)
    elif num%26==0:
        return num2alpha(num//26-1)+chr(90)
    else:
        return num2alpha(num//26)+chr(64+num%26)

a = int(input())

a1 = str.lower(num2alpha(a))

print(a1)

Measured memory_bytes: 9180
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))

B = [0] * n
m = 100
for i in range(n-1,-1,-1):
    if m < A[i]:
        B[i] = 1
    m = A[i]
# print(B)

ans = 1000
k = 0
for i in range(n):
    if (1 <= i < n-1 and A[i-1] <= A[i] and A[i] >= A[i+1]) or (i == n-1 and A[i-1] <= A[i]):
        ans += k * A[i]
        k = 0
    if (1 <= i < n-1 and A[i-1] >= A[i] and A[i] <= A[i+1]) or (i == 0 and A[i] <= A[i+1]):
        kau = ans // A[i]
        ans -= kau * A[i]
        k += kau
print(ans)

Measured memory_bytes: 61872
using System;
using System.Linq;
using System.Collections.Generic;

namespace ABC134
{
    class D
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var iList = new List<int>();
            var res = new int[N + 1];
            for (int i = N; i > 0; i--)
            {
                var j = 1;
                var sum = 0;
                while (i * j <= N)
                {
                    sum += res[i * j];
                    j++;
                }
                if (sum % 2 != a[i - 1]) { res[i] = 1; iList.Add(i); }
            }

            Console.WriteLine(iList.Count);
            if (iList.Count != 0) Console.WriteLine(string.Join(" ", iList));
        }
    }
}

Measured memory_bytes: 32984
import sys

a = int(sys.stdin.readline())
b = int(sys.stdin.readline())
c = int(sys.stdin.readline())
d = int(sys.stdin.readline())
e = int(sys.stdin.readline())

dishes = [a, b, c, d, e]

min_m = 10
for dish in dishes:
    diff = dish % 10
    if diff > 0:
        min_m = min(min_m, diff)

ans = 0
tmp = -1
for dish in dishes:
    diff = dish % 10
    if min_m != 10 and diff == min_m and tmp == -1:
        tmp = dish
    else:
        if diff:
            ans += dish + 10 - diff
        else:
            ans += dish
tmp = 0 if tmp == -1 else tmp
print(ans + tmp)

Measured memory_bytes: 3064
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner (System.in);
    int x = sc.nextInt();
    int y = sc.nextInt();
    if(x==2){
      System.out.println("No");
    }else if(x==4 || x==6 || x==9 || x==11){
      if(y==4 || y==6 || y==9 || y==11){
        System.out.println("Yes");
      }else{
        System.out.println("No");
      }
    }else if(x==1 || x==3 || x==5 || x==7 || x==8 || x==10 || x==12){
      if(y==1 || y==3 || y==5 || y==7 || y==8 || y==10 || y==12){
        System.out.println("Yes");
      }else{
        System.out.println("No");
      }
    }
  }
}


Measured memory_bytes: 21716
#include<iostream>
using namespace std;
int main(){
  int n=0,k,d,x,count=0;
  cin>>n>>k;
  int a[100]={};
  for(int i=0;i<k;i++){
    cin>>d;
    for(int j=0;j<d;j++){
      cin>>x;
      a[x-1]+=1;
    }
  }
  for(int i=0;i<n;i++){
    if(a[i]==0)
      count+=1;
  }
  cout<<count;
}

Measured memory_bytes: 3608
#include<iostream>

using namespace std;

int main()
{
    int a,b;
    cin >> a>> b;
    
    if(a<b) cout <<  "a < b"  <<endl;
    else if(a>b) cout << "a > b"<<endl;
    else cout << "a == b"<<endl;
    
    return 0;
}


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

int a[100];
int score[100];

int main() {
	int n, m; cin >> n >> m;
	rep(i, m) { cin >> a[i]; a[i]--; }
	rep(i, m) {
		int cnt = 1;
		rep(j, n) {
			int b; cin >> b; b--;
			if (j == a[i])continue;
			if (b == a[i])score[j]++;
			else cnt++;
		}
		score[a[i]] += cnt;
	}
	rep(i, n)cout << score[i] << endl;
	return 0;
}

Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

const int N = 3003;
double dp[N][N];

int main(){
    int n;
    scanf(" %d", &n);
    vector<double> p(n);
    rep(i,n) scanf(" %lf", &p[i]);

    dp[0][0] = 1;
    rep(i,n){
        rep(j,N-1){
            dp[i+1][j+1] += dp[i][j]*p[i];
            dp[i+1][j] += dp[i][j]*(1.0-p[i]);
        }
    }

    double ans = 0;
    rep(i,N){
        if(i > n-i) ans += dp[n][i];
    }
    printf("%.10f\n", ans);
    return 0;
}


Measured memory_bytes: 70656
import math

def main(A, B, N):
    x = min(B-1, N)
    answer = math.floor(A * x / B) - A * math.floor(x / B)
    print(answer)

if __name__ == '__main__':
    A, B, N = list(map(int, input().split()))
    main(A, B, N)


Measured memory_bytes: 9124
#include<bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;  
#define ordered_set tree<ll, null_type , less<ll> , rb_tree_tag , tree_order_statistics_Node_update> 
#define ll long long
#define ull unsigned long long
#define pb push_back
#define inf 1e18
#define mk make_pair
#define ld long double
#define mod 1000000007
#define fi first
#define se second
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test ll t; cin>>t; while(t--)
#define setbits __builtin_popcount
#define endl '\n'
#define LOCAL
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i));}
sim, class b dor(pair < b, c > d) {
    ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
        *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define maxn 100001
ll mark[maxn],sz[maxn],cnt=0;
void init()
{
    for(int i=0;i<maxn;i++)
    {
        mark[i]=i;
        sz[i]=1;
    }
}
ll find(ll x)
{
    if(mark[x]!=x)
    {
        return mark[x]=find(mark[x]);
    }
    return x;
}
void Union(ll x,ll y)
{
    ll val=find(x),val1=find(y);
    if(val==val1)
    {
        return;
    }
    cnt-=sz[val]*sz[val];
    cnt-=sz[val1]*sz[val1];
    sz[val1]+=sz[val];
    cnt+=sz[val1]*sz[val1];
    mark[val]=val1;
}
int main()
{   
    fastIO;
    init();
    ll n,m;
    cin>>n>>m;
    pair<ll,ll>p[m];
    ll x,y,val,val1;
    for(int i=0;i<m;i++)
    {
        cin>>p[i].fi>>p[i].se;
    }
    cnt=n;
    vector<ll>ans(m);
    for(int i=m-1;i>=0;i--)
    {
        val=(n*n-cnt)/2;
        ans[i]=val;
        Union(p[i].fi,p[i].se);
    }
    for(auto itr:ans)
    {
        cout<<itr<<endl;
    }
}

Measured memory_bytes: 7340
n = int(input())

a = []
a_li = input().split()

for i in range(n):
    a.append(int(a_li[i]))
    
ans = "YES"
cnt = 0
cnt2 = 0

for i in range(n):
    if a[i] != i+1:
        cnt2 += 1
        if a[a[i]-1] != i+1:
            cnt += 1
            
    if (cnt >= 1) or (cnt2 >= 3):
        ans = "NO"
        break
    
print(ans)
    

Measured memory_bytes: 3060
import sys
input = sys.stdin.readline
n, kk = map(int,input().split())
C = [list(map(int,input().split())) for i in range(n)]
mod = 10**9 + 7

l = 100
A = [[[0] * n for i in range(n)] for j in range(l)]

for i in range(n):
    for j in range(n):
        if C[i][j] == 1:
            A[0][i][j] = 1

for i in range(1, l):
    for j in range(n):
        for k in range(n):
            for m in range(n):
                A[i][j][m] = (A[i][j][m] + A[i-1][j][k] * A[i-1][k][m]) % mod

# print(A)
ANS = [[0] * n for i in range(n)]
for i in range(n):
    ANS[i][i] = 1

ind = 0
while kk > 0:
    if kk % 2 == 1:
        ANS_NEW = [[0] * n for i in range(n)]
        for j in range(n):
            for k in range(n):
                for m in range(n):
                    ANS_NEW[j][m] = (ANS_NEW[j][m] + ANS[j][k] * A[ind][k][m]) % mod

        for i in range(n):
            for j in range(n):
                ANS[i][j] = ANS_NEW[i][j]
    kk //= 2
    ind += 1
# print(ANS)
ans = 0
for i in range(n):
    ans = (ans + sum(ANS[i])) % mod
print(ans % mod)

Measured memory_bytes: 77028
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    int now = 1;
    int count = 0;
    for(int i = 0; i < N; i++) {
        cin >> a.at(i);
        if(now == a.at(i)) {
            now++;
        } else {
            count++;
        }
    }
    if(now == 1) {
        cout << -1 << endl;
    } else {
        cout << count << endl;
    }
}

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

int main() {
    ll n, a[87] = {0}; cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    ll money = 1000;
    ll cnt = 0;
    for(int i=0; i<n; i++) {
        if(a[i] < a[i + 1]) {
            cnt += money / a[i];
            ll num = money / a[i];
            money -= a[i] * num;
        }
        else {
            money += cnt * a[i];
            cnt = 0;
        }
    }
    cout << money << endl;
}

Measured memory_bytes: 3608
import networkx as nx

int1 = lambda x: int(x) - 1
MOD = 10 ** 9 + 7

N, K = map(int, input().split())

G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from([tuple(map(int1, input().split())) for _ in range(N - 1)])

deg = nx.degree(G)
ans = K
for i in range(deg[0]):
    ans = (ans * (K - i - 1)) % MOD

for parent, child in nx.dfs_edges(G, 0):
    for i in range(deg[child] - 1):
        ans = (ans * (K - i - 2)) % MOD

print(ans)


Measured memory_bytes: 163604
#include <bits/stdc++.h>
#define int long long
using namespace std;
int ceil(int x, int y){
    if (x % y == 0) return x/y;
    else return x/y+1;
}
main(){
    int n;
    scanf("%lld",&n);
    int cura = 0, curb = 0;
    scanf("%lld%lld",&cura,&curb);
    for (int i = 1; i < n; i++){
        //printf("%d %d\n",cura,curb);
        int a,b;
        scanf("%lld%lld",&a,&b);
        int ka = ceil(cura,a) * a;
        int kb = ka/a*b;
        int pb = ceil(curb,b) * b;
        int pa = pb/b*a;
        //printf("%d %d vs %d %d\n",pa,pb,ka,kb);
        if (kb >= curb){
            if (pa >= cura){
                if (pa < ka){
                    cura = pa;
                    curb = pb;
                }
                else{
                    curb = kb;
                    cura = ka;
                }
            }
            else{
                curb = kb;
                cura = ka;
            }
        }
        else{
            curb = pb;
            cura = pa;
        }
    }
    printf("%lld",cura+curb);
}


Measured memory_bytes: 256