akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const double EPS = 1e-8;
const double INF = 1e12;
const double PI = 3.1415926535;
typedef complex<double> P;
namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
  return real(conj(a)*b);
}

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};

struct C {
  P p; double r;
  C(const P &p, double r) : p(p), r(r) { }
  C() {}
};

P rotate(P p, double ang) {
  return P(real(p)*cos(ang)-imag(p)*sin(ang),
           real(p)*sin(ang)+imag(p)*cos(ang));
}
L rotate(L l, double ang) {
  return L(rotate(l[0], ang),rotate(l[1], ang));
}

vector<L> tanPairCircles(C c1, C c2) {
  vector<L> res;
  P d = c2.p-c1.p;
  P hoge = c1.r/(c1.r+c2.r)*d; // p1->ツ静堋静シツづ個古ーツ点
  P p = c1.p+hoge; // ツ静堋静シツづ個古ーツ点
  double ang = asin(c1.r/abs(hoge));
  res.push_back(L(p,p+rotate(-hoge, ang)));
  res.push_back(L(p,p+rotate(-hoge, -ang)));

  if (c1.r == c2.r) {
    P p1 = c1.p + rotate(d*c1.r/abs(d), PI/2);
    P p2 = c1.p + rotate(d*c1.r/abs(d), -PI/2);
    res.push_back(L(p1,p1+d));
    res.push_back(L(p2,p2+d));
  } else {
    if (c1.r<c2.r) swap(c1,c2);
    hoge = c1.r/(c1.r-c2.r)*d; // p1->ツ静堋静シツづ個古ーツ点
    p = c1.p+hoge; // ツ静堋静シツづ個古ーツ点
    ang = asin(c1.r/abs(hoge));
    res.push_back(L(p,p+rotate(-hoge, ang)));
    res.push_back(L(p,p+rotate(-hoge, -ang)));
  }
  return res;
}

P projection(const L &l, const P &p) {
  double t = dot(p-l[0], l[0]-l[1]) / norm(l[0]-l[1]);
  return l[0] + t*(l[0]-l[1]);
}
double distanceLP(const L &l, const P &p) {
  return abs(p - projection(l, p));
}

