akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#define XYMAX 1000000000
using namespace std;

int greatestCommonDivisor(int x, int y) {
    int gcd;
    if ( x < y ) swap(x, y);
    if ( x % y == 0 ) {
        gcd = y;
    } else {
        gcd = greatestCommonDivisor(y, x % y);
    }
    return gcd;
}

int main() {
    // input
    int x, y;
    cin >> x >> y;
    
    // solve
    int gcd;
    gcd = greatestCommonDivisor(x, y);

    // output
    cout << gcd << endl;
}


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

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = long.Parse(Console.ReadLine());
            var A = Console.ReadLine().Split().Select(long.Parse).ToArray();
            var B = Console.ReadLine().Split().Select(long.Parse).ToArray();

            var total = 0L;
            for (var i = 0; i < N; i++)
            {
                if (B[i] - A[i] >= 0)
                {
                    total += A[i];
                    B[i] -= A[i]; 
                    if (B[i] - A[i + 1] >= 0)
                    {
                        total += A[i + 1];
                        A[i + 1] = 0;
                    }
                    else
                    {
                        total += B[i];
                        A[i + 1] -= B[i];
                    }
                }
                else total += B[i];
            }
            Console.WriteLine(total);
        }
    }
}


Measured memory_bytes: 39984
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
typedef long long int ll;
using namespace std;
#define P 1000000007
#define rep(i,n) for(i=0;i<n;++i)
#define repp(i,a,n) for(i=a;i<n;++i)
#define repr(i,a,n) for(i=a;i>n;--i)

ll binpowmod(ll a, ll b, ll m) {
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

ll binpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

ll modInverse(ll n, ll p)
{
    return binpowmod(n, p-2, p);
}
ll variance(ll a[], ll n) 
{ 
    // Compute mean (average of elements) 
    ll sum = 0; 
    for (int i = 0; i < n; i++) 
        sum += a[i]; 
    double mean = (double)sum /  
                  (double)n; 
  
    // Compute sum squared  
    // differences with mean. 
    double sqDiff = 0; 
    for (int i = 0; i < n; i++)  
        sqDiff += (a[i] - mean) *  
                  (a[i] - mean); 
    return sqDiff / n; 
} 

double standardDeviation(ll arr[],  
                         ll n) 
{ 
    return sqrt(variance(arr, n)); 
}

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t,n,k,j,i;
    ll sum=0;
    cin >> n ;
    ll c[n];
    rep(i,n) cin >> c[i];
    ll ans=INT_MAX;
    for(i=1;i<=100;++i)
    {
        ll temp=0;
        for(j=0;j<n;++j)
        {
            temp+=pow((c[j]-i),2);
        }
        if(temp<ans) ans=temp;
    }
    cout << ans ;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int n,i,j,tmp;
    
    scanf("%d",&n);
    for(i=0;i<n;i++){
        tmp=i+1;
        for(j=0;j<4;j++){
            if((i+1)%3==0){
                printf(" %d",i+1);
                break;
            }else if(tmp%10==3){
                printf(" %d",i+1);
                break;
            }
            tmp=tmp/10;
        }if(i==n-1){
            printf("\n");
        }
    }
    
    return 0;
}

Measured memory_bytes: 600
n = int(input())
data=[]
for i in range(0,n):
    x, y, h = map(int,input().split())
    data.append((x,y,h))
data = sorted(data,key=lambda x:x[2],reverse=True)
st_x, st_y, st_h = data[0]
 
 
def get_search_area(x,y,n):
    area_list=[]
    for i in range(-n,n+1):
        for j in range(-n,n+1):
            if abs(i) == n or abs(j) == n:
                xi = x+i
                yi = y+j
                if 0<= xi <= 100 and 0 <= yi <= 100:
                    area_list.append((x+i, y+j, abs(i)+abs(j) ))
    return area_list
 
def meets_all_conditions(top, top_h,data):
    top_x, top_y, top_z = top
    top_h += top_z
    for item in data:
        pt_x, pt_y, pt_h = item
        tmp = max(top_h - abs(pt_x - top_x) - abs(pt_y - top_y), 0)       
        if pt_h != tmp:
            #print(pt_h, tmp ,"False")
            return False    
    #print("True")
    return True
    
def main():    
    for i in range(200):
        #print(i)
        a = get_search_area(st_x,st_y,i)
        #print(a)
        for item in a:
            if meets_all_conditions(item, st_h , data):
                print("{} {} {}".format(item[0],item[1],st_h+item[2]))
                return
    return
main()

Measured memory_bytes: 3064
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A[] = new int[N + 2];
		int sum = 0;
		A[0] = 0;
		for(int i = 1; i <= N; i++) {
			A[i] = sc.nextInt();
			sum = sum + Math.abs(A[i] - A[i - 1]);
		}
		A[N + 1] = 0;
		sum += Math.abs(A[N + 1] - A[N]);
		
		for(int i = 1; i <= N; i++) {
			System.out.println(sum - Math.abs(A[i] - A[i - 1]) - Math.abs(A[i] - A[i + 1]) + Math.abs(A[i - 1] - A[i + 1]));
		}
	}
}


Measured memory_bytes: 67848
import math

A = list(map(int, input().split()))

a = A[0]
b = A[1]
x = A[2]

if x > a*a*b/2:
    c = 2*x/(a*a)-b
    print(math.degrees(math.atan((b-c)/a)))
else:
    d = 2*x/(a*b)
    print(math.degrees(math.atan(b/d)))

