akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    int reverse = 0;
    int tmp, remaind;
 
    tmp = n; 
    while (tmp != 0) {
        remaind = tmp % 10;
        reverse = reverse * 10 + remaind;
        tmp /= 10;
    }
 
    if (n == reverse) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
a, b, k = map(int, input().split())
flag = True
for _ in range(k):
    if flag:
        if a % 2 == 1:
            a -= 1
        b += a // 2
        a = a // 2
        flag = False
    else:
        if b % 2 == 1:
            b -= 1
        a += b // 2
        b = b // 2
        flag = True
print("{} {}".format(a, b))


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(long long i = 0; i < (long long)(n); ++i)

using namespace std;
using ll = long long;

int main() {
	int x, ans = 0;
	cin >> x;
	ans += (x / 500) * 1000;
	x %= 500;
	ans += (x / 5) * 5;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T> inline istream& operator>>(istream& input, vector<T>& v) { for (auto& elemnt : v)input >> elemnt; return input; }

int main() {
    init();

    int n; cin >> n;
    vector<pair<int, int>> a(n);
    FOR(i, 0, n) {
        cin >> a[i].first;
        a[i].second = i + 1;
    }
    SORT(a);
    FOR(i, 0, n)cout << a[i].second << (i == n - 1 ? "\n" : " ");
}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

// 素因数分解
map<ll, ll> prime_factorize(ll N) {
    map<ll, ll> res;
    for (ll i = 2; i * i <= N; ++i) {
        while (N % i == 0) {
            res[i]++;
            N /= i;
        }
    }
    if (N != 1) res[N] = 1;
    return res;
}

void Main() {
    ll N, P; cin >> N >> P;
    map<ll, ll> x = prime_factorize(P);
    ll ans = 1;
    for (auto a: x){
        // cout << a.first << " " << a.second << endl;
        rep(i, a.second / N){
            ans *= a.first;
        }
    }
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


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

using namespace std;

int main()
{
	int a[5];
	int sum1=0;
	for(int i=0;i<3;i++)
	{
		cin>>a[i];
		if(a[i]==5){
			sum1++;
		}
	}		
	if(sum1==2){
		cout<<"YES";
	}else{
		cout<<"NO";
	}
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<ctype.h>
#include<stdio.h>
#include<set>
#include<vector>
#include<map>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<numeric>
#include<string>
using namespace std;
typedef long long ll;
bool Isprime(int n){
  if(n<2) return 0;
  if(n==2) return 1;
  if(n%2==0)return 0;
  for(int i=3; i*i<=n; i+=2){
      if(n%i==0){
        return 0;
      }
  }
  return 1;
}  
int main() {
	ll N;
	cin >> N;
	vector<ll>v;
	for (ll i = 7; i<50000; i += 5) {
		if (Isprime(i))
			v.push_back(i);
	}
	for (ll i = 0; i<N; ++i) {
		cout << v[i] << " ";
	}
	cout << "" << endl;
}

        
  
  

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define EPS (1e-15)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define bet(x, a, b) (a) <= (x) && (x) < (b)
typedef long long ll;
typedef unsigned long long ull;

ll fr[200002];
ll bk[200002];

int main()
{
	int N, K;
	ll ans = 0;

	cin >> N >> K;

	fr[1] = 0;
	bk[1] = N;

	repc(i, 2, N + 1) {
		fr[i] = fr[i - 1] + (i - 1);
		bk[i] = bk[i - 1] + (N - (i - 1));
	}
	
	repc(i, K, N + 1) ans = (ans + bk[i] - fr[i] + 1) % MOD;

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 6644
N = int(input())
w = list(map(int,input().split()))

sumw = [0]*N
sumw[0] = w[0]
for i in range(1,N):
    sumw[i] = sumw[i-1]+w[i]

ans = 10**5
for i in range(0,N-1):
    ans = min(ans, abs(sumw[N-1]-2 * sumw[i]))

print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <list>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)
double pi=3.14159265;

int main(){
    while(1){
        int H,W;
        cin >> H >> W;
        if(H==0 && W==0) return 0;
        rep(i,H){
            rep(j,W) cout << '#';
            cout << endl;
        }
        cout << endl;
    }
}


Measured memory_bytes: 3096
#include<bits/stdc++.h>
//#include<tr1/unordered_map>
#pragma GCC optimize ("Ofast")
#define ll long long
#define pll pair<long long,long long>
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define forn(i, n) for(int i=0; i<int(n); i++)
#define Forn(i, n) for(int i=1; i<=int(n); i++)

using namespace std;

const ll mod = 998244353;

ll powe(ll x, ll y)
{
    if(!y) return 1;
    ll ret = powe(x, y/2);
    ret = ret * ret % mod;
    if(y&1) ret = ret * x % mod;
    return ret;
}

ll inv(ll x){return powe(x, mod-2);}

int n;
ll a[200010];

int mu[1000100];
bool vis[1000100];
int cnt;
int prim[1000100];
ll inver[1000100];
void prep()
{
    mu[1] = 1;
    for(int i=2; i<=1000000; i++)
    {
        if(!vis[i])
        {
            prim[++cnt] = i;
            mu[i] = -1;
        }
        for(int j=1; j<=cnt && prim[j]*i<=1000000; j++)
        {
            vis[prim[j]*i] = 1;
            if(i%prim[j] == 0) break;
            else mu[i*prim[j]] = -mu[i];
        }
    }
    Forn(i, 1000000) inver[i] = inv(i);
    //cout << "done" << endl;
}

vector<ll> fac[1000100];

void factor(int x)
{
    vector<int> v;
    for(int i=1; i*i<=x; i++) if(x%i==0) v.pb(i);
    forn(i, v.size())
    {
        fac[v[i]].pb(x);
        if(v[i]*v[i]!=x) fac[x/v[i]].pb(x);
    }
}

ll F[1000100];

void calF()
{
    Forn(i, 1000000)
    {
        ll sum = 0;
        ll sum2 = 0;
        forn(j, fac[i].size())
        {
            sum += fac[i][j];
            sum2 += fac[i][j] * fac[i][j];
        }
        sum %= mod;
        sum2 %= mod;
        ll ans = (sum * sum - sum2) % mod * inver[2] % mod;
        //ans = ans * inv(i) % mod;
        F[i] = ans;
    }
}

int main()
{
    prep();

    cin.tie(0); ios_base::sync_with_stdio(false);
    cin >> n;
    forn(i, n)
    {
        int x;
        cin >> x;
        a[i] = x;
    }
    forn(i, n) factor(a[i]);
    calF();
    /*Forn(i, 10)
    {
        cout << "i = " << i << endl;
        forn(j, fac[i].size()) cout << fac[i][j] << " ";
        cout << endl;
        cout << "F[i] = " << F[i] << endl;
    }*/
    ll ans = 0;
    Forn(g, 1000000)
    {
        for(int d = 1; g*d<=1000000; d++)
        {
            ll add = mu[d] * F[g*d];
            add = add * inver[g] % mod;
            ans = (ans + add) % mod;
        }
    }
    cout << (ans + mod) % mod << endl;
}


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

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            input_iter = LazyLoadAllLines();
            //------------------------------------------------//
            var n = Read<long>();
            //var m = Read<long>();
            //var a = Read<long>();
            //var b = Read<long>();
            //var c = Read<long>();
            //var x = Read<long>();
            //var s = Read();
            var ls = Read<long>(n);
            //List<long> als = new List<long>(), bls = new List<long>();
            //List<List<long>> cls = new List<List<long>>();
            /*for (int i = 0; i < m; ++i)
            {
                als.Add(Read<long>());
                bls.Add(Read<long>());
                cls.Add(Read<long>(bls[i]));
            }*/

            ls.Sort((l, r) => (int)(r - l));


            long cnt = 0;
            for(int i = 0; i < n - 2; ++i)
            {
                var first = ls[i];
                int idx = (int)(n - 1);
                for(int j = i + 1; j < idx; ++j)
                {
                    var second = ls[j];
                    for (;idx > j; --idx)
                    {
                        if (ls[idx] + second > first) break;
                    }
                    cnt += idx - j;
                }
            }

            Console.WriteLine(cnt);
        }

        static IEnumerator<string> input_iter;

        static _T Read<_T>() where _T : struct
        {
            input_iter.MoveNext();
            return (_T)Convert.ChangeType(input_iter.Current, typeof(_T));
        }
        static string Read()
        {
            input_iter.MoveNext();
            return input_iter.Current;
        }
        static List<_T> Read<_T>(long num) where _T : struct { return new List<_T>(Enumerate<_T>(num)); }


        static IEnumerable<_T> Enumerate<_T>(long num)
        {
            for (long i = 0; i < num; ++i)
            {
                input_iter.MoveNext();
                yield return (_T)Convert.ChangeType(input_iter.Current, typeof(_T));
            }
        }
        static IEnumerator<string> LazyLoadAllLines()
        {
            string line;
            do
            {
                line = Console.ReadLine();
                foreach (var s in line.Split(' '))
                    yield return s;
            } while (line != null);
        }
    }
}


