akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.readline
N=int(input())
A=[int(i) for i in input().split()]
A.sort()
K=A[0]
x=0
y=0
for i in range(N):
    if A[i]!=K and A[i]!=K+1:
        print('No')
        sys.exit()
    if A[i]==K:
        x+=1
    elif A[i]==K+1:
        y+=1

if x==N and x >=2*K:
    print('Yes')
    sys.exit()
if x==N and N==K+1:
    print('Yes')
    sys.exit()
if x<=K and y>=(K-x+1)*2:
    print('Yes')
    sys.exit()
print('No')

Measured memory_bytes: 52752
#include<stdio.h>
#define MAX 100000
int depth(int, int);
void print(int);
struct node{
    int p,l,r;
};
struct node data[MAX];
int n, data2[MAX];

int main(){
    int l,r,i,j,id,k,c;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        data[i].p=-1;
        data[i].l=-1;
        data[i].r=-1;
    }
    for(i=0;i<n;i++){
        scanf("%d",&id);
        scanf("%d",&k);
        for(j=0;j<k;j++){
            scanf("%d",&c);
            if(j==0)data[id].l=c;
            else data[l].r=c;
            l=c;
            data[c].p=id;
        }
    }
    for(i=0;i<n;i++){
        if(data[i].p==-1)r=i;
    }
    depth(r,0);
    for(i=0;i<n;i++)print(i);
    return 0;
} 
int depth(int x, int y){
    data2[x]=y;
    if(data[x].r!=-1)depth(data[x].r,y);
    if(data[x].l!=-1)depth(data[x].l,y+1);
    else return 0;
}
void print(int x){
    int i,c;
    printf("node %d: ",x);
    printf("parent = %d, ",data[x].p);
    printf("depth = %d, ",data2[x]);
    if(data[x].p==-1)printf("root, ");
    else if(data[x].l==-1)printf("leaf, ");
    else printf("internal node, ");
    printf("[");
    for(c=data[x].l,i=0; c!=-1; i++,c=data[c].r){
        if(i)printf(", ");
        printf("%d",c);
    }
    printf("]\n");
}


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

class Main {
    public static void main(String[] args) {
        try {
        	BufferedReader kb = new BufferedReader( new InputStreamReader( System.in ) );
        	int n = Integer.parseInt( kb.readLine( ) );
			String[] str = kb.readLine( ).split( " " );

			Set<Integer> S = new TreeSet<Integer>( );
			for( int i=0; i<n; i++ ) {
				S.add( Integer.parseInt( str[i] ) );
			}
	
        	int q = Integer.parseInt( kb.readLine( ) );
			str = kb.readLine( ).split( " " );
			int[] T = new int[ q ];
			for( int i=0; i<q; i++ ) {
				T[i] = Integer.parseInt( str[i] );
			}

			int cnt = 0;
			for( Integer val: T ) {
				if( S.contains( val ) ) cnt++;
			}
			System.out.println( cnt );

        } catch( IOException e ) {
            System.err.println( e );
        }
    }
}

Measured memory_bytes: 23564
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//(a+b-1)/b