Measured memory_bytes: 3188
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <utility>
#include <random>
#include <chrono>

using namespace std;

#define ll long long

char s[200005];
int suf[200005];
ll freq[2050];

int main()
{
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    int curpwr = 1;
    freq[0]++;
    for (int i = n; i >= 1; i--) {
        suf[i] = (curpwr * (s[i] - '0') + suf[i+1]) % 2019;
        curpwr *= 10; curpwr %= 2019;
        freq[suf[i]]++;
    }
    ll ans = 0;
    for (int i = 0; i < 2019; i++) {
        ans += (freq[i] * (freq[i] - 1LL)) / 2LL;
    }
    printf("%lld", ans);
    return 0;
}


Measured memory_bytes: 4704
#include<bits/stdc++.h>
using namespace std;
const int INF = 999999999;
int dp[100001];
int frog(int arr[], int n){
    if(n<0) return INF;
    if(n==0) return 0;
    if(dp[n] != -1)
        return dp[n];
    else if(n==1)
        dp[n] = abs(arr[1] - arr[0]);
    else if(n>=2)
        dp[n] = min(abs(arr[n]-arr[n-1])+frog(arr,n-1), abs(arr[n]-arr[n-2])+frog(arr,n-2));
    return dp[n];
}
int main(){
    int n; cin>>n;
    int arr[n];
    memset(dp, -1, sizeof dp);
    for(int i=0; i<n; i++)
        cin>>arr[i];
    int a  = frog(arr,n-1);
    cout<<a;
}

Measured memory_bytes: 4992
#include <stdio.h>

const int N = 300005;
int n, L, p[N];

int main() {
	scanf("%d%d", &n, &L);
	for (int i = 1; i <= n; ++i) scanf("%d", p + i);
	int x = 0, y = 0;
	long long ans = n + 1;
	for (int i = 1, t; i <= n; ++i) {
		scanf("%d", &t);
		ans += (t - 1) / (2 * L);
		t -= (t - 1) / (2 * L) * (2 * L);
		bool l = t <= 2 * p[i], r = t <= 2 * (L - p[i]);
		if (i == n) {
			if (r) --ans;
			continue;
		}
		if (r) {
			if (l) ++y;
			if (x) --x, --ans;
			else if (y) --y, ++x;
		} else if (l) ++x;
	}
	printf("%lld\n", 2 * L * ans);
	return 0;
}


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

int main()
{
	int N;
	scanf("%d", &N);
	std::vector<int64_t> A(N);
	for (auto& e: A) scanf("%lld", &e);
	std::sort(A.begin(), A.end());
	if (A.front() >= 0)
	{
		int64_t sum{};
		for (int i{1}; i < N; i++)
			sum += A[i];
		sum -= A.front();
		printf("%lld\n", sum);
		sum = A.front();
		for (int i{1}; i < N - 1; i++)
		{
			printf("%lld %lld\n", sum, A[i]);
			sum -= A[i];
		}
		printf("%lld %lld\n", A.back(), sum);
	}
	else if (A.back() <= 0)
	{
		int64_t sum{};
		for (int i{}; i < N - 1; i++) sum -= A[i];
		sum += A.back();
		printf("%lld\n", sum);
		sum = A.back();
		for (int i{}; i < N - 1; i++)
		{
			printf("%lld %lld\n", sum, A[i]);
			sum -= A[i];
		}
	}
	else
	{
		int64_t sum{};
		for (auto& e: A) sum += std::abs(e);
		printf("%lld\n", sum);
		int64_t nega{A.front()}, pos{A.back()};
		for (int i{1}; i < N - 1; i++)
		{
			if (A[i] < 0)
			{
				printf("%lld %lld\n", pos, A[i]);
				pos -= A[i];
			}
			else
			{
				printf("%lld %lld\n", nega, A[i]);
				nega -= A[i];
			}
		}
		printf("%lld %lld\n", pos, nega);
	}

	return 0;
}


Measured memory_bytes: 2688
S = input()
ans = 'Yes'
for i, s in enumerate(S):
  if i % 2 == 0:
    if not s in set(['R','D','U']):
      ans = 'No'
      break
  else:
    if not s in set(['L','D','U']):
      ans = 'No'
      break
print(ans)

Measured memory_bytes: 38352
n,x,y = map(int, input().split())

ans = [0] * n

for i in range(1, n):
    for j in range(i + 1, n + 1):
        ans[min(j - i, abs(i - x) + abs(j - y) + 1)] += 1

for i in range(1, n):
    print(ans[i])

Measured memory_bytes: 46684
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <assert.h>
#include <memory.h>
#include <queue>
#include <string.h>
using namespace std;

#define N 100005

vector<int> adj[N];

int P[N];
bool hasValue[N];
int maxi[N],mini[N],myParent[N];
int dfsOrd[N], dfsPos = 0;

