akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi M_PI
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef string::const_iterator State;

string s;
int p, q, r;
 
int expression(State&);
int term(State&);
int factor(State&);
int number(State&);
 
int expression(State &begin){
    int ret = term(begin);
    while (1){
        if (*begin == '+'){
            begin++;
            ret = max(ret, term(begin));
        }else if (*begin == '*'){
            begin++;
            ret = min(ret, term(begin));
        }else{
            break;
        }
    }
    return ret;
}
 
int term(State &begin){
    int ret = factor(begin);
    while (1){
        if (*begin == '-'){
            begin++;
            ret = 2 - term(begin);
        }else{
            break;
        }
    }
    return ret;
}
 
int factor(State &begin){
    if (*begin == '('){
        begin++;
        int ret = expression(begin);
        begin++;
        return ret;
    }else{
        return number(begin);
    }
}
 
int number(State &begin){
    int ret = 0;
    while (isdigit(*begin) || (*begin >= 'P' && *begin <= 'R')){
        if (*begin == 'P') ret = p;
        else if (*begin == 'Q') ret = q;
        else if (*begin == 'R') ret = r;
        else{
            ret *= 10;
            ret += *begin - '0';
        }
        begin++;
    }
    return ret;
}

int main() {
    while (cin >> s && s != "."){
        int ans = 0;
        REP(_p,3) REP(_q,3) REP(_r,3){
            p = _p;
            q = _q;
            r = _r;            
            State begin = s.begin();
            if (expression(begin) == 2) ans++;
        }
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 3220
#教室内の位置は右*中央
#問題は「Restrictive Filesystem」(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2152)
#ところでコメントを今までより詳しく書くことにしました(説明が簡単なので)

while(True):
    #とりあえず複数のデータセットに対して行えるようにします
    N = int(input())
    #終了判定
    if N == 0:
        quit()

    #方針として、ヒントにもあるように[識別子,[セクタ範囲]]というデータ構造を作ります(以下の「data」)
    #工夫として、例えばセクタ3、4、5に同じ数字が入っている時、セクタ範囲を[3,6]とします
    #これによって、その範囲に同じ数字がいくつ入っているかをカウントするのが容易になります
    #また、これとは別に、Nullになっているセクタの範囲を記したデータ構造を作ります(以下の「emp」)
    #empに空のセクタを集めておくことで、どのセクタにどの識別子を入れているかの判別が簡単になり、
    #なおかつdeleteした時の空セクタを簡単に取り扱うことができます
    #commandはせいぜい10000個なのでセクタ範囲の分割もせいぜい10000個であり、これで間に合うことがわかります(最大でソートのO(NlogN))
    #以下実装

    data = []
    emp = [[0,1+10**9]] #empは最初セクタ0~セクタ10**9。
    for _____ in range(N): #N回の命令。
        tmp = input().split()
        if tmp[0] == "W":#書き込みの時
            c,k = int(tmp[1]),int(tmp[2]) #cが識別子、kが個数
            while(k): #empのうち、セクタ範囲が小さい順から順番に入れていけばいいことがわかります
                      #この操作のために、empが増えた時にはsortし、常にセクタ範囲が小さい順になるようにします
                      #入りきらなかった場合は、とりあえずその分を入れて残りを入れればいいので、whileループを回します
                if (emp[0][1]-emp[0][0]) > k: #最初の空な範囲のなかに識別子が全て入ってしまうとき。
                    data.append([c,[emp[0][0],emp[0][0]+k]]) #dataに書き込んだ分を追加
                    emp[0] = [emp[0][0]+k,emp[0][1]] #代わりにempの最初のセクタ範囲が入れた分だけ減ります
                    break
                else: #ぴったり入るか、入りきらない場合
                    data.append([c,emp[0]]) #とりあえず最初のとこに入るだけ入れちゃいます
                    k -= (emp[0][1]-emp[0][0]) #入れた分だけ残りの入れる分を消します
                    del(emp[0]) #空な範囲の最初の部分が消える。
        elif tmp[0] == "D": #消すとき
            emp += [i[1] for i in data if i[0] == int(tmp[1])] #消したい識別子と一致するような範囲を全てempに足します
            data = [i for i in data if i[0] != int(tmp[1])] #dataは消したい識別子以外の識別子の範囲だけになります
            emp.sort() #empの範囲が小さい順になるようにsort。ちなみに理屈から分かる通り範囲がかぶることはないので安心です
        else: #読み込みの時
            ans = True
            s = int(tmp[1]) #sは読み込みたいセクタ範囲
            for i in data:
                if i[1][0]<=s<i[1][1]: #sが空でないdataのセクタとして書いてあればその識別子を書いておしまいです
                    print(i[0])
                    ans = False
                    break
            if ans: #どこにも書いてなければ-1を書いて終わり。
                print(-1)
    print() #データセットごとに改行。



Measured memory_bytes: 6760
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b)for(int i=(a);i<=(b);i++)
#define repR(i,n) for(int i=n;i>=0;i--)
#define P pair<int, int>
#define sz(x) x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<int>
#define COUT(x) cout<<(x)<<endl
#define MA map<int,int>
#define SE set<int>
#define PQ priority_queue
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl

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;
}