signed main(){
	ll a,b; cin>>a>>b;
	ll ans=0;
	ll x=a;
	while(x<=b){
		ans++;
		x*=2;
	}
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 3620
// Virtual, WIP

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

// Utility
#define ALL(X) (X).begin(), (X).end()
#define RANGE(I, X, Y) for (int I = (X); I < (Y); I++)
using ll = int64_t;
using ull = uint64_t;
namespace std {
template<class ...Ts>        istream& operator>>(istream& i, tuple<Ts...>& x) { apply([&](auto&&... ys){ ((i >> ys), ...); }, x); return i; }
template<class T1, class T2> istream& operator>>(istream& i, pair<T1, T2>& x) { i >> x.first >> x.second; return i; }
template<class T>            istream& operator>>(istream& i, vector<T>& x)    { for (auto& y : x) { i >> y; } return i; }
}

// Debugging
#define DD(X) std::cout << #X ": " << (X) << std::endl << std::flush
namespace std {
template<class ...Ts>        ostream& operator<<(ostream& o, const tuple<Ts...>& x) { o << "("; apply([&](auto&& y, auto&&... ys){ o << y; ((o << ", " << ys), ...); }, x); o << ")"; return o; }
template<class T1, class T2> ostream& operator<<(ostream& o, const pair<T1, T2>& x) { o << tie(x.first, x.second); return o; }
template<class T>            ostream& operator<<(ostream& o, const vector<T>& x)    { o << "{"; for (auto it = x.begin(); it != x.end(); it++) { if (it != x.begin()) { o << ", "; } o << *it; } o << "}"; return o; }
template<class T1, class T2> ostream& operator<<(ostream& o, const set<T1, T2>& x)  { o << "{"; for (auto it = x.begin(); it != x.end(); it++) { if (it != x.begin()) { o << ", "; } o << *it; } o << "}"; return o; }
template<class T1, class T2> ostream& operator<<(ostream& o, const map<T1, T2>& x)  { o << "{"; for (auto it = x.begin(); it != x.end(); it++) { if (it != x.begin()) { o << ", "; } o << *it; } o << "}"; return o; }
}

// Main
vector<tuple<ll, ll>> factorize(ll n) {
  vector<tuple<ll, ll>> res(0, {0, 0});
  ll q = n;
  for (ll p = 2; p * p <= q; p++) {
    ll e = 0;
    while (q % p == 0) {
      q /= p;
      e++;
    }
    if (e > 0) {
      res.push_back({p, e});
    }
  }
  if (q > 1) {
    res.push_back({q, 1});
  }
  return res;
}

void mainCase() {
  ll n;
  cin >> n;

  auto factors = factorize(n);
  // DD(factors);

  ll res = 0;
  for (auto [_p, e] : factors) {
    // k-triangle-number <= e
    ll k = 1;
    while ((k * (k + 1)) <= 2 * e) {
      k++;
    }
    k--;
    // DD(tie(e, k));
    res += k;
  }
  cout << res << endl;
}

int main() {
  mainCase();
  return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SORT(i) sort((i).begin(),(i).end())
constexpr int INF = 2000000000;
constexpr int mod = 1000000007;

int main() {
	string s; cin >> s;
	string a = s;
	reverse(s.begin(), s.end());
	cout << (a == s ? "Yes" : "No") << "\n";

	return 0;
}

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

int main(){
  int n, k, x, sum;
  cin >> n >> k;
  for(int i=0;i<n;i++){
    cin >> x;
    if(k/2>=x) sum+=2*x;
    else sum+=2*(k-x);
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip> 



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

using namespace std;
int a,b;

int main(){
  cin >> a >> b;
  cout << a + b/2 << endl;
  return 0;
}


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

vector<int> graph[200000];
vector<ll> val;

void dfs(int v, int p = -1) {
  for (int c : graph[v]) {
    if (c == p) continue;
    val[c] += val[v];
    dfs(c,v);
  }
}

int main() {
  cout << setprecision(20);
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n-1; ++i) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  val.resize(n);
  for (int i = 0; i < q; ++i) {
    int p, x;
    cin >> p >> x;
    --p;
    val[p] += x;
  }
  dfs(0);
  for (int i = 0; i < n; ++i) {
    cout << val[i] << " "; 
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 24320
#include<bits/stdc++.h>
using namespace std;
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vec             vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define inf             1e18
#define no_of_test(x)        int x; cin>>x; while(x--)
const int mod = 1e9 + 7;
//actual code is at the top 
int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	no_of_test(x)
	{
      int a[3];
	  for(int i=0;i<3;i++) cin>>a[i];
	  sort(a,a+3);
	  if((a[0]==a[1]&& a[1]!=a[2])|| (a[2]==a[1]&& a[1]!=a[0]))
	  cout<<"Yes"<<'\n';
	  else
	  {
		  cout<<"No"<<'\n';
	  }
	  
	}
	return 0;
}

Measured memory_bytes: 3624
object Main {
  def main(args: Array[String]): Unit = {
    val factor_num   = scala.io.StdIn.readInt
    val factors      = scala.io.StdIn.readLine.split(" ").map{_.toInt}
    val sort_factors = factors.sorted

    var difference_num = 0

    (0 until factors.length).foreach { i =>
      if(factors(i) != sort_factors(i)) difference_num += 1
    }

    if(difference_num <= 2) println("YES")
    else                    println("NO")

  }
}

Measured memory_bytes: 25628
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)
 
    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod
 
    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv
 
    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv


comb = Combination(5 * 10**5)


def main():
    """
    「異なる」はネガティブだから逆を考えるべきなのか。。。
    そうすると包除原理が浮かんできそう
    A=[1,2,...,N]は仮定してよい。後で{}_M P_Nをかければよい。
    """
    N, M = map(int, input().split())
    ans = 0
    for i in range(N + 1):
        """
        B[j] = jなるものがi箇所ある場合。
        まずB[j] = jなるi箇所を選ぶためにcomb(N, i)必要。
        そのあとそれ以外の場所(N - i)箇所に埋める数を(M - i)個から選ぶための{}_{M-i} P_{N - i}が必要。
        """
        val = comb(N, i) * comb(M - i, N - i) * comb.fac[N - i] * (-1) ** i
        ans += val % mod
        #print("i={}, val={}".format(i, val))
    ans *= comb(M, N) * comb.fac[N]
    print(ans % mod)
    

if __name__ == "__main__":
    main()


Measured memory_bytes: 167196
n = int(input())
a = list(map(lambda x : int(x),input().split(" ")))
b = list(map(lambda x : int(x),input().split(" ")))
num = 0

for i in range(n):
  if a[i] >= b[i]:
    num += b[i]
  elif a[i] < b[i] and a[i+1] >= b[i] - a[i]:
    num += b[i]
    a[i + 1] = a[i + 1] - (b[i] - a[i])
  elif a[i] < b[i] and a[i+1] < b[i] - a[i]:
    num += a[i] + a[i+1]
    a[i + 1] = 0
    
print(num)

Measured memory_bytes: 18752
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c;
    int k;
    cin>>a>>b>>c>>k;
    if(a>=b&&a>=c){
        for(int i;i<k;i++){
            a *=2;
        }
    }
    else if(b>=c&&b>a){
        for(int i;i<k;i++){
            b *=2;
        }
    }
    else if(c>a&&c>b){
        for(int i=0;i<k;i++){
            c *=2;
        }
    }
    cout<<a+b+c<<endl;

}

Measured memory_bytes: 256
-- RayStark氏のコードを参考にした

local read = io.read
local floor = math.floor
local N = read("*n")
local A = {}
for i = 1, N do
	A[i] = read("*n")
end
table.sort(A)

local A_MAX = A[N]

local cant_div_s = {}
for i = 1, N do
	-- なんでcant_divs[i],(1<=i<=N)でないか
	-- A[i]にない数字は考えなくて良いから
	cant_div_s[A[i]] = true
end

local last_value = 0
for i = 1, N do
	-- cant_divs全部回したら時間かかるんじゃないのか？
	-- []のなかにA[i],(1<=i<=N)を使ってるのでN回の計算で済む
	if cant_div_s[A[i]] and last_value == A[i] then
		cant_div_s[A[i]] = false
	elseif cant_div_s[A[i]] then
		-- なんでj=1でなく2か
		-- A_MAXまでのA[i]より大きい倍数は倍数だから
		-- TODO: ここがボトルネックになっているためここの最適化
		for j = 2, floor(A_MAX / A[i]) do
			cant_div_s[A[i] * j] = false
		end
		-- なんで最後に処理した数字を残しておく必要があるか
		-- 同じ数が存在する場合にはじくため
		last_value = A[i]
	end
end

local num = 0
for i = 1, N do
	if cant_div_s[A[i]] then
		num = num + 1
	end
end

print(num)


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

using namespace std;

#define pb            push_back
#define mp            make_pair
#define po            pop_back
#define fi            first
#define se            second
#define mxn           100001
#define ll            long long int
#define ldb           long double
#define fr(i,a,b,k)   for(ll i=a ; i<b ; i+=k)
#define frr(i,a,b,k)  for(ll i=a ; i>b ; i-=k)
#define all(v)        v.begin(),v.end()
#define endl          "\n"
#define deg(x)        cout<<endl<<#x<<" = "<<(x)<<endl;
#define casep(x)      cout<<"Case #"<<(x)<<": ";
#define fast          ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));

typedef pair<ll,ll> pp;
typedef vector<ll> vi;
typedef vector<pp> vpp;
typedef vector<vi> vvi;

const int inf = 1e9+7;
const int minf = (-1)*(1e9+7);

ll power(ll a, ll n, ll mod) {ll p = 1;while (n > 0) {if(n%2) {p = p * a; p %= mod;} n >>= 1; a *= a; a %= mod;} return p % mod;}
ll gcd(ll a,ll b){ return __gcd(a,b);}
ll lcm(ll a,ll b){return a*b/__gcd(a,b);}

void solve(ll test){

    ll a,b,c;
    cin >> a >> b >> c;
    ll k;
    cin >> k;

    ll t1 = 0;
    while(a >= b){
        b*=2;
        t1++;
    }
    ll t2 = 0;
    while(b >= c){
        c *= 2;
        t2++;
    }

    ll ans = t1+t2;
    // deg(ans);
    (ans > k)?cout << "No": cout << "Yes";

}

int main(){

    fast;
    int t=1;
    // cin >> t;
    for(int i=1 ; i<=t ; i++){
        solve(i);
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
 
const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
ll gcd(ll x, ll y){
  if(y==0) return x;
  else return gcd(y, x%y);
}
ll lcm(ll x,ll y){
  ll g=gcd(x,y);
  return x/g*y;
}

using Graph=vector<vector<int>>;
Graph G;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a,b;
  cin >> a >> b;
  
  cout<<6-a-b<<endl;
}
    


Measured memory_bytes: 256
# from pprint import pprint
# import math
# import collections
from numba import jit

N = int(input())

# n, k = map(int, input().split(' '))
# a = list(map(int, input().split(' ')))

@jit(cache=True)
def calc(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


res = [0] * 1000009

for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            n = calc(x, y, z)
            res[n - 1] += 1

for i in range(N):
    print(res[i])


Measured memory_bytes: 117676
//g++ -std=gnu++14 a.cpp

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <random>
#include <math.h>
#include <stdio.h>

using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;
ll MODP = 998244353;

ll kai(ll x,ll y){
  if(y == 0)return 1;
  if(y == 1)return x;
  if(y&1){
    return (x*kai(x,y-1))%MOD;
  }else{
    ll t = kai(x,y/2);
    return (t*t)%MOD;
  }
}

ll comb(ll a,ll b,vector<ll> &p){
  if(a == 0)return 1;
  if(b == 0)return 1;
  ll ans = p[a+b];
  ans = (ans*kai(p[a],MOD-2))%MOD;
  ans = (ans*kai(p[b],MOD-2))%MOD;
  return ans;
}

ll mind(int x,vector<int> &v){
  int ok = v.size()-1,ng = -1;
  while(ok - ng > 1){
    int next = (ok+ng)/2;
    if(v[next] > x){
      ok = next;
    }else{
      ng = next;
    }
  }
  return ok;
}

ll maxd(int x,vector<int> &v){
  int ok = 0,ng = v.size();
  while(ng - ok > 1){
    int next = (ok+ng)/2;
    if(v[next] < x){
      ok = next;
    }else{
      ng = next;
    }
  }
  return ok;
}


int main(){
  ll N,K;
  cin >> N >> K;
  vector<ll> A(N);
  rep(i,N)cin >> A[i];
  ll ok = 1000000000,ng = 0;
  while(ok - ng > 1){
    ll kill = 0;
    ll next = (ok+ng)/2;
    rep(i,N){
      kill += A[i]/next;
      if(A[i]%next == 0)kill--;
    }
    if(kill <= K){
      ok = next;
    }else{
      ng = next;
    }
  }
  cout << ok << endl;

  return 0;
}


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

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    vector<int> b(n);
    rep(i, n) cin >> b[i];
    vector<int> c(n-1);
    rep(i, n) cin >> c[i];
    rep(i,n) a[i]--;
    int total = 0;
    rep(i,n){
        total += b[a[i]];
    }
    rep(i,n-1){
        if(a[i]+1 == a[i+1]){
            total += c[a[i]];
        }
    }
    cout << total << endl;
    return 0;
}
    

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define maxn 100003
#define maxk 100
#define mod 1000000007
using namespace std;

int n,k;
char s[maxn];
int dp[maxn][maxk][2];

int f(int curr, int sum, bool isSmaller) {
	if(curr == n)
		return (sum == 0);
	if(dp[curr][sum][isSmaller] != -1)
		return dp[curr][sum][isSmaller];
	dp[curr][sum][isSmaller] = 0;
	int val = s[curr] - '0';
	for( int i = 0 ; i <= val ; i++ )
		dp[curr][sum][isSmaller] = ( dp[curr][sum][isSmaller] + f(curr+1, (sum+i)%k, isSmaller || (i<val)) ) % mod;
	if(isSmaller)
		for( int i = val+1 ; i <= 9 ; i++ )
			dp[curr][sum][isSmaller] = ( dp[curr][sum][isSmaller] + f(curr+1, (sum+i)%k, true) ) % mod;
	return dp[curr][sum][isSmaller];
}

int main() {
	scanf("%s%d",s,&k);
	n = strlen(s);
	memset(dp, -1, sizeof(dp));
	printf("%d\n",(f(0,0,0)-1+mod)%mod);
	return 0;
}


Measured memory_bytes: 79488
#include <stdio.h>
#define N 200001
#include <stdlib.h>

int compareInt(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}


int main()
{

    int a;
    int b;
    int c;
    int d;
    int k;
    long long Big[N];
    long long small[N];

    scanf("%d", &a);

    for (int i = 0; i < a; i++)
    { //道を読み取る

        scanf("%lld %lld", &small[i],&Big[i]);

    }
    qsort(Big, a, sizeof(long long), compareInt);
    qsort(small,a, sizeof(long long), compareInt);

    if(a%2==0){
        long long distance =(Big[a / 2] + Big[a / 2-1] )- (small[a / 2]+small[a / 2-1]);//わる２して普通に差

        printf("%lld", distance+1);
    }
    else{//基)
        printf("%lld", Big[a / 2] - small[a / 2] + 1);
    }


    printf("\n");
}


Measured memory_bytes: 6812
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <string>
using namespace std;

int main(){
	int N, K;
	string S;
	cin >> N >> K >> S;
	vector<int> change;
	change.push_back(0);
	for(int i = 1;i<N;i++){
		if(S[i-1] != S[i]) change.push_back(i);
	}
	int R = (int)change.size();
	int ans = 0;
	for(int i=0;i<R;i++){
		if(S[change[i]] == '1')
			if(i + 2 * K + 1 < R){
				ans = max(ans, change[i + 2 * K + 1] - change[i]);
			}
			else ans = max(ans, N - change[i]);
		if(S[change[i]] == '0'){
			if(i + 2 * K < R){
				ans = max(ans, change[i + 2 * K] - change[i]);
			}
			else ans = max(ans, N - change[i]);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1020
/*
[abc134] B - Golden Apple
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

int N, D;

ll solve() { return (N + 2 * D) / (2 * D + 1); }

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

    cout << solve() << endl;

    return 0;
}


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

int main(){
   string s;
   string t;
   cin >> s >> t;
   int ans = 0;
   for(int i = 0; i< 3; i++){
       if (s.at(i) == t.at(i))
       {
           ans++;
       }
   }
   cout << ans << endl;
   
}
  

Measured memory_bytes: 256
import java.util.*

//fun <T> calcPermutationList(sortedList: Array<T>): List<List<T>> {
//    val permutationList = mutableListOf<List<T>>()
//    val queue = ArrayDeque<List<T>>().apply { addFirst(listOf()) }
//    while (queue.isNotEmpty()) {
//        val p = queue.removeFirst()
//
//        if (p.size == sortedList.size) {
//            permutationList += p
//        } else {
//            queue += sortedList.filterNot { p.contains(it) }.map { p + it }
//        }
//    }
//
//    return permutationList
//}

tailrec fun <T> calcPermutationList(
    sortedList: Array<T>,
    queue: ArrayDeque<List<T>>,
    permutationList: List<List<T>> = listOf()
): List<List<T>> {
    if (queue.isEmpty()) {
        return permutationList
    }

    val p = queue.removeFirst()
    val nextList = permutationList.toMutableList()
    if (p.size == sortedList.size) {
        nextList += p
    } else {
        queue += sortedList.filterNot { p.contains(it) }.map { p + it }
    }

    return calcPermutationList(sortedList, queue, nextList)
}

fun main(args: Array<String>) {
    val n = readInteger()
    val p = readIntegerList()
    val q = readIntegerList()

    calcPermutationList((1..n).toList().toTypedArray(), ArrayDeque<List<Int>>().apply { addFirst(listOf()) })
        .let { it.indexOf(p) - it.indexOf(q) }
        .let(Math::abs)
        .let(::println)
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)


Measured memory_bytes: 126896
N,K=map(int,input().split())
X=list(map(int,input().split()))
time=[]
zero=0
if 0 in X:
    zero=X.index(0)
    for i in range(N):
        if zero+i<N and zero-K+1+i>=0:
            time.append(min(abs(X[zero-K+1+i]),abs(X[zero+i]))+abs(X[zero-K+1+i])+abs(X[zero+i]))
else:
    g=1
    for i in range(N-1):
        if X[i]<0 and X[i+1]>0:
            g=0
            zero=i
            break
    if g==1:
        if X[0]<0:
            time.append(-X[-K])
        else:
            time.append(X[K-1])
        exit
    for i in range(N):
        if zero+i<N and zero-K+1+i>=0:
            time.append(min(abs(X[zero-K+1+i]),abs(X[zero+i]))+abs(X[zero-K+1+i])+abs(X[zero+i]))
print(min(time))


Measured memory_bytes: 14100
N, M = map(int, input().split())
A = list(set(map(lambda x : int(x)//2, input().split())))
def gcd(x, y):
  return x if y == 0 else gcd(y, x % y)
def lcm(x, y):
  return (x * y) // gcd(x, y)
l = A[0]
for a in A[1:]:
  l = lcm(l, a)
ans = (M // l + 1) // 2
for a in A[1:]:
  if (l // a) % 2 == 0:
    ans = 0
    break
print(ans)

Measured memory_bytes: 11356
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void p(vector<int> A){
    rep(i,A.size()){
        cout << A[i] << " ";
    }
    cout << "\n";
}

int main() {
    int n,k,q,a;
    cin >> n >> k >> q;
    vector<int> s(n);
    rep(i,q){
        cin >> a;
        s[a-1]++;
    }
    //p(s);
    rep(i,n) {
        //cout << k-q+s[i] << "\n";
        if(k-q+s[i] > 0)cout << "Yes" << "\n";
        else cout << "No" << "\n";
    }
}


Measured memory_bytes: 1024
package main

import (
	"fmt"
	"sort"
)

type sword struct {
	id, a, b int
}

type swords []sword

func (s swords) Len() int {
	return len(s)
}
func (s swords) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

type byAthenB struct {
	swords
}
type byBthenA struct {
	swords
}

func (a byAthenB) Less(i, j int) bool {
	if a.swords[i].a < a.swords[j].a {
		return true
	} else if a.swords[i].a == a.swords[j].a {
		if a.swords[i].b > a.swords[j].b {
			return true
		}
	}
	return false
}
func (b byBthenA) Less(i, j int) bool {
	if b.swords[i].b < b.swords[j].b {
		return true
	} else if b.swords[i].b == b.swords[j].b {
		if b.swords[i].a < b.swords[j].a {
			return true
		}
	}
	return false
}

func main() {
	var N, H int
	fmt.Scan(&N, &H)
	swords := make([]sword, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&swords[i].a, &swords[i].b)
		swords[i].id = i
	}
	// 斬りつけるための刀はaでソートして最大の剣のうち、投げつけ威力の小さいもの
	sort.Sort(byAthenB{swords})
	A := swords[len(swords)-1].a
	Aid := swords[len(swords)-1].id
	B := swords[len(swords)-1].b

	// 投げる価値のある剣を選ぶ
	Bs := make([]int, 0)
	sort.Sort(sort.Reverse(byBthenA{swords}))
	for i := 0; i < N; i++ {
		if swords[i].b >= A && swords[i].id != Aid {
			Bs = append(Bs, swords[i].b)
		}
	}
	// 投げられる剣は最初に全て投げてしまって良い
	ans := 0
	for i := 0; i < len(Bs); i++ {
		H -= Bs[i]
		ans++
		if H <= 0 {
			fmt.Println(ans)
			return
		}
	}
	// まだHPが残っていれば、残った剣で斬る（最後に投げる分を引いておく）
	if B > A {
		H -= B
		ans++
	}
	ans += ((H + A - 1) / A)
	fmt.Println(ans)
}


Measured memory_bytes: 8576
#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

int main(){
	int n; cin >> n; std::vector<int> x(n);
	for(int i = 0; i < n; i++) cin >> x[i];
	int L, Q; cin >> L >> Q;
	
	int cnt = 0;
	std::vector<std::vector<int>> dp(21, std::vector<int>(n, -1));
	for(int i = 0; i < n; i++) {
		while(cnt < n and x[cnt] - x[i] <= L) cnt++;
		dp[0][i] = cnt - 1;
	}
	
	for(int i = 1; i < 21; i++) {
		for(int j = 0; j < n; j++) {
			dp[i][j] = dp[i - 1][dp[i - 1][j]];
		}
	}
	
	for(int q = 0; q < Q; q++) {
		int a, b; cin >> a >> b; a--; b--;
		if(a > b) std::swap(a, b);
		
		int ans = 0;
		for(int i = 20; i >= 0; i--) {
			if(dp[i][a] < b) {
				ans |= (1 << i);
				a = dp[i][a];
			}
		}
	
		cout << ans + 1 << endl;
	}
	return 0;
}


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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

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

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 (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"; return os;}
template<class T,size_t n> ostream& operator<<(ostream &os, const array<T,n> &t) {os<<"{"; rep(i,n) {os<<t[i]<<",";} os<<"}"; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const ll INF = 1e9+7;


int main(){
	ios_base::sync_with_stdio(false);
	ll N;
	deque<int> ans;

	cin >> N;

	if( N == 1 ){
		cout << 2 << endl;
		cout << "1 1" << endl;
		return 0;
	}

	int idx = 1;
	for(ll k=45; k>0; k--){
		if( N & (1ll<<k) ){
			ans.push_back(idx++);
			if( ans.size() > 1 ){
				int f = ans.front();
				ans.pop_front();
				ans.push_front(idx++);
				ans.push_front(f);
			}
		}else if( ans.size() ){
			ans.push_back(idx++);
		}
	}
	ans.push_front(idx++);
	if( N & 1 ) ans.push_front(idx++);

	// verify
	vector<int> v;
	for(auto t: ans) v.push_back(t);
	v.push_back(idx);
	ll dp[10005]={};
	rep(i,v.size()){
		rep(j,i) if( v[j] < v[i] ) dp[i] += dp[j];
		dp[i] += 1;
	}
	//cout << "dp = " << dp[ans.size()]-1 << endl;

	cout << ans.size()*2 << endl;
	rep(i,ans.size()) cout << i+1 << " ";
	for(auto t: ans) cout << t << " ";
	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

using std::min;
using std::sort;

const int MAXN=100011;

int N;

struct Pair{
	int p, v;
} P[MAXN];

inline bool operator < (const Pair &A, const Pair &B){
	return (A.v==B.v)?(A.p<B.p):(A.v<B.v);
}

int Minp[MAXN];

long long Ans[MAXN];

int main(){
	
	scanf("%d", &N);
	
	for(int i=1;i<=N;++i){
		P[i].p=i;
		scanf("%d", &P[i].v);
	}
	
	sort(P+1, P+N+1);
	
	Minp[N]=P[N].p;
	for(int i=N;i>1;--i)	Minp[i-1]=min(Minp[i], P[i-1].p);
	
	for(int i=N;i>=1;--i){
		if(P[i].v!=P[i-1].v){
			Ans[Minp[i]]+=1LL*(P[i].v-P[i-1].v)*(N-i+1);
		}
	}
	
	for(int i=1;i<=N;++i)	printf("%lld\n", Ans[i]);
	
	return 0;
}

Measured memory_bytes: 2944
import math

def area(n):
    S,r,t=0,10,0
    for i in range(n):
        if i==n-1:
            v=360-t
        else:
            v=input()
            t+=v
        S+=r*r*math.sin(math.pi*v/180)/2
    return S

while True:
    m=input()
    if m==0:break
    S1=area(m)
    n=input()
    S2=area(n)
    if S1>S2:
        print 1
    elif S1<S2:
        print 2
    else:
        print 0

Measured memory_bytes: 4412
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;

const int N = 505;

int i, j, n, c[N], f[N], s[N];

int solve(int x, int curr) {
  if(x == n) return curr;

  if(curr < s[x]) curr = s[x];
  while(curr % f[x]) ++curr;
  return solve(x + 1, curr + c[x]);
}

int main() {
  scanf("%d", &n);
  for(i = 1; i < n; ++i) scanf("%d %d %d", c + i, s + i, f + i);

  for(i = 1; i <= n; ++i) printf("%d\n", solve(i, s[i]));

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int n;
int a[1 << 18];

//[l, r)
int dfs(int l, int r) {
	if (r - l == 1) return a[l];
	int x = dfs(l, l + (r - l) / 2);
	int y = dfs(l + (r - l) / 2, r);
	if (x > y) return x - y;
	if (x == y) return x;
	return y - x;
}

int main() {
	int i;
	cin >> n;
	rep(i, (1 << n)) cin >> a[i];
	cout << dfs(0, (1 << n)) << endl;
	return 0;
}

Measured memory_bytes: 1280
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int R = sc.nextInt();
		if(R<1200)System.out.println("ABC");
		if((1200<=R) && (R<2800))System.out.println("ARC");
		if(2800<=R)System.out.println("AGC");
	}
}

Measured memory_bytes: 22996
//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <iomanip>
#include <stack>
#include <bitset>

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

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(a>b){a=b;return 1;}return 0;}

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

  int n, k;
  string s;

  cin >> n >> k;
  cin >> s;

  int cnt = 0;

  REP(i, n-1) if(s[i] == s[i+1]) cnt++;

  cout << min(cnt+2*k, n-1) << endl;  

  return 0;
}


Measured memory_bytes: 512
// Example program
#include <iostream>
#include <string.h>
#include <algorithm>  
#include<vector>
using namespace std;
int main()
{

  int n,b;
  cin>>n;
  int a[50][28];
  char s[1000];
  for(int i=0;i<50;i++)
      for(int j=0;j<28;j++) a[i][j]=0;
  for(int i=0;i<n;i++){
      cin>>s;
      for(int j=0;j<strlen(s);j++){ 
          a[i][s[j]-'a']++;
      }
}
  for(int i=0;i<26;i++){
      int min=30000;
      for(int j=0;j<n;j++){
        
           if(a[j][i]<min){
            min=a[j][i];   
           }
      }
      char c='a'+i;
     
      for(int j=0;j<min;j++){
          cout<<c;
      }
  }

}


Measured memory_bytes: 256
parseInt(x) = parse(Int, x)

function isblack(x::Array{String, 2}, i, j, h, w)
	if i > h || j > w || i < 1 || j < 1
		return(0)
	elseif x[i,j] == "#"
		return(1)
	else
		return(0)
	end
end

function isolate(x::Array{String, 2}, i,j, h, w)
	if isblack(x, i-1, j, h, w)+isblack(x, i+1, j, h, w)+isblack(x, i, j-1, h, w)+isblack(x, i, j+1, h, w) == 0
		return(1)
	else
		return(0)
	end
end

function main()
	h, w = parseInt.(split(readline()))
	s = Array{String}(h,w)
	for i in 1:h
		s[i,:] = split(chomp(readline()), "")
	end
	flg = 0
	for i in 1:h
		for j in 1:w
			if s[i,j] == "#"
				if isolate(s, i, j, h, w) == 1
					print("No")
					flg = 1
					break
				end
			end
		end
		if flg == 1
			break
		end
	end
	if flg == 0
		print("Yes")
	end
end

main()

Measured memory_bytes: 122004
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int W, H, N, S;
    cin >> W >> H >> N;
    S = 0;
    int x[N], y[N], a[N];
    int gra[W][H];
    for (int i = 0; i < W;i++){
        for (int j = 0; j < H;j++){
            gra[i][j] = 1;
        }
    }
        for (int i = 0; i < N; i++)
        {
            cin >> x[i] >> y[i] >> a[i];
        }

    for (int i = 0; i < N;i++){
        if(a[i]==1){
            for (int j = 0; j < x[i];j++)
            {
                for (int k = 0; k < H;k++){
                    gra[j][k] = 0;
                }
            }
        }else if (a[i]==2){
            for (int j = x[i]; j < W; j++)
            {
                for (int k = 0; k < H; k++)
                {
                    gra[j][k] = 0;
                }
            }
        }else if (a[i]==3)
        {
            for (int j = 0; j < y[i]; j++)
            {
                for (int k = 0; k < W; k++)
                {
                    gra[k][j] = 0;
                }
            }
        }else
        {
            for (int j = y[i]; j < H; j++)
            {
                for (int k = 0; k < W; k++)
                {
                    gra[k][j] = 0;
                }
            }
        }
}
for (int i = 0; i < W; i++)
{
    for (int j = 0; j < H; j++)
    {
        S = S + gra[i][j];
    }
}
cout << S << endl;
}

Measured memory_bytes: 256
from fractions import gcd
from functools import reduce

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

gcds = [-1] * N
gcds_rev = [-1] * N
for i in range(0,N):
  if i == 0: gcds[i] = A[0]
  else: gcds[i] = gcd(gcds[i-1], A[i])

  rev_i = N-1-i
  if rev_i == N-1: gcds_rev[rev_i] = A[-1]
  else: gcds_rev[rev_i] = gcd(gcds_rev[rev_i+1], A[rev_i])

ans = -float('inf')
for i in range(N):
  if i == 0:val = gcds_rev[1]
  elif i == N-1:val = gcds[-2]
  else: val = gcd(gcds[i-1], gcds_rev[i+1])
  ans = max(ans, val)
print(ans)

Measured memory_bytes: 89580
S = input().rstrip()
if 1<=int(S[:2])<=12:
    if 1<=int(S[2:])<=12:
        print("AMBIGUOUS")
    else:
        print("MMYY")
else:
    if 1<=int(S[2:])<=12:
        print("YYMM")
    else:
        print("NA")



Measured memory_bytes: 61020
package main

import (
	"fmt"
)

func main() {
	var r int
	var d int
	var x2000 int

	fmt.Scan(&r)
	fmt.Scan(&d)
	fmt.Scan(&x2000)

	x := x2000
	for i := 0; i < 10; i++ {
		x = r*x - d
		fmt.Println(x)
	}
}


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

using namespace std;

#ifdef NeverBeRed
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<ll> point;
#define F first
#define S second



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

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

	ll a, b;
	cin >> a >> b;
	ll g = __gcd(a, b);
	int ans = 1;
	for (ll i = 2; i*i <= g; ++i)
		if (g % i == 0)
		{
			++ans;
			while (g % i == 0) g /= i;
		}

	cout << ans+(g > 1) << "\n";

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000000
#define endl '\n'
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; }
using namespace std;

signed main(void){
    string a; cin>>a;
    vector<char> vec(a.size());
    rep(i,a.size())vec.at(i)=a.at(i);
    sort(all(vec));
    vec.push_back('*');
    vector<int> cnt;
    int cou=0;
    rep(i,vec.size()-1){
        cou++;
        if(vec.at(i)!=vec.at(i+1)){
            cnt.push_back(cou);
            cou=0;
        }
    }
    int ans=(a.size())*(a.size()-1)/2;
    cnt.push_back(cou);
    rep(i,cnt.size()){
        ans-=(cnt.at(i))*(cnt.at(i)-1)/2;
    }
    cout<<ans+1<<endl;
}


Measured memory_bytes: 900
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Date;
import java.util.LinkedList;
import java.util.ListIterator;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO ?????????????????????????????????????????????
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		Date from = new Date();
		LinkedList<Integer> list = new LinkedList<Integer>();
		for(int i = 0; i < n; i++){
			String[] strArray = br.readLine().split(" ");
			String inst = strArray[0];

			if(inst.equals("insert")){
				list.addFirst(Integer.parseInt(strArray[1]));
			}
			else if(inst.equals("delete")){
				list.removeFirstOccurrence(Integer.parseInt(strArray[1]));
			}
			else if(inst.equals("deleteFirst")){
				list.poll();
			}
			else if(inst.equals("deleteLast")){
				list.removeLast();
			}
			//System.out.println("i = " + i);
			//printList(list);

		}
		Date to = new Date();

		//System.out.println("Instruction Done "+(to.getTime() - from.getTime()) + " milli sec");
		printList(list);
	}

	static void printList(LinkedList<Integer> list){

		Date from = new Date();
		int j = 0;
		StringBuffer sb = new StringBuffer();
		ListIterator<Integer> it = list.listIterator();
		for(int i = 0; i < list.size() ; i++){
			//list.get(i);

			int tmp = it.next();
			/*
			System.out.print(tmp);
			if(i != list.size() - 1){
				System.out.print(" ");
			}
			*/

			/*
			System.out.print(list.get(i));
			if(i != list.size() - 1){
				System.out.print(" ");
			}
			*/


			sb.append(String.valueOf(tmp));
			if(i != list.size() - 1){
				sb.append(" ");
			}

		}

		System.out.println(sb.toString());
		Date to = new Date();
		//System.out.println("it takes"+(to.getTime() - from.getTime()));
	}

}

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

rest = []
for i in range(n):
	s,p = map(str,input().split())
	rest.append([s,int(p)])

rest_sort = sorted(rest,key=lambda x:(x[0],-x[1]))

count = 0
while count != n:
	for i in range(n):
		if rest_sort[count] == rest[i]:
			print(i+1)
	count += 1

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

int main()
{
  string s;
  cin >> s;
  int plus;
  for(int i = 0; i < 3; i++)
  {
    if (s[i] == 'o')
      plus++;
  }
  cout << 700 + (plus * 100) << endl;
}

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

using namespace std;

const int maxn = 2010;

int n, a[maxn], tim;
int _vis[maxn], _mn = 0, in[maxn], vis[maxn], fa[maxn], mn[maxn];
vector<int> ans, vec[maxn*20];
vector<int> prm[maxn], tot_prm;

int gcd(int x, int y) {
	if (!y) return x;
	return gcd(y, x % y);
}

void _dfs(int u) {
	_mn = min(_mn, u);
	_vis[u] = 1;
	for (int v = 1; v <= n; v++) {
		if (gcd(a[u], a[v]) != 1 && !_vis[v]) {
			_dfs(v);
		}
	}
}

int getroot(int x) {
	if (x == fa[x]) return x;
	return fa[x] = getroot(fa[x]);
}

void Union(int x, int y) {
	int rx = getroot(x), ry = getroot(y);
	if (rx != ry) {
		fa[rx] = ry;
		mn[ry] = min(mn[ry], mn[rx]);
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		int x = a[i];
		for (int j = 2; j * j <= x; j++) {
			if (x % j == 0) {
				prm[i].push_back(j);
				tot_prm.push_back(j);
				while (x % j == 0) {
					x /= j;
				}
			}
		}
		if (x > 1) {
			prm[i].push_back(x);
			tot_prm.push_back(x);
		}
	}
	sort(tot_prm.begin(), tot_prm.end());
	tot_prm.erase(unique(tot_prm.begin(), tot_prm.end()), tot_prm.end());
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < prm[i].size(); j++) {
			prm[i][j] = int (lower_bound(tot_prm.begin(), tot_prm.end(), prm[i][j]) - tot_prm.begin());
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!_vis[i]) {
			_mn = n;
			_dfs(i);
			in[_mn] = 1;
		}
	}
	for (int T = 1; T <= n; T++) {
		for (int i = 0; i < tot_prm.size(); i++) vec[i].clear();
		for (int i = 1; i <= n; i++) {
			fa[i] = i;
			mn[i] = (in[i] ? i : n);
			if (!vis[i]) {
				for (int j = 0; j < prm[i].size(); j++) {
					vec[prm[i][j]].push_back(i);
				}
			}
		}
		for (int i = 0; i < tot_prm.size(); i++) {
			for (int j = 0; j + 1 < vec[i].size(); j++) {
				int x = vec[i][j], y = vec[i][j+1];
				Union(x, y);
			}
		}
		int mx = 0;
		for (int i = 1; i <= n; i++) {
			if (!vis[i]) {
				mx = max(mx, mn[getroot(i)]);
			}
		}
		vis[mx] = 1; ans.push_back(a[mx]);
		for (int i = 1; i <= n; i++) {
			if (getroot(i) == getroot(mx)) {
				in[i] = (gcd(a[i], a[mx]) != 1);
			}
		}
	}
	for (int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
	puts("");
	return 0;
}

Measured memory_bytes: 1664
h, w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
func=[]
for i in range(h):
    for j in range(w):
        if a[i][j] & 1:
            if j < w - 1:
                a[i][j + 1] += 1
                a[i][j] -= 1
                func.append((i, j, i, j + 1))

            elif i < h - 1:
                a[i + 1][j] += 1
                a[i][j] -= 1
                func.append((i, j, i + 1, j))

# for i in a:
#     print(*i)
print(len(func))
for y, x, i, j in func:
    print(y + 1, x + 1, i + 1, j + 1)


Measured memory_bytes: 97824
import java.util.*;

class Main {
    //
    static final long MOD = 1_000_000_007; // 10^9+7
    static final int MAX = 2_147_483_646; // intの最大値
    static final int INF = 1_000_000_000; // 10^9

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ary = new int[n];
        for (int i = 0; i < n; i++) {
            ary[i] = sc.nextInt();
        }
        Arrays.sort(ary);
        double ans = ary[0];
        for(int i = 1;i < n;i++){
            ans = ans + ary[i];
            ans /= 2;
        }
        System.out.println(ans);
        
    }

}

Measured memory_bytes: 21844
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int p[10][10];
int dis2;
int dis;
bool isint;
void check(int i, int j){
	dis2 = 0;
	for(int k=0;k<10;k++){
		dis2 += (p[i][k] - p[j][k])*(p[i][k] - p[j][k]);
	}
	dis = sqrt(dis2);

	if(dis2==dis*dis) isint = true;
	else isint = false;
}

int main(){
  	for(int i=0;i<10;i++){
  		for(int j=0;j<10;j++){
  			p[i][j] = 0;
  		}
  	}

  	int N, D;
  	cin >> N >> D;
  	for(int i=0;i<N;i++){
  		for(int j=0;j<D;j++){
  			cin >> p[i][j];
  		}
  	}
  	int ans = 0;

  	for(int i=0;i<N-1;i++){
  		for(int j=i+1;j<N;j++){
  			check(i, j);
  			//cout << dis <<endl;
  			if(isint) ans++;
  		}
  	}
  	cout << ans <<endl;

  	return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef long long ll;

int main()
{
	int A,B,C,D;
	scanf("%d%d%d%d", &A,&B, &C, &D);
	int a[2] = {B, D};
	int i = 1;
	while (1)
	{
		if (i % 2)
			C -= B;
		if (i % 2 == 0)
			A -= D;
		if (A <= 0)
		{
			printf("No");
			break ;
			return 0;
		}
		if (C <= 0)
		{
			printf("Yes");
			break ;
			return 0;
		}
		i++;
	}
	return (0);
}

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

using namespace std;
#define endl "\n"

const int MOD = 1000000007;



int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
    string x;
    cin >> x;
    if(x[0] == x[2]) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    
    
    
    
	return 0;
}

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

using namespace std;

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	
	priority_queue <double> pq;
	
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		pq.push(x);
	}
	
	for (int i = 0; i < m; i++) {
		double x = pq.top();
		pq.pop();
		pq.push(x / 2);
	}
	
	long long res = 0;
	
	for (int i = 0; i < n; i++) {
		res += (int)pq.top();
		pq.pop();
	}
	
	printf("%lld\n", res);
}


