akhauriyash/Code-Regression huggingface dataset:
#coding: utf-8

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        # xの根を探索
        if self.parents[x] < 0:
            return x
        else:
            # 再帰的に根を探索して経路圧縮
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        # 2つの木をマージする。
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        # xの根の所属するグループの要素数を返す
        return -self.parents[self.find(x)]

    def are_same(self, x, y):
        # 2つの要素の根が同じかどうかを調べる
        return self.find(x) == self.find(y)

    def members(self, x):
        # xと同じ根の要素をリストで出力
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == self.n]

    def roots(self):
        # 根である要素をリストで出力
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{} {}".format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
uf = UnionFind(N)
A, B = [], []
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
A = A[::-1]
B = B[::-1]
ans = [N*(N-1)//2]
for a, b in zip(A, B):
    if not uf.are_same(a-1, b-1):
        ans.append(max(0, ans[-1] - uf.size(a-1) * uf.size(b-1)))
    else:
        ans.append(ans[-1])
    uf.union(a-1, b-1)
# ans.append(max(0, ans[-1] - uf.size(a-1) * uf.size(b-1)))
print(*ans[::-1][1:], sep="\n")


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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const int INF=123456789;
int dp[17000][14];

int main()
{
    int n;
    while(cin >>n,n)
    {
        vector<string> city(n);
        rep(i,n) cin >>city[i];

        vector<string> s;
        rep(i,n)
        {
            bool isSubstring=false;
            int A=city[i].size();
            rep(j,n)
            {
                if(i==j) continue;

                int B=city[j].size();
                rep(k,B-A+1)
                {
                    if(city[j].substr(k,A)==city[i]) isSubstring=true;
                }
            }

            if(!isSubstring) s.pb(city[i]);
        }

        int S=s.size();

        // s[i],s[j]???????????£???????????????s[i]???suffix??¨s[j]???prefix?????±?????¨???????????§???
        int com[14][14]={0};
        rep(i,S)rep(j,S)
        {
            if(i==j) continue;
            int A=s[i].size(), B=s[j].size();
            for(int k=1; k<=min(A,B); ++k)
            {
                if(s[j].substr(0,k)==s[i].substr(A-k,k)) com[i][j]=k;
            }
        }

        fill(dp[0],dp[17000],INF);
        rep(i,S) dp[1<<i][i]=s[i].size();
        for(int mask=1; mask<(1<<S); ++mask)
        {
            rep(i,S)if(mask>>i&1)
            {
                rep(j,S)if(!(mask>>j&1))
                {
                    int add=s[j].size();
                    add-=com[i][j];
                    int nx=mask+(1<<j);

                    dp[nx][j]=min(dp[nx][j],dp[mask][i]+add);
                }
            }
        }

        int ans=INF;
        rep(i,S) ans=min(ans,dp[(1<<S)-1][i]);
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 4044
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n;
  cin >> n;
  unordered_set<char> s;
  rep(i, 0, n) {
    char c;
    cin >> c;
    s.insert(c);
  }

  cout << (s.size() == 3 ? "Three" : "Four") << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
 
const int maxn = 1e5 + 20, inf = 1e9+1;

ll n, a, b;

int main()
{
	
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> a >> b;
	cout << ( (abs(a-b)-1) & 1 ? "Alice" : "Borys") << endl;
	return 0;
}

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

int main(){
    string s; getline(cin, s); s = "0"+s;
    string t; getline(cin, t); t = "0"+t;
    int s_len = s.size(), t_len = t.size();

    int dp[s_len][t_len];
    char action [s_len][t_len];

    for (int i=0; i<s_len; i++){
        for (int j=0; j<t_len; j++){
            if (i==0||j==0){
                dp[i][j]=0;
                action[i][j] = '0';
            }
            else if (s[i]==t[j]){
                dp[i][j] = dp[i-1][j-1] + 1;
                action[i][j] = 'h';
            }
            else if (dp[i-1][j] > dp[i][j-1]){
                dp[i][j] = dp[i-1][j];
                action[i][j] = 'u';
            }
            else if (dp[i-1][j] <= dp[i][j-1]){
                dp[i][j] = dp[i][j-1];
                action[i][j] = 'l';
            }
        }
    }

    int ans_len = dp[s_len-1][t_len-1];
    int s_ind = s_len-1, t_ind = t_len-1;
    string ans = "";

    while(ans_len){
        if (action[s_ind][t_ind]=='h'){
            // cout << s[s_ind] << endl;
            ans = s[s_ind]+ans;
            s_ind--; t_ind--; ans_len--;
        }
        else if (action[s_ind][t_ind]=='l') t_ind--;
        else if (action[s_ind][t_ind]=='u') s_ind--;
    }
    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 44288
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
//#include<cstdio>//"scanf("%lf",&(double));printf("%f",(double));"
//#include<iomanip>//"cout<<fixed<<setprecision(n)<<sth<<endl;"
//#include<string>//"reverse(s's it,s's it)"
//#include<functional>//"greater<T>" "sort(a,a+n,greater<int>());""
//#include<cmath>//"abs" "sqrt"
//#include<numeric>//"accumulate(inputit,inputit,init,(optional) object)"
//#include<algorithm>//"lower_bound(it,it,v)" "next_permutation(a,a+n)"
//"reverse(v's it,v's it)"(v: vector)
//#include<cassert>//"assert(cond);": error if cond doesn't hold.
using namespace std;
#define pb push_back//also for STRING
#define fi first
#define sc second
#define mp make_pair
#define is insert//also use as v.is(v's it,w's it,w's it);//Be careful in topcoder
#define ps push//stack,(priority) queue,//Be careful in topcoder.
#define fr front//queue//for priority, use top().//Be careful in topcoder.
typedef long long ll;//not necessarily//Be careful in topcoder.
typedef pair<int,int> pii;//Be careful in topcoder.
//Add other types in the same way.
const ll M = 1000000007;//can be changed
ll mod(ll a){	return (a + M) % M;	}//M can be a variable
void plmod(ll &a,ll b){	a = (a + b + M) % M;	return;	}
void mnmod(ll &a,ll b){	a = (a - b + M) % M;	return;	}
void mlmod(ll &a,ll b){	a = (a * b) % M;  	return;	}
//Caution! you may need sth larger than "+M"!
void chmax(int &a,int b){	a = max(a, b);	return;	}
void chmin(int &a,int b){	a = min(a, b);	return;	}
//These 2 could be better in long long

#define MAX_N 100;
double a[100];

int main(){
    int n;
    cin>>n;
    double s=0;
    for(int i=0;i<n;++i){
        cin>>a[i];
        s+=a[i];
    }
    s/=n;
    double d = 10000.0;
    int ans = 0;
    for(int i=0;i<n;++i){
        if(d>abs(a[i]*1.0 - s)){
            ans = i;
            d = abs(a[i]*1.0 - s);
        }
    }
    printf("%d\n", ans);
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
    double r, area, cir, pi = 3.141592653589;
    scanf("%lf", &r);
    area = r * r * pi;
    cir = 2 * r * pi;
    printf("%f %f\n", area, cir);
    return 0;
}

Measured memory_bytes: 1076
N,M,X= map(int,input().split())
C = []
A = []
for i in range(N):
    I = list(map(int,input().split()))
    C.append(I[0])
    A.append(I[1:])
min = 10 ** 9
for i in range(2**N):
    U = [0 for i in range(M)]
    c = 0
    I = bin(i)[2:]
    I = "0"*(N-len(I)) + I
    for j in range(N):
        if int(I[j]):
            c += C[j]
            a = A[j]
            for s in range(M):
                U[s] = U[s] + a[s]
    state = 1
    for s in range(M):
        if U[s] < X:
            state = 0
            break
    if state:
        if min >= c:
            min = c
if min ==10 ** 9:
    print(-1)
else:
    print(min)

Measured memory_bytes: 9256
line = input().rstrip().split(' ')
n = int(line[0])
k = int(line[1])

line = input().rstrip().split(' ')
p = []

for i in range(n):
    p.append(int(line[i]))

p.sort()

ans = 0
for i in range(k):
    ans += p[i]

print(ans)


Measured memory_bytes: 9192
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<ll, int> P;
#define MOD (1000000007ll)

ll sq(ll x){
	return x*x;
}

int main(void){
	int n,k,x,y,ans;
	cin >> n;
	cin >> k;
	cin >> x;
	cin >> y;
	ans = (min(n,k))*x+(max(n-k,0))*y;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
# include <iostream>
# include <cstdio>
# include <cmath>
# include <algorithm>
using namespace std;
struct Node{
    long long d;
    long long c;
}N[400010];
int cnt = 0;
bool cmp(struct Node a,struct Node b)
{
    if (a.d==b.d) return a.c<b.c;
    return a.d>b.d;
}
int main(void)
{
    // freopen("aaa.in","r",stdin);
    long long X,Y,A,B,C;
    scanf("%lld%lld%lld%lld%lld",&X,&Y,&A,&B,&C);
    for (int i=1;i<=A;i++)
    {
        N[++cnt].c = 1;
        scanf("%lld",&N[cnt].d);
    }
     for (int i=1;i<=B;i++)
    {
        N[++cnt].c = 2;
        scanf("%lld",&N[cnt].d);
    }
     for (int i=1;i<=C;i++)
    {
        N[++cnt].c = 3;
        scanf("%lld",&N[cnt].d);
    }
    sort(N+1,N+cnt+1,cmp);
    long long ans = 0;
    long long Z=0;
    for (int i=1;i<=cnt;i++)
    {
        if (N[i].c==1)
        {
            if (X){
                X--;
                ans+=N[i].d;
            }
        }
        if (N[i].c==2)
        {
            if (Y)
            {
                Y--;
                ans+=N[i].d;
            }
        }
        if (N[i].c==3)
        {
            if (X>0||Y>0){
                Z++;
                ans+=N[i].d;
            }
        }
        if (Z==X+Y) break;
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 7908
n, a, b = gets.split(" ").map(&:to_i)

if (b - a).even?
  puts (b - a) / 2
else
  if b - a == 1
    puts [n - a, b - 1].min
  else
    puts [a - 1, n - b].min + 1 + (b - a - 1) / 2
  end
end


Measured memory_bytes: 1788
n=gets.to_i
x=eval b="gets.split.map &:to_f"
y=eval b
z=[]
d=[0]*3
1.upto(3){|j|
n.times{|i|d[j-1]+=(z[i]=(x[i]-y[i]).abs)**j}
d[j-1]**=1.0/j
}
puts d
p z.max


Measured memory_bytes: 6940
import java.util.*;

public class Main {
    private static Scanner sc = new Scanner(System.in);
    private static char[][] ary;
    private static boolean[][] b;
    private static int h;
    private static int w;
    public static void main(String[] args) throws Exception {
        h = sc.nextInt();
        w = sc.nextInt();
        int num = 0;
        for (int i = 0;i < h;i++) {
            String s = sc.next();
            for (int j = 0;j < w;j++) {
                if (s.charAt(j)=='#') num++;
            }
        }
        
        if (h+w-1==num) {
            System.out.println("Possible");
        } else {
            System.out.println("Impossible");
        }
    }
}


Measured memory_bytes: 10312
#include <cstdio>
#include <vector>

using namespace std;

int main(){
    vector<int> a(3);
    int k;
    scanf("%d %d %d %d", &a[0], &a[1], &a[2], &k);

    int max = 0;
    for(int i = 1; i < 3; i++){
        if(a[i] > a[max]) max = i;
    }

    for(int i = 1; i <= k; i++) a[max] *= 2;

    printf("%d\n", (a[0] + a[1] + a[2]));

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    int N;
    cin >> N;
    switch(N % 10)
    {
        case 0:
            cout << "pon";
            break;
        case 1:
            cout << "pon";
            break;
        case 2:
            cout << "hon";
            break;
        case 3:
            cout << "bon";
            break;
        case 4:
            cout << "hon";
            break;
        case 5:
            cout << "hon";
            break;
        case 6:
            cout << "pon";
            break;
        case 7:
            cout << "hon";
            break;
        case 8:
            cout << "pon";
            break;
        case 9:
            cout << "hon";
            break;
        default:
            cout << "hon";
            break;
    }
    return 0;
}

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

int main()
{
    int n, k;
    cin>> n>> k;
    string s;
    cin>> s;
    while (s[n+1]=='A' || s[n+1]=='B' || s[n+1]=='C'){
        }
    if (s[k-1]=='A'){
        s[k-1]='a';
    }else if(s[k-1]=='B'){
        s[k-1]='b';
        }else if (s[k-1]=='C'){
        s[k-1]='c';
        }
    cout<<s;
    return 0;
}

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

//#define int long long
typedef long long ll;
//const int INF = 2e9;
//const ll INF = 9e18;

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

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

struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
} comb(100000);

mint perm(int n, int k){
    mint res = comb(n,k);
    res *= comb.fact[k];
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, K;
    cin >> N >> K;
    for (int i=1;i<=K;i++){
        cout << comb(N-K+1,i)*comb(K-1,i-1) << "\n";
    }
}

Measured memory_bytes: 4632
// TOPSIC001_0

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef int _loop_int;
#define REP(i, n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i, a, b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i, a, b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a, b) a=min((a),(b))
#define CHMAX(a, b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a, b) (abs(a-b)<EPS)
typedef complex<Real> P;


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

    vector<string> vs(N);
    REP(i, N) cin >> vs.at(i);

    sort(vs.begin(), vs.end());

    REP(i, N) cout << vs.at(i);
}


Measured memory_bytes: 256
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
else:
    while k > 0:
        if k == 1 or len(mia) <= 1:
            if len(pla) == 0:
                cnt = cnt * mia.pop() % mod
            elif len(pla) > 0:
                cnt = cnt * pla.pop() % mod
            k -= 1
        elif len(pla) <= 1:
            cnt = cnt * mia.pop() * mia.pop() % mod
            k -= 2
        elif len(pla) >= 2 and len(mia) >= 2:
            if pla[-1] * pla[-2] > mia[-1] * mia[-2]:
                cnt = cnt * pla.pop() % mod
                k -= 1
            elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
                cnt = cnt * mia.pop() * mia.pop() % mod
                k -= 2
print(cnt)


Measured memory_bytes: 31728
#include <stdio.h>
#define MAX 100000
 
int A[MAX];
int partition();
 
 
int main(){

  int i;
  int n,q;
 
  scanf("%d",&n);

  for( i=0 ; i < n ; i++ ){

    scanf("%d",&A[i]);

  }

  q = partition( 0 , n-1 );
 
  for( i = 0; i < n; i++ ){

    if(i == q) printf("[");
 
      printf( "%d", A[i]);
 
      if(i == q) printf("]");
 
      if(i != n-1) printf(" ");
  }
  printf("\n");
 
  return 0;
}
 
int partition(int p,int r)
{
  int i,j;
  int x;
  int s;
 
  x = A[r];
  i = p-1;

  for(j = p; j < r; j++){

    if(A[j]<= x){

      i++;
      s = A[i];
      A[i] = A[j];
      A[j] = s;
    }
  }
      s = A[i+1];
      A[i+1] = A[r];
      A[r] = s;
  
    return i+1;
  }

Measured memory_bytes: 992
import java.util.Scanner;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<Integer, Integer> a = new HashMap<>();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int key = sc.nextInt();
            if (!a.containsKey(key)) {
                a.put(key, 0);
                cnt++;
                //    System.out.println(cnt);
            }
            a.put(key, a.get(key) + 1);
        }
        if ((n - cnt) % 2 == 0) {
            System.out.println(cnt);
            return;
        }
        System.out.println(cnt - 1);
    }
}


Measured memory_bytes: 62076
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <cstdio>

using namespace std;

int n;
int s,t;
const int INF=1000000000;

inline void setBit(int &s,int pos,int bit){
    if(bit)s|=(1<<pos);
    else s&=~(1<<pos);
}

class Sit{
public:
    int cost;
    int pos;
    int mask;
    Sit(int cost_,int pos_,int mask_){
        cost=cost_;
        pos=pos_;
        mask=mask_;
    }
    bool operator<(const Sit &s)const {
        return s.cost<this->cost;
    }
};

int d[16][1<<16];
priority_queue<Sit> que;
int bfs(){
    for(int j=0;j<n;j++)for(int k=0;k<(1<<n);k++)d[j][k]=INF;
    for(int i=0;i<n;i++){
        d[i][s]=0;
        que.push(Sit(0,i,s));
    }
    while(!que.empty()){
        Sit s=que.top();que.pop();
        if(d[s.pos][s.mask]<s.cost)continue;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                // ·ÅÉèÏÝ
                if((!(((s.mask>>i)&1)^((t>>i)&1)))&&(!(((s.mask>>j)&1)^((t>>j)&1)))){
                    continue;
                }
                //  éêÖÚ®µÄA»ÌêÆð·
                int cost=abs(i-s.pos)+abs(j-i);
                int nmask=s.mask;
                int a=(nmask>>i)&1;
                int b=(nmask>>j)&1;
                setBit(nmask,i,b);
                setBit(nmask,j,a);
                if(d[j][nmask]>d[s.pos][s.mask]+cost){
                    d[j][nmask]=d[s.pos][s.mask]+cost;
                    que.push(Sit(d[j][nmask],j,nmask));
                }
            }
        }
    }
    int res=INF;
    for(int i=0;i<n;i++)res=min(res,d[i][t]);
    return res;
}
//int solve(){
//    return bfs();
//    //for(int tern=n;tern>=0;tern--){
//    //    int nxt=tern%2;
//    //    int cur=(tern+1)%2;
//    //    for(int pos=0;pos<n;pos++){
//    //        for(int sit=0;sit<(1<<n);sit++){
//    //            int res=INF;
//    //            if(tern==n){
//    //                if(sit==t)res=0;
//    //            }
//    //            else{
//    //                for(int to=0;to<n;to++){
//    //                    // ®©·¾¯
//    //                    res=min(res,dp[cur][to][sit]+abs(to-pos));
//    //                    // trade
//    //                    int cost=abs(to-pos);
//    //                    int nsit=sit;
//    //                    int a=(sit>>pos)&1;
//    //                    int b=(sit>>to)&1;
//    //                    setBit(nsit,pos,b);
//    //                    setBit(nsit,to,a);
//    //                    res=min(res,dp[cur][to][nsit]+cost);
//    //                }
//    //            }
//    //            dp[nxt][pos][sit]=res;
//    //        }
//    //    }
//    //}
//    //int res=INF;
//    //for(int i=0;i<n;i++)res=min(res,dp[0][i][s]);
//    //return res;
//}
int main(){

    string ss,tt;
    while(cin>>n&&n){
        s=t=0;
        cin>>ss>>tt;
        for(int i=0;i<n;i++)if(ss[i]=='B')s|=(1<<i);
        for(int i=0;i<n;i++)if(tt[i]=='B')t|=(1<<i);
        printf("%d\n",bfs());
    }

    return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main()
{
	map<string,int>a;
	int n;
	cin>>n;
	int mx=0;
	for(int i=1;i<=n;i++){
		string t;
		cin>>t;
		a[t]++;
		mx=max(mx,a[t]);
	}
	for(auto i:a){
		if(i.second==mx){
			cout<<i.first<<'\n';
		}
	}
} 

Measured memory_bytes: 26496
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  unsigned int a, b;
  cin >> a >> b;
  int r = __gcd(a, b);
  cout << 1LL * a * b / r  << '\n';
  return 0;
}


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