Measured memory_bytes: 13780
#!/usr/bin/env python3
#ABC134 E

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

n = int(input())
a = [int(input()) for _ in range(n)]
m = []
for i in range(n):
    r = bisect.bisect_right(m,-a[i])
    if r == len(m):
        m.append(-a[i])
    else:
        m[r] = -a[i]
print(len(m))


Measured memory_bytes: 54872
#include "bits/stdc++.h"
#define double long double
#define int long long
#define mii map<int,int>
#define low lower_bound
#define upp upper_bound
#define inf 1000000007 //10^9+7
#define rep(i,n) for(int i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define sort(vec) sort(all(vec));
#define rever(vec) reverse(all(vec));
#define bisea binary_search
#define cend cout<<endl;
#define F first
#define S second
using namespace std;
int b[10]={0,0,0,0,0,0,1,1,1,2};
int d[10]={1,1,1,2,2,3,2,2,3,3};
int e[10]={2,3,4,3,4,4,3,4,4,4};
signed main() {
  int n,m=0,a=0,r=0,c=0,h=0,cnt=0;
  cin>>n;
  rep(i,n) {
    string s;
    cin>>s;
    char b=s[0];
    if(b=='M') m++;
    else if(b=='A') a++;
    else if(b=='R') r++;
    else if(b=='C') c++;
    else if(b=='H') h++;
  }
  int k[5];
  k[0]=m,k[1]=a,k[2]=r,k[3]=c,k[4]=h;
  rep(i,10) {
    cnt+=k[b[i]]*k[d[i]]*k[e[i]];
  }
  cout<<cnt<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define COUT(x) cout<<(x)<<"\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, n) for(int i=0;i<n;i++)
#define YES(x) cout<<(x?"YES":"NO")<<"\n"
#define Yes(x) cout<<(x?"Yes":"No")<<"\n"
#define dump(x) cout<<#x<<" = "<<(x)<<"\n"
#define endl "\n"
using G = vector<vector<int>>;
using M = map<int,int>;
using P = pair<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int,vector<int>,greater<int>>;
using V = vector<int>;
using ll = long long;
using edge = struct { int to; int cost; };
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  IOS;
  int h,w; cin >> h >> w;
  int k; cin >> k;
  char c[h][w];
  int bsum = 0;
  REP(i,h) REP(j,w) {
    cin >> c[i][j];
    if (c[i][j] == '#') bsum++;
  }

  int ans = 0;
  for (int bit = 0; bit < (1<<h); bit++) {
    vector<int> sh;

    REP(i,h) { if (bit >> i & 1) sh.push_back(i); }
    int tmp_b = 0;
    for(auto vh: sh)  {
      REP(j,w) {
        if (c[vh][j] == '#') {
          tmp_b++;
        }
      }
    }

    for (int bit = 0; bit < (1<<w); bit++) {
      vector<int> sw;
      REP(i,w) { if (bit >> i & 1) sw.push_back(i); }
      int tmp_b2 = 0;
      for(auto vw: sw) {
        REP(i,h) {
          if (c[i][vw] == '#') {
            tmp_b2++;
          }
        }
      }
      for(auto vh: sh)  {
        for(auto vw: sw) {
          if (c[vh][vw] == '#') {
            tmp_b2--;
          }
        }
      }
      if ( bsum - (tmp_b + tmp_b2) == k ) ans++;
    }
  }

  COUT(ans);
  return 0;
}


