akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include <iostream>
#include <math.h>
#include <climits>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <map> 
#include <set>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MD = 1000000007;

/* sample input

*/

int main()
{

	ll n;
	ll a;
	ll count4 = 0, count2 = 0, count1 = 0;

	cin >> n;
	for (ll i = 0; i < n; i++) {
		cin >> a;
		if (a % 2 == 0) {
			count2++;
			if (a % 4 == 0) {
				count2--;
				count4++;
			}
		}
		else {
			count1++;
		}
	}

	if (n % 2 == 1) {
		if (count1 == (n - 1) / 2 + 1 && count4 == (n - 1) / 2) {
			cout << "Yes";
		}
		else {
			if (count4 >= count1) {
				cout << "Yes";
			}
			else {
				cout << "No";
			}
		}
	}
	else {
		if (count4 >= count1) {
			cout << "Yes";
		}
		else {
			cout << "No";
		}
	}

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>
using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll,ll> pll;
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
#define MOD 1000000007
#define ARRAY_MAX 100005

const int INF = 1e9+7;


int main(){

    double a,b;
    cin >> a >> b;
    printf("%.12f\n",a/b);

    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cmath>

using namespace std;

const int INF = 1e9;

int main() {
  ios::sync_with_stdio(false);
  int n, m, c;
  cin >> n >> m >> c;

  int b[m];
  for (int j=0; j<m; j++) {
    cin >> b[j];
  }
  int cnt = 0;
  for (int i=0; i<n; i++) {
    int tmp = 0;
    for (int j=0; j<m; j++) {
      int aj;
      cin >> aj;
      tmp += b[j] * aj;
    }
    if (tmp + c > 0) {
       ++cnt;
    }
  }
  cout << cnt;

}

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

using ll = long long;
using namespace std;
const int INFint = 2e9+1;
const ll INFll = 2e18+1;
ll MOD=1e9+7;


int main(){
  int N;
  cin>>N;
  vector<int> A(N);
  for(int i(0);i<N-1;i++) cin>>A[i];
  int cnt[200001] = {0};
  for(int i(0);i<N;i++){
    cnt[A[i]]++; 
  }
  for(int i(1);i<=N;i++){
    cout << cnt[i] << endl; 
  }
  return 0;
}



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

using namespace std;

int main(){
	int a, b, c, d;
	cin >> a >> b >> c >> d;

	int left = a + b;
	int right = c + d;
	if (left > right){
		cout << "Left" << endl;
	} else if (left < right){
		cout << "Right" << endl;
	} else {
		cout << "Balanced" << endl;
	}
	
	return 0;
}


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

struct Card {
    char mark;
    int num;
};

void bubbleSort(vector<Card>& ary) {
    for (auto i = 0; i < ary.size(); i++) {
        for (auto j = ary.size()-1; j >= i+1; j--) {
            if (ary[j].num < ary[j-1].num) {
                swap(ary[j], ary[j-1]);
            }
        }
    }
}

void selectionSort(vector<Card>& ary) {
    for (auto i = 0; i < ary.size(); i++) {
        int minj = i;
        for (auto j = i; j < ary.size(); j++) {
            if (ary[j].num < ary[minj].num) {
                minj = j;
            }
        }
        swap(ary[i], ary[minj]);
    }
}

bool isStable(const vector<Card>& ary1, const vector<Card>& ary2) {
    for (auto i = 0; i < ary1.size(); i++) {
        if (ary1[i].mark != ary2[i].mark) {
            return false;
        }
    }
    return true;
}

void printCards(const vector<Card>& ary) {
    for (auto i = 0; i < ary.size(); i++) {
        cout << (i ? " " : "") << ary[i].mark << ary[i].num;
    }
    cout << endl;
}

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

    vector<Card> cards1(n), cards2(n);
    for (int i = 0; i < n; i++) {
        cin >> cards1[i].mark >> cards1[i].num;
    }
    cards2 = cards1;

    bubbleSort(cards1);
    selectionSort(cards2);

    printCards(cards1);
    cout << "Stable" << endl;
    printCards(cards2);
    if (isStable(cards1, cards2)) {
        cout << "Stable" << endl;
    } else {
        cout << "Not stable" << endl;
    }

    return 0;
}

Measured memory_bytes: 1220
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC080A
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, a, b;

            var word = Console.ReadLine().Split(' ');

            n = int.Parse(word[0]);
            a = int.Parse(word[1]);
            b = int.Parse(word[2]);

            if (n * a <= b)
                Console.WriteLine(n * a);

            else if(n * a >= b)
                Console.WriteLine(b);

            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 13140
import java.util.Scanner;

public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int d[];
		d = new int[100]; 
		for(int i=0;i<m;i++)
		{
			int a = sc.nextInt();
			int b = sc.nextInt();
			d[a]++;
			d[b]++;
		}
		for(int i=1;i<=n;i++)
			System.out.println(d[i]);
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<int> snuke(n, 0);
    for (int i = 0; i < k; ++i) {
        int d;
        cin >> d;
        for (int j = 0; j < d; ++j) {
            int a;
            cin >> a;
            a--;
            snuke[a]++;
        }
    }
    int ret = 0;
    for (int i = 0; i < n; ++i) {
        if (snuke[i] == 0)
            ret++;
    }
    cout << ret << "\n";

    return 0;
}