bool dfs(int node,int parent) {
  int parity;
  if(hasValue[node]) {
    maxi[node] = mini[node] = P[node];
    parity = P[node]&1;
  }
  dfsOrd[dfsPos++] = node;
  int sz = adj[node].size();
  for(int i=0;i<sz;++i) {
    int ch = adj[node][i];
    if(ch==parent) continue;
    if(!dfs(ch,node)) {
      return false;
    }
    if(!hasValue[ch]) {
      continue;
    } else {
      int tmpParity = maxi[ch]%2 ==0 ? 1 : 0;
      if(hasValue[node]) {
        if(tmpParity!=parity) {
          return false;
        }
        maxi[node] = min(maxi[node],maxi[ch]+1);
        mini[node] = max(mini[node],mini[ch]-1);
      } else {
        maxi[node] = maxi[ch] + 1;
        mini[node] = mini[ch] -1;
      }
      parity = tmpParity;
      hasValue[node] = true;
    }
  }
  if(mini[node]>maxi[node]) {
    return false;
  }
  return true;
}
int ret[N];
void construct(int node,int parent,int value) {
  ret[node] = value;
  for(int i=0;i<adj[node].size();++i) {
    int ch = adj[node][i];
    if(ch==parent) continue;
    if(!hasValue[ch]) {
      construct(ch,node,value-1);
    } else {
      int tmp = value-1;
      if(mini[ch]<=tmp && tmp<=maxi[ch]) {
        construct(ch,node,tmp);
      } else {
        construct(ch,node,tmp+2);
      }
    }
  }
}
void solve() {
  int n;scanf("%d ", &n);
  for(int i=0;i<n-1;++i) {
    int a,b;scanf("%d %d ", &a,&b);
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  int k;scanf("%d ",&k);
  int root = -1;
  for(int i=0;i<k;++i) {
    int num,v;
    scanf("%d %d ", &v,&num);
    P[v] = num;
    hasValue[v] = true;
    root = v;
  }
  assert(root!=-1);
  if(!dfs(root,0)) {
    printf("No\n");
    return;
  }
  construct(root,0,P[root]);
  printf("Yes\n");
  for(int i=1;i<=n;++i) {
    printf("%d\n", ret[i]);
  }
}

int main() {
  //freopen("input.txt","r",stdin);
  solve();
  return 0;
}


Measured memory_bytes: 16256
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
string s,t;
int main(){
    cin >> s >> t;
    if(t.size()!=s.size()+1){
        cout << "No" << endl;
        return 0;
    }
    bool ok = true;
    for(int i = 0; i < s.size(); i++) if(s[i]!=t[i]){
        ok = false;
        break;
    }
    if(!ok) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, e) for (int i = s; i < e; ++i)
#define sort_(a) stable_sort(a.begin(), a.end())
#define rsort(a) stable_sort(a.rbegin(), a.rend())
#define sum(a) accumulate(a.begin(), a.end(), 0LL)
#define join(a, d) accumulate(a.begin() + 1, a.end(), a[0], [](string s, string t) {return s + d + t;})
#define all(a) a.begin(), a.end()
// #define __lcm(a, b) std::__detail::__lcm(a, b)
typedef long long ll;
const long mod = 1e9 + 7;

int main(void) {
#ifdef DEBUG
  freopen("input.txt", "r", stdin);
#endif

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

  int N;
  cin >> N;
  vector<int> A(N);
  rep(i, 0, N) cin >> A[i];
  vector<int> nums(1000001, 0);
  rep(i, 0, N) {
    int j = 1;
    int n = A[i];
    while (n <= 1000000) {
      nums[n] += 1;
      if (j == 1 && nums[n] > 1) break;
      ++j;
      n = A[i] * j;
    }
  }
  int ans = 0;
  rep(i, 0, N) {
    if (nums[A[i]] < 2) {
      ++ans;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 7964
n,k = map(int,input().split())
d = []
a = []

while True:
    try:
        d.append(int(input()))
        a.append(list(map(int,input().split())))
    except:
        break
        
anslist = [0]*n
cnt = 0
for i in range(k):
    for j in range(d[i]):
        anslist[a[i][j]-1] +=1
        
for i in anslist:
  if i==0:
    cnt +=1
print(cnt)  

Measured memory_bytes: 9192
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    n::Int=parseInt(readline())
    cnt::Vector{Int}=ones(Int,n)
    ans::Int=1
    for i in 2:n
        for j in 1:n÷i
            cnt[i*j]+=1
        end
        ans+=cnt[i]*i
    end
    println(ans)
end
main()

Measured memory_bytes: 237684
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue> //priority_queue 优先队列
#include <map>
#include <set> //multiset  
#include <vector>
#include <stack>
#include <cmath>
#include <sstream>
#include <string>
#define mod 1000000007
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
const db eps=1e-6;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
using namespace std;
int x,y,z;
int t,n,m,a=0,b=0;
string s1,s2;
int sum=0,maxn=0,flag;
int main(){
	cin>>n;
	cin>>s1;
	for(int i=0;i<n;i++){
		if(s1[i]=='('){
			a++;
		}else{
			a--;
			if(a<0){
				sum++;
				a=0;
			}
		}
	}
	for(int i=0;i<sum;i++){
		cout<<"(";
	}
	cout<<s1;
	for(int i=0;i<a;i++){
		cout<<")";
	}
	cout<<endl;
	return 0;
}

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

const int mod = 1e9 + 7;
int main() {
  int n, K;
  cin >> n >> K;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  vector<vector<int>> dp(n, vector<int>(K + 1, 0));
  for (int j = 0; j <= a[0]; ++j) {
    if (j <= K)
      dp[0][j] =  1;
  }
  for (int i = 1; i < n; ++i)  {
    int acc = 0;
    for (int k = 0; k <= K; ++k) {
      acc += dp[i-1][k];
      if (acc >= mod) {
        acc -= mod;
      }
      if (k - a[i] - 1 >= 0) {
        acc -= dp[i-1][k-a[i]-1];
        if (acc < 0) {
          acc += mod;
        }
      }
      dp[i][k] += acc;
      if (dp[i][k] >= mod) {
        dp[i][k] -= mod;
      }
    }
  }
  cout << dp[n-1][K] << '\n';

  return 0;
}


Measured memory_bytes: 42768
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n) ;i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
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; }
const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];
ll gcd(ll a, ll b){
        if(b == 0) return a;
        return gcd(b, a % b);
}

map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

int main(int argc, char const *argv[]) {
  ll a,b;
  cin >> a >> b;
  ll m=gcd(a,b);
  set<ll> S;
  for(auto p : prime_factor(m)) {
    while(p.second--){
      S.insert(p.fi);
    }
  }
  cout << S.size()+1 << endl;


  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int count=0,i;
   string s;
   cin>>s;

   if(s[0]!='A')
   {
       cout<<"WA";
       return 0;
   }
    for(i=2;i<=s.size()-2;i++)
    {
        if(s[i]=='C')
            count++;
    }
    if(count!=1)
    {
        cout<<"WA";
        return 0;
    }
    for(i=0;i<s.size();i++)
    {
        if(s[i]>64 && s[i]<91)
        {
            if(s[i]!='A' && s[i]!='C')
            {
                //cout<<s[i]<<" ";
               cout<<"WA";
                return 0;
            }
        }
    }
    cout<<"AC";

}


Measured memory_bytes: 3612
def CountTriangles(A):
    n = len(A);

    A.sort();

    count = 0;

    for i in range(n - 1, 0, -1):
        l = 0;
        r = i - 1;
        while (l < r):
            if (A[l] + A[r] > A[i]):


                count += r - l;
                r -= 1;

            else:
                l += 1;
    print(count);


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

    CountTriangles(A);



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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz size()
#define pb(x) push_back(x) 
#define bg begin()
#define ed end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define mp(x,y) make_pair(x,y)
const ll MOD=1000000007;

vector<ll> pw2(51,1);
vector<ll> pw10(19,1);

ll maxx(ll x,ll y,ll z){
	return max(max(x,y),z);
}
ll minn(ll x,ll y,ll z){
	return min(min(x,y),z);
}
ll gcd(ll x,ll y){
	if(x%y==0) return y;
    else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
	return x*(y/gcd(x,y));
}
ll myceil(ll x,ll y){
	if(x<=y) return 1;
	else if(x%y==0) return x/y;
	else return x/y+1;
}

//a,b x
int main(){
	ll N; cin>>N;
	vector<ll> A(N);
	vector<ll> B(N);
	vector<ll> C;//A-B
	ll Asum=0,Bsum=0;
	rep(i,N){
		cin>>A[i];
		Asum+=A[i];
	}
	rep(i,N){
		cin>>B[i];
		Bsum+=B[i];
	}
	if(Asum<Bsum) cout<<-1;
	else{
		ll cnt=0,Csum=0;
		rep(i,N){
			if(A[i]>B[i]) C.pb(A[i]-B[i]);
		}
		sort(C.bg,C.ed,greater<ll>());
		rep(i,N){
			if(B[i]>A[i]){
				cnt++;
				Csum+=B[i]-A[i];
			}
		}
		if(cnt==0){
			cout<<0;
			return 0;
		}

		ll i=0,tmp=0;
		while(tmp<Csum){
			tmp+=C[i++];
		}
		cout<<cnt+i;
	}
}

Measured memory_bytes: 2556
#include <bits/stdc++.h>
using namespace std;
long long a[10010],b[10010],sum1,sum2;
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    	cin>>a[i];
    for(int i=1;i<=n;++i)
    	cin>>b[i];
    for(int i=1;i<=n;++i)
	{
        if(a[i]>b[i])
			sum1+=(a[i]-b[i]);
        else if(a[i]!=b[i])
			sum2+=(b[i]-a[i])/2;
    }
    if(sum1<=sum2)
		cout<<"Yes"<<endl;
    else
		cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int n,k;
    cin>>n>>k;
    map<int,int>P;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        P[a]++;
    }
    vector<int> s;
    for(auto x:P){
        s.push_back(x.second);
    }
    int ans=0;
    if(s.size()<=k){
        cout<<0<<endl;
    }
    else{
        sort(s.begin(),s.end(),greater<>());
        for(int i=k;i<s.size();i++){
            ans+=s[i];
        }
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 10748
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define lp(i, n) for (int i = 0; i < (n) ; ++i)
#define sz(v) (ll)(v).size()
#define int long long
#define mod 1000000007

int day;
int c[27];
int d[366][26], ansday[366];

void read_input() {
        //freopen("b1.in", "r", stdin);
        cin >> day;
        for (int i= 0; i< 26; i++) {
                cin >> c[i];
        }
        for (int i= 0; i< day; i++) {
                for (int j= 0; j< 26; j++) {
                        cin >> d[i][j];
                }
        }
}

void read_ans() {
        for (int i= 0; i< day; i++) {
                int x; cin >> x;
                ansday[i]= x- 1;
        }
}

int simu() {
        int lastuse[27]= {};
        int finalscore= 0;
        for (int i= 0; i< day; i++) {
                int choose= ansday[i];
                int score= d[i][choose];
                lastuse[choose]= i+ 1;
                int dec= 0;
                for (int j= 0; j< 26; j++) {
                        dec+= c[j]* ((i+ 1)- lastuse[j]);
                }
                finalscore+= score- dec;
        }
        return finalscore;
}

void query() {
        int m; cin >> m;
        vector<pair<int, int>> vp;
        for (int i= 0; i< m; i++) {
                int a, b; cin >> a>> b;
                vp.push_back({a, b});
        }
        for (int i= 0; i< m; i++) {
                int wday= vp[i].first- 1;
                int wc= vp[i].second- 1;
                ansday[wday]= wc;
                simu();
        }
}

void sol() {
        int lastuse[27]= {};
        for (int i= 0; i< day; i++) {
                vector<pair<int, int>> r;
                for (int j= 0; j< 26; j++) {
                        int dec= 0;
                        for (int k= 0; k< 26; k++) {
                                if (k== j) continue;
                                dec+= c[k]* ((i+ 1)- lastuse[k]);
                        }
                        r.push_back( { (d[i][j]- dec), j } );
                }
                sort(all(r));
                reverse(all(r));
                ansday[i]= r[0].second;
                lastuse[r[0].second]= i;
        }

}

void pr() {
        for (int i= 0; i< day; i++) {
                cout << ansday[i]+ 1<< "\n";
        }
}

void rand_query() {
        sol();
        int cur= simu();
        //cout << cur<< "\n";
        srand(time(0));
        for (int i= 0; i< 100000; i++) {
                int wday= rand() % 365;
                int wc= rand() % 26;
                int old= ansday[wday];
                ansday[wday]= wc;
                int r= simu();
                if (r< cur) {
                        ansday[wday]= old;
                } else {
                        cur = r;
                }
        }
        //cout << cur<< "\n";
        pr();
}

void solve() {
        read_input();
        //sol();
        //read_ans();
        //simu();
        //query();
        rand_query();
}

int32_t main(){
ios::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
        int t = 1;
        //cin >> t;
        while ( t-- ) {
                solve();
        }
return 0;
}


Measured memory_bytes: 3748
#include<iostream>
#include<string>
using namespace std;
int main() {
	string S;
	cin >> S;
	int counter = 0;

	for (int i = 0; i < 3; i++) {
		if (S.at(i) == 'o') {
			counter++;
		}
	}
	cout << 700 + 100 * counter << endl;
	return 0;
}


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

resident=[[[0 for i in range(10)] for j in range(3)] for k in range(4)]

def print_floor(b):
    for i in range(3):
        for j in range(10):
            print(" "+str(resident[b][i][j]),end="")
        print()


for i in range(n):
    b,f,r,v=map(int,input().split())
    resident[b-1][f-1][r-1]+=v

for i in range(4):
    print_floor(i)
    if i!=3:
        for j in range(20):
            print("#",end='')
        print()


Measured memory_bytes: 5628
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let s = read::<String>().chars().collect::<Vec<_>>();

    let mut count_dict = HashMap::<char, u64>::new();
    for ch in s {
        *count_dict.entry(ch).or_insert(0) += 1;
    }

    let values = count_dict.values().cloned().collect::<Vec<_>>();
    let value_sum = values.iter().sum::<u64>();

    let mut ans = 0;
    for v in values {
        ans += v * (value_sum - v);
    }
    ans /= 2;
    ans += 1;
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int main()
{
	long long n,a;
	cin >> n >> a;
	for(int i=0;i<4;i++)
	{
		long long tmp;
		cin >> tmp;
		if(tmp<a)a=tmp;
	}

	cout << (n+a-1)/a+4 << endl;



}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define rep3(i, s, n) for (int i = s; i > (int)(n); i--)
#define all(obj) obj.begin(), obj.end()
#define db(x) cerr << #x << ":" << x << " "
#define dbl(x) cerr << #x << ":" << x << "\n"
#define dbv(vec) cerr << #vec << ":"; for (auto e : vec) cerr << e << " "; cout << "\n"
#define dbvv(vv) cerr << #vv << ":\n"; for (auto vec : vv) { for (auto e : vec) cerr << e << " "; cerr << endl; }
#define YN(f) cout << (f ? "YES" : "NO") << endl
#define Yn(f) cout << (f ? "Yes" : "No") << endl
#define yn(f) cout << (f ? "yes" : "no") << endl
/*
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
*/

int main() {
	double L; cin >> L;
	cout << setprecision(10);
	cout << L * L * L / 27.0 << endl;
}

Measured memory_bytes: 256
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 210000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
long long p[110000];
int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	for(int i=0;i<a;i++)scanf("%lld",p+i);
	std::sort(p,p+a);
	
	int left=0;
	int right=a;
	while(left+1<right){
		int M=(left+right)/2;
		long long nv=p[M-1]+b;
		if(M-1>=a-d){
			right=M;continue;
		}
		if(nv<p[a-d]){
			left=M;continue;
		}
		int tr=c-M-(d-1);
		if(tr<=0){
			right=M;continue;
		}
		long long cur=0;
		for(int i=M;i<=a-d;i++){
			cur+=min((long long)b,nv-p[i]);
		}
		if(cur>=(long long)tr*b){
			right=M;
		}else left=M;
	}
	printf("%d\n",a-right+1);
}