Measured memory_bytes: 3652
#include <stdio.h>

int main(void)
{
	int i,n;
	
	scanf("%d",&n);
	int a[n];
	
	for (i=0;i<n; i++)
	scanf("%d",&a[i]);
	
	for(i=0;i<n-1;i++ )
		printf("%d ",a[n-1-i]);
		
	printf("%d\n",a[0]);
		
		return 0;
}


Measured memory_bytes: 2040
use proconio::input;

// https://atcoder.jp/contests/abc168

fn main() {
    input! {
        n: usize,
        m: usize,
        ab: [(usize, usize); m],
    }
    let mut cave = vec![vec![]; n+1];
    for p in ab {
        cave[p.0].push(p.1);
        cave[p.1].push(p.0);
    }
    for i in 1..cave.len() {
        cave[i].sort();
    }

    let mut check = vec![0; n+1];
    check[1] = 1;
    let mut que = std::collections::VecDeque::new();
    que.push_back(1);

    while que.len() > 0 {
        let v = que.pop_front().unwrap();

        for &i in &cave[v] {
            if check[i] != 0 {
                continue;
            }
            check[i] = v;
            que.push_back(i);
        }
    }
    
    println!("Yes");
    for i in 2..check.len() {
        println!("{}", check[i]);
    }
}


Measured memory_bytes: 15984
#include <stdio.h>
#define N 10000
void setDepth(int u,int d);
int setHeight(int u);
int getSibling(int u);
typedef struct{
  int p;
  int l;
  int r;
}Node;
 
Node T[N];
int n,D[N],H[N];
 
void setDepth(int u,int d){
  if(u == -1) return;
  D[u] = d;
  setDepth(T[u].l, d+1);
  setDepth(T[u].r, d+1);
}
 
int setHeight(int u){
  int h1=0, h2=0;
  if(T[u].l != -1) h1 = setHeight(T[u].l) + 1;
  if(T[u].r != -1) h2 = setHeight(T[u].r) + 1;
  return H[u] = (h1 > h2 ? h1 : h2);
}
 
int getSibling(int u){
  if(T[u].p == -1) return -1;
  if(T[T[u].p].l != u && T[T[u].p].l != -1) return  T[T[u].p].l;
  if(T[T[u].p].r != u && T[T[u].p].r != -1) return T[T[u].p].r;
  return -1;
}
 
int main(){
  int i,v,l,r,degree,root=0;
 
  scanf("%d",&n);
 
  for(i=0;i<n;i++) T[i].p = -1;
 
  for(i=0;i<n;i++){
    scanf("%d %d %d",&v,&l,&r);
    T[v].l = l;
    T[v].r = r;
    if(l != -1) T[l].p = v;
    if(r != -1) T[r].p = v;
  }
 
  for(i=0; i<n; i++){
    if(T[i].p == -1) root = i;
  }
 
  setDepth(root, 0);
  setHeight(root);
 
  for(i=0; i<n; i++){
    printf("node %d: ",i);
    printf("parent = %d, ",T[i].p);
    printf("sibling = %d, ",getSibling(i));
    degree = 0;
    if(T[i].l != -1) degree++;
    if(T[i].r != -1) degree++;
    printf("degree = %d, ", degree);
    printf("depth = %d, ", D[i]);
    printf("height = %d, ", H[i]);
    if(T[i].p == -1) printf("root\n");
    else if(T[i].l == -1 && T[i].r == -1) printf("leaf\n");
    else printf("internal node\n");
  }
   
  return 0;
}

Measured memory_bytes: 624
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#include <algorithm>
#include <set>

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define MOD 1000000007

typedef long long ll;

char pict[102][102];
char input[100][100];

using namespace std;
int main(){
    int H, W;
    cin >> H >> W;

    REP(i, H)
    {
       REP(j, W)
       {
         cin >> input[i][j];
       }
    }

    REP(i, H + 2)
    {
       REP(j, W + 2)
       {
          if (i == 0 || i == H + 1 || j == 0 || j == W + 1) pict[i][j] = '#';
          else pict[i][j] = input[i - 1][j - 1];

          cout << pict[i][j];
       }
       cout << " " << endl;
    }
}


Measured memory_bytes: 256
def main():
    while True:
        sq_sum = int(input())
        if sq_sum == 0: break
        
        abs_list = [[0, 0]]
        for i in range(sq_sum - 1):
            n, d = map(int, input().split())
            abs_list.append(abs_p(abs_list, n, d))
        xlist = []
        ylist = []
        for i in range(len(abs_list)):
            xlist.append(abs_list[i][0])
            ylist.append(abs_list[i][1])
        print(str(max(xlist) - min(xlist) + 1) + " " + str(max(ylist) - min(ylist) + 1))
    return 0