Measured memory_bytes: 3664
import java.awt.Point;
import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static int h, w;
	static int[][] arr;

	public static void main(String[] args) {
		final Scanner sc = new Scanner(System.in);
		while(true) {
			w = sc.nextInt();
			h = sc.nextInt();
			if(w==0&&h==0) break;
			int n = sc.nextInt();
			arr = new int[h + 1][w + 1];
			for (int i = 0; i < n; i++) {
				int x = sc.nextInt(), y = sc.nextInt();
				int x2 = sc.nextInt(), y2 = sc.nextInt();
				arr[y][x]++;
				arr[y2][x2]++;
				arr[y][x2]--;
				arr[y2][x]--;
			}
			for (int i = 0; i <= h; i++) {
				for (int j = 1; j <= w; j++) {
					arr[i][j] += arr[i][j - 1];
				}
			}
			for (int i = 1; i <= h; i++) {
				for (int j = 0; j <= w; j++) {
					arr[i][j] += arr[i - 1][j];
				}
			}
			//show(arr);
			long count = 0L;
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (arr[i][j] == 0) {
						count++;
						bfs(new Point(i, j));
					}
				}
			}
			System.out.println(count);
		}
	}

//	static void show(int[][] a) {
//		System.out.println("\nStart");
//		for (int[] aa : a) {
//			for (int i : aa) {
//				//System.out.print(i == 0 ? "■" : "□");
//				System.out.print(i);
//			}
//			System.out.println();
//		}
//	}

	static void bfs(Point start) {
		ArrayDeque<Point> deq = new ArrayDeque<>();
		deq.offer(start);
		while (!deq.isEmpty()) {
			Point p = deq.poll();
			if(arr[p.x][p.y]!=0) {
				continue;
			}
			arr[p.x][p.y] = 1;
			for (int i = 0; i < 4; i++) {
				if (p.x + dy[i] < 0 || p.x + dy[i] >= h || p.y + dx[i] < 0 || p.y + dx[i] >= w) {
				} else {
					deq.offer(new Point(p.x + dy[i], p.y + dx[i]));
				}
			}
		}
	}
}



Measured memory_bytes: 425448
#include<iostream>
using namespace std;
long long n;
int dfs(long long x,bool A,bool B,bool C){
	if(x>n) return 0;
	long long ret=0;
	if(A&&B&&C) ret++;
	ret+=dfs(x*10+7,true,B,C);
	ret+=dfs(x*10+5,A,true,C);
	ret+=dfs(x*10+3,A,B,true) ;
	return ret;
}
int main()
{
	cin >> n;
	cout << dfs(0,false,false,false)<<endl ;
	return 0;	
}

Measured memory_bytes: 760
// D.

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

using namespace std;

typedef pair<int, int> II;