using ll = long long;
using namespace std;

int main() {
  ll x;
  cin >> x;
  for (int a = -1; a < 1000; a++) {
    ll a5 = 1;
    rep(i, 5) a5 *= a;
    for (int b = -1000; b < 1000; b++) {
      ll b5 = 1;
      rep(i, 5) b5 *= b;
      if (a5 - b5 == x) {
        printf("%d %d\n", a, b);
        return 0;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 3772
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iostream>
using namespace std;

struct Node {
	int key;
	Node *right, *left, *parent;
};

Node *root, *NIL;

Node * treeMinimum(Node *x) {
	while(x->left != NIL) x = x->left;
	return x;
}

Node * find(Node *u, int k) {
	while (u != NIL && k != u->key) {
		if (k < u->key) u = u->left;
		else u = u->right;
	}
	return u;
}

Node * treeSuccessor(Node *x) {
	if (x->right != NIL) return treeMinimum(x->right);
	Node *y = x->parent;
	while (y != NIL && x == y->right) {
		x = y;
		y = y->parent;
	}
	return y;
}

void treeDelete(Node *z) {
	Node *y;
	Node *x;

	if (z->left == NIL || z->right == NIL) y = z;
	else y = treeSuccessor(z);

	if (y->left != NIL) {
		x = y->left;
	} else {
		x = y->right;
	}

	if (x != NIL) {
		x->parent = y->parent;
	}

	if (y->parent == NIL) {
		root =x;
	} else {
		if (y == y->parent->left) {
			y->parent->left = x;
		} else {
			y->parent->right = x;
		}
	}

	if (y != z) {
		z->key = y->key;
	}

	free(y);
}

void insert(int k) {
	Node *x = root;
	Node *y = NIL;
	while (x != NIL) {
		y = x;
		if (x->key == k) return;
		else if (x->key > k) x = x->left;
		else x = x->right;
	}
	Node* u = (Node*)malloc(sizeof(Node));
	u->key = k;
	u->left = u->right = NIL;
	u->parent = y;
	if (y == NIL) {
		root = u;
		return;
	}
	if (y->key > k) y->left = u;
	else y->right = u;
}

void inorder(Node *u) {
	if (u == NIL) return;
	inorder(u->left);
	printf(" %d", u->key);
	inorder(u->right);
}

void preorder(Node *u) {
	if (u == NIL) return;
	printf(" %d", u->key);
	preorder(u->left);
	preorder(u->right);
}

int main() {
	int n, i, x;
	string com;

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		cin >> com;
		if (com[0] == 'f') {
			scanf("%d", &x);
			Node *t = find(root, x);
			if (t != NIL) printf("yes\n");
			else printf("no\n");
		} else if (com == "insert") {
			scanf("%d", &x);
			insert(x);
		} else if (com == "print") {
			inorder(root);
			printf("\n");
			preorder(root);
			printf("\n");
		} else if (com == "delete") {
			scanf("%d", &x);
			treeDelete(find(root, x));
		}
	}
}



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

int main(){
	string s;
	cin >> s;
	if(s == "ABC")
		cout << "ARC" << endl;
	else
		cout << "ABC" << endl;
}

Measured memory_bytes: 3592
#include<iostream>
#include<vector>
#include<string>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= (int)end; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return 0;}
template<typename T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return 0;}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll X;
    cin >> X;
    ll now = 100;
    int ans = 0;
    while (now < X) {
        now += now / 100;
        ++ans;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3608
#include <stdio.h>

int main(void){
  
  char S[4];
  
  fgets(S,4,stdin);
  
  for(int i = 0;i < 3;++i){
    if(S[i] == '9'){
      printf("%c",'1');
    }
    else{
      printf("%c",'9');
    }
  }
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int a[1000000];
void seive(){
    for(int i=2;i*i<=1000000;i++){
        if(a[i]==1){
            for(int j=i*i;j<=1000000;j+=i){
                a[j]=0;
            }
        }
    }
}
int main()
{
    for(int i=0;i<1000000;i++){
        a[i]=1;
    }
    
    seive();
    a[0]=0;
    a[1]=0;
    int x;
    cin>>x;
    vector<int> v;
    for(int i=0;i<1000000;i++){
        if(a[i]==1){
            v.emplace_back(i);
            // cout<<i<<" ";
        }
    }
   
    for(auto it:v){
        // cout<<it<<" ";
        if(it>=x){
            cout<<it<<"\n";
            return 0;
        }
    }
    return 0;
}


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

int main() {
    int n;
    cin >> n;
    vector<string> s(n);
    for(int i = 0; i < n; i++) {
        cin >> s.at(i);
    }

    int m;
    cin >> m;
    vector<string> t(m);
    for(int i = 0; i < m; i++) {
        cin >> t.at(i);
    }

    map<string, int> money;
    for(int i = 0; i < n; i++) {
        money[s.at(i)]++;
    }
    for(int i = 0; i < m; i++) {
        money[t.at(i)]--;
    }

    int max = 0;
    string max_str = "";
    for(auto x : money) {
        if(x.second > max) {
            max_str = x.first;
            max = x.second;
        }
    }
    cout << max << endl;


}

Measured memory_bytes: 256
fun main(args : Array<String>){
    val (a,b,c) = readLine()!!.split(' ').map{ it.toInt() }
    val A = Math.abs(a - b) + Math.abs(b - c)
    val B = Math.abs(a - c) + Math.abs(b - c)
    val C = Math.abs(a - b) + Math.abs(a - c)

    println(Math.min(A,Math.min(B,C)))
}


Measured memory_bytes: 36376
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>

using namespace std;

int main() {
    long long int n, a, b;
    cin >> n >> a >> b;
    
    long long int pat = n / (a + b);
    long long int red;

    if (n % (a + b) <= a)red = n % (a + b);
    else red = a;
   
    cout << pat * a + red << endl;
    
}


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

int main()
{
  ll a, b, k;
  cin >> a >> b >> k;
  
  if (k <= a)
    cout << a - k << ' ' << b << endl;
  else if (k <= a + b)
    cout << 0 << ' ' << b - (k - a) << endl;
  else
    cout << 0 << ' ' << 0 << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main() {
	char s[6];
	scanf("%s", s);
	for (int i = 0; i < strlen(s) - 1; i++) {
		if (s[i] == 'A' && s[i + 1] == 'C') {
			printf("Yes\n");
			return 0;
		}
	}
	printf("No\n");
	return 0;
}

Measured memory_bytes: 128
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        String d = Integer.toString(N);
        char[] data = d.toCharArray();
        boolean answer = false;
        if (1000 <= N) {
            if (data[0] == data[1] && data[1] == data[2]) {
                answer = true;
            }
            if (data[1] == data[2] && data[2] == data[3]) {
                answer = true;
            }
        }
        System.out.println(answer ? "Yes" : "No");
    }
}


Measured memory_bytes: 23892
/*
For the brave souls who are here: You are the chosen ones, the valiant
knights of coding who toil away, without rest, fixing my most awful
code. To you, true saviors, kings of men, I say this:
never gonna give you up, never gonna let you down,
never gonna run around and desert you. Never gonna make you cry,
never gonna say goodbye. Never gonna tell a lie and hurt you.
*/

#include <algorithm>
#include <bitset>
#include <complex>
#include <cstring>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <unordered_map>
#include <vector>
//#include <boost/math/common_factor.hpp>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define REP(i, N) FOR(i, 0, N)
#define RREP(i, N) RFOR(i, N, 0)
#define FILL(A,value) memset(A,value,sizeof(A))
#define endl '\n'

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define pb push_back
#define mp make_pair
#define Pi 3.14159265358979
#define A first
#define B second

typedef long long ll;
typedef vector <int> vi;
typedef vector<ll> vl;
typedef pair <int, int> pi;
typedef pair <ll, int> pl;
typedef pair <ll, ll> pll;
typedef pair <double, double> pd;

//change these according to prob constraints
const int INF = 1000000000;
const int MAX = 100005;
const int MAX1 = 1005;
const int MAX2 = 105;
const int LEN = 105;
const int BASE = 1000000000;
const double EPS = 1e-7;
const int MOD = 1000000007;
//g++ -std=c++11 your_file.cpp -o your_program

int wt[105], val[105];
ll dp[MAX];

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ifstream in("");
	ofstream out("");
	clock_t begin = clock();
	int n, w;
    cin >> n >> w;
    REP(i, n){
        cin >> wt[i] >> val[i];
    }
    REP(i, MAX) dp[i] = 0x7fffffff;
    dp[0] = 0;
    REP(i, n) {
        RREP(j, 100001) {
            if (j < val[i]) break;
            dp[j] = min(dp[j], dp[j - val[i]] + wt[i]);
        }
    }
    RREP(i, 100001) {
        if (dp[i] <= w) {
            cout << i << endl;
            break;
        }
    }
	clock_t end = clock();
    double esecs = double(end - begin) / CLOCKS_PER_SEC;
    //cout << esecs << " seconds" << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
const int mod = 1e9 + 7;
int n, m;
int fac[maxn], ifac[maxn];
char s[maxn];
int mul(int x, int y) {
	return 1ll * x * y % mod;
}
int fpw(int x, int y) {
	int r = 1;
	for (int i = y; i; i >>= 1, x = mul(x, x))
		if (i & 1) r = mul(r, x);
	return r; 
}
int inv(int x) { return fpw(x, mod - 2); }
int mul(int x, int y, int z) { return mul(x, mul(y, z)); }
int C(int n, int m) { return mul(fac[n], ifac[m], ifac[n - m]); }
int read() {
	int x; scanf("%d", &x); return x;
}
int main() {
	#ifdef LOCAL
		freopen("1.in", "r", stdin);
	#endif
	n = read(); scanf("%s", s); m = strlen(s);
	fac[0] = ifac[0] = 1;
	for (int i = 1; i <= n + m; ++i) fac[i] = mul(fac[i - 1], i), ifac[i] = mul(ifac[i - 1], inv(i)); 
	// new length = m + n
	int ans = 0;
	for (int i = 0; i <= n; ++i) {
		ans += mul(mul(C(m + i - 1, i), fpw(25, i)), fpw(26, n - i));
		ans %= mod;
	}
	cout << ans << endl; 
}	


Measured memory_bytes: 20236
import math

N = int(input())
list = input().split(" ")
list.insert(0,"0")
list.append("0")

change = 0
now = 0
for i in range(N+1):
    if now < int(list[i]):
        change += int(list[i])-now
        now = int(list[i])
    else:
        change += now-int(list[i])
        now = int(list[i])
change += math.fabs(now)
change = int(change)

for i in range(1,N+1):
   ans = change - math.fabs(int(list[i])-int(list[i-1]))
   ans = ans - math.fabs(int(list[i+1])-int(list[i]))
   ans = ans + math.fabs(int(list[i+1])-int(list[i-1]))
   ans = int(ans)
   print(ans)


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

public static class Permi
{
    public static IEnumerable<IEnumerable<T>> Perm<T>(this IEnumerable<T> items, int? k = null)
    {
        if (k == null) k = items.Count();
        if (k == 0) yield return Enumerable.Empty<T>();
        else
        {
            var i = 0;
            foreach (var x in items)
            {
                var xs = items.Where((_, index) => i != index);
                foreach (var c in Perm(xs, k - 1))
                    yield return c.Before(x);
                i++;
            }
        }
    }
    public static IEnumerable<T> Before<T>(this IEnumerable<T> items, T first)
    {
        yield return first;
        foreach (var i in items) yield return i;
    }
}

public class Hello
{
    public static void Main()
    {
        while (true)
        {
            var n = int.Parse(Console.ReadLine().Trim());
            var m = int.Parse(Console.ReadLine().Trim());
            if (n == 0 && m == 0) break;
            var a = new string[n];
            for (int i = 0; i < n; i++) a[i] = Console.ReadLine().Trim();
            var hs = new HashSet<long>();
            var b = Enumerable.Range(0, n).Perm(m);
            foreach (var y in b)
            {
                var w = "";
                foreach (var x in y)
                    w += a[x];
                hs.Add(long.Parse(w));
            }
            Console.WriteLine(hs.Count());
        }
    }
}





Measured memory_bytes: 10380
N = int(input())
A = 0
B = 0
BA = 0
num = 0
for i in range(N):
    k = input()
    if k[0] == 'B' and k[-1] == 'A':
        BA += 1
    elif k[0] == 'B':
        B += 1
    elif k[-1] == 'A':
        A += 1

    for j in range(len(k) - 1):
        if k[j:j + 2] == 'AB':
            num += 1

num += max(0, BA - 1)
BA -= max(0, BA - 1)
num += min(BA, A) + min(BA, B)
A -= min(BA, A)
B -= min(BA, B)
num += min(A, B)
print(num)



Measured memory_bytes: 46808
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

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

int main() {
    int N, ans, ai;
    cin >> N;
    for (int i=0; i<N; i++) {
        scanf("%d", &ai);
        if (i==0) ans = ai;
        ans = gcd(ans, ai);
    }

    cout << ans << endl;

    return 0;

}


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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD =  (int)1e9 + 7;
const double EPS = 1e-9;

int N, M;
bool G[10][10];

signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	rep(i, 0, 10)rep(j, 0, 10)G[i][j] = false;

	cin >> N >> M;
	int a, b;
	rep(i, 0, M)
	{
		cin >> a >> b;
		a--, b--;
		G[a][b] = true;
		G[b][a] = true;
	}

	vector<int> v;
	rep(i, 0, N)v.push_back(i);

	int ans = 0;
	do {
		if (v[0] != 0)continue;
		bool ok = true;
		rep(i, 0, N - 1)
		{
			if (!G[v[i]][v[i + 1]])ok = false;
		}
		if (ok)ans++;
	} while (next_permutation(all(v)));

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
int main(){
  int x,y,i;
  scanf("%d %d",&x,&y);
  if(x<y){
    i=y;
    y=x;
    x=i;
  }
  while(y>0){
    i=x%y;
    x=y;
    y=i;
  }
  printf("%d\n",x);
  return 0;
}

Measured memory_bytes: 592
#!python3

iim = lambda: map(int, input().rstrip().split())
from itertools import chain, repeat

def resolve():
    N, K = iim()

    if N < K:
        print(0)
        return
    if N == 1 or K == 1:
        print(1)
        return

    mod = 10**9 + 7

    dp = [[0]*(K+1) for i in range(N+1)]
    dp[0][0] = 1

    for i, kx, i0 in zip( range(1, N+1), chain(range(1, K), repeat(K)), chain(repeat(1, N+1-K), range(2, K+1))):
        #print(i, kx, i0)
        for k in range(i0, kx + 1):
            dp[i][k] = dp[i-1][k-1] + dp[i-k][k]

    #for row in  dp:
    #    print(row)

    print(dp[N][K] % mod)

if __name__ == "__main__":
    resolve()



Measured memory_bytes: 16780
function main()
	N=parse(Int,readline())
	xd=Pair{Int,Int}[]
	for s=readlines()
		x,d=map(x->parse(Int,x),split(s))
		push!(xd,x=>d)
	end
	sort!(xd)
	w=zeros(Int,N+1)
	v=zeros(Int,N+1)
	w[1]=1
	v[1]=2*10^9
	id=1
	r=1
	for (x,d)=reverse(xd)
		while v[id]<x+d
			id-=1
		end
		r=(r+w[id])%998244353
		id+=1
		v[id]=x
		w[id]=r
	end
	println(r)
end
main()


Measured memory_bytes: 171632
import numpy as np

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

a = np.array(a)
c = np.sort(a)[::-1]
MOD = 10 ** 9 + 7
count = 1
ans = 0
d = 0
e = 0
for i in a:
    b = a[count:n]
    d += len(c[c < i])
    e += len(b[b < i])
    count += 1

ans = (e * k + k*(k-1)//2 * d)
ans %= MOD

print(int(ans))

Measured memory_bytes: 14536
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val pList = readLine()!!.split(' ').map(String::toLong)

    var count = 0
    (1 until (n - 1)).forEach {
        val list = mutableListOf<Long>(pList[it - 1], pList[it], pList[it + 1]).sorted()
        if (list[1]==pList[it])count++
    }

    println(count)
}


Measured memory_bytes: 38208
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll sq(ll num) { return num*num; }
ll mod_pow(ll x, ll n) {
	if (n == 0)return 1;
	if (n == 1)return x%MOD;
	ll res = sq(mod_pow(x, n / 2));
	res %= MOD;
	if (n % 2 == 1) {
		res *= x;
		res %= MOD;
	}
	return res;
}
ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }

int n;
ll h[5001];
ll p[5001];
vector<P> vp;

ll dp[5001][5001];

int main(){
	cin >> n;
	rep(i,n){
		cin >> h[i] >> p[i];
		vp.push_back(P(p[i]+h[i],i));
	}
	sort(ALL(vp));
	rep(i,5001)rep(j,5001)dp[i][j] = INF;
	dp[0][0] = 0;
	rep(i,n){
		ll id = vp[i].second;
		ll pp = p[id];
		ll hh = h[id];
		rep(j,n+1){
			if(dp[i][j] <= hh)dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j] + pp);
			dp[i+1][j] = min(dp[i+1][j],dp[i][j]); 
		}
	}
	ll ans = 0;
	rep(i,n+1)if(dp[n][i] != INF)ans = i;
	cout << ans << endl;
}