def abs_p(abs_list, fromm, wch):
    if wch == 0:return[abs_list[fromm][0] - 1, abs_list[fromm][1]]
    if wch == 1:return[abs_list[fromm][0], abs_list[fromm][1] + 1]
    if wch == 2:return[abs_list[fromm][0] + 1, abs_list[fromm][1]]
    if wch == 3:return[abs_list[fromm][0], abs_list[fromm][1] - 1]
    return 0
main()



Measured memory_bytes: 5624
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a)  for(ll i=0; i< a; i++)
#define rep1(i,a)   for(ll i = 1; i< a; i++)
#define foi(i, a, b)    for(ll i = a; i<b ; i++)
#define fod(i, a, b)    for(ll i = a; i>=b ; i--)
#define max3(a, b, c)   max(max(a, b), c)
#define min3(a, b, c)   min(min(a, b), c)
#define MAX 1000005
#define MOD 1000000007

ll findgcd(ll n,ll m){
    return __gcd(n,m);
}
ll findlcm(ll n,ll m){
    return (n*m)/findgcd(n,m);
}

int main(){
    ll a,b,c,d,x,y;
    cin>>a>>b>>c>>d;
    cout<<max(max3(max(a,b)*max(c,d),min(a,b)*min(c,d),max(a,b)*min(c,d)),max(c,d)*min(a,b));

return 0;
}

Measured memory_bytes: 3632
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
  char s[17],s1[17]="CODEFESTIVAL2016";
  int ans=0;
  scanf("%s",s);
  for(int i=0;i<16;i++)
    if(s[i]!=s1[i])
      ans++;
  printf("%d\n",ans);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define debug(...)
#include <complex.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;


int32_t main() {
    ios::sync_with_stdio (false);
    cin.tie (0);
    ll x,  y;
    cin >> x >> y;
    ll ans = 0;
    x--, y--;
    vl a = {100000
            ,
            200000
            ,
            300000
           };
    reverse (a.begin(), a.end());
    ans = (x==y && x == 0 ? 400000: 0);
    if (x <= 2)
        ans+= a[x];
    if (y <= 2)
        ans += a[y];
    cout << ans << '\n';



    return 0;
}













Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;

int n, p, a[105];
LL sum[5];

int main()
{
	scanf("%d%d", &n, &p);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	sum[0] = 1; sum[1] = 0;
	for(int i = 1; i <= n; i++) {
		LL u = sum[0], v = sum[1];
		if(a[i] & 1) {
			sum[0] += v;
			sum[1] += u;
		}
		else {
			sum[0] += u;
			sum[1] += v;
		}
	}
	printf("%lld\n", sum[p]);
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<iomanip>
#include<stack>
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define sz(a) (int)a.size()
using namespace std;

//mod無しバージョン
ll pow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}