int main(int argc, char *argv[]) {
	int n, m, a, b, ans = 0;
	cin >> n >> m;
	vector<II> v(m);
	for (int i = 0; i < m; ++i) {
		cin >> a >> b;
		v[i].first = -a;
		v[i].second = b;
	}
	sort(v.begin(), v.end());
	a = b = n + 1;
	for (auto kv : v) {
		int p = -kv.first, q = kv.second;
		if (q >= b) {
			continue;
		}
		if (q > a) {
			b = q;
			continue;
		}
		++ans;
		a = p, b = q;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve() {
   int n;
   cin>>n;
   int arr[n];
   for(int i=0;i<n;++i) cin>>arr[i];
   int sum=0;
   int maxm=arr[0];
   for(int i=1;i<n;++i)
   {
       if(arr[i]>maxm){
           maxm=arr[i];
       }
       else sum+=maxm-arr[i];
   }
   cout<<sum;
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

Measured memory_bytes: 5212
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S, T;
    cin >> S >> T;
    int A, B;
    cin >> A >> B;
    string U; cin >> U;
    if (S == U) cout << A - 1 <<  " " << B << endl;
    else cout << A << " " << B - 1 << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

typedef long long int llint;

llint H, N;

int main() {
	cin >> H >> N;
	llint sum = 0;
	for (int i = 0; i < N; i++) {
		llint A;
		cin >> A;
		sum += A;
	}
	if (sum >= H) { cout << "Yes" << endl; }
	else { cout << "No" << endl; }
}

Measured memory_bytes: 256
#!/usr/bin/env python3
# DPL_1_F: Combinatorial - 0-1 Knapsack Problem II


def max_value(total_weight, items):
    total_value = sum([v for v, _ in items])
    ws = [total_weight+1] * (total_value+1)
    ws[0] = 0

    for item in sorted(items):
        v, w = item
        for i in reversed(range(total_value-v+1)):
            ws[i+v] = min(ws[i+v], ws[i] + w)

    return max([i for i, w in enumerate(ws) if w <= total_weight])


def run():
    n, t = [int(i) for i in input().split()]
    vs = []

    for _ in range(n):
        v, w = [int(i) for i in input().split()]
        vs.append((v, w))

    print(max_value(t, vs))


if __name__ == '__main__':
    run()



Measured memory_bytes: 5924
#include<stdio.h>
int main(void){
  int i;
  char s[100000];
  
  scanf("%s",s);

  for(i=0; s[i]!='\0'; i++){
    if(i%2 == 0){
      printf("%c",s[i]);
    }
  }

  printf("\n");
  
  return 0;
}


Measured memory_bytes: 256
//Author: Fuadul Hasan(fuadul202@gmail.com)
//BSMRSTU,Gopalganj
#include<bits/stdc++.h>
using namespace std;int tc = 1;
#define happy ios::sync_with_stdio(false);
#define coding  cin.tie(0);
#define F first
#define S second
#define mp make_pair
#define ll long long
#define Pi atan(1)*4
#define pb  push_back
#define vpr vector<pr> 
#define pr pair<int, int> 
#define vi std::vector<int>
#define vll std::vector<ll>
#define YES printf("YES\n");
#define NO printf("NO\n");
#define Yes printf("Yes\n");
#define No printf("No\n");
#define all(n) n.begin(),n.end()
#define point(x) setprecision(x)
#define Test printf("Case %d: ",tc++);
#define Unique(c) (c).resize(unique(all(c))-(c).begin())
#define vout(v) for (auto z: v) cout << z << " "; cout << endl;

#define error(args...) {vector<string>_v=split(#args,',');err(_v.begin(),args);cout<<endl;}
vector<string> split(const string &s, char c) {vector<string>v; stringstream ss(s); string x;
while (getline(ss, x, c))v.emplace_back(x); return move(v);} void err(vector<string>::iterator it) {}
template<typename T, typename... Args>void err(vector<string>::iterator it, T a, Args...args) {
cout << it->substr((*it)[0] == ' ', it->length()) << " = " << a << " "; err(++it, args...);}

const int M = 1e9 + 7;
const ll  Inf = (ll)2e18 + 5;
const int N   = 2e5 + 5;
ll vis[N],res[N];

int solve() 
{
	//happy coding

	int n,m,k;
	cin>>n>>m>>k;
	vi a(n),b(m);
	vll rem(n+1);

	for(int i=0;i<n;i++){
		cin>>a[i];
		rem[i+1] = rem[i]+a[i];
	}

	for(int i=0;i<m;i++){
		cin>>b[i];
	}
	ll sum  =0;
	int mx = 0;
	for(int i=0;i<=m&&sum <= k;i++){
		int x = upper_bound(all(rem),k - sum)- rem.begin();
		mx = max(mx,i+x-1);
		sum += b[i];
	}


	cout<<mx<<endl;



	
	return 0;
}
int main(){
	int test = 1;
  	//scanf("%d", &test);
  	while (test--)solve();return 0;
}

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

N, M = list(map(int, input().split()))
x_list = list(map(int, input().split()))
x_list = sorted(x_list)
d_list = [abs(a - b) for a, b in zip(x_list[:-1], x_list[1:])]
d_list = sorted(d_list, reverse=True)

if N >= M:
    ans = 0
else:
    ans = sum(d_list[N-1:])

print(ans)


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

int main() {
  int x;
  cin >> x;
  if (x == 7 || x == 5 || x == 3) cout << "YES" << endl;
  else cout << "NO" << endl;
}


Measured memory_bytes: 256
# https://atcoder.jp/contests/abc052/tasks/arc067_a
# C - Factors of Factorial

N = int(input())

n = 1
for i in range(2, N + 1):
    n = n * i

def get_prime_factor(n):
    from collections import defaultdict
    res = defaultdict(int)
    for i in range(2, n + 1):
        if i * i > n:
            break
        while n % i == 0:
            res[i] = res[i] + 1
            n = n // i
    if n != 1:
        res[n] = 1
    return res

prime_factor = get_prime_factor(n)

factors_count = 1
for count in prime_factor.values():
    factors_count = factors_count * (count + 1)

res = factors_count % (10 ** 9 + 7)
print(res)

Measured memory_bytes: 3316
N = int(input())
A = list(map(int, input().split()))
S = sum(A)
X1 = S - 2 * sum(A[1::2])
ans = [0] * N
ans[0] = X1
for i in range(1, N):
    ans[i] = 2 * A[i - 1] - ans[i - 1]

print(*ans)

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

int main() {
    int N, L;
    cin >> N >> L;
    int favor = (L*2+N-1) * N / 2;
    int a = L, b = L + N - 1;
    if (a * b <= 0) cout << favor;
    else cout << favor - (a > 0 ? L : L + N-1);
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <cmath>
typedef long long ll;
using namespace std;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for (ll i = init; i < (n); i++)

int main()
{
    double a, b, x;
    cin >> a >> b >> x;
    if (a * b / 2 > x / a)
    {
        cout << fixed << setprecision(10) << atan2(a * b * b,2 * x)*180 /M_PI << endl;
    }
    else
    {
                cout << fixed << setprecision(10) << atan2(b - 2 * x / (a * a) + b,a)*180 /M_PI<< endl;
    }
    return 0;
}

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

int main(){
 string S,T;
 cin>>S;
 cin>>T;
 sort(S.begin(),S.end());
 sort(T.begin(),T.end());
 reverse(T.begin(),T.end());
  
 if(S<T)cout<<"Yes";
 else cout<<"No";
  
  
}


Measured memory_bytes: 3092
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef pair<ll, ll> P;


// a と b の最大公約数を返す
ll gcd(ll a, ll b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}


ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}



// 素数判定
bool is_prime(ll N) {
    if (N == 1) return false;
    for (ll i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}


// 約数列挙
vector<ll> enum_divisors(ll N) {
    vector<ll> res;
    for (ll i = 1; i * i <= N; ++i) {
        if (N % i == 0) {
            res.push_back(i);
            if (N/i != i) res.push_back(N/i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}


// 素因数分解
vector<pair<ll, ll>> prime_factorize(ll N){
    vector<pair<ll, ll>> res;
    for(ll i = 2; i * i <= N; i++){
        if(N % i != 0)  continue;
        ll ex = 0;

        while(N % i == 0){
            ex++;
            N /= i;
        }

        res.push_back({i, ex});
    }

    if(N != 1)  res.push_back({N, 1});
    return res;
};


int main(){
    ll n, m;    cin >> n >> m;
    vector<ll> divisors = enum_divisors(m);

    reverse(divisors.begin(), divisors.end());
    for(auto x: divisors){
        if(m / x >= n){
            cout << x << endl;
            return 0;
        }
    }

    return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner in = new java.util.Scanner(System.in);
		//String N = in.nextLine();
		int a = in.nextInt();
		int b = in.nextInt();
		int c = in.nextInt();
		int d = in.nextInt();

		if(Math.abs(a-c) <= d){
			System.out.print("Yes");
		}else if(Math.abs(a-b) <= d && Math.abs(c-b) <= d){
			System.out.print("Yes");
		}else{
			System.out.print("No");
		}
		in.close();
	}
}

Measured memory_bytes: 22996
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int H,W;
class disjoint_union_set{
	private:
		vi rank,p,set_size;
	public:
		disjoint_union_set(int n){
			rank.assign(n,1);p.assign(n,0);set_size.assign(n,1);
			for(int i=0;i<n;i++){
				p[i] = i;
			}
		}
		int find_set(int i){
			return p[i] == i?i:p[i] = find_set(p[i]);
		}
		bool is_same_set(int i,int j){
			return find_set(i) == find_set(j);
		}
		void union_set(int i,int j){
			int x = find_set(i);int y = find_set(j);
			if(is_same_set(i,j))return;
			if(rank[x] < rank[y]){
				p[x] = y;
				set_size[y] += set_size[x];
			}else{
				p[y] = x;
				set_size[x] += set_size[y];
				if(rank[x] == rank[y])rank[y]+=1;
			}
		}
		int no_of_set(int i){
			return set_size[find_set(i)];
		}
		
};	
int encode(int i,int j){
	return i*W + j;
}
pair<int,int> decode(int cod){
	return make_pair(cod/W ,cod%W);
}

int main(){
	
	
	cin>>H>>W;
	char arr2[H][W];

	int flag = 0;
	for(int i=0;i<H;i++){
	for(int j=0;j<W;j++){
		char t;
		cin>>t;
		arr2[i][j] = t;
		
	}
	}

	int count[H][W];
	memset(count,0,sizeof(count));
	disjoint_union_set row_union(5*(int)1e6);
	disjoint_union_set col_union(5*(int)1e6);
	
	for(int i =0;i<H;i++)
		for(int j=0;j<W;j++){
			if( arr2[i][j] == '#')continue;
			if(j&& arr2[i][j-1] != '#')
			row_union.union_set(encode(i,j),encode(i,j-1));
			if(i && arr2[i-1][j]!= '#')
				col_union.union_set(encode(i-1,j),encode(i,j));
		}
	int maxno = 0;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(arr2[i][j] == '#'){
				count[i][j] = -1000000;
				continue;
			}else{
				count[i][j] += row_union.no_of_set(encode(i,j))+col_union.no_of_set(encode(i,j))-1;
				maxno = max(maxno,count[i][j]);
			}
		}
	}
	
	// for(int j =0;j<W;j++)
		// for(int i=0;i<H;i++){
			// if(!i || arr2[i][j] == '#')continue;
			// if(arr2[i-1][j]!= '#')
			// col_union.union_set(encode(i-1,j),encode(i,j));
		// }
	
	// for(int i=0;i<H;i++){
		// for(int j=0;j<W;j++){
			// if(arr2[i][j] == '#'){
				// count[i][j] = -1000000;
				// continue;
			// }else{
				
				// count[i][j]+= col_union.no_of_set(encode(i,j))-1;
				
				// maxno = max(maxno,count[i][j]);
			// }
		// }
	// }
	cout<<maxno<<endl;
	return 0;
}

Measured memory_bytes: 136960
S = input().strip()
K = int(input())
N = len(S)
def cmb(n, r):
    nn = n
    rrr = r
    rr = 1
    for i in range(r):
        rr *= n
        n -= 1
    for i in range(r):
        rr //= r
        r -= 1
#    print(nn, rrr, rr)
    return rr

d = dict()
def f(k, i):
    if (k, i) in d:
        return d[(k, i)]
    if i == N:
        if k==0:
            return 1
        else:
            return 0
    dd = int(S[i])
    if k!=0:
        if dd == 0:
            rn = 0
            rm = 0
            r0 = f(k, i+1)
        else:
            rn = (dd-1)*cmb(N-i-1, k-1)*(9**(k-1))
            rm = f(k-1, i+1)
            r0 = cmb(N-i-1, k)*(9**k)
    else:
        rn = 0
        rm = 0
        r0 = f(k, i+1)
    d[(k,i)] = rm+rn+r0
#    print(k,i,rm,rn,r0)
    return rm + rn + r0

print(f(K, 0))


Measured memory_bytes: 38384
/*
 * I wish I could travel by the road that crosses baby's mind,
 * and out beyond all bounds;
 * Where messengers run errands for no cause 
 * between the kingdoms of kings of no history;
 * Where Reason makes kites of her laws and flies them, 
 * and Truth sets Fact free from its fetters.
 *                                         Rabindranath Tagore
 */

#include <cstdio>
#include <cstring>

#ifndef ORZ_EVERYBODY
#define ORZ_EVERYBODY
#endif

const size_t MAX_N = 5e5 + 5;

int dp[MAX_N], up[MAX_N];
char str[MAX_N];

template <typename T>
inline void updMin(T& x, const T& val) {
    if (!(~x) || val < x) x = val;
}

int main() {
    int n, cnt = 0;
    scanf("%d%s", &n, str);
    up[n] = n;
    for (int i = n - 1; i >= 0; --i)
        if (str[i] == '1') {
            ++cnt;
            up[i] = up[i + 1];
        } else {
            up[i] = i;
        }
    memset(dp, -1, sizeof dp);
    dp[0] = 0;
    for (int i = 0; i < n; ++i)
        if (str[i] == '0') {
            updMin(dp[i + 1], dp[i]);
        } else {
            updMin(dp[i + 1], dp[i] + 1);
            if (str[up[i] + 1] == '1') 
                updMin(dp[up[i] + 2], dp[i] + 1);
            if (up[i] == i + 1) 
                for (int j = i + 2; j <= n; ++j) {
                    if ((str[j] - '0')) updMin(dp[j + 1], dp[i] + 1); 
                    else break;
                }
        }
    return printf("%d\n", cnt - dp[n]), 0;;
}


Measured memory_bytes: 4608
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=998244353;
const LL LINF=1LL<<60;
const int INF=1<<20;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

int G[201][201];
int s[201];
int n;

bool dfs(int u,int f){
    if(~s[u]){
        return s[u] != f;
    }
    s[u] = f;
    bool ret = false;
    for (int i = 0; i < n; i++) {
        if(!G[u][i]) continue;
        int to = i;
        ret |= dfs(to,f^1);
    }
    return ret;
}


int main(){
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;cin >> s;
        for (int j = 0; j < n; j++) {
            G[i][j] = s[j] -'0';
        }
    }
    memset(s,-1,sizeof(s));
    if(dfs(0,0)){
        puts("-1");
        return 0;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(!G[i][j]) G[i][j] = INF;
        }
        G[i][i] = 0;
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                G[i][j] = min(G[i][j],G[i][k] + G[k][j]);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans, G[i][j]);
        }
    }
    cout << ans + 1 << endl;
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>
#include <random>
#include <vector>
#include <unordered_map>
#include <bitset>

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

LL mod = 1000000007;

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

  LL A,B,C;
  cin >> A >> B >> C;
  if(A==B&&B==C){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c, d, l, r;
  cin >> a >> b >> c >> d;
  l = a + b;
  r = c + d;
  if (l > r) {
    cout << "Left" << endl;
  }
  else if (l < r) {
    cout << "Right" << endl;
  } 
  else {
    cout << "Balanced" << endl;
  }
}


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

const int N = 1e5 + 100;

int n, W;
long long w[N], v[N], dp[200][N];


int main(){
    # ifdef FILEs
        freopen( "input.txt", "r" ,stdin );
        freopen( "output.txt", "w", stdout );
    # endif
    ios_base::sync_with_stdio(false);
    cin >> n >> W;
    for( int i = 1; i <= n; i ++ ){
        cin >> w[i] >> v[i];
    }
    for( int i = 1; i <= n; i ++ ){
        for( int j = 1; j <= W; j ++ ){
            dp[i][j] = dp[i-1][j];
            if( j >= w[i] ){
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
            }
        }
    }
    cout << dp[n][W];
}   

Measured memory_bytes: 81408
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

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

    rep(i, s.size()) {
        s[i] = (s[i] - 'A' + n)%26 + 'A';
    }

    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a, b, c, n, cnt;
int main() {
    cin >> a >> b >> c >> n;
    for (int i = 0; i <= a; i++) {
        for (int j =0 ; j <= b; j++) {
            if ((n - i * 500 - j * 100 >= 0) 
            && (n - i * 500 - j * 100 <= c * 50)) {
                cnt++;
            }
        }
    }
    cout << cnt;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
set<int> ans;
int n,a[10005],prime[10005],cnt,vis[10005];
bool Test(int x,int mod){
	int sum=0;
	for(int i=0;i<=n;++i)
		sum=1ll*sum*x%mod+a[i],
		sum=(sum+mod)%mod;
//	cout<<x<<" "<<mod<<" "<<sum<<endl;
	return sum==0;
}
void test(int p){
//	cout<<p<<endl;
	int T=20;
	while(T--){
		int tmp=1ll*rand()*rand()%1000000000+1;
		if(Test(tmp,p)==0) return;		
	}
	ans.insert(p);
}
void print(int x){
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
int rd(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) f=(ch=='-'?-1:f),ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}
signed main(){
//	freopen("11.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	cin>>n;int tmp=0;
	for(int i=0;i<=n;++i)
		a[i]=rd(),tmp=__gcd(tmp,abs(a[i]));
	for(int i=2;i*i<=tmp;++i)
		if(tmp%i==0) ans.insert(i),tmp/=i;
	if(tmp>1) ans.insert(tmp);
	for(int i=2;i<=n;++i)
		if(!vis[i]){
			prime[++cnt]=i;
			for(int j=i+i;j<=n;j+=i)
				vis[j]=1;
		}
	for(int i=1;i<=cnt;++i)
		test(prime[i]);
	for(auto v:ans) print(v),puts("");
	return 0;
}

Measured memory_bytes: 3656
#include<bits/stdc++.h>
#define l(a)std::lower_bound(B,B+n,a-A)
int n,a[2<<18],B[1<<18],s,A,i=1,j,L;main(){for(;std::cin>>(n?a[A++]:n););for(;i<1<<29;i*=2){for(j=0;j<n;)B[j]=a[n+j++]%(i*2);for(std::sort(B,B+n);j--;s^=(a[j]&i?n-L:L)%2*i)A=a[j]%i,L=l(i*2)-l(i);}std::cout<<s;}

Measured memory_bytes: 2688
#include <iostream>
#include<iomanip>
#include <cmath>
#include <climits>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <queue>
#include <tuple>
#include <map>
#include <list>
#include <string>
#include <numeric>
#include <utility>
#include <cfloat>

using namespace std;
int A[100000];
int B[100000];
int C[100000];
long long ans_num[100000];
int main(){
    int N;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    for(int i = 0; i < N; i++){
        cin >> B[i];
    }
    for(int i = 0; i < N; i++){
        cin >> C[i];
    }

    sort(A, A + N);
    sort(B, B + N);
    sort(C, C + N);

    ans_num[N - 1] = C + N - upper_bound(C, C + N, B[N - 1]);
    for(int i = N - 2; i >= 0; i--){
        ans_num[i] = (C + N - upper_bound(C, C + N, B[i])) + ans_num[i + 1];
    }

    long long ans = 0;
    for(int i = 0; i < N; i++){
        long long ans_num_ind = upper_bound(B, B + N, A[i]) - B;
        if(ans_num_ind >= N){
            continue;
        }
        ans += ans_num[upper_bound(B, B + N, A[i]) - B];
    }

    cout << ans << endl;

    return 0;
}

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

int main(){
  int a,b,c;
  cin >>a>>b>>c;
  
  int ans;
  if(a==b && b==c) ans = 1;
  else if((a!=b)&&(a!=c)&&(c!=b)) ans = 3;
  else ans = 2;
  
  cout <<ans<< endl;
}

Measured memory_bytes: 256
#include <vector>
#include <complex>
#include <iomanip>
#include <iostream>
using namespace std;
typedef complex<double> Point;
bool intersect(Point p1, double r1, Point p2, double r2) {
	double d = abs(p1 - p2);
	if (d < abs(r1 - r2)) return false;
	if (d > r1 + r2) return false;
	return true;
}
Point crosspoint(Point p1, double r1, Point p2, double r2) {
	double c = (r1 * r1 + norm(p1 - p2) - r2 * r2) / (2.0 * r1 * abs(p1 - p2));
	return p1 + (p2 - p1) / abs(p1 - p2) * r1 * Point(c, sqrt(1.0 - c * c));
}
int n; double x[109], y[109], v[109];
int main() {
	while (cin >> n, n) {
		for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> v[i];
		double l = 0.0, r = 1000.0;
		for (int i = 0; i < 50; i++) {
			double m = (l + r) * 0.5;
			bool flag = false;
			for (int j = 0; j < n; j++) {
				bool ok = true;
				for (int k = 0; k < n; k++) {
					if (abs(Point(x[k] - x[j], y[k] - y[j])) > v[k] * m + 1.0e-7) ok = false;
				}
				if (ok) flag = true;
			}
			for (int j = 0; j < n; j++) {
				for (int k = j + 1; k < n; k++) {
					if (intersect(Point(x[j], y[j]), v[j] * m, Point(x[k], y[k]), v[k] * m)) {
						Point p1 = crosspoint(Point(x[j], y[j]), v[j] * m, Point(x[k], y[k]), v[k] * m);
						Point p2 = crosspoint(Point(x[k], y[k]), v[k] * m, Point(x[j], y[j]), v[j] * m);
						bool ok1 = true, ok2 = true;
						for (int l = 0; l < n; l++) {
							if (abs(Point(x[l], y[l]) - p1) > v[l] * m + 1.0e-7) ok1 = false;
							if (abs(Point(x[l], y[l]) - p2) > v[l] * m + 1.0e-7) ok2 = false;
						}
						if (ok1 || ok2) flag = true;
					}
				}
			}
			if (flag) r = m;
			else l = m;
		}
		cout << fixed << setprecision(10) << l << endl;
	}
	return 0;
}

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

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

int main() {
  int64_t N, K, amari,ans;
  cin >> N >> K;
  if (N<K) cout << min(N, K-N) << endl;
  else if(N==K) cout << 0 << endl;
  else {
    amari = N%K;
    ans = min(amari, max(amari,K)-min(amari,K));
    cout << ans << endl;
  }
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll mod(ll a){
  return a % MOD;
}

ll lcm(ll a,ll b){
  return (a*b)/gcd(a,b);
}

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll nCrcheep(ll n,ll r){
  if(r == 0) return 1;
  else if(r == 1) return n;
  else return nCrcheep(n-1,r-1)*n/r;
}

vector<pair<ll,ll>> prime_factorize(ll n){
  vector<pair<ll,ll>> res;
  
  for(ll i=2; i*i <= n; i++){
    if(n % i != 0) continue;
    
    ll ex = 0;
    while(n % i == 0){
      ex++;
      n /= i;
    }
    
    res.push_back({i,ex});
  }
  
  if(n != 1) res.push_back({n,1});
  
  return res;
  
}




int main(){
  ll n; cin >> n;
  
  ll power = 1;
  
  for(ll i=1; i <= n; i++){
    power *= i;
    power = mod(power);
  }
  
  cout << power << endl;
  
  
}

Measured memory_bytes: 3640
package main

import "fmt"

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

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

	var count, flag int

	for {
		for i, v := range a {
			if v%2 != 0 {
				flag++
				break
			}
			a[i] /= 2
		}
		if flag > 0 {
			break
		}
		count++
		// fmt.Println(a)
		// fmt.Println(count)
	}
	fmt.Println(count)
}


Measured memory_bytes: 512
#include <cstdio>
#include <cstdlib>
#include <cstring>
struct Node{
    int key;
    Node *next, *prev;
};

Node *nil;

Node *listSearch(int key){
  Node *cur = nil->next;
  while (cur != nil && cur->key != key){
    cur = cur->next;
  }
  return cur;
}

void init(){
  nil = (Node *)malloc(sizeof(Node));
  nil->next = nil;
  nil->prev = nil;
}

void printList(){
  Node *cur = nil->next;
  int isf = 0;
  while (1){
    if(cur == nil) break;
    if(isf++ > 0) printf(" ");
    printf("%d", cur->key);
    cur = cur->next;
  }
  printf("\n");
}

void deleteNode(Node *t){
  if(t == nil)return;
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

void deleteFirst(){
  deleteNode(nil->next);
}

void deleteLast(){
  deleteNode(nil->prev);
}

void deleteKey(int key){
  deleteNode(listSearch(key));
}

void insert(int key){
  Node *x = (Node *)malloc(sizeof(Node));
  x->key = key;
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}

int main(){
  int key, n, i;
  int size = 0;
  char com[20];
  int np = 0, nd = 0;
  scanf("%d", &n);
  init();
  for(i = 0; i < n; i++){
    scanf("%s%d", com, &key);
    if(com[0] == 'i'){
      insert(key);
      np++;
      size++;
    } else if(com[0] == 'd'){
      if(strlen(com) > 6){
        if(com[6] == 'F') deleteFirst();
        else if(com[6] == 'L') deleteLast();
      } else{
        deleteKey(key);
        nd++;
      }
      size--;
    }
  }

  printList();

  return 0;
}



Measured memory_bytes: 33992
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CStrangeBank solver = new CStrangeBank();
        solver.solve(1, in, out);
        out.close();
    }

        static int[] DP = new int[100000 + 1];
    static class CStrangeBank {
        static final int[] C6 = {6, 36, 216, 1296, 7776, 46656};
        static final int[] C9 = {9, 81, 729, 6561, 59049};
        int[] m;

        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            m = new int[n + 1];
            out.println(min(n));
        }

        int min(int n) {
            if (n == 0) {
                return 0;
            }
          if(DP[n]!=0){return DP[n];}
            int min = Integer.MAX_VALUE;
            for (int i = C6.length - 1; i >= 0; i--) {
                if (n >= C6[i]) {
                    min = Math.min(min, min(n - C6[i]) + 1);
                    //break;
                }
            }
            for (int i = C9.length - 1; i >= 0; i--) {
                if (n >= C9[i]) {
                    min = Math.min(min, min(n - C9[i]) + 1);
                    //break;
                }
            }
            min = Math.min(min,  min(n - 1) + 1);
          return DP[n]=min;
        }

    }
}



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