Measured memory_bytes: 896
import java.io.*;
import java.util.StringTokenizer;



public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		int k = sc.nextInt();
		long sum=0;
		for(int a=1; a<=k ; a++) {
			for(int b=1;b<=k;b++) {
				for(int c=1;c<=k;c++) {
					int gcdab= gcd(a,b);
					int gcdabc = gcd(gcdab,c);
					sum+=gcdabc;
					
				}
			}
		}
		System.out.println(sum);
		
	}
	static int gcd(int x, int y) {
		if (y == 0)
			return x;
		return gcd(y, x % y);
	}


	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

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

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

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}


Measured memory_bytes: 32860
using System;
using System.Linq;
using System.Text;

namespace ALDS1_6_A
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string[] input = Console.ReadLine().Split(' ');
            int[] list = new int[N];

            for (int i = 0; i < N; i++)
            {
                list[i] = int.Parse(input[i]);
            }

            int[] outlist = CountSort(list, list.Max());
            string output = ArrayJoin(outlist);
            Console.WriteLine(output);

        }

        public static int[] CountSort(int[] arr, int k)
        {
            int[] count = new int[k + 1];
            int[] output = new int[arr.Length];

            for (int i = 0; i < arr.Length; i++)
            {
                    count[arr[i]]++;
            }

            for (int i = 1; i <= k; i++)
            {
                count[i] += count[i - 1];
            }

            for (int i = arr.Length - 1; i >= 0; i--)
            {
                output[count[arr[i]] - 1] = arr[i];
                count[arr[i]]--;
            }

            return output;
        }

        public static string ArrayJoin(int[] arr)
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < arr.Length; i++)
            {
                if (sb.Length > 0)
                {
                    sb.Append(" ");
                }
                sb.Append(arr[i]);
            }
            return sb.ToString();
        }
    }
}

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

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

    vector<int> aa(N);
    map<int, int> list;
    rep(i, N) cin >> aa.at(i);
    rep(i, N)
    {
        if (list.count(aa.at(i)))
        {
            list[aa.at(i)]++;
        }
        else
        {
            list[aa.at(i)] = 1;
        }
    }

    int mx = -1;
    for (auto key : list)
    {
        int i = key.first;
        int sum = 0;
        if (list.count(i - 1))
        {
            sum += list.at(i - 1);
        }
        if (list.count(i))
        {
            sum += list.at(i);
        }
        if (list.count(i + 1))
        {
            sum += list.at(i + 1);
        }
        mx = max(mx, sum);
    }
    cout << mx << endl;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define vi vector<int>