Measured memory_bytes: 195968
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define loopinc(i, a, b, inc) for(int i = a; i < (b); i += inc)
#define loop(i, a, b) for(int i = a; i < (b); i++)
#define rep(i, n) loop(i, 0, n)
#define rrep(i, n) for (int i = n-1; i >= 0; i--)
#define endl "\n"
#define all(c) (c).begin(),(c).end()
#define lloopinc(i, a, b, inc) for(ll i = a; i < (b); i += inc)
#define lloop(i, a, b) for(ll i = a; i < (b); i++)
#define lrep(i, n) lloop(i, 0, n)
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tuple<int, int, int> tiii;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

constexpr int maxn = 10000010;
ll arr[maxn];
signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	memset(arr, 0, sizeof(arr));
	loop(i, 2, n/2+5) {
		loopinc(j, i*2, n+5, i) arr[j]++;
	}
	ll acc = 0;
	lloop(i, 1, n+1) {
		acc += (arr[i] + (i == 1 ? 1 : 2)) * i;
	}
	cout << acc << endl;
}


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

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 1e6 + 5;
const int mod = 1e9 + 7;

int add(int x,int y) {
  return x + y >= mod ? x + y - mod : x + y;
}

inline int mul(int x,int y) {
  return (ll) x * y % mod;
}