#define ll long long
#define ld long double
#define fi first
#define se second
#define pi 3.1415926535
#define mod1 1000000007
#define mod2 1000000009
#define no_of_digits(n) floor(log10(n)) + 1
#define lcm(a, b) (a/__gcd(a,b)*b

using namespace std;


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

  int n;
  cin >> n;
  map<string, int> m;
  int mx = 0;
  string s;
  for(int i = 0; i < n; i++){
    cin >> s;
    m[s]++;
    mx = max(m[s], mx);
  }
  for(auto it:m){
    if(it.second == mx){
      cout << it.first << '\n';
    }
  }
  return 0;
}

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

int main()
{
    int n;
    cin >> n;
    if (n >= 30) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3632
#include "bits/stdc++.h"
using namespace std;
int N; double p, dp[3000][3000], ans;
int main(){
    scanf("%d", &N); dp[0][0] = 1.0;
    for(int i=1; i<=N; i++){
        scanf("%lf", &p);
        dp[i][0] = dp[i-1][0] * (1-p);
        for(int j=1; j<=i; j++){
            dp[i][j] = dp[i-1][j-1]*p + dp[i-1][j]*(1-p);
        }
    }
    for(int i=N; i>N/2; i--) ans += dp[N][i];
    printf("%.9f\n", ans);
}

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

int main () {
	long long a, b;
	int k;
	cin >> a >> b >> k;

	for (int i = 1; i <= k; i++) {
		if (i % 2 == 1) {
			if (a % 2 == 1) {
				a--;
				a = a / 2;
				b += a;
			} 
			else {
				a = a / 2;
				b += a;
			}
		}
		
		if (i % 2 == 0) {
			if (b % 2 == 1) {
				b--;
				b = b / 2;
				a += b;
			}
			else {
				b = b / 2;
				a += b;
			}
		}
	}
	cout << a << " " << b << endl;
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  map<ll, int> m;
  for (int i = 0; i < n; i++) {
    if (m.count(a[i]) == 0) m[a[i]] = 0;
    m[a[i]]++;
  }

  ll ans(0);
  for (auto e : m)
    if (e.second % 2 != 0) ans++;

  cout << ans << endl;
}


Measured memory_bytes: 10384
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <algorithm>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <math.h>
#include <stdio.h>
#include <tuple>

#define rep(i,m,n) for(int i=(m);i<(n);++i)
#define rem(i,m,n) for(int i=(m);i>(n);--i)
#define MOD 1000000007

using namespace std;

using ll = long long int;
using std::swap;

vector<int> v;
vector<long long int> vll;
vector<long long int> w;
vector<vector<int>> vec(50,vector<int>(4,0));




int main() {
	int N, K;
	int ans = 0;
	cin >> N >> K;
	v.resize(N,0);
	rep(i, 0, K) {
		int d;
		cin >> d;

		rep(j, 0, d) {
			int A;
			cin >> A;
			++v[A-1];
		}
	}
	rep(i, 0, N) {
		if (v[i] == 0)++ans;
	}
	cout << ans << '\n';

	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B,L,R;
string S,T;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

typedef vector<P> vp;
typedef vector<vp> matP;

int main() {
    cin>>N>>S;
    ll temp = 0, ans = 1;
    rep(i,N*2){
        if((temp + (S[i] == 'W'))&1){
            if(temp == 0){
                cout<<0<<endl;
                return 0;
            }else{
                (ans *= temp)%=MOD;
                --temp;
            }
        }else{
            ++temp;
        }
    }
    reps(i,1,N+1){
        (ans *= i)%=MOD;
    }
    cout<<((temp == 0) ? ans : 0)<<endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int X;
	cin>>X;
	vector<bool> expo(X+1);
	expo[1]=1;
	for (int b=2;b<=32;b++)
	{
		int v=b*b;
		while (v<=X)
		{
			expo[v]=1;;
			v*=b;
		}
	}
	for (int i=X;i>=1;i--)
	{
		if (expo[i])
		{
			cout<<i<<endl;
			return 0;
		}
	}
}

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int x[6];
	for(int i = 1; i <= 5; i++){
		cin >> x[i];
		if (x[i] == 0){
			cout << i << '\n';
			return 0;
		}
	}

	return 0;
}

Measured memory_bytes: 3648
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

// Acknowledgement: Special thanks to kyomukyomupurin, who developed this
// template.
template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
  return os << '(' << p.first << ", " << p.second << ')';
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  int n = 0;
  for (auto e : vec) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& st) {
  int n = 0;
  for (auto e : st) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) {
  int n = 0;
  for (auto e : mp) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
  for (T& e : vec) is >> e;
  return is;
}