#define vs vector<string>
#define ll long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ull unsigned long long
#define ld long double
#define pll pair<unsigned long long,unsigned long long>
#define mod 1000000007
using namespace std;

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

	for(int i = 0; i<s.length(); ++i)
	{
		s[i] = (((s[i]-'A')+n)%26)+'A';
	}

	cout<<s<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> P;

int main(){
  int n; cin >> n; P p[n]; int x;
  for(int i=0; i<n; i++) {
    cin >> x;
    p[i].first = x;
    p[i].second = i+1;
  }
  sort(p, p+n);
  for(P y:p) {
    cout << y.second << " ";
  }
}

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

class DisjointSet{
private:
  vector< int > rank, p;
  size_t sz;
  void link(int x,int y){
    if(rank[x] > rank[y]){
      p[y] = x;
    } else {
      p[x] = y;
      if(rank[x] == rank[y]) rank[y]++;
    }
  }
public:
  DisjointSet(int size):sz(size){
    rank.resize(size,0);
    p.resize(size,0);
    for(int i = 0; i < size; i++) p[i] = i, rank[i] = 0;
  }
  void Union(int x,int y){
    if(Find(x) != Find(y)) link(Find(x),Find(y)), --sz;
  }
  int Find(int x){
    return( x != p[x] ? p[x] = Find(p[x]) : p[x]);
  }
  size_t Size(){
    return sz;
  }
};