int n,dp[N],pre[N + N];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n;
  pre[0] = 1;
  for (int i = 1 ; i <= N ; i++)
    pre[i] = pre[i - 1] + 1;
  dp[1] = n;
  pre[N + 1] = add(n,pre[N]);
  for (int i = 2 ; i <= n ; i++) {
    dp[i] = add(dp[i],dp[i - 1]);
    dp[i] = add(dp[i],mul(n - 1,n - 1));
    dp[i] = add(dp[i],add(pre[i - 3 + N],mod - pre[i - n - 2 + N]));
    pre[i + N] = add(pre[i + N - 1],dp[i]);
  }
  cout << dp[n] << endl;
}

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

int main() {
	// your code goes here
	int n, k;
	cin >> k >> n;
	int a[2 * n - 1];
	for(int i = 0; i < n; i++){
	    cin >> a[i];
	}
	for(int i = n; i < 2 * n - 1; i++){
	    a[i] = a[i - n];
	}
	int diff[n], d = 0;
	for(int i = 0; i < n; i++){
	    if(i != n - 1){
	        d += a[i + 1] - a[i];
	        diff[i] = d;
	    }
	    else{
	        d += k - a[i] + a[0];
	        diff[i] = d;
	    }
	}
	int ans = INT_MAX, dist = 0;
	for(int i = 0; i < n; i++){
	    if(i == 0) dist = diff[n - 2];
	    else dist = diff[n - 1] - diff[i] + diff[i - 1];
	    ans = min(ans, dist);
	}
	cout << ans << endl;
	return 0;
}


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