#ifdef LOCAL
#define debug(...) \
  std::cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}
using namespace std;
using int64 = long long;

int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  cin >> v;
  map<int, int> mp_even;
  map<int, int> mp_odd;
  mp_even[-1] = 0;
  mp_odd[-1] = 0;
  // even
  for (int i = 0; i < n; i += 2) {
    if (mp_even.count(v[i])) {
      mp_even[v[i]]++;
    } else {
      mp_even[v[i]] = 1;
    }
  }
  vector<pair<int, int>> v_even(mp_even.begin(), mp_even.end());
  sort(v_even.begin(), v_even.end(), [](const auto& x, const auto& y) {
    if (x.second == y.second)
      return x.first > y.first;
    else
      return x.second > y.second;
  });

  // odd
  for (int i = 1; i < n; i += 2) {
    if (mp_odd.count(v[i])) {
      mp_odd[v[i]]++;
    } else {
      mp_odd[v[i]] = 1;
    }
  }
  vector<pair<int, int>> v_odd(mp_odd.begin(), mp_odd.end());
  sort(v_odd.begin(), v_odd.end(), [](const auto& x, const auto& y) {
    if (x.second == y.second)
      return x.first > y.first;
    else
      return x.second > y.second;
  });

  debug(v_even);
  debug(v_odd);

  if (v_even[0].first != v_odd[0].first) {
    cout << n - v_even[0].second - v_odd[0].second << endl;
  } else {
    cout << n - max(v_even[0].second + v_odd[1].second,
                    v_even[1].second + v_odd[0].second)
         << endl;
  }
  return 0;
}