int main() {
  int n;
  while(cin >> n, n) {
    C c[2*n];
    double d[n];

    REP(i,n) {
      double x,y,r;
      cin >> x>>y>>r>>d[i];
      c[i] = C(P(x,y),r);
    }
    if (n==1) {
      cout << 1 << endl;
      continue;
    }
    REP(i,n) {
      c[n+i] = C(c[i].p, c[i].r+d[i]);
    }
    int ans = 0;
    REP(i,2*n-1) {
      for (int j=i+1;j<2*n;++j) {
        vector<L> v = tanPairCircles(c[i],c[j]);
        FOR(it, v) {
          L l = *it;
          int tmp = 0;
          REP(k,n) {
            if (distanceLP(l, c[k].p) < d[k]+c[k].r+EPS && distanceLP(l, c[k].p) > c[k].r - EPS)
              tmp++;
          }
          ans = max(ans, tmp);
        }
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 1004
# -*- coding: utf-8 -*-
"""
Created on Sun May  3 11:14:35 2020

@author: ab
"""
import math
import sys
input = sys.stdin
output = sys.stdout
while True:
    lineElements = input.readline().rstrip("/n").split(" ")
    if(lineElements[0] == ''):
        break;
    a,b,n = lineElements
    a,b,n = int(a),int(b),int(n)
    if n==1:
        x = 0
    elif n<b-1:
        x = n
    else:
        x = b-1
    result = math.floor((a*x)/b)-a*math.floor(x/b)
    print(str(result)+'\n')
    

Measured memory_bytes: 9184
#include <bits/stdc++.h>
using namespace std;
#define REP(i,b,e) for(int i=(b);i<(e);++i)
#define RREP(i,b,e) for(int i=(b)-1;i>=e;--i)
#define rep(i,e) for(int i=0;i<(e);++i)

inline void print(void) { cout<<'\n'; }
template<class T> inline void print(const T &x) { cout<<x<<'\n'; }
template<class T, class... U> inline void print(const T &x, const U&... y) { cout<<x<<" "; print(y...); }

int main() {
  int n; long long k; cin>>n>>k;
  vector<vector<int>> b(45, vector<int>(2, 0));
  rep(i, n) {
    long long a; cin>>a;
    rep(j, 45) ++b[j][(a>>j) & 1];
  }

  long long dp[45][2];
  rep(i, 45) rep(j, 2) dp[i][j] = -1;
  dp[44][0] = 0;

  RREP(i, 44, 0) {
    long long mask = (1LL<<i);
    if (dp[i+1][0] != -1) {
      if (k & (1LL<<i)) {
        dp[i][0] = max(dp[i][0], dp[i+1][0] + mask * b[i][0]);
        dp[i][1] = max(dp[i][1], dp[i+1][0] + mask * b[i][1]);
      } else {
        dp[i][0] = max(dp[i][0], dp[i+1][0] + mask * b[i][1]);
      }
    }
    if (dp[i+1][1] != -1) {
      dp[i][1] = max(dp[i][1], dp[i+1][1] + mask * (max(b[i][0], b[i][1])));
    }
  }
  print(max(dp[0][0], dp[0][1]));

  return 0;
}

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

using namespace std;

// Rooted Trees
// 左手右兄弟表現
// 二重連鎖木(Double chained tree)
//
//

static const int N = 100000;
static const int NIL = -1;

// 二分木のノード
struct Node
{
    int parent;
    int left;
    int right;
};
struct Node T[N];
int D[N];

// ノードの深さを求める
// 頂点uの深さをD[u]で保持する。つまり、D[頂点]配列を見ると、
// 自分の深さが分かり、最大値を調べると最も深い部分もわかる。
void setDepth(int u, int parent)
{
   D[u] = parent;
   if (T[u].right != NIL) setDepth(T[u].right, parent);
   if (T[u].left != NIL) setDepth(T[u].left, parent + 1);
}

void printNode(int u)
{
    cout << "node " << u << ": ";
    cout << "parent = " << T[u].parent << ", ";
    cout << "depth = " << D[u] << ", ";

    if (T[u].parent == NIL) cout << "root, ";
    else if (T[u].left == NIL) cout << "leaf, ";
    else cout << "internal node, ";

    cout << "[";
    for (int i = 0, child = T[u].left; child != NIL; i++, child = T[child].right)
    {
        if (i) cout << ", ";
        cout << child;
    }

    cout << "]" << endl;
}


int main(int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);



    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        T[i].left = NIL;
        T[i].right = NIL;
        T[i].parent = NIL;
    }

    // 多分木を二分木(二重連鎖木(Double chained tree))で、データ保持する
    for (int i = 0; i < n; i++)
    {
        int nodeId, k;
        int prevChild;
        cin >> nodeId >> k;
        for (int j = 0; j < k; j++)
        {
            int child;
            cin >> child;
            // 左子右兄弟表現.もっとも左が子で、そこに兄弟を繋げる。
            if (j == 0) T[nodeId].left = child;
            else T[prevChild].right = child;

            T[child].parent = nodeId;

            prevChild = child;
        }
    }

    int rootNode;
    for (int i = 0; i < n; i++)
    {
        if (T[i].parent == NIL)
        {
            rootNode = i;
            break;
        }
    }

    setDepth(rootNode, 0);

    for (int i = 0; i < n; i++)
        printNode(i);

    return 0;
}


Measured memory_bytes: 7864
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
 
//const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
 
int main()
{
	int h, w;
	cin >> h >> w;
	int ans[h][w];
	string c[h];
	REP(i, h) cin >> c[i];

	REP(i, h){
		bool flag = 0;
		int count = 0;
		REP(j, w){
			if (c[i][j] == 'c'){
				flag = 1;
				count = 0;
			}
			if (flag){
				ans[i][j] = count;
				count++;
			}
			else {
				ans[i][j] = -1;
			}

		}
	}

	REP(i, h){
		REP(j, w){
			if (j < w-1) cout << ans[i][j] << " ";
			else cout << ans[i][j];
		}
		cout << endl;
	}
}



Measured memory_bytes: 3264
n = int(input())
parent = [-1 for i in range(n)]
depth = [-1 for i in range(n)]
G = [[] for i in range(n)]
for _ in range(n):
    cin = input().split()
    id, k = int(cin[0]), int(cin[1])
    children = list(map(int, cin[2:]))
    G[id] = children
    for child in children:
        parent[child] = id
for i in range(n):
    if parent[i] == -1:
        depth[i] = 0
        que = [i]
        while len(que) > 0:
            r = que.pop()
            for child in G[r]:
                depth[child] = depth[r] + 1
                que.append(child)
        break
for i in range(n):
    T = ''
    if parent[i] == -1:
        T = 'root'
    elif len(G[i]) == 0:
        T = 'leaf'
    else:
        T = 'internal node'
    print(f'node {i}: parent = {parent[i]}, depth = {depth[i]}, {T}, {G[i]}')


Measured memory_bytes: 25696
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>
#include<set>
#include<bitset>
#include<cassert>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

ll a, b, c, d;

int main() {
	cin >> a >> b >> c >> d;
	if ((c + b - 1) / b <= (a + d - 1) / d) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 3620
n, m, X, Y = map(int, input().split(' '))
x = list(map(int, input().split(' ')))
y = list(map(int, input().split(' ')))
x.append(X)
y.append(Y)
x.sort()
y.sort()
if x[-1] < y[0]:
    print('No War')
else:
    print('War')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int n,w[N],b[N],x;//w[x] 编号x的位置. 
int dp[N][N],cw[N][N],cb[N][N];
int main()
{
	memset(cw,0,sizeof(cw));
	memset(cb,0,sizeof(cb));
	scanf("%d",&n);
	for(int i=1;i<=2*n;i++)
	{
		char op[2];
		scanf("%s%d",op,&x);
		if(op[0]=='W')
			w[x]=i;
		else
			b[x]=i;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<i;j++)
			if(w[i]<w[j])
				cw[i][0]++;
		for(int j=1;j<=n;j++)
		{
			cw[i][j]=cw[i][j-1];
			if(w[i]<b[j])
				cw[i][j]++;	
		}
	}	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<i;j++)	
			if(b[i]<b[j])
				cb[0][i]++;
		for(int j=1;j<=n;j++)
		{
			cb[j][i]=cb[j-1][i];
			if(b[i]<w[j])
				cb[j][i]++;
		}
	}
	int c1=0,c2=0;
	for(int i=1;i<=n;i++)
	{
		c1+=cw[i][0],c2+=cb[0][i];
		dp[i][0]=c1,dp[0][i]=c2;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dp[i][j]=min(dp[i-1][j]+cw[i][j],dp[i][j-1]+cb[i][j]);	
	cout<<dp[n][n]<<'\n';
	return 0;
}


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

int main() {
  int n,k,min = 100000,s = 0;
  cin >> n >> k;
  vector<int>data(n);
  for(int i = 0;i < n;i++){
    cin >> data.at(i);
    if(data.at(i) < min){
      min = data.at(i);
    }
  }
  for(int i = 0;i < n;i++){
    if(data.at(i) == min) s++;
  }
  if((n-s)%(k-1) == 0) cout << (n-s)/(k-1) << endl;
  else cout << (n-s)/(k-1)+1 << endl;
}


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

int main() {
	ll n,k,j,p;
	cin >> n >> k;
	set<int> s;
	for(int i=0;i<k;i++)
	{
		cin >> j;
		for(int l=0;l<j;l++)
		{
			cin >> p;
			s.insert(p);
		}
	}
	cout << n- s.size();
	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
#define itn int
#define all(c) c.begin(),c.end()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
#define ll long long
#define ull unsigned long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
using namespace std;
 
const ll MAX_N = 2e5 + 5, inf = 1e18, mod = 1000000007;
const double PI = 3.1415926536;
int days[13] = {0, 31, 28, 31, 30, 31,30, 31, 31, 30, 31, 30, 31};
 
template<typename T>
ostream& operator <<(ostream& out, const vector<T>& mas) {
    for (const auto& x : mas) {
        out << x << ' ';
    }
    return out;
}
 
void ok() {
    cout << "OK" << '\n';
}
 
void no() {
    cout << "NG" << '\n';
}
 
inline ll nxt() {
    ll x;
    cin >> x;
    return x;
} 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    ll n = nxt();
    vector<pair<ll, ll>> buf;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                cnt++;
                n /= i;
            }
            buf.push_back({i, cnt});
        }
    }
    if (n > 1) {
        buf.push_back({n, 1});
    }

    int ans = 0;
    for (int i = 0; i < buf.size(); i++) {
        int cur = 1;
        while (cur <= buf[i].second) {
            buf[i].second -= cur;
            cur++;
        }
        ans += cur - 1;
    }
    cout << ans;
    return 0;

}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<N;i++)
#define p(S) cout<<S<<endl
using namespace std;
int allh[1500010],allw[1500010];
int main(){
	int N,M;
	while(cin>>N>>M&&N){
		int h[1501],w[1501];
		REP(i,0,1500010) allh[i]=allw[i]=0;
		int ans=0,k;
		REP(i,0,N){
			cin>>h[i];
			k=0;
			for(int j=i;j>=0;j--){
				k+=h[j];
				allh[k]++;
			}
		}
		REP(i,0,M){
			cin>>w[i];
			k=0;
			for(int j=i;j>=0;j--){
				k+=w[j];
				allw[k]++;
			}
		}
		REP(i,0,1500010){
			ans+=allh[i]*allw[i];
		}
		p(ans);
	}

	return 0;
}