int main()
{
  int N;
  while(scanf("%d", &N), N){
    DisjointSet UnionFind(N * N);
    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
        int x, y;
        scanf("%d %d", &x, &y);
        UnionFind.Union( i * N + j, y * N + x);
      }
    }
    printf("%d\n", UnionFind.Size());
  }
}

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

using namespace std;

int main()
{
    int n;
    cin>>n;
    int a[n];
    vector<int>v;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        v.push_back(a[i]-(i+1));
    }
    sort(v.begin(),v.end());
    long long ans=0;
    for(int i=0;i<n;i++)
    {
        ans += abs(a[i] - (i+1) - v[v.size()/2]);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1912
import java.util.*;
import java.io.*;

public class Main {
	static class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

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

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

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

		int[] readArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

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

		public long[] readLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}
	}

	static final FS sc = new FS();
	static final PrintWriter out = new PrintWriter(System.out);
	static final int mod = 1000000007;

	public static void main(String[] args) {
		String s = sc.next();
		if (s.equals("Sunny") ) {
			out.println("Cloudy");
		} else if (s.equals("Rainy")) {
			out.println("Sunny");
		} else if (s.equals("Cloudy")) {
			out.println("Rainy");
		}

		out.close();
	}

}


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

// short names
typedef long long ll;
#define down_queue(...) priority_queue<__VA_ARGS__>
#define up_queue(...) priority_queue<__VA_ARGS__, vector<__VA_ARGS__>, greater<__VA_ARGS__>>
#define all(x) x.begin(), x.end()
#define rall(x) x.begin(), x.end(), greater<int>()
#define split_str(str, sp_word) istringstream stream(str); string res; for(int cnt = 0; getline(stream,res,sp_word); cnt++)
#define digit(x) ((int)log10((double)(x)) + 1)
#define mp(...) make_pair(__VA_ARGS__)
#define pb(...) push_back(__VA_ARGS__)
#define pf(...) push_front(__VA_ARGS__)
vector<int> digit_split(int n){vector<int> result(digit(n));for(int i = 0; n; i++){result[i] = n % 10;n /= 10;}return result;}
#define vec_cpy(to,from) copy(all(to),back_inserter(from))
#define ary_cpy(to,from) memcpy(to, from, sizeof(from))
#define MOD 1000000007 