using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
bool compare_by_b(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

const long long MOD = 1000000007;
const long long INF = 1LL << 50;

// pair -> vector<pair<int,int>> 
//		   AandB.push_back(make_pair(a[i],b[i]))



signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m; cin >> n >> m;
	vector<int>a(m);
	rep(i, n) {
		int k; cin >> k;
		vector<int>b(k);
		rep(j, k) {
			cin >> b[j]; b[j]--;
			a[b[j]]++;
		}
	}
	int ans = 0;
	rep(i, m) {
		if (a[i] == n)ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES // for C++  
#include "bits/stdc++.h"
using LL = long long;
using ULL = unsigned long long;
#define NUM 1000000007

using namespace std;

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

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

int main(){
	int n;
	cin>>n;
	vector<int> a(n);
	map<int, int> d;
	rep(i, n){
		cin>>a[i];
		d[a[i]]++;
	}
	ll res = 0;
	rep(i, n){
		if(d[a[i]]!=0){
			if(d[a[i]]>=a[i]) d[a[i]] -= a[i];
			res += d[a[i]];
			d[a[i]] = 0;
		}
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 5120
n = int(input())
A = [int(input()) for _ in range(n)]

A.sort()

if n%2 == 0:
    ans = A[n//2]-A[n//2-1]
    m = A[n//2]-A[n//2-1]
    for i in range(n):
        if i == n//2-1 or i == n//2:
            continue
        else:
            if i <= n//2:
                ans += m-2*A[i]
            else:
                ans += 2*A[i]-m
else:
    m = A[n//2]
    ans1 = m-A[n//2-1]
    for i in range(n):
        if i == n//2-1 or i == n//2:
            continue
        else:
            ans1 += 2*abs(A[i]-m)
    m = A[n//2]
    ans2 = A[n//2+1]-m
    for i in range(n):
        if i == n//2+1 or i == n//2:
            continue
        else:
            ans2 += 2*abs(A[i]-m)
    ans = max(ans1, ans2)
print(ans)


Measured memory_bytes: 13228
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static class State{
		int Cx, Cy;
		long H;
		boolean flag;
		public State(int Cx, int Cy, long H, boolean flag) {
			this.Cx = Cx;
			this.Cy = Cy;
			this.H = H;
			this.flag = flag;
		}
	}

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

    		int N = sc.nextInt();
    		Queue<State> q = new LinkedList<State>();
    		for(int i=0; i<101; i++) {
    			for(int j=0; j<101; j++) {
    				q.add(new State(i, j, 0, false));
    			}
    		}

    		for(int n=0; n<N; n++) {
    			int xn = sc.nextInt();
    			int yn = sc.nextInt();
    			int hn = sc.nextInt();
    			int size = q.size();
    			for(int i=0; i<size; i++) {
    				State state = q.remove();
    				long h = hn+Math.abs(xn-state.Cx)+Math.abs(yn-state.Cy);
    				//if(hn == 0) q.add(new State(state.Cx, state.Cy, Math.min(h, state.H)))
    				if(h < 1)	continue;
    				if(n == 0) {
    					if(hn == 0)
    						q.add(new State(state.Cx, state.Cy, h, true));
    					else
    						q.add(new State(state.Cx, state.Cy, h, false));
    				}
    				else {
    					if(state.flag == true) {
    						if(hn == 0) {
    							q.add(new State(state.Cx, state.Cy, Math.min(h, state.H), true));
    						}
    						else if(h <= state.H) {
    							q.add(new State(state.Cx, state.Cy, h, false));
    						}
    					}
    					else {
    						if(hn > 0 && state.H == h) {
    							q.add(new State(state.Cx, state.Cy, h, false));
    						}
    						else if(hn == 0 && h >= state.H){
    							q.add(new State(state.Cx, state.Cy, state.H, false));
    						}
    					}
    				}
    			}
    		}
    		State state = q.remove();
    		System.out.println(state.Cx+" "+state.Cy+" "+state.H);

    	}
    }
}



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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
const int dx[] = {0,0,1,1,1,-1,-1,-1};
const int dy[] = {1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

void dfs(int ci, int cj, VVI& board, VVI& visited, int h,int w){
  visited[ci][cj] = 1;
  rep(dir,8){
    if((ci + dy[dir]) < h && (cj + dx[dir]) < w &&
       (ci + dy[dir]) >= 0 && (cj + dx[dir]) >= 0  &&
       visited[(ci + dy[dir])][(cj + dx[dir])] == 0 &&
       board[(ci + dy[dir])][(cj + dx[dir])] == 1){
      dfs((ci + dy[dir]),(cj + dx[dir]),board,visited,h,w);
    }
  }
}

void solve(int h, int w){
  VVI board(h,VI(w));
  rep(i,h)rep(j,w) cin >> board[i][j];
  VVI visited(h,VI(w,0));
  int cnt = 0;
  rep(i,h)rep(j,w){
    if(board[i][j] == 1 && visited[i][j] == 0){
      dfs(i,j,board,visited,h,w);
      cnt++;
      //cout << i << ' ' << j << endl;
    }
  }
  cout << cnt << endl;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h,w;
  while(true){
    cin >> w >> h;
    if(h == 0 &&  w == 0){
      break;
    }
    solve( h,  w);
  }
  return 0;
}



Measured memory_bytes: 3348
n,k = map(int,input().split())
s = []
ans = 0
for i in range(k):
  d = int(input())
  A = list(map(int,input().split()))
  for i in range(d):
    s.append(A[i])

for i in range(n+1):
  if s.count(i) == 0:
    ans += 1
    
print(ans-1)

Measured memory_bytes: 9160
N = int(input())
A = list(map(int, (input().split())))

D = {}
for i in A:
    if i not in D:
        D[i] = 1
    else:
        D[i] += 1

r = 0
for v in D.values():
    r += (v*(v-1))//2

for i in A:
    print(r - (D[i] - 1))


Measured memory_bytes: 24748
#include <stdio.h>

int main(void){
    long long int a,b;
    scanf("%lld",&a);
    scanf("%lld",&b);
    long long int x = a * b;
    long long int tmp,r;
    if(a<b){
    tmp = a;
    a = b;
    b = tmp;
    }

    r = a % b;
    while(r!=0){
    a = b;
    b = r;
    r = a % b;
    }
    printf("%lld\n",x/b);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

#define rep(i,a) for(int i = 0 ; i < a ; i ++)
#define loop(i,a,b) for(int i = a ; i < b ; i ++)
typedef pair<int,int> pii;
#define MAX_V 110
#define INF (1<<30)

struct edge{int to,cost;};
vector<edge> G[MAX_V],IN[MAX_V];
int d[MAX_V];
 
void dijkstra(int s,int V){
    priority_queue< pii,vector<pii>,greater<pii> > que;
    rep(i,V)d[i]=INF;
    d[s]=0;
    que.push(pii(0,s));
     
    while(que.size()){
        pii p=que.top();
        que.pop();
         
        int v=p.second;
        if(d[v]<p.first)continue;
         
        rep(i,G[v].size()){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                que.push(pii(d[e.to],e.to));
            }
        }
    }
}

int N,M,o;
int maze[100][100],tim[100][100];
int main(void){
	while(cin>>N>>M,N+M){
		rep(i,MAX_V)G[i].clear();
		while(M--){
			cin>>o;
			if(o){
				int a,b,c;
				cin>>a>>b>>c;
				--a,--b;
				edge e = {b,c}, e1 = {a,c};
				G[a].push_back(e);
				G[b].push_back(e1);
			}else{
				int a,b;
				cin>>a>>b;
				--a,--b;
				dijkstra(a,N);
				cout<<(d[b]==(1<<30)?-1:d[b])<<endl;
			}
		}
	}
	

}

Measured memory_bytes: 1256
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <numeric>
#include <queue>
#include <numeric>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <map>
#include <functional>
#include <limits>
#include <set>
#include <stack>
#include <cctype>
#define rep(i,a,b) for((i)=a;i<(int)(b);i++)

#define AAA (1000000007) 


using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pairII;
typedef vector<int> vecI;

ll gcd(ll a, ll b) {
	if (b == 0)return a;
	return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}
ll powD(ll a, ll b) {
	ll ans = 1;
	a %= AAA;
	for (int i = 0; i < b; i++)
	{
		ans *= a;
		ans %= AAA;
	}
	return ans;
}



int main() {
	int i, j, k;
	int N, M, K;
	
	ll D;
	cin >> N >> D;
	vector<ll> X(N), Y(N);

	rep(i, 0, N) {
		cin >> X[i] >> Y[i];
	}
	int ans = 0;
	rep(i, 0, N) {
		if (X[i] * X[i] + Y[i] * Y[i] <= D * D)
			ans++;
	}
	cout << ans;

	return 0;
}


Measured memory_bytes: 6424
import java.util.*;

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

        int h = sc.nextInt();
        int n = sc.nextInt();
        int sum = 0;
        for(int i = 0;i < n;i++){
            int damage = sc.nextInt();
            sum += damage;
        }
        System.out.println(sum>=h?"Yes":"No");
    }
}

Measured memory_bytes: 48900
use proconio::input;

fn main() {
    input! {
        s: String,
        t: String
    }

    solve(s, t);
}

fn solve(s: String, t: String) {
    if s == t[..(t.len() - 1)] {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 2084
#include "bits/stdc++.h"
using namespace std;
int main(void){
    long long ans,N,T,t[200000];
    cin >> N >> T;
    ans = N*T;
    for (int i=0;i<N;i++){
        cin >> t[i];
    }
    for (int i=0;i<N-1;i++){
        if (T-(t[i+1] - t[i]) > 0){
            ans -= (T-(t[i+1] - t[i]));
        } 
    }
    cout << ans << endl;
}

Measured memory_bytes: 1920
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
class UnionFind():
   # 作りたい要素数nで初期化
   # 使用するインスタンス変数の初期化
   def __init__(self, n):
       self.n = n
       # root[x]<0ならそのノードが根かつその値が木の要素数
       # rootノードでその木の要素数を記録する
       self.root = [-1]*(n+1)
       # 木をくっつける時にアンバランスにならないように調整する
       self.rnk = [0]*(n+1)
   # ノードxのrootノードを見つける
   def Find_Root(self, x):
       if(self.root[x] < 0):
           return x
       else:
           # ここで代入しておくことで、後の繰り返しを避ける
           self.root[x] = self.Find_Root(self.root[x])
           return self.root[x]
   # 木の併合、入力は併合したい各ノード
   def Unite(self, x, y):
       # 入力ノードのrootノードを見つける
       x = self.Find_Root(x)
       y = self.Find_Root(y)
       # すでに同じ木に属していた場合
       if(x == y):
           return
       # 違う木に属していた場合rnkを見てくっつける方を決める
       elif(self.rnk[x] > self.rnk[y]):
           self.root[x] += self.root[y]
           self.root[y] = x
       else:
           self.root[y] += self.root[x]
           self.root[x] = y
           # rnkが同じ（深さに差がない場合）は1増やす
           if(self.rnk[x] == self.rnk[y]):
               self.rnk[y] += 1
   # xとyが同じグループに属するか判断
   def isSameGroup(self, x, y):
       return self.Find_Root(x) == self.Find_Root(y)
   # ノードxが属する木のサイズを返す
   def Count(self, x):
       return -self.root[self.Find_Root(x)]
n,m=map(int,input().split())
e=[tuple(map(int,input().split())) for _ in range(m)]
e.reverse()
h=UnionFind(n)
ans=[0]*m
k=n*(n-1)//2
for i in range(m):
    ans[i]=k
    s,t=e[i]
    if not h.isSameGroup(s,t):
        k-=h.Count(s)*h.Count(t)
        h.Unite(s,t)
for i in ans[::-1]:
    print(i)

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

using namespace std;

int main() {
	int N,Q;
	string str;
	cin >> N >> Q >> str;
	int num = str.size();
	vector<int> ans,sum(num + 1,0);

	for (int i = 2; i <= num; i++) {
		sum[i] = sum[i - 1];
		if (str[i - 1 -1] == 'A' && str[i -1] == 'C')
			sum[i]++;
	}

	for (int i = 0; i < Q; i++)
	{
		int l, r;
		cin >> l >> r;

		ans.push_back(sum[r] - sum[l]);
	}
	for (auto a : ans) {
		cout << a << endl;
	}


	return 0;
}

Measured memory_bytes: 1912
X,N=map(int,input().split())
 
if N==0:
    _=input()
    print(X)
    
else:
    Ps=list(map(int,input().split()))
    d=0
    while 1:
        if X-d not in  Ps:
            print(X-d)
            break
        elif X+d not in Ps:
            print(X+d)
            break
        d+=1

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

/*vector<int> p(n);
cin >> p[i]*/

int main(){

    int a,b,c;
    cin >> a >> b >> c;

    if((a == b && a != c) || (b == c && b != a) || (c == a && a != b)) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
using namespace std;
int n;
double a[3005],f[3000][3000];
int main()
{
    cin>>n;
    for (int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    f[0][0]=1;
    for (int i=1;i<=n;++i)
    {
        f[i][0]=f[i-1][0]*(1-a[i]);
        for (int j=1;j<=i;++j)
        {
            f[i][j]=(f[i-1][j]*(1-a[i]))+(f[i-1][j-1]*a[i]);
        }
    }
    double res=0;
    int tmp=(n+1)/2;
    for (int i=n;i>=tmp;--i)
    {
        res+=f[n][i]; 
    }
    cout<<setprecision(9)<<fixed<<res;
    return 0;
}

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

int main(){
   int n;
   cin >> n;
   int a[n];
   for(int i=0;i<n;i++)cin >> a[i];
   int q;
   cin >> q;
   int s[q];
   for(int i=0;i<q;i++)cin >> s[i];
   int ans=0;
   for(int i=0;i<q;i++){
       for(int j=0;j<n;j++){
           if(a[j]==s[i]){
               ans++;
               break;
           }
       }
   }
   cout << ans << endl;
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(a) (a).begin(), (a).end()
typedef vector<int> vi;
const int INF = 1LL << 60; //10e18+10e17ちょっとくらい
const int MOD = 1000000007;
const int MAX_N = 200100;

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

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

mint memo[100010];
signed main()
{
    //  以降 cin の入力元が 'input.txt' になる
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());
    int N, K;
    cin >> N >> K;
    mint ans = K;
    ans = ans.pow(N);

    for (int i = K; i > 1; --i)
    {
        //iの倍数の個数
        mint num = K / i;

        memo[i] = num.pow(N);

        REP(j, num.x - 1)
        {
            memo[i] -= memo[i * (j + 2)];
        }

        ans += memo[i] * (i - 1);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4368
H,W = map(int,input().split())
A = [input().strip() for _ in range(H)]
C = {chr(i):0 for i in range(97,123)}
for i in range(H):
    for j in range(W):
        C[A[i][j]] += 1
if H%2==0 and W%2==0:
    flag = 0
    for a in C:
        if C[a]%4!=0:
            flag = 1
            break
    if flag==0:
        print("Yes")
    else:
        print("No")
elif H%2==0 and W%2==1:
    cnt = 0
    flag = 0
    for a in C:
        if C[a]%4==2:
            cnt += 1
        elif C[a]%4!=0:
            flag = 1
            break
    if flag==1:
        print("No")
    else:
        if cnt<=H//2:
            print("Yes")
        else:
            print("No")
elif H%2==1 and W%2==0:
    flag = 0
    cnt = 0
    for a in C:
        if C[a]%4==2:
            cnt += 1
        elif C[a]%4!=0:
            flag = 1
            break
    if flag==1:
        print("No")
    else:
        if cnt<=W//2:
            print("Yes")
        else:
            print("No")
else:
    cnt1 = 0
    cnt2 = 0
    for a in C:
        if C[a]%4==2:
            cnt2 += 1
        elif C[a]%2==1:
            cnt1 += 1
    if cnt1!=1:
        print("No")
    else:
        if cnt2<=(H-1)//2+(W-1)//2:
            print("Yes")
        else:
            print("No")

Measured memory_bytes: 65496
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
struct edge { int to, from, cost; };
int INF = 1000000000000;
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m, p;
  cin >> n >> m >> p;

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

  edge es[m];
  for(int i = 0; i < m; i++) {
    es[i] = (edge) { b[i], a[i], p - c[i]};
  }
  int d[n];
  for(int i = 0; i < n; i++) d[i] = INF;
  d[0] = 0;

  bool neg_loop = false;
  for(int i = 0; i < 2 * n; i++) {
    for(int j = 0; j < m; j++) {
      edge e = es[j];
      if(d[e.to] > d[e.from] + e.cost) {
        d[e.to] = d[e.from] + e.cost;
        if(i >= n - 1 && e.to == n - 1) {
          neg_loop = true;
          break;
        }
      }

    }
  }

  if(neg_loop) {
    cout << -1 << "\n";
    return 0;
  }


  cout << max(0LL, -d[n - 1]) << "\n";
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
  int N,K,x,l=0,m;
  cin >> N >> K;

  for (int i=0;i<N;i++){
	cin >> x;
    if(x-K<0){
    	m=K-x;
    }else{
      m=x-K;
    }
    if(x>m){
    	l+=m*2;
    }else{
    	l+=x*2;
    }  
  } 
  	cout << l << endl;
}

Measured memory_bytes: 256
from itertools import accumulate

class Factorial:
    def __init__(self, n, mod=10**9+7):
        self.fac = [0] * (n+1)
        self.ifac = [0] * (n+1)
        self.fac[0] = 1
        self.ifac[0] = 1
        self.mod = mod
        modmod = self.mod - 2
        for i in range(n):
            self.fac[i+1] = self.fac[i] * (i+1) % self.mod
            self.ifac[i+1] = self.ifac[i] * pow(i+1, modmod, self.mod) % self.mod

    def comb(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        tmp =  self.ifac[n-r] * self.ifac[r] % self.mod
        return tmp * self.fac[n] % self.mod

    def perm(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        return (self.fac[n] * self.ifac[n-r]) % self.mod

def resolve():
    n, k = map(int, input().split())
    a = sorted(map(int, input().split()))
    mod = 10**9 + 7

    fact = Factorial(n + 1)
    lll = [fact.comb(i, k-1) for i in range(k-1, n)]
    # acc = list(accumulate(lll))

    ans = 0
    for i in range(n-k+1):
        # print(i, -1-i, f" --- {a[i]}, {a[-i-1]}, {lll[-i-1]}")
        ans = (ans + (a[-i-1] - a[i]) * lll[-i-1]) % mod
    print(ans)

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 22932
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main
{
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
    public static void main(String args[])
    {
        FastReader obj = new FastReader();
       int n = obj.nextInt();
        TreeSet<Integer> arr = new TreeSet<>();
        boolean flag = true;
        for(int i=0;i<n;i++)
        {
            int k = obj.nextInt();
            if(!arr.contains(k))
                arr.add(k);
            else
                flag = false;
        }
        System.out.println((flag)?"YES":"NO");
    }
}


Measured memory_bytes: 56088
// AOJ 1180

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

string mold(string str, int l)
{
	int tmp = l - str.length();
	for (int i = 0; i < tmp; i++){
		str += '0';
	}

	return str;
}
int main(void)
{
	int a, l;
	while (cin >> a >> l, a || l){
		vector <string> data;
		string tmp = toString(a); tmp = mold(tmp, l);
		data.push_back(tmp);
		while (1){
			string d = toString(a);
			d = mold(d, l);

			string high = d;
			sort(high.rbegin(), high.rend());
			string low = d;
			sort(low.begin(), low.end());

			int h = toInt(high), l = toInt(low);
			string tmp = toString(h - l);
			data.push_back(tmp);
			for (int i = 0; i < data.size()-1; i++){
				if (data[i] == tmp){
					cout << i << " " << tmp << " " << data.size()-1-i << endl;
					goto END;
				}
			}
			a = toInt(tmp);
		}
		END : ;
	}

	return 0;

}

Measured memory_bytes: 1260
n=int(input())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
all_order={}
def dfs(a):
  if len(a)==n:
    all_order[tuple(a)]=len(all_order.keys())+1
  else:
    for nv in range(n):
      nv+=1
      if nv in a:continue
      dfs(a+[nv])
dfs([])
print(abs(all_order[tuple(p)]-all_order[tuple(q)]))



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

using namespace std;

#define int int64_t

signed main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;
	a--, b--, c--, d--;
	string s;
	cin >> s;
	int good[4][n];
	memset(good, 0, sizeof(good));
	good[0][a] = good[1][b] = 1;
	good[2][c] = good[3][d] = 1;
	for(int i = a; i <= c; i++) {
		if(i >= a + 1) {
			good[0][i] |= good[0][i - 1] && s[i] != '#';
		}
		if(i >= a + 2) {
			good[0][i] |= good[0][i - 2] && s[i] != '#';
		}
	}
	for(int i = b; i <= d; i++) {
		if(i >= b + 1) {
			good[1][i] |= good[1][i - 1] && s[i] != '#';
		}
		if(i >= b + 2) {
			good[1][i] |= good[1][i - 2] && s[i] != '#';
		}
	}
	for(int i = c; i >= a; i--) {
		if(i <= c - 1) {
			good[2][i] |= good[2][i + 1] && s[i] != '#';
		}
		if(i <= c - 2) {
			good[2][i] |= good[2][i + 2] && s[i] != '#';
		}
	}
	for(int i = d; i >= b; i--) {
		if(i <= d - 1) {
			good[3][i] |= good[3][i + 1] && s[i] != '#';
		}
		if(i <= d - 2) {
			good[3][i] |= good[3][i + 2] && s[i] != '#';
		}
	}
	if(good[0][c] && good[1][d]) {
		if(c < d) {
			cout << "Yes" << endl;
		} else {
			for(int i = b; i <= d; i++) {
				if(good[1][i] && good[3][i] && good[0][i - 1] && good[2][i + 1]) {
					cout << "Yes" << endl;
					return 0;
				}
			}
			cout << "No" << endl;
		}
	} else {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 6608
function Main(input) {
  const lines = input.trim().split("\n").slice(1).map((line, i) => {
    const [S, P] = line.split(' ');
    return { name: S, score: P, id: i + 1 };
  });
  lines.sort((a, b) => {
    if (a.name > b.name) {
      return 1;
    }
    else if (a.name < b.name) {
      return -1;
    }
    else {
      return b.score - a.score;
    }
  });
  lines.forEach(line => {
    console.log(line.id);
  });
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb(n) push_back(n)
#define mp make_pair
#define INF LONG_LONG_MAX
#define yn(f) cout << (f ? "Yes" : "No") << endl;

int n,k,fa,ba,a,ans=INF;


signed main() {
    cin >> k >> n >> ba;
    fa = ba;
    rep(i,n-1) {
        cin >> a;
        ans = min(ans, k-abs(a-ba));
        ba = a;
    }
    ba -= k;
    ans = min(ans, k-abs(fa-ba));
    cout << ans << endl;
}

Measured memory_bytes: 256
N,C = map(int,input().split())

xv = []

for i in range(N):

    x,v = map(int,input().split())
    xv.append([x,v])

xv.sort()

ldis = [0]
lcal = [0]

for i in range(N):

    ldis.append(xv[i][0])
    lcal.append(lcal[-1] + xv[i][1])

lmax = [0]
for i in range(N):
    i += 1
    lmax.append( max(lmax[-1] , lcal[i] - ldis[i]) )

rdis = [0]
rcal = [0]

for i in range(N):
    i = N-1-i
    rdis.append(C - xv[i][0])
    rcal.append(rcal[-1] + xv[i][1])

rmax = [0]
for i in range(N):
    i += 1
    rmax.append ( max(rmax[-1] , rcal[i] - rdis[i]) )

lmax2 = [0]
for i in range(N):
    i += 1
    lmax2.append( max(lmax2[-1] , lcal[i] - ldis[i] * 2) )
rmax2 = [0]
for i in range(N):
    i += 1
    rmax2.append ( max(rmax2[-1] , rcal[i] - rdis[i] * 2) )

ans = 0
for i in range(N+1):

    if i != N-i:
        ans = max(ans,lmax[i] + rmax2[N-i],lmax2[i] + rmax[N-i])

#print (lmax,lmax2,rmax,rmax2)
print (ans)

Measured memory_bytes: 81112
n=int(input())
x = [int(input()) for i in range(n)]
ans=1
visited=[False]*n
now=0
visited[now]=True

while(1):
  #nextは次のボタンの番号
  now=x[now]-1
  if visited[now]:
    print(-1)
    break
   
  visited[now]=True
  if now==1:
    print(ans)

    break
  else:
    ans+=1

Measured memory_bytes: 7852
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <map>




#define AS(a) (sizeof(a)/sizeof(a[0]))
using namespace std;
long long int MOD = 1000000007;
long long int INF = 1000000007;


int main() {
  int N = 0;
  cin >> N;
  long long int sum = 0;
  for(int i = 0; i < N; i++) {
    int l,r;
    cin >> l >> r;
    sum += r - l + 1;
  }
  cout << sum << endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{

	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException
	{
		// TODO 自動生成されたメソッド・スタブ
		for(int i = 1;; i++)
		{
			String str[] = input(2);
			int a = Integer.parseInt(str[0]);
			int b = Integer.parseInt(str[1]);
			if(a == 0 && b == 0) break;
			for(int j = 0; j < a; j++)
			{
				for(int k = 0; k < b; k++)
				{
					System.out.print("#");
				}
				System.out.println();
			}
			System.out.println();
		}
	}

	public static String[] input(int Num) throws IOException
	{
		String str[] = new String[Num];
		String str2 = br.readLine();
		int j = 0;
		for(int i = 0; i < Num; i++)
		{
			if(i < Num - 1)
			{
				str[i] = str2.substring(j, str2.indexOf(" ", j));
				j = str2.indexOf(" ", j) + 1;
			}
			else
			{
				str[i] = str2.substring(j);
			}
		}
		return str;
	}

}



Measured memory_bytes: 31064
#include <bits/stdc++.h>
#define ll long long
#define p pair<ll, int>
using namespace std;

int inf[20005];
int main() {
    int n, m;
    while (cin >> n >> m, n | m) {
        memset(inf, 0, sizeof(inf));
        inf[1] = 1;
        vector<p> v;
        int s[m], d[m];
        for (int i = 0; i < m; i++) {
            ll t;
            cin >> t >> s[i] >> d[i];
            v.push_back(p(t, i));
        }
        sort(v.begin(), v.end());
        for (int i = 0; i < m; i++) {
            int idx = v[i].second;
            if (inf[s[idx]]) inf[d[idx]] = 1;
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (inf[i]) ans++;
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3852
#include<iostream>
#include<algorithm>
#include<string>
#include<functional>
#include<utility>
#include<stack>
#include<queue>
#include<cmath>
#include<list>
#include<cstdint>
#include<vector>
#include<map>
#define rep(i,rept)	for(ll i = 0; i<rept;i++)
typedef long long ll;
using namespace std;

long long int a = 0, b = 0, c = 1, x = 0, y = 0, z = 0, maxy = -1, mini = 9999, counter = 0,startp=0,endp=0,checker=0;
std::vector<unsigned long long int> vec{}, vecsec{};
int iremono[100001];
std::vector<long long int>kinds{}, ans{}, kaku{};

bool okada = false,okada2=false;
std::string output, output2, input, one, two;
char cutcount[201];
int kakunou2[50][50] = {};

int ctoi(const char c) {
	if ('0' <= c && c <= '9') return (c - '0');
	return -1;
}
unsigned long long int LCM(unsigned long long int a, unsigned long long int b) {
	unsigned long long int i, j;
	i = a; j = b;
	while (true) {

		c = i % j;
		i = j;
		if (c != 0) {

			j = c;

		}
		else {
			break;
		}
	}
	return j * (a / j) * (b / j);
}
int main()
{
	cin >> a>>b;
	rep(i, b) {
		cin >> x;
		kaku.push_back(x);
	}
	if (a >= b) {
		cout << 0 << endl;
		return 0;
	}
	else {
		std::sort(kaku.begin(), kaku.end());
		for (int j = 1; j < kaku.size();j++) {
			y = kaku[j] - kaku[j - 1];
			ans.push_back(y);
	
		}
		std::sort(ans.begin(), ans.end());
		for (int k = 0; k < b-a; k++) {
			counter += ans[k];
		
		}



		cout << counter << endl;


	}
}

	
	





Measured memory_bytes: 2548
import java.util.Scanner;
public class Main {
	public static void main(String[] arg){
		// ?¨??????\???
        Scanner scan = new Scanner(System.in);
        // int???????????????
        int n = scan.nextInt();
        int cube = n * n * n;
        // ??????(????°???????????????????????????????)
        System.out.println(cube);
        // Scanner????????????
        scan.close();
	}
}

Measured memory_bytes: 26192
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
ll N, M;

int main(){
   cin >> N >> M;
   ll ans = INF;
   ll m = M / 2;
   ll n = N / 2;
   for(int i = 1; i < N;++i){
       ll s1 = i * M;
       ll t = N-i;
       // tate
       ll s2 = t * m;
       ll s3 = t * (M - m);
       chmin(ans,max(s1,max(s2,s3)) - min(s1,min(s2,s3)));

       // yoko
       s2 = (t / 2) * M;
       s3 = (t - t / 2) * M;
       chmin(ans,max(s1,max(s2,s3)) - min(s1,min(s2,s3)));


   }

   for(int i = 1; i < M;++i){
       ll s1 = i * N;
       ll t = M-i;
       // tate
       ll s2 = t * n;
       ll s3 = t * (N - n);
       chmin(ans,max(s1,max(s2,s3)) - min(s1,min(s2,s3)));

       // yoko
       s2 = (t / 2) * N;
       s3 = (t - t / 2) * N;
       chmin(ans,max(s1,max(s2,s3)) - min(s1,min(s2,s3)));
  }

   cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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;
}

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
map<ll, ll> prime_factor(ll n) {
	map<ll, ll> ret;
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ret[i]++;
			n /= i;
		}
	}
	if (n != 1) ret[n] = 1;
	return ret;
}

const long long MOD = 1000000007;
//const long long MOD = 998244353;
const long long INF = 1LL << 60;



const long double PI = 3.14159265359;
const int MAX_N = 100010;

bool tmp[11];
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m; cin >> n >> m;
	vector<int>k(m);
	vector<vector<int>>s(m);
	rep(i, m) {
		cin >> k[i];
		s[i].resize(k[i]);
		rep(j, k[i]) {
			cin >> s[i][j]; s[i][j]--;
		}
	}
	VE p(m);
	rep(i, m) {
		cin >> p[i];
	}
	int ans = 0;
	rep(bit, 1 << n) {
		rep(i, 11)tmp[i] = false;
		rep(i, n) {
			if (bit &(1 << i)) {
				tmp[i] = true;
			}
		}
		bool ok = true;
		rep(i, m) {
			int cnt = 0;
			rep(j, k[i]) {
				
				if (tmp[s[i][j]]) {
					cnt++;
				}
			}
			if (cnt % 2 != p[i])ok = false;
		}
		if (ok)ans++;
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
  int a, b, c;
  int Array[3];
  int v,j;

  cin >> a >> b >> c;
  Array[0] = a;
  Array[1] = b;
  Array[2] = c;

  for(int i=1; i < 3; i++) {
    v = Array[i];
    j = i-1;
    while( j >= 0 && Array[j] > v ) {
      Array[j+1] = Array[j];
      j--;
    }
    Array[j+1] = v;
  }

  cout << ( Array[2] * 10 + Array[1] ) + Array[0] << endl;

  return 0;
}


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

int main()
{
	string s;
	cin >> s;
	string answer = "";

	for (int i = 0; i < s.size(); i++)
	{
		if (i % 2 == 0)
		{
			answer += s.at(i);
		}
	}

	cout << answer << endl;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)

int main(){
    ll K, A, B;
    cin >> K >> A >> B;

    ll ans = 1;
    if(B-A <= 2){
        ans += K;
        cout << ans << endl;
        return 0;
    }

    ll k = K;
    //k -= (A-1);
    k -= (A-1);
    ll num = k/2;
    ans = (B-A)*(num-1) + B;
    if(k%2) ans++;

    ll ans2 = 1;
    ans2 += K;
    ans = max(ans, ans2);

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


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

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int w, n;
  cin >> w >> n;

  int p[30];
  iota(p, p + w, 0);
  for (int i = 0; i < n; i++) {
    int a, b;
    char c;
    cin >> a >> c >> b;
    swap(p[a - 1], p[b - 1]);
  }
  for (int i = 0; i < w; i++) {
    cout << p[i] + 1 << endl;
  }

  return 0;
}


Measured memory_bytes: 3100
// #pragma GCC target("avx2")
#pragma GCC optimize("O3", "unroll-loops")

// #include <bits/extc++.h>
// using namespace __gnu_pbds;

#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define double long double
// template <typename T>
// using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pii = pair<int, int>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = priority_queue<T>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back

#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define RANDOM() random_device __rd; \
                 mt19937 __gen = mt19937(__rd()); \
                 uniform_int_distribution<int> __dis(0, 1); \
                 auto rnd = bind(__dis, __gen);

const int INF = 1E18;
const int mod = 1E9 + 7;

int32_t main() {
    fastIO();
    
    int k, a, b;
    cin >> k >> a >> b;
    
    for (int i = a; i <= b; ++i) {
        if (i % k == 0) return cout << "OK\n", 0;
    }
    
    cout << "NG\n";
    
    return 0;
}

Measured memory_bytes: 3652
#include <iostream>
using namespace std;
int main(void){
    long long int H,W;
    cin>>H>>W;
    long long int ans=(H*W+1)/2;
    if (H!=1&&W!=1)cout<<ans<<endl;
    else if (H==1||W==1)cout <<1<<endl;
    return 0;
    
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int n,k,c=0; cin>>n>>k;
    vector<int> cnt(n,inf);
    rep(i,n){
        int a; cin>>a;
        if(cnt[a-1]==inf){
            cnt[a-1]=0; c++;
        }
        cnt[a-1]++;
    }
    if(c<=k) cout<<0<<endl;
    else{
        sort(al(cnt));
        int ans=0;
        rep(i,c-k) ans+=cnt[i];
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int compare(string a, string b){
	int diff = 0;
	for (int i=0; i<a.length(); i++){
		if (a[i]!=b[i]) diff ++;
	}
	return diff;
}
int main() {
	string s, t;
	cin >> t >> s;
	int smallchange = s.length();
	for (int i=0; i<= t.length()-s.length(); i++){
		string pat =t.substr(i, s.length());
		int diff = compare(s, pat);
		if (diff < smallchange) smallchange = diff;
	}
	cout << smallchange << '\n';
}

Measured memory_bytes: 3144
while True:
    n, k = map(int, input().split())
    if n == 0:
        break
        
    a = [int(input()) for i in range(n)]

    s = [0 for i in range(n+1)]
    # 累積和配列の生成
    for i in range(n):
        s[i+1] = s[i] + a[i]

    ans = -float("inf")
    for i in range(n-k):
        ans = max(ans, s[i+k] - s[i])

    print(ans)


Measured memory_bytes: 13436
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
#include<assert.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long INF = 1LL << 40;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
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(){
  while(1){
    int m,f,r;
    cin >> m >> f >> r;
    if(m==-1 && f==-1 && r==-1){
      break;
    }
    if(m==-1 || f==-1){
      cout << "F" << endl;
      continue;
    }
    if(80 <= m+f){
      cout << "A" << endl;
    }else if(65 <= m+f){
      cout << "B" << endl;
    }else if(50 <= m+f || 50 <= r){
      cout << "C" << endl;
    }else if(30 <= m+f){
      cout << "D" << endl;
    }else{
      cout << "F" << endl;
    }
  }
  return 0;
}



Measured memory_bytes: 3116
#include <stdio.h>
int main(void){
	int i,j,H,W;
	while(1){
		scanf("%d %d",&H,&W);
		if(H==0 && W==0){
			break;
		}
		for(i=1;i<=H;i++){
			for(j=1;j<=W;j++){
				if( (i+j)%2 == 0){
					printf("#");
				}
				else{
					printf(".");
				}			
			}
			puts("");
		}
		puts("");
	}
	return 0;
}

Measured memory_bytes: 588
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

x,y = map(int,input().split())

if (x+y) % 3 == 0 and x <= 2*y and y <= 2*x:
    jump = (x+y)//3
    jump12 = y-jump
    
    print(cmb(jump,jump12,mod))
else:
    print(0)

Measured memory_bytes: 124980