Measured memory_bytes: 9040
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
#include <iomanip>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
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; }
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

#define MAX_N 10
int n;
pair<int, int> p[MAX_N];

void input() {
  cin >> n;
  rep(i, 0, n) {
    int x, y;
    cin >> x >> y;
    p[i] = make_pair(x, y);
  }
}

long double dis(int sx, int sy, int ex, int ey) {
  return sqrt(pow(ex - sx, 2) + pow(ey - sy, 2));
}

int kaijo(int n) {
  int rsl = 1;
  rep(i, 1, n + 1) rsl *= i;
  return rsl;
}

void solve() {
  int array[n];
  rep(i, 0, n) array[i] = i;
  long double rsl = 0;
  do {
    rep(i, 1, n) {
      int sx = p[array[i - 1]].first, sy = p[array[i - 1]].second;
      int ex = p[array[i]].first, ey = p[array[i]].second;
      rsl += dis(sx, sy, ex, ey);
    }
  }while(next_permutation(array, array + n));
  rsl /= kaijo(n);
  cout << fixed << setprecision(10) << rsl << endl;
}

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

  input();
  solve();
}



Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){

    char a, b;
    cin >> a >> b;

    if(a == 'H'){
        cout << (b == 'H' ? 'H' : 'D') << endl;
    }else{
        cout << (b == 'H' ? 'D' : 'H') << endl;
    }
    
    return 0;
}


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

const int maxn = 1000;
int n, k, c[maxn + 3], a[maxn + 3][maxn + 3];

int main() {
	scanf("%d", &k);
	if (k == 1) {
		puts("1\n1");
		return 0;
	}
	n = (((k - 1) >> 2) + 1) << 1;
	for (int i = 0; i < n * 2; i++) {
		c[i] = i;
	}
	for (int i = n * 2 - 1; i >= k; i--) {
		c[i] -= n;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (~i & 1) {
				a[i][j] = c[(i + j) % n];
			} else {
				a[i][j] = c[(i + j) % n + n];
			}
		}
	}
	printf("%d\n", n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("%d%c", a[i][j] + 1, " \n"[j == n - 1]);
		}
	}
	return 0;
}

Measured memory_bytes: 3200