// math
ll gcd(ll a,ll b){while(b){ll tmp = a % b;a = b;b = tmp;}return a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
bool is_prime(ll n){switch(n){case 0:case 1: return false;case 2: return true;}if(n % 2 == 0) return false;for(ll i=3;i * i <= n; i += 2)if(n%i == 0) return false;return true;}
string to_qn(ll quaternary, ll from){string result = "";if(!from) return "0";else{while(from){result = (char)((from % quaternary) + '0') + result;from /= quaternary;}return result;}}

int main(){
  vector<int> abc(3);
  cin >> abc[0] >> abc[1] >> abc[2];
  sort(all(abc));
  if(abc[0] == abc[1]){
    cout << abc[2] << endl;
  }else{
    cout << abc[0] << endl; 
  }
  return 0;
}

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

using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define FORr(i,n,m) for(ll i=n; i>(ll)m; i--)
#define FORm(i,m) for(auto i=m.begin();i!=m.end();i++)
#define VEC2(x,a,b) vector<vector<ll>> x = vector<vector<ll>>(a,vector<ll>(b,0))
#define sortAl(v) sort(v.begin(),v.end())
#define sortAlr(v) sort(v.begin(),v.end()); reverse(v.begin(),v.end())
#define cinv(v,n,m) FOR(i,n,m) cin>>v.at(i)
#define coutv(v,n,m) FOR(i,n,m) cout<<v.at(i) <<" "; cout<<endl
#define cout(n) cout<<fixed<<setprecision(n)
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll x;
  cin>>x;
  map<string,ll> mp;
  vector<string> v(x);
  cinv(v,0,x);
  string res="Yes";

  FOR(i,0,x){
    if(mp.find(v[i])==mp.end())mp[v[i]]++;
    else res="No";
  }
  FOR(i,1,x){
    if(v[i][0]!=v[i-1][v[i-1].size()-1])res="No";
  }
  cout<<res<<endl;
}


Measured memory_bytes: 256
S = input()
L = len(S)
K = int(input())

dp = [[[0,0] for _ in range(K+1)] for _ in range(L+1)]
dp[0][0][0] = 1
for i,c in enumerate(S):
    c = int(c)
    for k in reversed(range(K+1)):
        for d in range(10):
            nk = k + (d>0)
            if nk > K: continue
            dp[i+1][nk][1] += dp[i][k][1]
            if d > c: continue
            less = int(d < c)
            dp[i+1][nk][less] += dp[i][k][0]
print(sum(dp[-1][-1]))

Measured memory_bytes: 9128
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
int a[maxn],b[maxn];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int n,k,c;
	string s;
	cin>>n>>k>>c>>s;
	int num=0; 
	for(int i=0;i<n;i++) 
	{
		if(s[i]=='o') 
		{
			a[num++]=i;
			i+=c;
		}
	}
	num=k-1;
	for(int i=n-1;i>=0;i--) 
	{
		if(num<0)
			break;
		if(s[i]=='o') 
		{
			b[num--]=i;
			i-=c;
		}
	}
	for(int i=0;i<k;i++) 
		if(a[i]==b[i])
			cout<<a[i]+1<<endl;
	return 0; 
}


Measured memory_bytes: 6676
S = input()
mod = 10 ** 9 + 7

ret = 0
la, rc = 0, S.count('C')
lq, rq = 0, S.count('?')

def comb(ac, q) :
    if q == 0 :
        return ac * pow(3, q, mod) % mod
    else :
        p = pow(3, q - 1, mod)
        return (q * p + ac * p * 3) % mod

for s in S :
    if s == '?' :
        rq -= 1
        ret += comb(la, lq) * comb(rc, rq)
        ret %= mod
        lq += 1
    elif s == 'A' :
        la += 1
    elif s == 'B' :
        ret += comb(la, lq) * comb(rc, rq)
        ret %= mod
    elif s == 'C' :
        rc -= 1
    
print(ret)

Measured memory_bytes: 41328
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10


N = INT()
S = input()

former = S[:N]
latter = S[N:][::-1]

dic_f = defaultdict(int)
dic_l = defaultdict(int)

for x in product([0, 1], repeat=N):
	tmp_red = ""
	tmp_blue = ""
	for i in range(N):
		if x[i]:
			tmp_red += former[i]
		else:
			tmp_blue += former[i]
	dic_f["{},{}".format(tmp_red, tmp_blue)] += 1

for x in product([0, 1], repeat=N):
	tmp_red = ""
	tmp_blue = ""
	for i in range(N):
		if x[i]:
			tmp_red += latter[i]
		else:
			tmp_blue += latter[i]
	dic_l["{},{}".format(tmp_red, tmp_blue)] += 1

ans = 0

for key in dic_f:
	ans += dic_f[key] * dic_l[key]

print(ans)




Measured memory_bytes: 230612
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
S = input()
dp = [[0]*(n+1) for i in range(n)]
# dp[i][j] = i番目まででi番目の数字より大きい数字が残りj個の通り数
# i番目の数字より小さい数はn = i + j + kよりk = n-i-j
for j in range(n):
  dp[0][j] = 1
for i in range(n-1):
  acum = [0]*(n+1)
  for j in range(n):
    acum[j+1] = acum[j] + dp[i][j]
  for j in range(n-i-1):
    if S[i] == "<":
      dp[i+1][j] = (acum[n]-acum[j+1]) % mod
    else:
      dp[i+1][j] = (acum[j+1] - acum[0]) % mod