int main() {
    ll x;
    cin >> x;
    for (ll i = -1000; i <= 1000; i++) {
        for (ll j = -1000; j <= 1000; j++) {
            if (pow(i, 5) - pow(j, 5) == x) {
                cout << i << " " <<j<< endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 4116
n=int(input())
AB=[list(map(int,input().split())) for i in range(n)]
#print(AB)
AB.sort(key=lambda ab:ab[1])
#print(AB)
time=0
ans="Yes"

for i in range(n):
    time+=AB[i][0]
    if(time>AB[i][1]):
        ans="No"
        break

print(ans)

Measured memory_bytes: 53660
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;

map<string,int> m;
int memo[99999];
int N;
string s;

void bs(int start,int end){
    //cout<<"aaa1"<<endl;
    int v1,v2,vc;
    int c=(start+end)/2;

    //cout<<"aaa2"<<endl;
    if(memo[start]==-1){
        cout<<start<<'\n'<<flush;
        cin>>s;
        if(m[s]==2){
            return;
        }
        v1=memo[start]=m[s];
    }else{
        v1=memo[start];
    }

    //cout<<"aaa3"<<endl;
    if(memo[end]==-1){
        cout<<end<<'\n'<<flush;
        cin>>s;
        if(m[s]==2){
            return;
        }
        v2=memo[end]=m[s];
    }else{
        v2=memo[end];
    }

    //cout<<"aaa5"<<endl;
    if(memo[c]==-1){
        cout<<c<<'\n'<<flush;
        cin>>s;
        if(m[s]==2){
            return;
        }
        vc=memo[c]=m[s];
    }else{
        vc=memo[c];
    }

    //cout<<"aaa6"<<endl;
    if((c-start)%2==1 && v1==vc){
        bs(start,c);
    }else if((c-start)%2==0 && v1!=vc){
        bs(start,c);
    }else if((end-c)%2==1 && v2==vc){
        bs(c,end);
    }else if((end-c)%2==0 && v2!=vc){
        bs(c,end);
    }
    
}

int main(){
    m["Male"]=0;
    m["Female"]=1;
    m["Vacant"]=2;
    fill(memo,memo+99999,-1);
    cin>>N;

    bs(0,N-1);
}

Measured memory_bytes: 1236
N = int(input())
Alist = list(map(int,input().split()))
Blist = []
p = 0
q = 0
r = 0
for i in range(N):
    Blist.append(Alist[i] - i- 1)
Blist.sort()
u = Blist[N//2]
for i in range(N):
    q = q + abs(Blist[i]-u)
print(q)

Measured memory_bytes: 25200
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	string s;
	cin >> s;
	
	int n = s.size();
	int S = 0, N = 0, E = 0, W = 0;
	for(int i = 0; i < n; ++i) {
		if( s[i] == 'N' ) N = 1;
		if( s[i] == 'S' ) S = 1;
		if( s[i] == 'E' ) E = 1;
		if( s[i] == 'W' ) W = 1;
	}
	
	if( N + S == 1 || E + W == 1 ) cout << "No" << endl;
	else cout << "Yes" << endl;
	
	return 0;
}


Measured memory_bytes: 384
#include<stdio.h>

int main() {
  int i, j, a[100], n, temp, cnt=0;

  scanf("%d", &n);
  for(i = 0; i < n; i++) scanf("%d", &a[i]);

  for(i = 0; i < n; i++){
    for(j = n - 1; j != i; j--){
      if(a[j] < a[j - 1]){
        temp = a[j];
        a[j] = a[j-1];
        a[j-1] = temp;
	cnt++;
      }
    }
  }
  for(i = 0; i < n; i++){
      printf("%d", a[i]);
      if(i < n-1) printf(" ");
      else printf("\n%d\n", cnt);
  }
  return 0;
}



Measured memory_bytes: 2736
def main():
	N = int(input())
	friendliness = [int(a) for a in input().split(" ")]

	friendliness.sort(reverse=True)
	put = 1
	comfort = 0
	for i in range(len(friendliness)):
		if i == 0:
			put += 1
			comfort += friendliness[0]
		elif put + 2 <= len(friendliness):
			put += 2
			comfort += 2 * friendliness[i]
		else:
			comfort += (len(friendliness) - put) * friendliness[i]
			break

	print(comfort)

main()

Measured memory_bytes: 31472
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
int N, M, Q;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
ll mx = -1;
ll a[60], b[60], c[60], d[60], A[1000];

void calc(ll num, ll i) {
  if (i == N) {
    ll number = 0;
    for (int i = 0; i < Q; i++) {
      if (A[b[i]] - A[a[i]] == c[i]) number += d[i];
    }
    if (mx < number) mx = number;
    return;
  }
  for (ll j = num; j <= M; j++) {
    A[i + 1] = j;
    calc(j, i + 1);
  }
}
int main() {
  cin >> N >> M >> Q;
  REP(i, Q) { cin >> a[i] >> b[i] >> c[i] >> d[i]; }
  for (int i = 1; i <= M; i++) {
    A[0] = i;
    calc(i, 0);
  }
  cout << mx << endl;
  return 0;
}

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

int main() {
   int r,d,x0;
   cin >> r >> d >> x0;
   int x[10];x[0]=r*x0-d;
   rep(i,10){
      x[i+1]=r*x[i]-d;
   }
   for(int ans : x)
   cout << ans << endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var n int
  	fmt.Scan(&n)
  
  	var s string	
  	flg := false
    for i := 0; i < n; i++ {
      fmt.Scan(&s)
      if s == "Y" {
      	flg = true
      }
    }
  
    if flg {
      fmt.Println("Four")
    } else {
      fmt.Println("Three")
    }
}

Measured memory_bytes: 512
using System;
using System.Linq;
class c
{
    static void Main()
    {
        var s = Console.ReadLine();
        var n = s.Length;
        var k = long.Parse(Console.ReadLine());
        if (s.Distinct().Count() == 1) Console.WriteLine(s.Count() * k / 2);
        else
        {
            long front = 1;
            for (int i = 1; i < n; i++)
            {
                if (s[i] == s[i - 1]) front++;
                else break;
            }
            long rear = 1;
            for (int i = n - 2; i >= 0; i--)
            {
                if (s[i] == s[i + 1]) rear++;
                else break;
            }
            long block = 0;
            char temp = s[0];
            int cnt = 1;
            for (int i = 1; i <= n; i++)
            {
                if (n == i)
                {
                    block += cnt / 2;
                    break;
                }
                if (s[i] == temp)
                {
                    cnt++;
                }
                else
                {
                    temp = s[i];
                    block += cnt / 2;
                    cnt = 1;
                }
            }
            block -= front / 2 + rear / 2;
            if (k == 1) Console.WriteLine(block + front / 2 + rear / 2);
            else Console.WriteLine(block * k + front / 2 + rear / 2 + (s[0] == s[n - 1] ? (front + rear) / 2 * (k - 1) : (front / 2 + rear / 2) * (k - 1)));
        }
    }
}


Measured memory_bytes: 13268
MOD=10**9+7
cnt=0; sum=0; prev=nil; can=true; h=Hash.new(0)
def gs() gets.chomp end
def gi() gets.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end

def desc(ar) ar.sort!{|x,y|y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+) end

def C(a,b) b==0||a==b ? 1 : (b=a-b if a/2<b;(a-b+1..a).inject(:*)/(1..b).inject(:*)) end

def puts_yesno(can) puts(can ? 'Yes' : 'No') end
def putsend(s) puts s; exit end
def debug(k,v) puts "#{k}:#{v}" end
########### ( ˘ω˘ )ｽﾔｧ… ###########
N,K=gsmi
A=gsmi.sort
F=desc gsmi

putsend(0) if sum(A)<=K

# コストnumでできるか？
def can(num)
  train=0
  N.times do |i|
    train += A[i]-num/F[i] if A[i]*F[i]>num
  end
  train <= K
end

l=1
r=10**12
while l != r do
  cen= r-l>1 ? (l+r)/2 : l
  #puts cen
  if can(cen)
    r=cen
  else
    break if l==cen
    l=cen
  end
end

puts r

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

int main(){
    int n,k;
    cin>>n>>k;
    int b[200010]={0};
    for(int i=0;i<n;i++){
        int a; cin>>a;
        b[a]++;
    }
    sort(b,b+n+5,greater<int>());
    if(b[k]==0){
        cout<<"0"<<endl;
        return 0;
    }
    int ans=0;
    for(int i=k;i<n+5;i++){
        ans+=b[i];
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include<stdio.h>
int main()
{
	long long x,y,i,max=1e18,t,count=0;
	scanf("%lld%lld",&x,&y);
	if(x%y==0) printf("-1\n");
	else
   {
     	i=2;
     	 while(1)
     	 {
     	 	t=x*i;
     	 	if(t<=max)
     	 	{
     	 	  if(t%y!=0)
     	 	  {
     	 	  	count=1;
     	 	  	break;
			  }
			} 
			else  break;
			i++;
		 }
	if(count==1) printf("%lld\n",t);
	else  printf("-1\n");
   }
   return 0;	
}

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

#include <math.h>
#include <stdlib.h>


#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;


int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;

    vector<ll> p(a);
    vector<ll> q(b);
    vector<ll> r(c);
    for(int i = 0; i < a; i++) {
        cin >> p[i];
        p[i] *= -1;
    }
    for(int i = 0; i < b; i++){
        cin >> q[i];
        q[i] *= -1;
    }
    for(int i = 0; i < c; i++) {
        cin >> r[i];
        r[i] *= -1;
    }
    sort(p.begin(), p.end());
    sort(q.begin(), q.end());
    sort(r.begin(), r.end());

    priority_queue<ll> px;
    priority_queue<ll> qy;

    for(int i = 0; i < x; i++) px.push(p[i]);
    for(int i = 0; i < y; i++) qy.push(q[i]);

    for(int i = 0; i < c; i++){
        ll tp = px.top();
        ll tq = qy.top();
        if(r[i] >= tp && r[i] >= tq) break;
        if(tp > tq){
            px.pop();
            px.push(r[i]);
        } else {
            qy.pop();
            qy.push(r[i]);
        }
    }

    ll ans = 0;
    while(!px.empty()){
        ans += px.top();
        px.pop();
    }

    while(!qy.empty()){
        ans += qy.top();
        qy.pop();
    }

    ans *= -1;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4852
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<iostream>
#include<algorithm>//next_permutation
using namespace std;
int main() {
	int n, m;
	cin >> n >> m;
	vector<int>a(n);
	int count = 0;
	for (int i = 0;i < n;i++) {
		cin >> a.at(i);
		count += a.at(i);
	}
	sort(a.begin(), a.end());
	reverse(a.begin(), a.end());
	bool F = false;
	for (int i = 0;i < m;i++) {
		if (count % (4 * m) != 0) {
			if (a.at(i) < count / (4 * m) + 0.1) {
				F = true;
				break;
			}
		}
		else {
			if (a.at(i) < count / (4 * m)) {
				F = true;
				break;
			}
		}
	}
	if (F) cout << "No" << endl;
	else cout << "Yes" << endl;
}

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

using std::cout;
using std::cin;
using std::endl;

int main(){
  int n,q;
  cin >> n;
  int S[n];
  for(int i=0;i<n;i++)   
    cin >> S[i];
  cin >> q;
  int T[q];
  for(int i=0;i<q;i++)   
    cin >> T[i];

  int target, mid, cnt=0;  int left, right;       
  for(int i=0;i<q;i++){  
    target=T[i];
    left=0;    right=n;
    while(right > left){
      mid=(left+right)/2;
      //cout << target << "," << left << "," << mid << "," << right << endl;
      if(S[mid]==target){
        cnt++;
        //cout << target << endl;
        break;
      }else if(target > S[mid]){
        left=mid+1;
      }else if(target < S[mid]){
        right=mid;
      }
    }
  }
  cout << cnt << endl;
}


Measured memory_bytes: 3588
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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

count = 0

if N*2 <= M:
    count += N
    M -= N*2

    count += (M // 4)
else:
    count += (M // 2)

print(count)

Measured memory_bytes: 3060
from operator import itemgetter
N,M = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(N)]
ls = sorted(ls,key=itemgetter(0))
ans = 0
pon = 0
for i in range(N):
    if pon < M:
        pon += ls[i][1]
        ans += ls[i][1]*ls[i][0]
    else:
        i = i-1
        break
if pon == M:
    print(ans)
else:
    ans -= ls[i][0]*(pon - M)
    print(ans)

Measured memory_bytes: 29864
n = int(input())
x = []
y = []
import math
for i in range(n):
    xi,yi = map(int, input().split( ))
    x.append(xi)
    y.append(yi)
if n==2:
    x.append(x[0]+10**(-8))
    y.append(y[0]+10**(-8))
import itertools
def get_circle_center_and_radius(x1, y1, x2, y2, x3, y3):
    """
    3点を通る円の中心と半径を取得
    """
    d = 2 * ((y1 - y3) * (x1 - x2) - (y1 - y2) * (x1 - x3))
    if d==0:
        return ((0,0),10**10)
    x = ((y1 - y3) * (y1 ** 2 - y2 ** 2 + x1 ** 2 - x2 ** 2) - (y1 - y2) * (y1 ** 2 - y3 ** 2 + x1 ** 2 - x3 ** 2)) / d
    y = ((x1 - x3) * (x1 ** 2 - x2 ** 2 + y1 ** 2 - y2 ** 2) - (x1 - x2) * (x1 ** 2 - x3 ** 2 + y1 ** 2 - y3 ** 2)) / -d
    r = math.sqrt((x - x1) ** 2 + (y - y1) ** 2)
    return (x, y), r
ans = 10**10
e = 10**(-8)
for i,j,k in itertools.product(range(n),range(n),range(n)):
    if i!=j and i!=k and j!=k:
        x1, y1, x2, y2, x3, y3 = x[i],y[i],x[j],y[j],x[k],y[k]
        (xc,yc),r = get_circle_center_and_radius(x1, y1, x2, y2, x3, y3)
        flag = True
        for l in range(n):
            if (x[l]-xc)**2 + (y[l]-yc)**2>r**2*(1+e):
                flag = False
                break
        if flag:
            ans = min(ans,r)


for i,j in itertools.product(range(n),range(n)):
    xc = (x[i]+x[j])/2
    yc = (y[i]+y[j])/2
    r = (x[i]-xc)**2 + (y[i]-yc)**2
    flag = True
    for l in range(n):
        if (x[l]-xc)**2 + (y[l]-yc)**2>r*(1+e):
            
            flag = False
            break
    
    if flag:
        ans = min(ans,r**(1/2))
print(ans)

Measured memory_bytes: 73304
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author yassin
 */

#include <fstream>

#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstdlib>
#include <tuple>
#include <queue>
#include <functional>
#include <stack>
#include <cassert>

using namespace std;

class atD {
public:
    void solve(istream& in, ostream& out) {
        int N, K;
        in >> N >> K;
        vector<int> a(N);
        int mx = 0;
        for (int i = 0; i < N; ++i) {
            in >> a[i];
            mx = max(mx, a[i]);
        }
    
        vector<vector<int>> prefix(K+1, vector<int>(N+1, 0)), suffix(K+1, vector<int>(N+1, 0));
        for (int j = 0; j <= N; ++j) {
            prefix[0][j] = 1;
        }
        for (int i = 1; i <= K; ++i) {
            for (int j = 1; j <= N; ++j) {
                prefix[i][j] = prefix[i][j-1] || (i-a[j-1] >= 0 ? prefix[i-a[j-1]][j-1] : 0);
            }
        }
        for (int j = 0; j <= N; ++j) {
            suffix[0][j] = 1;
        }
        for (int i = 1; i <= K; ++i) {
            for (int j = 1; j <= N; ++j) {
                suffix[i][j] = suffix[i][j-1] || (i-a[N-j] >= 0 ? suffix[i-a[N-j]][j-1] : 0);
            }
        }
        
        int res = 0;
        for (int ind = 0; ind < N; ++ind) {
            //check if sum with a[i] in the range [K, K+a[i]) is possible
            //if so, a[i] is NOT unnecessary
            if (a[ind] >= K) {
                continue;
            }
            
            bool flag = false;
            for (int S = 0; !flag && S <= K; ++S) {
                if (prefix[S][ind] == 1) {
                    for (int x = max(K-a[ind]-S, 0); !flag && x < K-S; ++x) {
                        if (suffix[x][N-ind-1] == 1) {
                            flag = true;
                        }
                    }
                }
            }
            
            res += !flag;
        }
        out << res << "\n";
    }
};


int main() {
	std::ios::sync_with_stdio(false);

	atD solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

#define REPS(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (int i = (a); i >= n; --i)
#define DEP(i, n) DEPS(i, n, 0)

#define vint(v, n) vector<int> v(n); REP(i,n) cin >> v[i];
#define vints(v, v1, n) vector<int> v(n), v1(n); REP(i,n) cin >> v[i] >> v1[i];

int main(void){

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

  int A, B, C, X, Y;
  int ans = 0;
  cin >> A >> B >> C >> X >> Y;

  if(A+B >= C*2){
    int Z = min(X, Y);
    ans += 2*Z*C;
    if(X == max(X, Y) && A < C*2){
      ans += (X-Z)*A;
    }else if(X == max(X, Y) && A >= C*2){
      ans += (X-Z)*C*2;
    }else if(Y == max(X, Y) && B < C*2){
      ans += (Y-Z)*B;
    }else{
      ans += (Y-Z)*2*C;
    }
  }else{
    if(A < C*2 && B < C*2){
      ans += X*A+Y*B;
    }else if(A >= C*2 && B < C*2){
      ans += X*2*C+Y*B;
    }else if(A < C*2 && B >= C*2){
      ans += X*A+Y*2*C;
    }else{
      ans += 2*C*(X+Y);
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main(){
    int n;
    std::cin >> n;

    int tmp = 0;
    unsigned long long int step = 0;
    for (int i = 0; i < n; i++)
    {
        int a;
        std::cin >> a;
        if (tmp <= a)
        {
            tmp = a;
        }
        else
        {
            step += tmp - a;
        }
    }
    
    std::cout << step << std::endl;

    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;


int main(void){
  int n,i,p[10],q[10],t[10],k,a,b;
  
  cin >> n;
  for (i=0;i<n;i++) cin >> p[i];
  for (i=0;i<n;i++) cin >> q[i];
  
  for (i=0;i<n;i++) t[i]=i+1;
  
  k=0;
  do{
    for (i=0;i<n;i++){
      if (p[i]!=t[i]) break;
    }
    if (i==n) a=k;
    
    for (i=0;i<n;i++){
      if (q[i]!=t[i]) break;
    }
    if (i==n) b=k;
    
    k++;
    
  }while (next_permutation(t,t+n));
  
  cout << abs(a-b) << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e9;
template<typename T> void cmax(T &a, T b) { a = max(a, b); }
template<typename T> void cmin(T &a, T b) { a = min(a, b); }

signed main() {
  int n;
  cin >> n;
  string s, t;
  cin >> s >> t;
  string u = "";
  rep(i, n) {
    if (s[i] == t[i]) {
      u += "A";
    } else {
      u += "B";
      i++;
    }
  }
  int ans;
  if (u[0] == 'A')
    ans = 3;
  else
    ans = 6;
  loop(i, 1, u.size()) {
    if (u[i - 1] == 'A')
      (ans *= 2) %= MOD;
    else {
      if (u[i] == 'A')
        ;
      else
        (ans *= 3) %= MOD;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll ac(ll n, ll k) { ll a = 1; rep(i, 1, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }
int dp[31][3001];
int main()
{
	int a, b, c, d, e, f, ans_a = 1, ans_b = 0;
	cin >> a >> b >> c >> d >> e >> f;
	dp[0][0] = 1;
	rep(i, 0, 31) {
		rep(i2, 0, f + 1) {
			if (100*i + i2 > f || i*e < i2)continue;
			if (i - a >= 0)dp[i][i2] |= dp[i - a][i2];
			if (i - b >= 0)dp[i][i2] |= dp[i - b][i2];
			if (i2 - c >= 0)dp[i][i2] |= dp[i][i2 - c];
			if (i2 - d >= 0)dp[i][i2] |= dp[i][i2 - d];
			if (dp[i][i2] == 1) {
				//printf("%f\n", 100 * i2 / (double)(100 * i + i2));
				if (i2 * (100 * ans_a + ans_b) >= ans_b * (100 * i + i2)) {
					ans_a = i, ans_b = i2;
				}
			}
		}
	}
	printf("%d %d\n", ans_a * 100 + ans_b, ans_b);
	return 0;
}


Measured memory_bytes: 3928
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define siz(v) (ll)(v).size()
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, x, n) for (ll i = x; i < (ll)(n); i++)
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
const ll mod = 1000000007;
const ll INF = 100000000000000099;
vector<ll> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
//cin.tie(0);
//ios::sync_with_stdio(false);

ll dp[200020][2] = {};

const ll MAX = 200030;//設定して

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

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int 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;
    }
}


signed main()
{
  COMinit();
  
  ll n;
  cin >> n;
  string s;
  cin >> s;

  dp[0][0] = 1;

  ll nofk = 0;

  for (int i = 1; i <= 2*n; i++)
  {

    if (s.at(i - 1) == 'B') //odd
    {
      dp[i][0] = 0;

      if ((nofk%2)==0 && nofk>=0)
      { //前偶数
        dp[i][1] = dp[i - 1][1]+dp[i-1][0];
        nofk++;
      }
      else if(nofk>=0)
      {
        dp[i][1] = ((dp[i - 1][1]+dp[i-1][0])%mod) * nofk;
        nofk--;
      }
    }
    else //even
    {
      dp[i][1] = 0;

      if ((nofk%2)==1 && nofk>=0)
      { 
        dp[i][0] = dp[i - 1][1]+dp[i-1][0];
        nofk++;
      }
      else if(nofk>=0)
      {
        dp[i][0] = ((dp[i - 1][1]+dp[i-1][0])%mod) * nofk;
        nofk--;

      }
    }

    dp[i][0]%=mod;
    dp[i][1]%=mod;
    //cout<<i<<":"<<dp[i][0]<<":"<<dp[i][1]<<":"<<nofk<<endl;

    if(nofk<0 || (nofk!=0 && i==2*n)){
      cout<<0<<endl;
      return 0;
    }
  }

  cout << ((dp[2 * n][1]%mod)*(fac[n]%mod))%mod << endl;
}

Measured memory_bytes: 8324
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    ll n; cin >> n;
    ll a = ll(sqrt(n));
    vector<ll> und(0,0);

    rep(i,a+1){
        if(n % (i+1) == 0) und.push_back(i+1);
    }

    ll maxi = 0;

    rep(i,und.size()){
        maxi = max(maxi,und[i]);
    }

    ll semians = n/maxi;

    ll ans = 0;

    for(ll i=1; i <= semians; i*=10){
        ans++;
    }

    cout << ans << endl;
}

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

using namespace std;
const int MAX = 1e5+5;

long int A[MAX], DP[MAX];

int main() {
    int N, K; cin >> N >> K;
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    DP[0] = 0; DP[1] = abs(A[1]-A[0]);
    for(int i = 2; i < N; i++) {
        DP[i] = 1e9;
        for(int j = max(i-K,0); j < i; j++) {
            DP[i] = min(DP[i], DP[j] + abs(A[i] - A[j]));
            // DP[i] = min(DP[i], DP[i-2] + abs(A[i] - A[i-2]));
        }
    }

    cout << DP[N-1] << "\n";

    return 0;
}

Measured memory_bytes: 1792
N,M,X = map(int, input().split())

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

A.append(X)

# print(A)


A.sort()

X_index = int(A.index(X))
# print(X_index)

t = len(A)


# print(t)
# print(A)
diff_s = X_index
diff_b = t - X_index - 1

# print(diff_s)
# print(diff_b)


if diff_b == 0 or diff_s == 0:
  print(0)
elif diff_b < diff_s:
  print(diff_b)
else:
  print(diff_s)

  # 2 4 7 9 14

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
string poyo(string s,int n,int N);

int main() {
    int N;
    cin >> N;
    string s;
    if (N==1) {
        cout << "a" <<endl;
        return 0;
    }
    else {
        poyo("a",N-1,1);
    }
}

// poyo(ここまでの文字,残り文字数,文字種カウント)
string poyo(string s,int n,int cnt) {
    string t;
    if (n==1) {
        for (int i=0; i<cnt+1; i++) {
            t = 'a' + i;
            cout << s+t << endl;
        }
    }
    else {
        for (int i=0; i<cnt+1; i++) {
            t = 'a'+i;
            if (i == cnt) poyo(s+t,n-1,cnt+1);
            else poyo(s+t,n-1,cnt);
        }

    }
    return "null";
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

int n, k, fpb, maxim;
int a[N];

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

int main() {

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

    cin >> n >> k;
    maxim = INT_MIN;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        maxim = max(maxim, a[i]);
    }
    fpb = a[1];
    for(int i = 2; i <= n; i++) {
        fpb = gcd(fpb, a[i]);
    }
    if(k > maxim || k % fpb != 0) cout << "IMPOSSIBLE\n";
    else cout << "POSSIBLE\n";
}

Measured memory_bytes: 3960
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int i;
  long x[n];
  long x2[n];
  for(i=0;i<n;i++){
    cin >> x[i];
    x2[i] = x[i];
  }
  sort(x2,x2+n);
  long sm,la;
  sm = x2[n/2 -1];
  la = x2[n/2];
  for(i=0;i<n;i++){
    if(x[i]<=sm)cout <<la << endl;
    else cout << sm << endl;
  }
  
}

Measured memory_bytes: 5376