Measured memory_bytes: 1400
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(I, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
using ll = long long;

int main() {
  string s;
  cin >> s;
  
 
  
  if(s != "AAA" && s != "BBB") cout << "Yes" << endl;
  else  cout << "No" << endl;
  
}

Measured memory_bytes: 3636
n = int(input())
s1 = input()
s2 = input()

ans=3
last="X"
i=0

if s1[i] == s2[i]:
    last="x"
    ans=3
    i=1
else:
    last="y"
    ans=6
    i=2

while i < n:
    if s1[i] == s2[i]: # x
        if last=="x":
            ans*=2
        last="x"
        i+=1
    else:
        if last=="x":
            ans*=2
        else:
            ans*=3
        last="y"
        i+=2
    ans %= 1000000007
print(ans)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    
    int n;
    cin >> n;

    vector<int> v(n);
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
        sum += v[i];
    }

    int psum = 0;
    int res = 1e9;
    for (int i = 0; i < n; ++i) {
        psum += v[i];
        res = min(res, abs(sum - 2*psum));
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 384
#include<stdio.h>

int main(){
   char s[11], t[12];
   scanf("%s", s);
   scanf("%s", t);

   int s_len, t_len;
   for(s_len = 0; s[s_len] != 0; s_len++);
   for(t_len = 0; t[t_len] != 0; t_len++);

   if(1 <= s_len && s_len <= 10 && s_len  == t_len - 1){
      int judge = 0;
      for(int i=0; i<s_len; i++){
         if(s[i] != t[i]){
            judge = 1;
         }
      }
      if(judge == 0){
         printf("Yes\n");
      } else {
         printf("No\n");
      }
   } else {
      printf("No\n");
   }

   return 0;
}

Measured memory_bytes: 1600
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem A

if __name__ == '__main__':
    n = int(input())
    k = int(input())
    x = int(input())
    y = int(input())
    diff = n - k

    if diff > 0:
        print((k * x) + diff * y)
    else:
        print(n * x)


Measured memory_bytes: 2940
#include <algorithm>
#include <bits/stdc++.h>
#include<iostream>
#include<string>
using namespace std;
#define rep(i, n) for (int i = 0; i <(int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
const ll MOD=100000007;
const ll INF=1000000101001;
int main(){
string s;cin>>s;
bool ok=true;
int size=s.size();
rep(i,size){
    if(i%2==0&&s[i]=='L')ok=false;
    if(i%2!=0&&s[i]=='R')ok=false;
}
if(ok)cout << "Yes" << endl;
else cout << "No" << endl;
}

Measured memory_bytes: 256