print(dp[n-1][0])
# print(*dp,sep = "\n")
# print(acum)


Measured memory_bytes: 112988
H,W,A,B=map(int,input().split())
X=[[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if i<2*B and j<2*A:
            X[i][j]=(i+j)%2
        elif i<B or j<A:
            X[i][j]=0
        else:
            X[i][j]=1

for line in X:
    print("".join([str(i) for i in line]))


Measured memory_bytes: 14580
gets.to_i.times do
  arr = gets.split(" ").map(&:to_i)
  first, second = 0, 0
  i = 0
  while i < arr.length and (arr[i] > first or arr[i] > second)
    if arr[i] < first
      second = arr[i]
    elsif arr[i] < second
      first = arr[i]
    else
      if first < second
        second = arr[i]
      else
        first = arr[i]
      end
    end
    i += 1
  end
  if i == arr.length
    puts "YES"
  else
    puts "NO"
  end
end

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

int main() {
	int N,i,alice,bob;
	alice=0;
	bob=0;
	
	cin>>N;
	
	vector<int> card(N);
	
	for(i=0;i<N;i++){
		cin>>card.at(i);
	}//カードの値よむ//
	
	sort(card.begin(),card.end());
	reverse(card.begin(),card.end());
	if(N%2==0){
		for(i=0;i<N/2;i++){
		alice=alice+card.at(2*i);
		bob+=card.at(2*i+1);
		}
	}
	else{
		for(i=0;i<(N-1)/2;i++){
		alice=alice+card.at(2*i);
		bob+=card.at(2*i+1);
		}
		alice+=card.at(N-1);
	}
	cout<<(alice-bob)<<endl;
	return 0;
}







Measured memory_bytes: 256
// import chie template :) {{{
import std.stdio,
       std.algorithm,
       std.array,
       std.string,
       std.math,
       std.conv,
       std.range,
       std.container,
       std.bigint,
       std.ascii;
// }}}
// tbh.scanner {{{
class Scanner {
  import std.stdio;
  import std.conv : to;
  import std.array : split;
  import std.string : chomp;

  private File file;
  private dchar[][] str;
  private uint idx;

  this(File file = stdin) {
    this.file = file;
    this.idx = 0;
  }

  private dchar[] next() {
    if (idx < str.length) {
      return str[idx++];
    }

    dchar[] s;
    while (s.length == 0) {
      s = file.readln.chomp.to!(dchar[]);
    }

    str = s.split;
    idx = 0;

    return str[idx++];
  }

  T next(T)() {
    return next.to!(T);
  }

  T[] nextArray(T)(uint len) {
    T[] ret = new T[len];

    foreach (ref c; ret) {
      c = next!(T);
    }

    return ret;
  }
}
// }}}

void main() {
  auto cin = new Scanner;
  int n = cin.next!int;
  int[] ar = cin.nextArray!int(n);
  int[int] chie;
  foreach (i; ar) {
    chie[i] = 1;
  }
  writeln(chie.length);
}


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

using namespace std;

template <class T>
bool allMatch(vector<T> vec, function<bool(T)> p){
    bool match = false;
    for(T x : vec){
        match = p(x);
        if (!match){
            return false;
        }
    }
    return match;
}

template <class T, class U>
vector<U> collect(vector<T> vec, function<U(T)> f){
    vector<U> newVec;
    for (T x : vec) newVec.push_back(f(x));
    return newVec;
}


int main(){
    int N;
    cin >> N;
    
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A.at(i);
    
    int count = 0;
    while (allMatch<int>(A, [](int i)->bool{ return i % 2 == 0; })){
        A = collect<int, int>(A, [](int i)->int{ return i / 2;});
        count ++;
    };
    
    cout << count << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

const int MOD = 998244353;
map <__int128, int> S[120];

char A[110];

inline __int128 Get(__int128 B, int l, int v) {
	return (B >> l) & (((__int128)1 << v) - 1);
}

int Do(int L, __int128 B) {
	if(!L) return 1;
	if(S[L].find(B) != S[L].end()) return S[L][B];
	if(L == 1) {
		if(B == 1) return S[L][B] = 2;
		else return S[L][B] = 1;
	}
	int res = Do(L - 1, B >> 1);
	if(B & 1) res = (res + res) % MOD;
	for(int j=1;j+j<=L;j++) {
		__int128 val = Get(B, 0, j);
		for(int k=j+j;k<=L;k+=j) {
			val &= Get(B, k-j, j);
			res = (res + Do(L - k, B >> k) * (ll) Do(j, val)) % MOD;
		}
	}
	return S[L][B] = res;
}

void solve(){
	scanf("%s", A+1);
	int L = (int)strlen(A+1);
	__int128 x = 0;
	for(int i=1;i<=L;i++) x = x * 2 + A[i] - '0';
	printf("%d\n", Do(L, x));
}

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

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

int main() {
  int n,T; cin >>n >>T;
  vector<int> t(n+1);
  for (int i=1; i<n+1; i++) cin >>t.at(i);
  
  int nowater = 0;
  for (int i=1; i<=n-1; i++){
    if (t.at(i+1)-(t.at(i)+T)>0){
      nowater += t.at(i+1) - (t.at(i)+T);
    }
  }
  int ans = (t.at(n)+T) - nowater;
  cout <<ans <<endl;
  
  //if (ans) cout <<"YES" <<endl;
  //else cout <<"NO" <<endl;
  
}


Measured memory_bytes: 1024