akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

#define N 810
string g[N];
int h, w, k;
int d[N][N];
int dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1};

int main(){
	cin>>h>>w>>k;
	rep(i, h) cin>>g[i];
	int si, sj;
	rep(i, h) rep(j, w) if(g[i][j]=='S'){
		si = i;
		sj = j;
	}
	mset(d, -1);
	d[si][sj] = 0;
	priority_queue<PP, vector<PP>, greater<PP> > q;
	q.push(PP(0, P(si, sj)));
	int res = h*w;
	while(!q.empty()){
		PP pp = q.top(); q.pop();
		P p = pp.snd;
		if(d[p.fst][p.snd]<pp.fst) continue;
		rep(i, 4){
			int x = p.fst+dx[i], y = p.snd+dy[i];
			if(d[x][y]>=0) continue;
			d[x][y] = max(d[p.fst][p.snd]+1, g[x][y]=='#'?k+1:0);
			if(x==0||y==0||x==h-1||y==w-1){
				res = min(res, (d[x][y]+k-1)/k);
				continue;
			}
			q.push(PP(d[x][y], P(x, y)));
		}
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 10736
def main():
    h, w = map(int, input().split())
    ary = [list(input()) for _ in range(h)]
    for i in reversed(range(h)):
        if len(ary[i]) == ary[i].count('.'):
            del ary[i]
    for i in reversed(range(w)):
        ok = True
        for a in ary:
            if a[i] != '.':
                ok = False
        if ok:
            for j in range(len(ary)):
                del ary[j][i]
    for a in ary:
        print("".join(a))


if __name__ == '__main__':
    main()


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

#define Vsort(a) sort(a.bigin(), a.end())
#define rep(i,n) for(int i = 0; i < (n); i++)

int main(){
  long long int n, d;
  long long int a, b, count = 0;
  double c;
  cin >> n >> d;
  vector<long long int> x(n);
  vector<long long int> y(n);
  for(int i = 0; i < n; i++){
    cin >> x[i] >> y[i];
  }
  for(int i = 0; i < n; i++){
    a = x[i];
    b = y[i];
    c = sqrt((a * a) + (b * b));
    if(c <= d) count++;
  }
  cout << count;
}


Measured memory_bytes: 6424
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mk make_pair
#define REP(i,a,b) for(int i=a; i<=b; i++)

int main()
{
    int m, d;
    cin >> m >> d;
    int ans = 0;
    REP(i,1,m)
    {
        REP(j,22,d)
        {
            int a = j%10, b = j/10;
            if (a >= 2 && b >= 2 && a*b == i)
            {
                //cout << m << " " << a << b << endl;
                ans += 1;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
int d[10][10] = {};
void warshall_floyd(int n) {
    for (int k = 0; k < n; k++){       // 経由する頂点
        for (int i = 0; i < n; i++) {    // 始点
            for (int j = 0; j < n; j++) {  // 終点
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

int main() {
    int h, w;
    cin >> h >> w;
    int i, j;
    for (i = 0; i < 10; i++) {
        for (j = 0; j < 10; j++) {
            cin >> d[j][i];
        }
    }
    warshall_floyd(10);
    long long sum = 0;
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            int x;
            cin >> x;
            if(x == -1)continue;
            sum += d[1][x];
        }
    }
    cout << sum<< endl;
}


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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

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

Measured memory_bytes: 3624
#include<stdio.h>

int main(){
    int x,y;
    
    while(1){
        scanf("%d %d",&x,&y);
        if(( x == 0 ) && ( y == 0 )){
            break;
        }
        if(y<x)
        printf("%d %d\n",y,x);
        if(x<y)
        printf("%d %d\n",x,y);   
        if(x==y)
        printf("%d %d\n",x,y);
        
    }
    return 0;
}


Measured memory_bytes: 2044
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const ll nmax = 8;
const ll INF = 1e9;
bool graph[nmax][nmax];
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}

class UnionFind
{
public:
    vector<ll> Parent;

    UnionFind(ll N)
    {
        Parent = vector<ll>(N, -1);
    }
    ll find(ll A)
    {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = find(Parent[A]);
    }

    ll size(ll A)
    {
        return -Parent[find(A)];
    }

    bool Union(ll A, ll B)
    {
        A = find(A);
        B = find(B);
        if (A == B)
        {
            return false;
        }
        if (size(A) < size(B))
            swap(A, B);

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }
};

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

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

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

ll ceil(ll a, ll b)
{
    return (a + b - 1) / b;
}

int main()
{
    long long N;
    scanf("%lld", &N);
    long long C;
    scanf("%lld", &C);
    vector<ll> x(N + 1), v(N + 1), vc(N + 1);

    x[0] = 0;
    v[0] = 0;

    for (int i = 1; i < N + 1; i++)
    {
        cin >> x[i] >> v[i];
    }

    vc[0] = v[0];
    for (int i = 1; i <= N; i++)
    {
        vc[i] = vc[i - 1] + v[i];
    }
    vector<ll> r(N + 1);
    r[0] = 0;
    for (int i = 1; i <= N; i++)
    {
        r[i] = max(r[i - 1], vc[i] - x[i]);
    }
    vector<ll> l(N + 1);
    l[N] = vc[N] - vc[N - 1] - (C - x[N]);
    for (int i = N - 1; i >= 1; i--)
    {
        l[i] = max(l[i + 1], vc[N] - vc[i - 1] - (C - x[i]));
    }

    ll ans = 0;
    for (int i = 1; i < N + 1; i++)
    {
        ll tmp = vc[i] - x[i];
        ans = max(ans, tmp);

        if (i < N)
        {
            tmp = vc[i] - 2 * x[i] + l[i + 1];
            ans = max(ans, tmp);
        }
    }
    for (int i = N; i >= 1; i--)
    {
        //ケース3
        ll tmp = vc[N] - vc[i - 1] - (C - x[i]);
        if (tmp > ans)
            ans = tmp;

        //ケース4
        tmp = vc[N] - vc[i - 1] - 2 * (C - x[i]) + r[i - 1];
        if (tmp > ans)
            ans = tmp;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4224
import java.util.*;
public class Main {
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int L = sc.nextInt();
        int sum=0,opt = 999999999,opt_num=0;
        for(int i=1;i<=N;i++) {
            int num = L+i-1;
            sum+=num;
            if(opt>Math.abs(L+i-1)){
                opt = Math.abs(L+i-1);
                opt_num = L+i-1;
            }
        }
        System.out.println(sum-opt_num);
    }
}


Measured memory_bytes: 21844
### constant

DIRCS = [[1, 0], [0, -1], [-1, 0], [0, 1]]

### subroutines

def neighbors(pos)
  x = pos % $w
  y = pos / $w
  for dxy in DIRCS
    x0 = x + dxy[0]
    y0 = y + dxy[1]
    if x0 >= 0 && x0 < $w && y0 >= 0 && y0 < $h
      yield (y0 * $w + x0)
    end
  end
end

def max_discount(t, pos, gbits)
  return 0 if t >= $max_et
  return $mdcache[t][pos][gbits] if ! $mdcache[t][pos][gbits].nil?

  dsum = 0
  gbits0 = gbits

  for g in $brds[pos]
    if t >= $goods[g][1] && t < $goods[g][2]
      gb = (1 << g)
      if (gbits0 & gb) != 0
        dsum += $goods[g][0]
        gbits0 ^= gb
      end
    end
  end

  max_d0 = 0

  for pos0 in $npos[pos]
    d0 = max_discount(t + 1, pos0, gbits0)
    if max_d0 < d0
      max_d0 = d0
    end
  end

  $mdcache[t][pos][gbits] = dsum + max_d0
end

### main

while true
  $w, $h = gets.strip.split(' ').map{|s| s.to_i}
  $wh = $w * $h
  break if $wh == 0

  start = nil
  $brds = $wh.times.map{[]}

  for y in (0...$h)
    hl = gets.strip.split(' ')
    for x in (0...$w)
      pos = y * $w + x
      case hl[x]
      when 'P'
        start = pos
      when '0'..'9'
        g = hl[x].to_i
        neighbors(pos) do |pos0|
          if ! $brds[pos0].nil? && ! $brds[pos0].include?(g)
            $brds[pos0] << g
          end
        end
        $brds[pos] = nil
      end
    end
  end
  #p pos
  #p $brds

  $npos = []
  for pos in (0...$wh)
    if ! $brds[pos].nil?
      nbrs = []
      neighbors(pos) do |pos0|
        if ! $brds[pos0].nil?
          nbrs << pos0
        end
      end
      $npos[pos] = nbrs
    end
  end
  #p $npos

  $n = gets.strip.to_i
  $goods = []
  $max_et = 0

  $n.times do
    g, d, st, et = gets.strip.split(' ').map{|s| s.to_i}
    $goods[g] = [d, st, et]
    $max_et = et if $max_et < et
  end
  #p $goods
  #p $max_et

  $mdcache = $max_et.times.map{$wh.times.map{[]}}

  max_d = max_discount(0, start, (1 << $n) - 1)
  puts max_d
end

Measured memory_bytes: 53036
#include <stdio.h>
#include <string.h>

int main(void) {
  char s[40], ans[1200][40], maxm = 0, maxl = 0;
  int now = 0, i, j, k, n[1200];
  while(scanf("%s", s) != EOF) {
    int t = 1;
    for(i = 0; i < now; ++i) if(!strcmp(s, ans[i])) {
      n[i]++, t = 0;
      break;
    }
    if(t) {
      strcpy(ans[now], s);
      n[now] = 1;
      now++;
    }
  }
  for(i = 0; i < now; ++i) {
    if(maxm < n[i]) maxm = n[i];
    if(maxl < strlen(ans[i])) maxl = strlen(ans[i]);
  }
  char ansm[40], ansl[40];
  for(i = 0; i < now; ++i) {
    if(maxm == n[i]) strcpy(ansm, ans[i]);
    if(maxl == strlen(ans[i])) strcpy(ansl, ans[i]);
  }
  printf("%s %s\n", ansm, ansl);
  return 0;
}


Measured memory_bytes: 2732
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 25

ll gcd(ll x,ll y){

	x = abs(x);
	y = abs(y);

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

//最小公倍数
ll lcm(ll x,ll y){

	return (x*y)/gcd(x,y);
}


int N;
ll POW[SIZE],table[SIZE];

int main(){

	POW[0] = 1;

	for(int i = 1; i < SIZE; i++){

		POW[i] = POW[i-1]*2;
	}

	scanf("%d",&N);

	for(int i = 0; i < N; i++){

		scanf("%lld",&table[i]);
	}

	int ans = 0;

	bool FLG;

	vector<int> V;

	for(int state = 1; state < POW[N]; state++){

		ll LCM = 1;
		V.clear();

		for(int loop = 0; loop < N; loop++){

			if(state & (1 << loop)){

				LCM = lcm(LCM,table[loop]);

			}else{

				V.push_back(table[loop]);
			}
		}

		FLG = true;

		for(int i = 0; i < V.size(); i++){

			if(LCM%V[i] == 0){

				FLG = false;
				break;
			}
		}
		if(FLG)ans++;
	}

	printf("%d\n",ans);

	return 0;
}



Measured memory_bytes: 3268
import java.io.*;
import java.util.Arrays;
import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int[] a = new int[3];
        for(int i=0;i<3;i++) {
            a[i] =scan.nextInt();
        }
        Arrays.sort(a);
        for(int i=0;i<3;i++){
            System.out.print(a[i]);
            if(i<2)System.out.print(" ");
        }
        System.out.println("");
    }
}


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

typedef long long int ll;
int main(){
  ll n,array[65001],p[65001];
  while(cin >> n && n){
    ll s = 0;
    for(int i=0; i<n; i++){
      cin >> array[i];
      s += array[i];
    }

    for(int i=0; i<n-1; i++) cin >> p[i];

    ll ans = 0;
    sort(p,p+n-1);
    reverse(p,p+n-1);

    for(int i=0; i<n; i++) ans += array[i];
    ans *= n;


    ll pipe = 0;
    for(int i=1; i<n; i++){
      pipe += p[i-1];
      ans = max(ans,(ll)((pipe+s) * (n-i)));
    }
    cout << ans << endl;
  }
  return 0;
}

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

int main() {
  int N;
  cin>> N;
  int a=0;
  for(int i=0 ; i<N ; i++){
    string s;
    cin>> s ;
    if(s=="Y"){
      a++;
    }
  }
  if(a==0){
    cout<< "Three" << endl;
  }
  else{
    cout<< "Four" << endl;
  }
}

Measured memory_bytes: 3608
#include<iostream>

using namespace std;

inline int f(int n){
  if(n%2==1){
    return 3*n+1;
  }else{
    return n/2;
  }
}

int main(){
  int a[128];
  cin>>a[0];
  for(int i=1;1;i++){
	a[i]=f(a[i-1]);
    for(int j=0;j<i;j++){
      if(a[i]==a[j]){
        cout<<i+1;
        goto end;
      }
    }
  }
  end:
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define endl '\n'
using namespace std;
int main()
{
   vector<int>v(9);
   vector<int>::iterator it;
   for(int i = 0; i<9; i++)
        cin>>v[i];
   int n,b;
   cin>>n;
   while(n--)
   {
       cin>>b;
       for(int i = 0; i<9; i++)
       {
            it = find(v.begin(),v.end(),b);
            if(it!=v.end())
                *it = 0;
       }
   }
   int flag = 0;
   for(int i= 0; i<9; i++){
    if(v[0] ==0 && v[1] ==0 && v[2] == 0)flag = 1;
    else if(v[0] ==0 && v[3] == 0 && v[6] == 0)flag = 1;
    else if(v[0]==0 && v[4]==0 && v[8]==0)flag = 1;
    else if(v[1]==0 && v[4]==0 && v[7]==0)flag = 1;
    else if(v[2]==0 && v[5]==0 && v[8]==0)flag = 1;
    else if(v[3]==0 && v[4]==0 && v[5]==0)flag = 1;
    else if(v[6]==0 && v[7]==0 && v[8]==0)flag = 1;
    else if(v[2]==0 && v[4]==0 && v[6]==0)flag = 1;
   }
   if(flag)puts("Yes");
   else puts("No");
   return 0;

}


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

int main(){
  int a,b,c;
  cin >> a;
  cin >> b;
  c = a*b;
  if (c%2 == 0){
    cout << "Even" << endl;
  }
  else{
    cout << "Odd" << endl;
  }
}
    

Measured memory_bytes: 256
def main():
    h, w = list(map(int, input().split()))
    for i in range(1, h + 1):
        S = input().split()
        for j, s in enumerate(S):
            if s == 'snuke':
                print(''.join([chr(j + 65), str(i)]))
                break


if __name__ == '__main__':
    main()


Measured memory_bytes: 9176
s = input()
p = list(s) 
if p[len(p) - 1] == "?": #最後が？だったら
  p[len(p) - 1] = "D"  # Dにする
 
for i in range(len(p) - 1):
  if p[i] == "?":         # ？だったら
    if i == 0:            # 最初の文字
      if p[i + 1] == "D" or p[i + 1] == "?": # 二番目の文字がDか？
        p[i] = "P"
      else:                                   # 二番目の文字がDか？でなかったら
        p[i] = "D"
    else:
      p[i] = "D"          # D
print("".join(p))

Measured memory_bytes: 10796
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [tuple(int(i) for i in input().split()) for _ in range(n)]
ab.sort()
hq = []
result = 0
j = 0
for i in range(1, m + 1):
    while j < n and ab[j][0] <= i:
        heappush(hq, -ab[j][1])
        j += 1
    if hq:
        result -= heappop(hq)
print(result)

Measured memory_bytes: 67804
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR_IN(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i, n) FOR(i,0,n)
const int MOD = 1000000007;

// 可変引数で最大公約数を求める関数
// コンパイルオプションに"-std=c++17"を追加
template <class T>
T vgcd(T m, T n) {
  return std::gcd(m, n);
}

template <class T, class... Args>
T vgcd(T a, Args... args) {
  return vgcd(a, vgcd(args...));
}

ll MODPOW(ll res_mod,ll N){
    ll res = 1;
    while(N > 0){
        if(N & 1) res = res * res_mod % MOD;
        res_mod = res_mod * res_mod % MOD;
        N >>= 1;
    }
    return res;
}

int main(void){
    ll N,K;
    cin >> N >> K;
    ll ans = 0;
    vector<ll> bucket(K+10,0);
    for(int i = K; i > 0;i--){
        ll tmp = MODPOW(K/i,N);

        bucket[i] = tmp;
        
        int tmp_num = i*2;
        while(tmp_num <= K){
            bucket[i] -= bucket[tmp_num];
            tmp_num += i;
        }
    }
    FOR_IN(i,1,K){
        ans += i*bucket[i]%MOD;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4016
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n = ri()
s, t = rsl()
res = ''
for c0, c1 in zip(s, t):
    res += c0 + c1
print(res)

Measured memory_bytes: 3064
#16D8101014F 久留米 竜之介 2018/5/14
n=int(input())
S=list(map(int,input().split()))
q=int(input())
T=list(map(int,input().split()))
point=0
for i in T:
	left=0
	right=n
	while left < right:
		mid=int((left+right)/2)
		if S[mid] == i:
			point += 1
			break
		elif i < S[mid]:
			right = mid
		else:
			left = mid + 1
	#print(i,point)

print(point)


Measured memory_bytes: 16704
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define EPS 1e-9
#define fst first
#define scd second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  string s;
  cin>>s;
  if(s.size() ==3) reverse(s.begin() , s.end() );
  cout<<s<<endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int b[999999], n, c[999999];
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%d",&c[i]);
	}
	b[1] = 0;
	for (int i = 2; i <= n; i++) {
		b[i] = b[i / 2] + b[(i + 1) / 2] + i;
	}
	sort(c, c + n);
	for (int i = 0; i < n; i++) {
		cout << c[i];
		if (i < n - 1) {
			cout << ' ';
		}
		else { cout << endl; }
	}
	cout << b[n] << endl;
	return 0;
}


Measured memory_bytes: 7040
import sys, math
from functools import lru_cache
from collections import defaultdict
from decimal import Decimal
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N, M = mi()
    S, T = [list(input()), list(input())]

    g = math.gcd(N, M)
    l = N*M//g

    for i in range(g):
        if not (S[N//g*i] == T[M//g*i]):
            print(-1)
            return

    print(l)


if __name__ == '__main__':
    main()


Measured memory_bytes: 11228
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define mex 10000005
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
//vector<int> adj[mex];
//a+b=a^b+2*(a&b)
#define int long long 

int p[mex];
void sieve(int n){
	for(int i=1;i<=n;i++)
	 p[i]=i;
	 
	for(int i=2;i*i<=n;i++){
		if(p[i]==i){
			for(int j=i*i;j<=n;j+=i){
				if(p[j]==j)
				 p[j]=i;
			 }
		 }
	 }
}

signed main(){
	fast
	
	int n;
	cin>>n;
	sieve(n);
	ll pp=0;
	for(int i=1;i<=n;i++){
		ll c=1,n1=i;
		while(n1!=1){
			int y=p[n1];
			ll cc=0; 
			while(n1%y==0){
				cc+=1;
				n1/=y;
			}
			c=c*(cc+1);
		}
		pp=(pp+i*c);
	}
	cout<<pp;
}


Measured memory_bytes: 81708
#include<iostream>
#define MAX 100010
using namespace std;

int main(){
    long long n,k;
    cin >> n >> k;
    long long c[MAX] = {0};
    for(int i = 0;i < n;i++){
        long long a,b;
        cin >> a >> b;
        c[a] += b;
    }

    for(int ans = 0;ans < MAX;ans++){
        if(k <= c[ans]){
            cout << ans << endl;
            break;
        }
        k -= c[ans];
    }
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#define Abs(x) ((x)<0?-(x):(x))
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int N=1001000;
int n,m=30,tmp;
ll X[N],Y[N];
void work(ll x,ll y){
	if(tmp) cout<<'R';
	ROF(i,m,0){
		ll dx=Abs(x),dy=Abs(y);
		if(dx<dy && y>0) cout<<'U',y-=1ll<<i;
		else if(dx<dy && y<0) cout<<'D',y+=1ll<<i;
		if(dx>dy && x>0) cout<<'R',x-=1ll<<i;
		else if(dx>dy && x<0) cout<<'L',x+=1ll<<i;
	}puts("");
}
int main(){
	scanf("%d",&n);
	FOR(i,1,n) scanf("%lld%lld",&X[i],&Y[i]);
	FOR(i,2,n)if((Abs(X[i]+Y[i])^Abs(X[1]+Y[1]))&1) return puts("-1"),0;
	if(Abs(X[1]+Y[1])%2==0){tmp=1;FOR(i,1,n) X[i]--;}
	cout<<m+tmp+1<<'\n';
	if(tmp) cout<<1<<' ';ROF(i,m,0) cout<<(1ll<<i)<<' ';cout<<'\n';
	FOR(i,1,n) work(X[i],Y[i]);
	return 0;
}

Measured memory_bytes: 2304
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cctype>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <numeric>
#include <functional>
#include <cstdlib>
#include <regex>
#include <list>
int main() {
	int a, b, k, c = 1;
	std::cin >> a >> b >> k;
	for (int i = 100;i >= 1;i = i - 1) {
		if (a%i == 0 && b%i == 0) {
			if (c == k) {
				std::cout << i << std::endl;
				break;
			}
			c += 1;
		}
	}
	return 0;
}

Measured memory_bytes: 256
n = int(input())
h = list(map(int, input().split()))

res = 0
i = 0
while sum(h) != 0:
    if h[i] != 0:
        while i < n and h[i] != 0:
            h[i] -= 1
            i += 1
        res += 1
        i = 0
    else:
        i += 1

print(res)


Measured memory_bytes: 3060
#include <iostream>
#include <string>

int main()
{
  std::string s, h, l;

  std::cin >> s;

  h.assign(s, 0, s.size()/2);
  l.assign(s, s.size()/2+1, s.size()/2);
  
  if (l == h) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }

  return 0;
}


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

int main() {
    long long H, W, h, w;
    std::cin >> H >> W >> h >> w;
    if (H % h == 0 && W % w == 0) {
        std::cout << "No" << std::endl;
        return 0;
    }

    std::cout << "Yes" << std::endl;
    if (W % w) {
        std::vector<long long> s(W + 1);
        s[W] = 1;
        s[W - W % w] = - W / w;
        for (auto i = W - w; i > 0; i--) s[i] = i % w ? s[i + w] + 1 : - i / w;

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) std::cout << s[j + 1] - s[j] << " ";
            std::cout << std::endl;
        }
    } else {
        std::vector<long long> s(H + 1);
        s[H] = 1;
        s[H - H % h] = - H / h;
        for (auto i = H - h; i > 0; i--) s[i] = i % h ? s[i + h] + 1 : - i / h;
        
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) std::cout << s[i + 1] - s[i] << " ";
            std::cout << std::endl;
        }
    }

    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h> 
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<ll> 
#define vd vector<double>
#define vld vector<long double>
#define vp vector<pair<ll, ll>>
#define all(a) a.begin(), a.end()
#define pb push_back
#define pi pair<int, int>
#define pl pair<ll, ll>
#define mp make_pair
#define fi first
#define sc second
#define for0(i, n) for(ll i=0; i<n; i++) 
#define for1(i, n) for(ll i=1; i<=n; i++)
using namespace std;
const ll mod = 1e9+7;

void solve(){
	int x; cin>>x;
	if(x<600)
		cout<<8;
	else if(x<800)
		cout<<7;
	else if(x<1000)
		cout<<6;
	else if(x<1200)
		cout<<5;
	else if(x<1400)
		cout<<4;
	else if(x<1600)
		cout<<3;
	else if(x<1800)
		cout<<2;
	else
		cout<<1;
}

int main() {

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

	ll test = 1;
	//cin>>test;
	while(test--)
		solve();

	return 0;
}

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

int main()
{
  string S;
  cin >> S;
  int a = 0, b = 0, c = 0;
  int cnt = 0;
  for (int i = 0; i < S.size(); i++)
  {
    if (S[i] == 'a')
    {
      if (a == 0)
        cnt++;
      a++;
    }
    else if (S[i] == 'b')
    {
      if (b == 0)
        cnt++;
      b++;
    }
    else
    {
      if (c == 0)
        cnt++;
      c++;
    }
  }
  bool can = true;
  if (cnt == 1)
    if (S.size() > 1)
      can = false;
  if (cnt == 2)
  {
    if ((a == 1 and b == 1) or (b == 1 and c == 1) or (c == 1 and a == 1))
      can = true;
    else
      can = false;
  }
  if (cnt == 3)
  {
    int min_abc = min(a, min(b, c));
    if (a - min_abc > 1 or b - min_abc > 1 or c - min_abc > 1)
      can = false;
  }
  if (can)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}


Measured memory_bytes: 512
N = int(input())
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

#print(x)
#print(y)

ans = 0

for j in range(N):
    for k in range(N):
        if(j == k):
            continue
        disx = x[k] - x[j]
        disy = y[k] - y[j]
        ans += ((disx ** 2) + (disy ** 2))**0.5

print(ans/N) 

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

#define FOR(i,a,b)  for(ll i=a;(i)<(b);++(i))
#define RFOR(i,a,b) for(ll i=a;(i)>=(b);--(i))
#define REP(i,n)    FOR(i,0,n)
#define RREP(i,n)   RFOR(i,n,0)
#define ALL(v)      v.begin(), v.end()
#define UNIQ(v)     sort(ALL(v)); v.erase(unique(ALL(v)), v.end())
#define BIT(n)      (1LL<<(n))
#define DEBUG(a)    cerr << #a << " = " << a << endl

const int inf = 1001001001;
const int mod = (int)1e9+7;
//const ll inf = 1e15;
//const ll mod = 1e9+7;

int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};

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

    ll ans = 1;
    while(N >= K) {
        N /= K;
        ans++;
    }
    cout << ans << endl;
}


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

int z , p , q , w ;

deque<int>vc,cv;



int main( ) {

    string s , t ;
    cin >> s >> t ;
    int n , m ;
    cin >> n >> m ;
    string h ;
    cin >> h ;
    if( h == s ){
        n -- ;
    }
    else{
        m -- ;
    }
    cout<< n << ' ' << m ;

}





Measured memory_bytes: 256
#include <stdio.h> 
  
int main(void) { 
        int a, N, R; 
 
        scanf("%d %d", &N, &R); 
 
        if (N >= 10) { 
                a = R; 
        } else { 
                a = R + 100 * (10 - N); 
        } 
        printf("%d\n", a); 
 
        return 0; 
}


Measured memory_bytes: 128
import math as mt
NK=input().split()
N=int(NK[0])
K=int(NK[1])
P=N-K

print(P+1)


for i in range(1,K):
    if i<=N-K:
        Q=(mt.factorial(N-K+1)*mt.factorial(K-1))//(mt.factorial(K-i-1)*mt.factorial(i)*mt.factorial(N-K-i)*mt.factorial(i+1))
        print(Q%int(1e9+7))
    else:
        print(0)


Measured memory_bytes: 3316
import math
import sys
n, m = map(int, input().split())
s = list(input())
t = list(input())
a = (n*m)//math.gcd(n, m)
b0 = [i*(a//n)+1 for i in range(n)]
b1 = [i*(a//m)+1 for i in range(m)]
b2 = set(b0)
b3 = set(b1)

for j, i in enumerate(b0):
    if i in b3:
        if s[j] != t[b1.index(i)]:
            print(-1)
            sys.exit()
            
for j, i in enumerate(b1):
    if i in b2:
        if s[b0.index(i)] != t[j]:
            print(-1)
            sys.exit()
print(a)


Measured memory_bytes: 27864
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>  
#include <complex>
#include <queue>
#include <set>
#include <unordered_set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <fstream>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
ll MOD = 1e9+7;
double eps = 1e-12;
#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(ll i = s; i < e; i++)
#define rforn(i,s) for(ll i = s; i >= 0; i--)
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 2e18
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
 
ll mpow(ll a, ll b){
	if(a==0) return 0;
	if(b >= (MOD-1)) b %= (MOD-1);
	if(b==0) return 1;
	ll t1 = mpow(a,b/2);
	t1 *= t1;
	t1 %= MOD;
	if(b%2) t1 *= a;
	t1 %= MOD;
	return t1;
}
 
ll mpow(ll a, ll b, ll p){
	if(a==0) return 0;
	if(b==0) return 1;
	ll t1 = mpow(a,b/2,p);
	t1 *= t1;
	t1 %= p;
	if(b%2) t1 *= a;
	t1 %= p;
	return t1;
}
 
ll modinverse(ll a, ll m){
	ll m0 = m; 
    ll y = 0, x = 1; 
    if (m == 1) return 0; 
    while (a > 1){
        ll q = a / m; 
        ll t = m; 
        m = a % m, a = t; 
        t = y; 
        y = x - q * y; 
        x = t; 
    }
    if (x < 0) x += m0; 
    return x; 
}

mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
 
ll range(ll l, ll r){
	return l + mt()%(r-l+1);
}
 
ll rev(ll v){
	return mpow(v,MOD-2);
}

void solve(){
	ll n;
	cin >> n;
	n++;
	ll a[n];
	forn(i,n) cin >> a[i];
	ll b[n];
	ll pr = 1;
	forn(i,n){
		b[i]=min(pr-a[i],(ll)INF);
		if(b[i]<0){
			cout << -1 << ln;
			return;
		}
		pr = 2*b[i];
	}
	b[n-1]=0;
	rforn(i,n-2){
		b[i]=min(b[i],b[i+1]+a[i+1]);
	}
	ll ans = 0;
	forn(i,n) ans += b[i]+a[i];
	cout << ans << ln;
}
 
int main()
{
	fast_cin();
    ll t=1;
    // cin >> t;
    forn(i,t) {
    	// cout << "Case #" << i+1 << ": ";
    	solve();
    }
    return 0;
}

Measured memory_bytes: 5176
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n,m;
  cin>>n>>m;
  vector<long long> h(n),d(n);
  for(int i=0;i<n;i++){
    cin>>h[i];
    d[i]=1;
  }
  for(int i=0;i<m;i++){
    long long a,b;
    cin>>a>>b;
    if(h[a-1]>h[b-1])d[b-1]=0;
    else if(h[a-1]==h[b-1]){
      d[a-1]=0;
      d[b-1]=0;
    }else if(h[a-1]<h[b-1])d[a-1]=0;
  }
  long long ans=0;
  for(int i=0;i<n;i++){
    if(d[i]==1)ans++;
  }
  cout<<ans<<endl;
  return 0;
  
  
}

Measured memory_bytes: 4860
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>
#include <random>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod  1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pi;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

int main(){
  ll N, M, ans = 0;
  cin >> N >> M;
  if(2 * N <= M){
    ans += N;
    M -= 2 * N;
    N = 0;
  }else{
    ans += M / 2;
    N -= M / 2;
    M = 0;
  }
  ans += M / 4;
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main(void){
  	int N;
  	int i = 0;
 	scanf("%d", &N);
  	char S[10000];
  	scanf("%s", S);
  	int len = strlen(S);
	for(i = 0; i < len; i++){
        int ans = S[i] + N;
      	while(ans > 'Z'){
          	ans -= 26;
        }
  	    printf("%c", ans);
    }
  	printf("\n");
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

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

    if(N&1){
        pr(0);
        return 0;
    }

    ll ans = 0;
    ll bo = 10;
    while(bo <= N){
        ans += N/bo;
        bo *= 5;
    }

    pr(ans);
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  vector<int> v(N, 0);
  for (int i = 0; i < N-1; ++i) {
    int key;
    cin >> key;
    ++v.at(key-1);
  }
  for (int i = 0; i < N; ++i) {
    cout << v[i] << "\n";
  }
}
  
  
  

Measured memory_bytes: 4000
#include <bits/stdc++.h>
using namespace std;
#define INF 100000000
#define rep(i,a,b) for(int (i)=a;(i)<(int)(b);(i)++)


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

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

const int N=501010;
char s[N];

struct Bigint
{
    int a[N],n;
    int& operator [] (const int &x){return a[x];}
    Bigint(){memset(a,0,sizeof(a));n=0;}
    Bigint(char *s){n=strlen(s);for(int i=0;i<n;i++)a[i]=s[n-i-1]-'0';}
    void carry()
    {
        for(int i=0;i<n;i++)
        {
            if(a[i]<=9) continue;
            a[i+1]+=a[i]/10;
            a[i]%=10;
            if(i==n-1) n++;
        }
    }
    Bigint& operator *= (int x){for(int i=0;i<n;i++)a[i]*=x;carry();return *this;}
    int get(){int res=0;for(int i=0;i<n;i++)res+=a[i];return res;}
    void gao(int &sum)
    {
        a[0]+=9;sum+=9;
        for(int i=0;a[i]>9;i++)
        {
            sum-=a[i];sum-=a[i+1];
            a[i+1]+=a[i]/10;a[i]%=10;
            sum+=a[i];sum+=a[i+1];
            if(i==n-1) n++;
        }
    }
} A;

int main()
{
    scanf("%s",s);
    A=s;A*=9;
    int sum=A.get(),k;
    for(k=1;true;k++)
    {
        A.gao(sum);
        if(sum<=9*k&&sum%9==0) break;
    }
    cout<<k<<endl;
    return 0;
}

Measured memory_bytes: 4608
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <cctype>  // std::islower(), std::isupper(), std::tolower, std::toupper
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

int main (void) {
  int a, b; std::cin >> a >> b;
  int maxd = b - a;
  
  int length = (1 + maxd) * maxd / 2;
  std::cout << length - b << std::endl;
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;
class program{
  static void Main(string[] args){
    program p = new program();
    p.Run();
  }
  void Run(){
	string s= ReadLine();
    string t = ReadLine();
    int res=0;
    for(int i=0;i<3;i++)
      if(s.Substring(i,1)==t.Substring(i,1))
        res++;
    WriteLine(res.ToString());
  }

  int[] Readint(){
    string[] s = ReadLine().Split();
    int[] res=new int[s.Length];
    Parallel.For(0,s.Length,i=>{
      res[i]=int.Parse(s[i]);
    });
    return res;
  }
}

Measured memory_bytes: 13140
#include<iostream>
using namespace std;
int main()
{
  int n,x,ans=1,sare=0;
  cin>>n>>x;
  for ( int i = 1 ; i <= n ; i++ ){
    int val;
    cin>>val;
    sare += val;
    if ( sare <= x )
      ans++;
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=200000;

char s[MAXN+1]; int n;

vector<int> pos[26];
int at[26],lft;
int dst[MAXN];
int rev[MAXN];

int bit[MAXN+1];
void bmod(int idx,int by) { ++idx; while(idx<=n) { bit[idx]+=by; idx+=idx&-idx; } }
int bget(int idx) { int ret=0; ++idx; while(idx>0) { ret+=bit[idx]; idx-=idx&-idx; } return ret; }


void run() {
	scanf("%s",s); n=strlen(s);

	REP(i,26) pos[i].clear(); REP(i,n) pos[s[i]-'a'].PB(i);
	int odd=-1; REP(i,26) if(SZ(pos[i])%2==1) { if(odd!=-1) { printf("-1\n"); return; } odd=i; }

	memset(at,-1,sizeof(at)); lft=0; memset(dst,-1,sizeof(dst));
	REP(i,n) {
		int x=s[i]-'a'; while(pos[x][at[x]]!=i) ++at[x];
		if(x==odd&&2*at[x]+1==SZ(pos[x])) { dst[i]=(n-1)/2; continue; }
		if(at[x]<SZ(pos[x])-at[x]-1) {
			dst[i]=lft++;
		} else {
			dst[i]=n-dst[pos[x][SZ(pos[x])-at[x]-1]]-1;
		}
	}
	//printf("dst:"); REP(i,n) printf(" %d",dst[i]); puts("");

	memset(bit,0,sizeof(bit));
	REP(i,n) rev[dst[i]]=i;
	ll ret=0;
	REP(i,n) {
		int before=bget(rev[i]);
		ret+=rev[i]-before;
		bmod(rev[i],+1);
	}
	printf("%lld\n",ret);
}

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


Measured memory_bytes: 3832
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
bool isPrime(int x)
{
	for (int i = 2; i <= sqrt(x); i++)
		if (x%i == 0)
			return false;
	return true;
}
int main()
{
	int n;
	cin >> n;
	vector<int> res;
	int temp = n;
	if (isPrime(n))
		res.push_back(n);
	else
	{
		for (int i = 2; i <= n; i++)
		{
			if (isPrime(i))
				while (temp%i == 0)
				{
					res.push_back(i);
					temp /= i;
				}
			if (temp == 1)
				break;
		}
	}
	cout << n << ":";
	for (int i = 0; i < res.size(); i++)
	{
		cout << " ";
		cout << res[i];
	}
	cout << endl;
}


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

static int current_depth = 0;

struct Node{
  Node() : parent(-1), depth(-1) {}
  int parent, depth;
  vector<int> cld_;
};

void bfs(int pos, vector<Node>& tree){
  tree[pos].depth = current_depth;
  for(int i=0; i<tree[pos].cld_.size(); i++){
    current_depth++;
    bfs(tree[pos].cld_[i], tree);
    current_depth--;
  }
}

int main(){
  int n, id, k, cld;
  cin >> n;
  vector<Node> tree(n);
  for(int i=0; i<n; i++){
    cin >> id >> k;
    while(k--){
      cin >> cld;
      tree[id].cld_.push_back(cld);
    }
  }
  //set parent
  for(int i=0; i<n; i++){
    for(int j=0; j<tree[i].cld_.size(); j++)
      tree[tree[i].cld_[j]].parent = i;
  }
  //what is the root?
  int root;
  for(root=0; root<n; root++)
    if(tree[root].parent == -1)
      break;

  //set the depth
  bfs(root,tree);

  for(int i=0; i<tree.size(); i++){
    cout << "node " << i << ": parent = " << tree[i].parent << ", depth = " << tree[i].depth << ", ";
    if(tree[i].parent == -1)
      cout << "root, [";
    else if(tree[i].cld_.size() == 0)
      cout << "leaf, [";
    else
      cout << "internal node, [";
    if(tree[i].cld_.size()!=0){
      for(int j=0; j<tree[i].cld_.size()-1; j++)
	cout << tree[i].cld_[j] << ", ";
      cout << tree[i].cld_[tree[i].cld_.size()-1];
    }
    cout << "]\n";
  }

  return 0;
}

Measured memory_bytes: 4896
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

ans = float("inf")

for bit in range(1 << d):
    count = 0
    sum = 0
    nokori = set(range(1, d + 1))

    for i in range(d):
        if bit & (1 << i):
            sum += pc[i][0] * (i + 1) * 100 + pc[i][1]
            count += pc[i][0]
            nokori.discard(i + 1)

    # G 点に満たなければ nokori のうち一番大きいものを解く
    if sum < g:
        use = max(nokori)
        n = min(pc[use - 1][0], -(-(g - sum) // (use * 100)))
        count += n
        sum += n * use * 100

    if sum >= g:
        ans = min(ans, count)

print(ans)

Measured memory_bytes: 9212
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef pair<int,int> P;

struct matrix{
	vector< vector<int> > m;
	matrix(){}
	matrix(int h, int w){
		m = vector< vector<int> >(h, vector<int>(w));
		for(int y=0 ; y < h ; y++ )
			for(int x=0 ; x < w ; x++ )
				m[y][x] = 0;
	}
};
matrix operator*(const matrix& a, const matrix& b){
	int h1 = a.m.size(), w1 = a.m[0].size(), h2 = b.m.size(), w2 = b.m[0].size();
	if( w1 != h2 || h1 != w2 ) return matrix();
	
	matrix c(h1, w1);
	for(int i=0 ; i < h1 ; i++ ){
		for(int j=0 ; j < w2 ; j++ ){
			int e = 0;
			for(int k=0 ; k < w1 ; k++ ){
				e += a.m[i][k] * b.m[k][j];
			}
			c.m[i][j] = e;
		}
	}
	return c;
}

matrix get_identify(int n){
	matrix res(n,n);
	for(int i=0 ; i < n ; i++ ) res.m[i][i] = 1;
	return res;
}

matrix pow(const matrix& A, const int z){
	matrix res = get_identify(A.m[0].size());
	matrix x = A;
	for(int i=z-1 ; i ; i >>= 1 ){
		if( i & 1 ){
			res = res * x;
		}
		x = x * x;
	}
	return res;
}

int n, m, z;
P edge[101];

int main(){
	while( cin >> n >> m >> z , n || m || z ){
		for(int i=0 ; i < m ; i++ ){
			int u, v;
			cin >> u >> v;
			u--, v--;
			edge[2*i + 0] = P(u,v);
			edge[2*i + 1] = P(v,u);
		}
		matrix A(2*m, 2*m);
		for(int i=0 ; i < 2*m ; i++ ){
			for(int j=0 ; j < 2*m ; j++ ){
				if( edge[i].second == edge[j].first && edge[i].first != edge[j].second ){
					A.m[i][j] = 1;
				}
			}
		}
		A = pow(A, z);
		bool after[101] = {false};
		bool result[101] = {false};
		for(int i=0 ; i < 2*m ; i++ ){
			if( edge[i].first == 0 ){
				after[i] = true;
			}
		}
		for(int i=0 ; i < 2*m ; i++ ){
			for(int j=0 ; j < 2*m ; j++ ){
				result[j] |= A.m[i][j] && after[i];
			}
		}
		bool ans = false;
		for(int i=0 ; i < 2*m ; i++ ){
			if( result[i] && edge[i].second == n-1 ){
				ans = true;
			}
		}
		cout << (ans? "yes" : "no") << endl;
	}
}

Measured memory_bytes: 1420
N,D = (int(x) for x in input().split())
table = [[int(i) for i in input().split()] for N in range(N)]

cnt = 0
for i in range(N):
    if D**2 >= (table[i][0]*table[i][0] + table[i][1]*table[i][1]):
        cnt+=1

print(cnt)


Measured memory_bytes: 102408
#include<bits/stdc++.h>
using namespace std;
#define optimizar_io ios_base::sync_with_stdio(0); cin.tie(0);
#define fore(i, a, b) for(int i = a; i < b; i++)
#define fori(i, a, b) for(int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb push_back
#define popb pop_back
#define mk make_pair
#define fi first
#define se second
#define endl '\n'
#define MAX 60
typedef long long int lli;
typedef long double ld;
const double PI = acos(-1.0);
ld eps = 1e-9;

int main() {
	optimizar_io
	string s;
	int k; cin >> k >> s;
	if(s.size() <= k) {
		cout << s << endl;
	} else {
		s = s.substr(0, k);
		cout << s << "..." << endl;
	}
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll N;
    cin >> N;
    ll miniZ = numeric_limits<ll>::max(), maxiZ = numeric_limits<ll>::min();
    ll miniW = numeric_limits<ll>::max(), maxiW = numeric_limits<ll>::min();
    rep(i, N) {
        ll x, y;
        cin >> x >> y;
        ll tempZ = x + y;
        ll tempW = x - y;
        miniZ = min(miniZ, tempZ);
        maxiZ = max(maxiZ, tempZ);
        miniW = min(miniW, tempW);
        maxiW = max(maxiW, tempW);
    }
    cout << max(abs(maxiZ - miniZ), abs(maxiW - miniW)) << endl;
    return 0;
}


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

void solve(long long A, long long B){
	if(max(A,B) <= 8) {
		cout << "Yay!" << endl;
	} else {
		cout << ":(" << endl;
	}
}

int main(){	
	long long B;
	long long A;
	scanf("%lld",&A);
	scanf("%lld",&B);
	solve(A, B);
	return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int W, H, x, y;
    cin >> W >> H >> x >> y;

    double ans = (double)W * H / 2;
    int num = (W == x * 2 && H == y * 2) ? 1 : 0;
    cout << ans << " " << num << endl;

    return 0;
}

Measured memory_bytes: 256