Measured memory_bytes: 14708
#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)
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
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 main()
{
cin.tie(0);
ios::sync_with_stdio(false);

string s,t;
cin >> s >> t;

// dp[i+1][j+1]:= s[i]までとt[j]までの最長共通部分列の長さ
vvi dp(s.size()+1,vi(t.size()+1,0));

for(int i = 0; i < s.size(); ++i) {
    for(int j = 0; j < t.size(); ++j) {
        if(s[i] == t[j]) dp[i+1][j+1] = dp[i][j]+1;
        else dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
    }
}

// 復元
string ans = "";
int i = s.size(); int j = t.size();
while(i > 0 && j > 0) {
    if(dp[i][j-1] == dp[i][j]) --j;
    else if(dp[i-1][j] == dp[i][j]) --i;
    else {
        ans = s[i-1] + ans;
        --i;--j;
    }
}
cout << ans << endl;
return 0;
}

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


int main(void){
    string s; cin >> s;
    string d = "";
    rep(i,5){
        d+="hi";
        if(s==d){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}


Measured memory_bytes: 256
/*
  B - Between a and b ...
  <http://abc048.contest.atcoder.jp/tasks/abc048_b>
  [Tips]
  ・変数の範囲に注意<http://seclan.dll.jp/c99d/c99d05.htm>
*/

#include <stdio.h>

typedef long long int int64_t;

int main(int argc, char const *argv[]) {

  int64_t a, b, x;

  if( scanf("%lld %lld %lld", &a, &b, &x) != EOF ){
    fprintf(stderr, "scanf ERROR!\n");
  }

  printf("%lld\n", (b/x) - ( a!=0 ? (a-1)/x : -1) );

  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

#define XAXIS 10
#define YAXIS 10

int main(){
	int paper[XAXIS][YAXIS];
	int x,y,s;
	int white = 0, most=0;

	for(int i=0; i<XAXIS; i++)
	for(int j=0; j<YAXIS; j++)
		paper[i][j] = 0;

	while(scanf("%d,%d,%d", &x, &y, &s) != EOF){
		switch(s){
			case 3:
				if(x+2 <  XAXIS) paper[x+2][y] += 1;
				if(y+2 <  YAXIS) paper[x][y+2] += 1;
				if(x-2 >= 0)     paper[x-2][y] += 1;
				if(y-2 >= 0)     paper[x][y-2] += 1;

			case 2:
				if(x+1 <  XAXIS && y+1 < YAXIS )  paper[x+1][y+1] += 1;
				if(x+1 <  XAXIS && y-1 >= 0)       paper[x+1][y-1] += 1;
				if(x-1 >= 0     && y+1 < YAXIS )  paper[x-1][y+1] += 1;
				if(x-1 >= 0     && y-1 >= 0)       paper[x-1][y-1] += 1;

			case 1:
				if(x+1 <  XAXIS) paper[x+1][y] += 1;
				if(y+1 <  YAXIS) paper[x][y+1] += 1;
				if(x-1 >= 0)     paper[x-1][y] += 1;
				if(y-1 >= 0)     paper[x][y-1] += 1;
				paper[x][y] += 1;
				break;
		}
	}

	for(int i=0; i<XAXIS; i++)
	for(int j=0; j<YAXIS; j++){
		if(paper[i][j] == 0 )  white++;
		most = max(most,paper[i][j]);
	}

	cout<<white<<endl<<most<<endl;
	return 0;
}

Measured memory_bytes: 1208
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cstring>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
 
int MOD = 1000000007;

int main() {
	int n; cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	reverse(a.begin(), a.end());
	for (int i = 0; i < n; i++)
		cout << a[i] << (i < n - 1 ? ' ' : '\n');
}

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

typedef long long ll;
#define BR "\n"
#define SP " "
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << SP; } cout << BR;
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << BR;

const ll MOD = 1e9 + 7;

ll p(ll n, ll k) {
  if (n == 0) return 1;
  if (n == 1) return k;

  ll temp = p(n / 2, k) % MOD;
  temp = (temp * temp) % MOD;

  if (n % 2) {
    return (k * temp) % MOD;
  } else {
    return temp;
  }
  return 0;
}

int main() {
  ll n, k;
  cin >> n >> k;

  cout << p(n, k) << "\n";
  return 0;
}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n,k,t,ans;
  cin >> n >> k;
  
  t = n % k;
  if(t > k-t){
  	ans = k-t;
  }
  else{
  	ans = t;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;

@SuppressWarnings("unchecked")
public class Main {
	// public static void printArray(int[] a) {
	// 	for (int i = 0; i < a.length; i++) {
	// 		System.out.print(a[i] + ", ");
	// 	}
	// 	System.out.println();
	// }

	// public static<T> void printArrayT(T[] a) {
	// 	for (int i = 0; i < a.length; i++) {
	// 		System.out.print(a[i] + ", ");
	// 	}
	// 	System.out.println();
	// }

	public static String joinInt(int[] a, String separator) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < a.length; i++) {
			if (i > 0) {
				sb.append(separator);
			}
			sb.append(a[i]);
		}
		return sb.toString();		
	}

	static int[] nextIntArray(Scanner sc, int N) {
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		return arr;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		double[] P = new double[N];
		for (int i = 0; i < N; i++) {
			P[i] = sc.nextDouble();
		}
		double[] dist = { 1.0 };
		for (int i = 0; i < N; i++) {
			double p = P[i];
			double[] next = new double[i + 2];
			for (int j = 0; j <= i; j++) {
				next[j] = dist[j] * p;
			}
			double p1 = 1 - p;
			for (int j = 0; j <= i; j++) {
				next[j + 1] += dist[j] * p1;
			}
			dist = next;
		}
		// 1 -> 1
		// 2 -> 2
		// 3 -> 3, 2
		// 4 -> 4, 3
		// 5 -> 5, 4, 3
		int lim = (N + 1) / 2;
		double sum = 0;
		for (int i = 0; i < lim; i++) {
			sum += dist[i];
		}
		System.out.println(sum);
	}
}


Measured memory_bytes: 48300
#include<bits/stdc++.h>
#define  int long long
using namespace std;


int32_t main()
{
    int T;
    T = 1;
    while (T--)
    {
        int N,K,tmp,cnt=0;
        cin>>N>>K;
        for(int i=0; i<N; i++)
        {
            cin>>tmp;
            if(tmp >= K)
                ++cnt;
        }
        cout<<cnt;

    }
}

Measured memory_bytes: 384
from heapq import heappush, heappop

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
V = set()

que = [(-(A[0] + B[0] + C[0]), 0, 0, 0)]
V.add((0, 0, 0))
ans = []
for _ in range(K):
    val, a, b, c = heappop(que)
    ans.append(-val)

    for x, y, z in [(0, 0, 1), (0, 1, 0), (1, 0, 0)]:
        x = min(a + x, X - 1)
        y = min(b + y, Y - 1)
        z = min(c + z, Z - 1)
        if not (x, y, z) in V:
            heappush(que, (-(A[x] + B[y] + C[z]), x, y, z))
            V.add((x, y, z))

print(*ans, sep='\n')

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

void call(int n){
  for(int i=1;i<=n;i++){
    int x = i;
    if(x % 3 == 0) cout << ' ' << x;
    else {
      while(x){
        if(x % 10 == 3){
          cout << ' ' << i;
          break;
        }
        x /= 10;
      }
    }
  }
  cout << endl;
}

int main(){
  int n;
  while(cin >> n) call(n);
}

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

int main(void) {
  int N;
  cin >> N;
  long long ans = 0;
  for (int i = 1; i <= N; i++) {
    if (i % 3 != 0 && i % 5 != 0) ans += i;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3592
#include <stdio.h>
int main(void)
{
	int n, x, i, j, k, c;
	while(scanf("%d%d", &n, &x), (0 != n) || (0 != x)){
		c=0;
		for(i=1; i<=n; i++){
			for(j=i+1; j<=n; j++){
				for(k=j+1; k<=n; k++){
					if(x == i+j+k){
						c++;
					}
				}
			}
		}
		printf("%d\n", c);
	}
	return 0;
}

Measured memory_bytes: 600
s = input()
a = int(s[0])
b = int(s[1])
c = int(s[2])
d = int(s[3])
pm = '+-'
for i in range(2):
  for j in range(2):
    for k in range(2):
      if i == 0:
        temp = a + b
      else:
        temp = a - b
      if j == 0:
        temp += c
      else:
        temp -= c
      if k == 0:
        temp += d
      else:
        temp -= d
      if temp == 7:
        print(s[0] + pm[i] + s[1] + pm[j] + s[2] + pm[k] + s[3] + '=7')
        exit()

Measured memory_bytes: 9176
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]
L = sorted(L, key=lambda x: x[1])
tmp = L[0][1]

ans = 1

for a, b in L:
    if a < tmp <= b:
        continue
    else:
        ans += 1
        tmp = b
print(ans)




Measured memory_bytes: 31960
#include<cstdio>
#include<cctype>

int main(){
    char ch;
    int counter[26]={};
    
    while(scanf("%c",&ch) !=EOF){
        if(isalpha(ch)){
            if(isupper(ch)){
                ch = tolower(ch);
            }
        int num = ch -'a';
        counter[num]++;
        }
    }
    for(int i =0;i<26;i++){
        printf ("%c : %d\n",i+'a', counter[i]) ;
    }
    return 0;
}


Measured memory_bytes: 2744
#define _USE_MATH_DEFINES // M_PI
#include<cmath>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define rREP(i,a,n) for(int (i)=(n)-1; (i)>=(a);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 2147483647;
constexpr ll mod = 1000000007;

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;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

template<class T> T pow(T a, T b) {
	if (b == 0)return 1;
	if (b % 2) {
		T ret = pow(a, (b - 1) / 2);
		return ret * ret * a;
	}
	else {
		T ret = pow(a, b / 2);
		return ret * ret;
	}
}
int main() {
	init();

	ll H; cin >> H;
	ll p = (ll)log2(H);
	ll ans = pow(2LL, p) * 2LL - 1LL;
	cout << ans << "\n";

	return 0;
}

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

int main(){
    int64_t N,M,K;
    cin >> N >> M >> K;
    vector<int64_t> A(N);
    vector<int64_t> B(M);
    for(int i=0; i<N; i++){
        cin >> A.at(i);
    }
    for(int i=0; i<M; i++){
        cin >> B.at(i);
    }
    /*
    //int64_t ans = 0;
    int64_t a_i = 0;
    int64_t b_i = 0;
    while(K >= 0){
        if(a_i == N && b_i == M) break;
        if(a_i == N){
            if(K < B.at(b_i)) break;
            //ans++;
            K -= B.at(b_i);
            b_i++;
        }
        else if(b_i == M){
            if(K < A.at(a_i)) break;
            //ans++;
            K -= A.at(a_i);
            a_i++;
        }
        else if(A.at(a_i) < B.at(b_i)){
            if(K < A.at(a_i)) break;
            //ans++;
            K -= A.at(a_i);
            a_i++;
        }
        else{
            if(K < B.at(b_i)) break;
            //ans++;
            K -= B.at(b_i);
            b_i++;
        }
    }
    cout << a_i+b_i << endl;
    */
   int64_t max_A = 0;
   int64_t time = 0;
   while(K >= time){
       if(max_A == N) break;
       if(K-time >= A.at(max_A)){
           time += A.at(max_A);
           max_A++;
       }
       else break;
   }
   int64_t max_B = 0;
   while(K >= time){
       if(max_B == M) break;
       if(K-time >= B.at(max_B)){
           time += B.at(max_B);
           max_B++;   
        }
        else break;
    }
    int64_t ans = max_A + max_B;
    while(max_A>=1 && max_B < M){
        max_A--;
        time -= A.at(max_A);
        while(K >= time){
            if(max_B == M) break;
            if(K-time >= B.at(max_B)){
                time += B.at(max_B);
                max_B++;
            }
            else break;
        }
        ans = max(ans, max_A+max_B);
    }
    cout << ans << endl;
}

Measured memory_bytes: 6412
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_A&lang=jp
def diameter(N, E, D):#diamete of a tree
    from collections import deque
    V = [-1]*N
    V[0] = 0
    q = deque([0])
    while q:
        v = q.popleft()
        for w in E[v]:
            if V[w] == -1:
                V[w] = V[v] + D[(v,w)]
                q.append(w)
    s = V.index( max(V))
    p = deque([s])
    W = [-1]*N
    W[s] = 0
    while p:
        v = p.popleft()
        for w in E[v]:
            if W[w] == -1:
                W[w] = W[v] + D[(v,w)]
                p.append(w)
    return max(W)

from collections import defaultdict
N = int( input())
E = [ [] for _ in range(N)]
D = defaultdict( int)
for _ in range(N-1):
    a, b, w = map( int, input().split())
    E[a].append(b)
    E[b].append(a)
    D[(a,b)] = D[(b,a)] = w
print( diameter( N, E, D))


Measured memory_bytes: 56068
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) {
		FastScanner fs=new FastScanner();
		int n=fs.nextInt();
		int[] ans=new int[n+1];
		for (int a=1; a<101; a++) {
			for (int b=1; b<101; b++) {
				for (int c=1; c<101; c++) {
					int val=a*a+b*b+c*c+a*b+a*c+b*c;
					if (val>n) continue;
					ans[val]++;
				}
			}
		}
		for (int i=1; i<=n; i++) System.out.println(ans[i]);
	}

	static void sort(int[] a) {
		ArrayList<Integer> l=new ArrayList<>();
		for (int i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}
	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}

	
}