#define ALL(obj) (obj).begin(), (obj).end()
#define rep(i,n) for(int i=0; i<n; i++)
#define rep2(i,a,b) for(int i=a; i<=b; i++)
using ll = long long;
#define pb push_back
class Position {
  public: 
    int x;
    int y;
    Position(int y, int x) {
      this->x = x;
      this->y = y;
    }
    Position(const Position& co) {
      this->x = co.x;
      this->y = co.y;
    }
    Position() {
      this->x = 0;
      this->y = 0;
    }
    bool equal(Position &a) {
      if ( (this->x == a.x) && (this->y == a.y) )
        return true;
      else 
        return false;
    }
};


const int MOD = (int) 1e9 + 7;
const double EPS = 1e-9;
struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};


int main()
{
  int N;
  cin >> N;
  vector<ll> a(N);
  rep(i,N)
    cin >> a[i];
  map<ll, int> b;
  rep(i,N)
    b[a[i]]++;
  ll ans = 0;
  for (auto c: b) {
    // cout << c.first << ": " << c.second << endl;
    if (c.second > c.first)
      ans += c.second - c.first;
    else if (c.first > c.second) {
      ans += c.second;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 7040
import java.util.*

//

fun main() {
    abc085d()
}

fun abc085d() {
    val (ns, hs) = readLine()!!.split(" ")
    val n = ns.toInt()
    var h = hs.toLong()
    val priorityQueue = PriorityQueue<Katana> {o1, o2 -> (o2.damage - o1.damage).toInt() }
    repeat(n) {
        val (a, b) = readLine()!!.split(" ").map { it.toLong() }
        priorityQueue.add(Katana(a, true))
        priorityQueue.add(Katana(b, false))
    }
    var count = 0L
    while (h > 0L) {
        val k = priorityQueue.poll()
        h -= k.damage
        count++
        if (k.repeat) {
            val r = h / k.damage
            h -= k.damage * r
            count += r
            if (h > 0L) {
                h -= k.damage
                count++
            }
        }
    }
    println(count)
}

private data class Katana(val damage: Long, val repeat: Boolean)

Measured memory_bytes: 66896