Measured memory_bytes: 35884
fun main(args: Array<String>) {
    val (N, D) = readLine()!!.split(" ").map(String::toInt)
    val X = Array(N) { readLine()!!.split(" ").map(String::toInt) }
    var ans = 0
    for (i in 0 until N) {
        for (j in i + 1 until N) {
            val d = X[i].zip(X[j]).map { Math.pow(it.first - it.second.toDouble(), 2.0) }.sum()
            if (d.isSquare()) ans++
        }
    }
    println(ans)
}

fun Double.isSquare(): Boolean {
    val s = Math.sqrt(this)
    return s == Math.round(s).toDouble()
}

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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    int N, L, R;
    vector<int> ans;
    while(true){
        int res = 0;
        cin >> N >> L >> R;
        if(N == 0) break;
        vector<int> A(N);
        rep(i, N) cin >> A[i];
        for(int i = L; i <= R; i++){
            int idx = 0;
            while(i % A[idx] > 0){
                idx++;
                if(idx == N) break;
            }
            if(idx == N){
                if(N % 2 == 0) res++;
            }
            else if(idx % 2 == 0) res++;
        }
        ans.push_back(res);
    }
    rep(i, ans.size()) cout << ans[i] << endl;
    return 0;
}


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

void dfs(string now, vector<string> &vec,ll d){
    if(now.length()==n){
        vec.push_back(now);
        return;
    }
    for(ll i=0;i<=d;i++){
        string next=now+char('a'+i);
        ll m=d;
        if(i==d) m++;
        dfs(next,vec,m);
    }
}
int main() {
    cin >> n;
    vector<string>ans;
    dfs("a",ans,1);
    for(ll i=0;i<ans.size();i++){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 7300
#include <bits/stdc++.h>
#include <random>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using Pt = pair<int, int>;

int main()
{
	string S;
	cin >> S;
	int r = 0;
	int ans = 0;
	for (int i = 0; i < 3; ++i)
	{
		if (S[i] == 'R')
		{
			++r;
		}
		else
		{
			ans = max(r, ans);
			r = 0;
		}
	}
	ans = max(r, ans);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3592
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>

#define TRACE(x) std::cout << #x << " = " << x << "\n"
#define _ << " _ " <<

using namespace std;
using i64 = int64_t;

int64_t f(int64_t N, int64_t A, int64_t B) {
  if (A % 2 == B % 2) {
    return (B - A) / 2;
  }
  if (A > B) swap(A, B);
  if (N - B - 1 < A) {
    A = N - A - 1;
    B = N - B - 1;
    swap(A, B);
  }
  return A + 1 + (B - (A + 1)) / 2;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  int64_t N, A, B;
  cin >> N >> A >> B;
  --A, --B;

  cout << f(N, A, B) << '\n';
  return 0;
}


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

int main()
{
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	int ans=0;
	if(k<a)
		cout<<k<<"\n";
	else if(k<a+b)
		cout<<a<<"\n";
	else if(k<a+b+c)
	{
		k=k-a-b;
		cout<<a-k<<"\n";

	}
	else
	{
		cout<<a-c<<"\n";
	}
	
	


}

Measured memory_bytes: 3612
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
char s[200005];
int f[200005];
int main(){
	// freopen("b.in","r",stdin);
	int n,m;
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	if(s[1]=='B')
		for(int i=1;i<=m;i++)s[i]=(s[i]=='R'?'B':'R');
	int lst=0,k=n&1?n-2:n-1;
	for(int i=1;i<=m;i++){
		if(s[i]=='B'){
			if(lst!=i-1){
				if(!lst){
					if((i-lst-1)&1)k=min(k,i-lst-1);
					else k=min(k,i-lst-1+1);
				}
				if((i-lst-1)&1)k=min(k,i-lst-1);
			}
			lst=i;
		}
	}
	if(!lst){
		int ans=2;
		f[1]=1;
		for(int i=2;i<=n;i++){
			f[i]=(f[i-1]+f[i-2])%mod;
			if(i!=n)ans=(ans+f[i])%mod;
			else ans=(ans+f[i-1])%mod;
		}
		// puts("ok");
		printf("%d\n",ans);
		return 0;
	}
	k++;
	f[1]=f[3]=1;
	for(int i=5;i<=n;i+=2)f[i]=(2ll*f[i-2]+(i>=k+2?mod-f[i-k-2]:0))%mod;	
	int ans=0;
	for(int i=1;i<=min(n,k);i++)if(i&1)ans=(ans+1ll*f[n-i]*(i+1))%mod;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1152
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <cstdlib>
#include <memory>
#include <queue>
#include <cassert>
#include <cmath>
#include <ctime>
#include <complex>
#include <bitset>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <numeric>

using namespace std;

#define ws ws_____________________
#define y1 y1_____________________
#define y0 y0_____________________
#define left left_________________
#define right right_______________
#define next next_________________
#define prev prev_________________
#define hash hash_________________

#define pb push_back
#define fst first
#define snd second
#define mp make_pair 
#define sz(C) ((int) (C).size())
#define forn(i, n) for (int i = 0; i < (int) n; ++i)
#define ford(i, n) for (int i = ((int) n) - 1; i >= 0; --i)
#define all(C) begin(C), end(C)

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef long double ld;
typedef complex<double> cd;

#define FILE_NAME "a"

const int MAXN = 1e5 + 10;

int i, o, t, j, l, s, z;

bool read() {
	if  (!(cin >> i >> o >> t >> j >> l >> s >> z)) {
		return 0;
	}
	return 1;
}

ll solve2() {
	ll ans = 0;

	ans += (i / 2) * 2;

	ans += o;

	ans += (j / 2) * 2;

	ans += (l / 2) * 2;

	return ans;
}

ll solve() {		
	ll ans = solve2();
	if (i > 0 && j > 0 && l > 0) {
		--i;
		--j;
		--l;
		ans = max(ans, 3 + solve2());
	}
	return ans;
}

int main() {
#ifdef LOCAL
	freopen(FILE_NAME ".in", "r", stdin);
	// freopen(FILE_NAME ".out", "w", stdout);
#endif

	while (read()) {
		cout << solve() << endl;
	}

#ifdef LOCAL
	cerr.precision(5);
	cerr << "Time: " << fixed << (double) clock() / CLOCKS_PER_SEC << endl;
#endif
	return 0;
}


Measured memory_bytes: 256
#include <iostream> // cin, cout, cerr, clog
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota, accumulate, inner_product
#include <cstdio> // printf, scanf
#include <climits> // INT_MIN, LLONG_MIN
#include <cmath> // long, trig, pow
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <stack> // stack
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <unordered_map> // hashed by keys
#include <unordered_set> // hashed by keys
#include <iomanip> // cout<<setprecision(n)
#include <functional> // std::function<void(int)>

#define rep(i,n) for(int i = 0; i < n; i++)
#define ENDL "\n"
#define print(i) std::cout << (i) << "\n"

#define int long long // at least int64 > 9*10^18
#define all(v) v.begin(), v.end()

signed main() {
	int n;
	std::cin >> n;
	std::vector<int> a(n);
	std::vector<int> b(n);
	std::vector<int> c(n);
	rep(i,n) std::cin >> a[i];
	rep(i,n) std::cin >> b[i];
	rep(i,n) std::cin >> c[i];
	std::sort(all(a));
	std::sort(all(b));
	std::sort(all(c));

	std::vector<int> bc(n,0);
	rep(i,n) {
		bc[i] = c.end() - std::upper_bound(all(c),b[i]);
	}

	std::vector<int> dp(n,0);
	{
		int accum = 0;
		for(int i=n-1;i>=0;i--) {
			accum += bc[i];
			dp[i] = accum;
		}
	}

	int count = 0;
	rep(i,n) {
		count += dp[(std::upper_bound(all(b),a[i]) - b.begin())];
	}
	print(count);
	return 0;
}


Measured memory_bytes: 4224
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=sum(b)
for i in range(n-1):
    if a[i]==a[i+1]-1:
        ans+=c[a[i]-1]
print(ans)

Measured memory_bytes: 3064
#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 <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<cmath>
#include<limits>
#define ll long long
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int_INF 2147483647
#define pint_INF 2000000000
#define ll_INF 	9223372036854775807
#define MOD 1000000007
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define vvc vector<vector<char>>
#define vll vector<long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define sysp system("PAUSE")
#define pno cout << "no" << endl
#define pyes cout << "yes" << endl
#define pYes cout << "Yes" << endl
#define pNo cout << "No" << endl
using namespace std;
int N, K;
vector<int> accumulative_form_alize(vector<int> v) {
    vi res(N+2);
    for (int i = 1; i < N+1; i++) {
            int l = max(0, i - v[i]);
            int r = min(N + 1, i + v[i]+1);

            res[l]++;
            res[r]--;
    }
    return res;
}

vector<int> Sum_form_alize(vi v) {//input is acc form
    vi res(N + 2);
    res[0] = v[0];

    for (int i = 1; i < N+1; i++) {
        res[i] = res[i - 1] + v[i];
    }
    res[0] = 0;
    res[N + 1] = 0;
    return res;
}

vi next(vi v) {// input is sum form
    vi v1 = accumulative_form_alize(v);
    return Sum_form_alize(v1);
}
int main() {
    cin >> N >> K;
    vector<int> vec(N+2);
    for (int i = 1; i < N + 1; i++) {
        cin >> vec[i];
   }
    int M = 50;
    vector<vi> ans(M);
    ans[0] = vec;
    for (int i = 1; i < M; i++) {
        ans[i] = next(ans[i - 1]);
    }
    K = min(K, M-1);

    for (int i = 1; i < N + 1; i++) {
        cout << ans[K][i] << " ";
    }
}

Measured memory_bytes: 45324
import sys
input = sys.stdin.buffer.readline
N, K = map(int, input().split())
p = list(map(int, input().split()))
class SegTree:
  def segfunc(self, x, y):
    u = min(x[0], y[0])
    v = max(x[1], y[1])
    return (u, v) #ここ判定関数（ただし結合則があるもの）
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res
p = [(x, x) for x in p]
seg = SegTree(N, (float("inf"), 0), p)
mini = [0] * (N - K + 1)
maxi = [0] * (N - K + 1)
for i in range(N - K + 1):
  temp = seg.query(i, i + K)
  mini[i] = temp[0]
  maxi[i] = temp[1]
#print(mini, maxi)
dcount = 0
alsorted = 0
temp = 0
for i in range(1, N - K + 1):
  if mini[i] != mini[i - 1] and maxi[i] == p[i + K - 1][0]:
    dcount += 1
for i in range(N - 1):
  if p[i][0] < p[i + 1][0]:
    temp += 1
  else: temp = 0
  if temp == K - 1:
    alsorted += 1
if alsorted == 0: alsorted = 1
print(N - K + 1 - dcount - alsorted + 1)

Measured memory_bytes: 116132
N = int(input())
A = input()
B = input()
C = input()

answer = A
def calc_answer(answer):
    answer = answer
    for i in range(N):
        ver = [A[i], B[i], C[i]]
        same_index = get_same_index(ver)
        if same_index == (1,2):
            answer_lis = list(answer)
            answer_lis[i] = B[i]
            answer = ''
            for k in answer_lis:
                answer += k
    return answer

def get_same_index(lis):
    if lis[0] == lis[1] == lis[2]:
        return 0, 1, 2
    if lis[0] == lis[1]:
        return 0, 1
    if lis[1] == lis[2]:
        return 1, 2
    if lis[2] == lis[0]:
        return 0, 2
    else:
        return -1


def get_differency(answer):
    differency = 0
    answer = calc_answer(answer)
    for i in range(N):
        if answer[i] != A[i]:
            differency += 1
        if answer[i] != B[i]:
            differency += 1
        if answer[i] != C[i]:
            differency += 1
    return differency

differency = get_differency(answer)
print(differency)

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

#define rep(i, o) for (int i = 0; i < (o); ++i)
#define REP(i,a,b)for(int i=(int)(a);(i)<(int)(b);i++)
#define NUM 1e5

typedef long long ll;
typedef unsigned long long ull;

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

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

  vector<ll> h(n);
  rep(i, n) {
      cin >> h[i];
  }

  vector<pair<int, int>> bridge(m);
  rep(i, m) {
      int first, second;
      cin >> first >> second;
      bridge[i] = make_pair(first,second);
    //   cin >> bridge.at(i).first >> bridge.at(i).second;
  }

  vector<bool> good(n, true); ll max_h[m] = {0};
  rep(i, m) {
      max_h[i] = max(h[bridge.at(i).first-1], h[bridge.at(i).second-1]);
      if (h[bridge.at(i).first-1] < h[bridge.at(i).second-1])
      {
          good.at(bridge.at(i).first-1) = false;
      }
      else if (h[bridge.at(i).first-1] > h[bridge.at(i).second-1])
      {
          good.at(bridge.at(i).second-1) = false;
      }
      else
      {
          good.at(bridge.at(i).first-1) = false;
          good.at(bridge.at(i).second-1) = false;
      }
  }

  ll count = 0; map<int, bool> ismax;
  rep(i, n) {
      if (good.at(i) == true) count++;
  }
//   rep(i, m) {
    //   if (i == 0)
    //   {
        //   ismax.emplace(bridge.at(i).second, true);
    //   }
    //   if (i != 0)
    //   {
        //   /* code */
        //   if (bridge.at(i).second != bridge.at(i-1).second && 
            //   !ismax[bridge.at(i).second]                  &&
            //   good.at(bridge.at(i).first) == true ) 
        //   {
            //   ismax.emplace(bridge.at(i).second, true);
            //   count++;
        //   }
    //   }
//   }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 5608
L, R = map(int, input().split())

tmp = []
if L + 2019 < R:
    for i in range(L, L+2019+1):
        for j in range(L, L+2019+1):
            if i == j:
                continue
            tmp.append(i * j % 2019)
else:
    for i in range(L, R+1):
        for j in range(L, R+1):
            if i == j:
                continue
            tmp.append((i * j) % 2019)

print(min(tmp))

Measured memory_bytes: 130660
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Globalization;
using System.Diagnostics;
using static System.Console;
using Pair = System.Collections.Generic.KeyValuePair<int, int>;
//using System.Numerics;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    Random rnd = new Random();
    Stopwatch sw = new Stopwatch();
    readonly int[] dd = { 0, 1, 0, -1, 0 };
    readonly int mod = 1000000007;
    readonly string alfa = "abcdefghijklmnopqrstuvwxyz";
    readonly string ALFA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    int N;
    void solve()
    {
        N = cin.nextint;
        var A = cin.scanint;
        var B = new int[N];
        foreach (var item in A)
        {
            B[item]++;
        }
        bool flag = true;
        if (N % 2 == 0 && B[0] != 0) flag = false;
        if (N % 2 == 1 && B[0] != 1) flag = false;


        for (int i = 1 + (N % 2); i < N; i += 2)
        {
            //WriteLine(i + " " + B[i]);
            if (B[i] != 2) flag = false;
        }

        if (flag)
        {
            long ans = 1;
            for (int i = 0; i < N / 2; i++)
            {
                ans *= 2;
                ans %= mod;
            }
            WriteLine(ans);
        }
        else
        {
            WriteLine(0);
        }
    }


}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

Measured memory_bytes: 19292
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n;
	cin >> n;
	string s;
	cin >> s;
	int cnt = 0;
	rep(i, n - 2){
		if(s.substr(i, 3) == "ABC") cnt++;
	}
	cout << cnt << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 256
N = int(input())
count = 0
for i in range(N):
    n = int(input())
    if (n != 2) * (n % 2 == 0):
        continue
    j = 3
    while j*j <= n:
        if n % j == 0:
            break
        j += 2
    if j*j > n:
        count += 1
print(count)
            


Measured memory_bytes: 5608
#include<stdio.h>
int main(void){
	int a[5],r[5];
	int i,max=0,sum=0;
	for(i=0;i<5;i++){
		scanf("%d",&a[i]);
		r[i]=(10-a[i]%10)%10;
		max=max<r[i]?r[i]:max;
	}
	for(i=0;i<5;i++){
		sum+=a[i]+r[i];
	}
	printf("%d",sum-max);
	return 0;
}

Measured memory_bytes: 1640
def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

mod=998244353
n,m,k=map(int,input().split())
frac=[1 for i in range(n+1)]
frac_inv=[1 for i in range(n+1)]
beki=[m for i in range(n+1)]

for i in range(1,n+1):
    frac[i]=frac[i-1]*i%mod
    frac_inv[i]=inv(frac[i],mod)
    beki[i]=beki[i-1]*(m-1)%mod
ans=0
for i in range(n-k,n+1):
    ans+=beki[i-1]*frac_inv[n-i]*frac_inv[i-1]%mod
print(ans*frac[n-1]%mod)

Measured memory_bytes: 94372