akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

int main(int argc, char *argv[])
{
    double x1, y1, x2, y2;
    scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);

    double res = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    printf("%f\n", res);

    return 0;
}



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

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

    char cell[100][100];
    for (int i=0; i<H; i++) {
        for (int j=0; j<W; j++) {
            cin >> cell[i][j];
        }
    }

    for (int i=0; i<W+2; i++) {
        cout << '#';
    }
    cout << endl;

    for (int i=0; i<H; i++) {
        cout << '#';
        for (int j=0; j<W; j++) {
            cout << cell[i][j];
        }
        cout << '#' << endl;
    }

    for (int i=0; i<W+2; i++) {
        cout << '#';
    }
    cout << endl;
}

Measured memory_bytes: 256
used = [[False for i in range(13)] for i in range(4)]
mark = ["S", "H", "C", "D"]
n = int(input())
for i in range(n):
    row = input().split()
    m = row[0]
    j = int(row[1])
    used[mark.index(m)][j - 1] = True
    
for i in range(4):
    for j in range(13):
        if used[i][j] == False:
            print(mark[i], j + 1)
        


Measured memory_bytes: 5604
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <string>
#include <stdio.h>
#include <math.h>
#include <string.h>
#define N 110
#define M 110

using namespace std;

queue<char>qa;
queue<char>qb;
queue<char>qc;

void game()
{
    char t = qa.front();
    qa.pop();
    int flag = 0;
    while(1)
    {
        if (t=='a')
        {
            if (qa.empty())
            {
                flag = 1;
                break;
            }
            t = qa.front();
            qa.pop();
        }
        else if (t=='b')
        {
            if (qb.empty())
            {
                flag = 2;
                break;
            }
            t = qb.front();
            qb.pop();
        }
        else if (t=='c')
        {
            if (qc.empty())
            {
                flag = 3;
                break;
            }
            t = qc.front();
            qc.pop();
        }
    }
    if (flag == 1)
    {
        printf("A\n");
    }
    else if (flag == 2)
    {
        printf("B\n");
    }
    else if (flag == 3)
    {
        printf("C\n");
    }
}

int main()
{
    char a[N], b[N], c[N];
    scanf("%s%s%s",a,b,c);
    int lenA = strlen(a);
    int lenB = strlen(b);
    int lenC = strlen(c);
    for (int i=0;i<lenA;i++)
    {
        qa.push(a[i]);
    }
    for (int i=0;i<lenB;i++)
    {
        qb.push(b[i]);
    }
    for (int i=0;i<lenC;i++)
    {
        qc.push(c[i]);
    }
    game();
    return 0;
}


Measured memory_bytes: 256
while true
    arr = gets.chomp.split.map(&:to_i)
    break if arr == [0, 0, 0, 0, 0, 0]

    arr2, arr3 = [], []
    3.times{|i|
        q, r = (arr[i] + arr[i + 3]).divmod(3)
        arr2 << q
        arr3 << r
    }
    sum = arr2.inject(:+) + arr3.min
    sum += 1 if arr3.sort == [0, 2, 2] && arr2[arr3.index(0)] > 0
    puts sum
end



Measured memory_bytes: 7004
#include<bits/stdc++.h>
using namespace std;
void PDF(int s,int w)
{
    if(s>w)
    {
        cout << "safe" <<endl;
    }
    else
    {
        cout << "unsafe" <<endl;
    }
}
int main()
{
    int s,w;
    cin >> s >> w;
    PDF(s,w);
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
 
int main(){
int N;  cin >> N;
unordered_map<string, long long> mp; 
for (int i = 0; i < N; i++) {
    string tmp;  cin >> tmp;
    sort(tmp.begin(), tmp.end());
    mp[tmp]++;
}

long long ans = 0;
long long n;
for (auto pair: mp) {
    n = pair.second;
    ans += (n * (n - 1) / 2);
}

cout << ans << endl;

}

Measured memory_bytes: 10660
class Lca:
    def __init__(self, E, root):
        import sys
        sys.setrecursionlimit(500000)
        self.root = root
        self.E = E  # V<V>
        self.n = len(E)  # 頂点数
        self.logn = 1  # n < 1<<logn  ぴったりはだめ
        while self.n >= (1<<self.logn):
            self.logn += 1

        # parent[n][v] = ノード v から 1<<n 個親をたどったノード
        self.parent = [[-1]*self.n for _ in range(self.logn)]

        self.depth = [0] * self.n
        self.dfs(root, -1, 0)
        for k in range(self.logn-1):
            for v in range(self.n):
                p_ = self.parent[k][v]
                if p_ >= 0:
                    self.parent[k+1][v] = self.parent[k][p_]

    def dfs(self, v, p, dep):
        # ノード番号、親のノード番号、深さ
        self.parent[0][v] = p
        self.depth[v] = dep
        for e in self.E[v]:
            if e != p:
                self.dfs(e, v, dep+1)

    def get(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u  # self.depth[u] <= self.depth[v]
        dep_diff = self.depth[v]-self.depth[u]
        for k in range(self.logn):
            if dep_diff >> k & 1:
                v = self.parent[k][v]
        if u==v:
            return u
        for k in range(self.logn-1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]

n = int(input())
E = [[] for _ in range(n)]
for i in range(n):
    kc = list(map(int, input().split()))
    k = kc[0]
    for c in kc[1:]:
        E[i].append(c)
        E[c].append(i)
lca = Lca(E, 0)
Q = int(input())
for _ in range(Q):
    u, v = map(int, input().split())
    print(lca.get(u, v))



Measured memory_bytes: 143568
#include<cstdio>
int main(){for(int n,a,c,r,t;c=0,r=scanf("%d",&n),n;printf("%d\n",r))for(char d[]="123456",s[9];n--;r+=*d-48)scanf("%s",s),*s%6-4?a=(*s-78?*s%5-1:0)+c&3,a+=1+(1-a%2*2)*(a/2),t=*d,*d=d[a],d[a]=d[5],d[5]=d[5-a],d[5-a]=t:c+=*s+3;}

Measured memory_bytes: 0
N=int(input())
S=input()

count=0
count_r=0
count_g=0
count_b=0

for s in S:
    if s=="G":
        count_g+=1
    elif s=="R":
        count_r+=1
    else:
        count_b+=1

for i in range((N-3)//2+1):
    #print(i)
    for j in range(N-(i*2)-2):
        #print("---")
        if S[j]==S[j+i+1] or S[j]==S[j+2*i+2] or S[j+i+1]==S[j+2*i+2]:
            pass
        else:
            count+=1

answer=count_g*count_r*count_b-count

print(answer)

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

using namespace std;

int h, w;
char s[55][55];
bool cell[55][55];
bool judge = true;

int main(){
  for(int i = -1; i <= h; ++i){
    for(int j = -1; j <= w; ++j){
      cell[i][j] = 0;
    }
  }
  cin >> h >> w;
  for(int i = 0; i < h; ++i){
    for(int j = 0; j < w; ++j){
      cin >> s[i][j];
      //cout << s[i][j] << endl;
      if(s[i][j] == '#'){
        cell[i][j] = 1;
      }
      //cout << cell[i][j] << endl;
    }
  }
  
  
  for(int i = 0; i < h; ++i){
    for(int j = 0; j < w; ++j){
      //cout << cell[i][j] << endl;
      if(cell[i][j] == 1){
        if(!(cell[i - 1][j] == 1 || cell[i + 1][j] == 1 || cell[i][j - 1] == 1 || cell[i][j + 1] == 1)){
          judge = false;
        }
      }
    }
  }
  if(judge == true){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>

int main()
{
    constexpr auto max = 1'000'000'000'000'000'000 ;
    unsigned int n ;
    std::cin >> n ;

    unsigned long long sum = 1 ;
    bool overed = false ;
    bool included_zero = false ;
    auto past = max ;

    unsigned long long a ;
    for(unsigned int i = 0 ; i < n ; i++) {
        std::cin >> a ;
        if(a == 0) {
            included_zero = true ;
            continue ;
        }
        if(included_zero || overed) {
            continue ;
        }
        if(a > max) {
            overed = true ;
            continue ;
        }
        past = sum ;
        sum *= a ;
        if(sum > max) {
            overed = true ;
            continue ;
        }

        if((sum / a) != past) {
            overed = true ;
            continue ;
        }
    }

    if(included_zero) {
        std::cout << 0 << std::endl ;
        return 0 ;
    }
    if(overed) {
        std::cout << -1 << std::endl ;
        return 0 ;
    }
    std::cout << sum << std::endl ;
    return 0 ;
}

Measured memory_bytes: 3604
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int INF = 1e8;

signed main() {
	int N;
	cin >> N;
	if (N <= 999)cout << "ABC";
	else cout << "ABD";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;
#define F first
#define S second

signed main(){

  int n;
  cin>>n;
  set<P>st,now;
  r(i,(1<<n)){
    int x;
    cin>>x;
    st.insert(P(x,i));
  }
  set<P>::iterator it=st.lower_bound(P(1e9+10,0)); it--;
  now.insert(*it);
  st.erase(P((*it).F,(*it).S));
  //cout<<'a'<<(*it).first<<' '<<(*it).second<<endl;

  while((int)st.size()){
    set<P>tmp;
    for(auto &e:now){
      //cout<<e.first<<endl;
      it=st.lower_bound(P(e.first,0));
      //cout<<'a'<<(*it).first<<' '<<(*it).second<<endl;
      it--;
      if((*it).first >= e.first){
        cout<<"No"<<endl;
        return 0;
      }
      //cout<<'a'<<(*it).first<<' '<<(*it).second<<endl;
      tmp.insert(*it);//cout<<' '<<(int)st.size()<<endl;
      st.erase(P((*it).F,(*it).S));//cout<<' '<<(int)st.size()<<endl;
    }
    //cout<<' '<<(int)st.size()<<endl;
    for(auto &e:tmp)now.insert(e);
  }

  cout<<"Yes"<<endl;

}

Measured memory_bytes: 24832
h,w = gets.chomp.split.map &:to_i
c = []
a = []
10.times{ c << gets.chomp.split.map(&:to_i) }
h.times{ a << gets.chomp.split.map(&:to_i) }

def warshal_floyd(n, edge)
  n.times do |k|
    n.times do |i|
      n.times do |j|
        edge[i][j] = [edge[i][j], edge[i][k] + edge[k][j]].min
      end
    end
  end
end

warshal_floyd(10, c)

need_change = a.flatten.select{|v| v != 1 && v != -1}
if need_change.empty?
  p 0
else
  p need_change.map{|v| c[v][1]}.inject(:+)
end


Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;

int n;
vi ao(200009);
int inf = 999999;

bool test(int k){
    vector<pii> d;
    //cout << "test " << k << endl;
    d.push_back(pii(0,-inf));
    rep(i,0,n){
        int a = ao[i];
        //printf("i %d a\n", i);
        pii t = d.back();
        int ad = 0;
        while(t.first > a){
            d.pop_back();
            t = d.back();
            ad = 1;
        }
        //printf("i %d b\n", i);
        if(t.first == a){
            d.pop_back();
            d.push_back(pii(t.first, t.second+1));
        }else{
            d.push_back(pii(a, ad));
        }
        while(d.back().second == k){
            t = d.back(); d.pop_back();
            pii t2 = d.back();
            if(t2.first == t.first-1){
                d.pop_back();
                d.push_back(pii(t.first-1, t2.second+1));
            }else{
                d.push_back(pii(t.first-1, 1));
            }
        }
        if(d.back().first != a){
            d.push_back(pii(a,0));
        }
        // rep(i,0,sz(d)){
        //     printf("%d,%d; ", d[i].first, d[i].second);
        // }
        // printf("\n");
    }
    if(d[0].second == -inf){
        return true;
    }else{
        return false;
    }
}

int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);

    cin >> n;
    rep(i,0,n){ cin >> ao[i]; }

    bool can1 = true;
    rep(i,0,n-1){
        if(ao[i] >= ao[i+1]) can1 = false;
    }
    if(can1){
        cout << 1 << endl;
    }else{
        int lo = 1;
        int hi = 200001;
        while(lo+1 < hi){
            int mi = (lo+hi)>>1;
            if(test(mi)){
                hi = mi;
            }else{
                lo = mi;
            }
        }

        cout << hi << endl;

    }    
    return 0;
}


Measured memory_bytes: 2092
#include<stdio.h>
#define MAX 500000
#define NUMBER 1000000000

int Left[MAX/2+2],Right[MAX/2+2];
int count=0;

void Merge(int A[],int n,int left,int middle,int right)
{
  int i,j,l,m;
  n=middle-left;
  m=right-middle;
  for(i=0;i<n;i++) Left[i]=A[left+i];
  for(i=0;i<m;i++) Right[i]=A[middle+i];
  Left[n]=NUMBER;
  Right[m]=NUMBER;
  i=0;
  j=0;
  for(l=left;l<right;l++)
    {
      count++;
      if(Left[i]<=Right[j])
        {
          A[l]=Left[i++];
        }
      else
        {
          A[l]=Right[j++];
        }
    }
}

void MergeSort(int A[],int num, int left,int right)
{
  int mid;
  if(left+1<right)
    {
      mid=(left+right)/2;
      MergeSort(A,num,left,mid);
      MergeSort(A,num,mid,right);
      Merge(A,num,left,mid,right);
    }
}
int main()
{
  int A[MAX],n,i;

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

  for(i=0;i<n;i++)
    {
      if(i) printf(" ");
      printf("%d",A[i]);
    }
  printf("\n");
  printf("%d\n",count);

  return 0;
}








Measured memory_bytes: 5588
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using Graph = vector<vector<int>>;
int main() {
  int n, m;
  cin >> n >> m;
  Graph G(n);
  Graph d(n, vector<int>(n, 100100100));
  map<P, int> edge;
  int ans = 0;
  for(int i=0;i<n;i++) d[i][i] = 0;
  for(int i=0;i<m;i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
    d[a][b] = c;
    d[b][a] = c;
    P p = make_pair(a, b);
    edge[p] = c;
  }
  for(int k=0;k<n;k++) {
    for(int i=0;i<n;i++) {
      for(int j=0;j<n;j++) {
        if(d[i][j] > d[i][k] + d[k][j]) d[i][j] = d[i][k] + d[k][j];
      }
    }
  }
  for(auto it = edge.begin(); it!= edge.end(); it++) {
    int from = (it->first).first;
    int to = (it->first).second;
    if(d[from][to] != it->second) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 384
N = int(input())
M0 = M1 = -float('inf')
m0 = m1 = float('inf')

for _ in range(N):
    x, y = map(int, input().split())
    M0 = max(M0, x - y)
    m0 = min(m0, x - y)
    M1 = max(M1, x + y)
    m1 = min(m1, x + y)

print(max(M0 - m0, M1 - m1))

Measured memory_bytes: 74228
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<unordered_map>

#define MAX (200000 + 1)

using namespace std;

int t[MAX], N;

struct segment
{
    bool vertical;
    bool start;
    int x, y1, y2;
};

vector<segment> space;
set<int> appear;
unordered_map<int, int> index;

int sum(int n)
{
    int s = 0;
    while(n > 0)
    {
        s += t[n];
        n -= n & -n;
    }
    return s;
}

void add(int n, int d)
{
    while(n <= N)
    {
        t[n] += d;
        n += n & -n;
    }
    return;
}

int query(int a, int b)
{
    return sum(b) - sum(a - 1);
}

bool cmp(const segment& a, const segment& b)
{
    if(a.x == b.x) // true if a goes first
    {
        if(a.vertical && !b.vertical && b.start) return false;
        else if(a.vertical && !b.vertical && !b.start) return true;
        else if(!a.vertical && a.start && b.vertical) return true;
        else if(!a.vertical && a.start && !b.vertical && !b.start) return true;
        else if(!a.vertical && !a.start && b.vertical) return false;
        else if(!a.vertical && !a.start && !b.vertical && b.start) return false;
    }
    return a.x < b.x;
}

int main()
{
    int n;
    int ans = 0;
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        appear.insert(y1);
        appear.insert(y2);
        if(y1 == y2)
        {
            segment tmp1, tmp2;
            tmp1.vertical = false;
            tmp2.vertical = false;
            tmp1.start = true;
            tmp2.start = false;
            tmp1.y1 = tmp1.y2 = y1;
            tmp2.y1 = tmp2.y2 = y1;
            tmp1.x = min(x1, x2);
            tmp2.x = max(x1, x2);
            space.push_back(tmp1);
            space.push_back(tmp2);
        }
        else
        {
            segment tmp;
            tmp.vertical = true;
            tmp.x = x1;
            tmp.y1 = min(y1, y2);
            tmp.y2 = max(y1, y2);
            space.push_back(tmp);
        }
    }
    set<int>::iterator it = appear.begin();
    for(int i = 0; i < appear.size(); ++i)
    {
        index[*it] = i + 1;
        it++;
    }
    N = appear.size();

    sort(space.begin(), space.end(), cmp);
    for(int i = 0; i < space.size(); ++i)
    {
        if(space[i].vertical) ans += query(index[space[i].y1], index[space[i].y2]);
        else if(space[i].start) add(index[space[i].y1], 1);
        else add(index[space[i].y1], -1);
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 11744
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    X = int(readline())

    n, X = divmod(X, 500)
    m = X // 5

    ans = 1000 * n + 5 * m

    print(ans)

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 61764
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
#include <math.h>
#include <map>

#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;


int main() {
    FASTIO
    int H,W;cin >> H >> W;
    int h,w;cin >> h >> w;
    bool arr[H][W];memset(arr,0, sizeof(arr));
    for(int i=0;i<h;i++){

        for(int j=0;j<W;j++) arr[i][j] = true;
    }
    for(int i=0;i<w;i++){

        for(int j=0;j<H;j++) arr[j][i] = true;
    }
    int cnt = 0;
    for(int i=0;i<H;i++){

        for(int j=0;j<W;j++){

            if(!arr[i][j]) cnt++;
        }
    }
    cout << cnt;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <string.h>
#include <math.h>
#include <map>

using namespace std;

int main(){
	int D, G;
	int p[10], c[10];
	int ans = 1e9;

	cin >> D >>G;

	for (int i = 0; i < D; ++i){
		cin >> p[i] >> c[i];
	}

	for (int mask = 0; mask < (1 << D); ++mask){
		int s = 0, max = 0, total = 0;
		for (int i = 0; i < D; ++i){
			if (mask >> i & 1){
				s += 100 * (i + 1) * p[i] + c[i];
				total += p[i];
			}
			else
				max = i;
		}
		if (s < G){
			int rest = ceil((double)(G - s) / ((max + 1) * 100));
			if (rest >= p[max])
				continue;
			total += rest;
		}
		ans = min(total, ans);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{   long long n;
    scanf("%lld",&n);
    if(n%2==0){
        printf("%lld %lld %lld",n,n,n/2);
        return 0;
    }
    for(long long i=1;i<=3500;i++){
        for(long long j=1;j<=3500;j++){
            if((4*i*j-n*i-n*j)>0&&n*i*j%(4*i*j-n*i-n*j)==0&&n*i*j/(4*i*j-n*i-n*j)>0){
                printf("%lld %lld %lld",i,j,n*i*j/(4*i*j-n*i-n*j));
                return 0;
            }
        }
    }

    return 0;
}


Measured memory_bytes: 128
from collections import deque
n,m = map(int,input().split())
path = [[] for _ in range(n)]
inf = float('inf')
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a].append(b)
    path[b].append(a)
que = deque([0])
parent = [-1]*n
d = [inf]*n
d[0] = 0
while que:
    p = que.popleft()
    for nxt in path[p]:
        if d[nxt] <= d[p]+1:continue
        d[nxt] = d[p] + 1
        parent[nxt] = p+1
        que.append(nxt)
print('Yes')
print('\n'.join(str(i) for i in parent[1:]))


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

int main()
{
ll a,b,c,d,e;
cin>>a>>b>>c>>d>>e;

ll p=a*60+b;
ll q=c*60+d;
ll res=abs(p-q)-e;
   cout<<res<<endl;







}

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

using namespace std;
#define sz(a) int(a.size())
#define ll  long long
#define ull unsigned long long
//#define mod int(1e9+7)
#define endl '\n'
#define Engz ios::sync_with_stdio(0);ios_base::sync_with_stdio(0);cin.tie(0) , cout.tie(0) ;
#define pi double(acos(-1))
#define S second
#define F first

//  freopen("input.txt","r",stdin);

//------------------- BESH ----------------------//
long long mod ;
long long p(long long a ,long long b)
{
    if(b==0)
        return 1;

    long long z=p(a,b/2);


    if(b%2==0)return ((z%mod)*(z%mod))%mod; else return (((z*z)%mod)*a)%mod;
}

long long g(long long a, long long b)
{
    if(a==0)
        return b;
    else return g(b%a , a);
}

//-----------sieve --------------------//

bool prime[1000001];

void sieve()
{
memset(prime , true , sizeof prime);
prime[0]=prime[1]=0;

for(int i=2 ; i*i<=1000000; i++)
{
    if(prime[i]==true)
    for(int j=i*i ; j<=100000 ; j+=i)
    prime[j]=false;
}
}

ll lcm(ll a, ll b)
{
    return (a*b)/__gcd(a,b);
}


int a[1002][1002]={{}};

int main()
{


   int n , x;
   cin>>n>>x;
   int a[n];

   for(int i=0 ; i<n ; i++) cin>>a[i];
   int ans[n];

   ans[0]=0; ans[1]=(abs(a[1]-a[0]));

   for(int i=2 ; i<n ; i++)
   {
       ans[i]=1e9;
    for(int j=i-1 ; j>=max(0, i-x) ; j--)
    ans[i]=min(ans[j]+abs(a[i]-a[j]) ,ans[i]);
   }
   cout<<ans[n-1];
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    if (a >= k) {
        cout << k << endl;
    } else if (a+b >= k) {
        cout << a << endl;
    } else {
        cout << a - (k-a-b) << endl;
    }
}

Measured memory_bytes: 3644
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N, M = lr()
A = set(ir() for _ in range(M))
dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
    if i+2 not in A and i+2 <= N:
        dp[i+2] += dp[i]
    if i+1 not in A:
        dp[i+1] += dp[i]

print(dp[-1]%MOD)


Measured memory_bytes: 465268
#include <bits/stdc++.h>
using namespace std;
bool is_proper(unsigned int in);
int main() {
  unsigned int a = 0, b = 0;
  cin >> a >> b;
  while(!is_proper(a) || !is_proper(b)){
    cin >> a >> b;
  }
  cout << (a+b+1)/2<< endl;
}

bool is_proper(unsigned int in){
  if (in>=1&&in<=100){
    return true;
  }
  return false;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)

ll A[100100];
int main(){
    int N;
    cin >> N;
    int odd = 0;
    int even = 0;
    REP(i,N){
        ll a;
        cin >> a;
        A[i] = a;
        if(a%2) odd++;
        else even++;
    }

    bool ans;
    ans = (odd != 0);

    if(ans)
        printf("first\n");
    else
        printf("second\n");
    return 0;
}


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

using namespace std;

int main() {
  int n, m;
  cin >> n;
  vector<string> u(n);
  map<string, int> mp;
  for (int i = 0; i < n; i++) {
    cin >> u[i];
    mp[u[i]]++;
  }
  cin >> m;
  vector<string> t(m);
  for (int i = 0; i < m; i++) {
    cin >> t[i];
  }
  bool f = true;
  for (int i = 0; i < m; i++) {
    if (mp[t[i]] == 0) {
      cout << "Unknown " << t[i] << endl;
    } else {
      if (f) {
        f = !f;
        cout << "Opened by " << t[i] << endl;
      } else {
        f = !f;
        cout << "Closed by " << t[i] << endl;
      }
    }
  }

  return 0;
}


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

#define INF 1e18
#define REP(i, n) for (int i=0; i<n; i++)
#define print(x) cout << x << endl
#define debug(x) cout << #x << " = "<< x << endl

const double PI=3.141592653589793238462643383279502884197169399375105820974944;

typedef long long ll;

using namespace std;

void solve() {
    string S;
    cin >> S;
    vector<int> a(S.length()+1, 0), b(S.length()+1, 0);
    for (int i = 1; i < a.size(); i++) {
        if (S[i-1] == '<') {
            a[i] = a[i-1] + 1;
        }
    }
    for (int i = b.size()-2; i >= 0; i--) {
        if (S[i] == '>') {
            b[i] = b[i+1] + 1;
        }
    }

    ll ans = 0;
    REP(i, a.size()) {
        ans += max(a[i], b[i]);
    }
    print(ans);
}

signed main() {
    solve();
}


Measured memory_bytes: 4740
import heapq
def solve():
    N = int(input())
    klr = [list(map(int,input().split())) for _ in range(N)]
    
    ll = []
    lr = []
    for i in range(N):
        if klr[i][1]>klr[i][2]:
            ll.append(klr[i])
        else:
            lr.append(klr[i])

    ansl = 0
    ll.sort(key=lambda x:-x[0])
    j = 0
    cand = []
    for i in range(len(ll)-1,-1,-1):
        while j<len(ll):
            if ll[j][0]-1<i:
                break
            heapq.heappush(cand,[ll[j][2]-ll[j][1],ll[j][0],ll[j][1],ll[j][2]])
            j += 1
        if cand:
            d,k,l,r = heapq.heappop(cand)
            ansl += l
    while cand:
        d,k,l,r = heapq.heappop(cand)
        ansl += r

    ansr = 0
    lr.sort(key=lambda x:x[0])
    j = 0
    cand = []
    for i in range(len(ll),N+1):
        while j<len(lr):
            if lr[j][0]>i:
                break
            heapq.heappush(cand,[-lr[j][2]+lr[j][1],lr[j][0],lr[j][1],lr[j][2]])
            j += 1
        if cand and i!=N:
            d,k,l,r = heapq.heappop(cand)
            ansr += r
    while cand:
        d,k,l,r = heapq.heappop(cand)
        ansr += l
    ans = ansl+ansr
    print(ans)

T = int(input())
for t in range(T):
    solve()        

Measured memory_bytes: 130792
#include <iostream>
using namespace std;
int main(){
  string s,t,u;
  int a,b;
  cin >> s >> t >> a >> b >> u;
  if(s==u) cout << a-1 << " " << b << "\n";
  else cout << a << " " << b-1 << "\n";
  return 0;
}  

Measured memory_bytes: 3468
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ABC126_a solver = new ABC126_a();
        solver.solve(1, in, out);
        out.close();
    }

    static class ABC126_a {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int N = in.nextInt();
            int K = in.nextInt();
            String S = in.next();

            char low = S.charAt(K - 1);
            String s = String.valueOf(low).toLowerCase();
            for (int i = 0; i < S.length(); i++) {
                if (i == K - 1) {
                    out.print(s);
                } else {
                    out.print(S.charAt(i));
                }
            }
        }

    }
}



Measured memory_bytes: 23252
import java.util.*;

class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        int total = a + b;
        
        if (total % 2 == 0) {
            System.out.println(total / 2);
        } else {
            System.out.println("IMPOSSIBLE");
        }
        
    }
}

Measured memory_bytes: 22740
#include <stdio.h>

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

  return 0;
}


Measured memory_bytes: 2032
//ΔARC087E
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long LL;
const int N = 111111;
int n,w,s[N];
int tot,l[N],r[N],h[N];
char ch[N];
LL k;
int ad(int u){
	h[++tot]=h[u]+1;
	return tot;
}
void dfs(int u,int d){
	if(d==w)
		return;
	if(ch[d]=='0'){
		if(!l[u])
			l[u]=ad(u);
		dfs(l[u],++d);
	}
	else{
		if(!r[u])
			r[u]=ad(u);
		dfs(r[u],++d);
	}
}
LL lowbit(LL x){
	return x&-x;
}
int main()
{
	int i;
	LL ans;
	cin>>n>>k;
	s[0]=1;
	while(n--){
		scanf("%s",ch);
		w=strlen(ch);
		dfs(0,0);
	}
	ans=0;
	for(i=0;i<=tot;i=i+1)
		if((l[i]==0)^(r[i]==0))
			ans^=lowbit(k-h[i]);//,cout<<k-h[i]<<endl;
	if(ans==0)
		cout<<"Bob\n";
	else
		cout<<"Alice\n";
	return 0;
}

Measured memory_bytes: 1536
import java.util.Scanner;
 

//result = Math.pow(num1, num3)
//StringBuffer str = new StringBuffer(hoge1);
//String hoge2 = str.reverse().toString();
//map.containsKey(A)

//Map<String, Integer> map = new HashMap<String, Integer>(n);
/*for ( キーのデータ型 key : マップの名前.keySet() ) {
	データのデータ型 data = マップの名前.get( key );
	
	// keyやdataを使った処理;
}*/

//ArrayList<String> cc = new ArrayList<>(n);
//Collections.sort(list);
//Array.sort(list);
//Arrays.asList(c).contains("a")
//list.set(1,"walk");
public class Main {
	//static String eikomoji[]={"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
	static long N;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=Integer.parseInt(sc.next());;
		int nextMin=1;
		int ctn=0;
		int v;
		for(int i=0;i<n;i++) {
			v=Integer.parseInt(sc.next());
			if(v==nextMin) {
				nextMin++;
			}else {
				ctn++;
			}
		}
		if(nextMin==1) {
			System.out.println(-1);
		}else {
			System.out.println(ctn);
		}

	}
	

	
	
	
}


Measured memory_bytes: 49696
#include <bits/stdc++.h>
using namespace std;
    
#define IOS cin.sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, n) for (int i = 0; i < n; i++)
#define repn(i, a, b) for (int i = a;i<=b;i++)
#define ll long long int
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define mem(x) memset(x, 0, sizeof(x))
#define ritr(it, a) for (auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define pai pair < int, int> 
#define pal pair < ll, ll> 
#define vi vector <int> 
#define vl vector < ll > 
#define vpai vector < pii > 

const int mod = 1e9+7;
const int INF = INT_MAX;
const int sze = 3005;

void solve() {
    int n;
    cin>>n;
    ll arr[n];
    ll dp[n];
    mem(dp);
    rep(i,n) cin>>arr[i];
   
    sort(arr,arr+n,greater<int>());
     ll sum=arr[0];
    int j=2,i=1;
    while(j<n){
        sum+=arr[i];
        j++;
        if(j>=n) break;
        sum+=arr[i];
        i++;
        j++;
    }

    cout<<sum;

}

int main() {
    IOS;

    int t = 1;
    // cin >> t;
    while (t--) {
       solve();
    }

  return 0;
}

Measured memory_bytes: 6788
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            int[] array=cin.ReadIntArray(4);
            int sx = array[0];
            int sy = array[1];
            int tx = array[2];
            int ty = array[3];
            int dx = tx - sx;
            int dy = ty - sy;

            string answer = new string('U', dy)
                + new string('R', dx)
                + new string('D', dy)
                + new string('L', dx)
                + 'L'
                + new string('U', dy + 1)
                + new string('R', dx + 1)
                + 'D'
                + 'R'
                + new string('D', dy + 1)
                + new string('L', dx + 1)
                + 'U';

            Console.WriteLine(answer);
            


        }

    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
    int N; cin >> N;
    vector<vector<int> > a(10, vector<int> (10));
    for(int i = 1; i <= N; i++){
        string s = to_string(i);
        a[s[0] - '0'][s[s.size() - 1] - '0']++;
    }
    int ans = 0;
    for(int i = 1; i <= 9; i++){
        for(int j = 1; j <= 9; j++){
            ans += a[i][j] * a[j][i];
        }
    }
    cout << ans << endl;
}

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

ansl = [[0 for _ in range(w)] for _ in range(h)]

idx = 0
for color, a in enumerate(al):
    for i in range(a):
        yoko = idx % w
        tate = idx // w
        if tate % 2 == 1:
            yoko = w - yoko - 1 
        ansl[tate][yoko] = str(color+1)
        idx += 1

for ans in ansl:
    print(" ".join(ans))

Measured memory_bytes: 3700
#include <stdio.h>

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

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

int main() {
	int sum = 0;
	for (int i = 0; i < 4; i++) {
		int x;
		cin >> x;
		sum += x;
	}
	cout << sum / 60 << endl;
	cout << sum % 60 << endl;
	return 0;
}

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

int main() {
  ll N;
  cin >> N;
  ll j = 1;
  rep(i,N) {
    j *= i + 1;
    j %= MOD;
  }
  cout << j;
}

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

#define sb long long int

using namespace std;

int main()
{
  sb a, b;
  cin >> a >> b;
  if(a > 9 or b > 9)
  {
    cout << -1;
    
  }
  else cout << a * b; 
  return 0;
}

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

#define rep(i,n) for (int i=0; i<(n); i++)
const int INF =1001001001;
const ll BIG = 1000000007;

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> h(n);
    rep(i,n) cin >> h[i];
    vector<int> a(m), b(m);
    rep(i,m) cin >> a[i] >> b[i];
    vector<int> d(n+1,1);
    d[0] = 0;
    rep(i, m){
        int high;
        if(h[a[i]-1]>h[b[i]-1]) high = b[i];
        else if(h[a[i]-1]==h[b[i]-1]){
            d[a[i]] = 0;
            d[b[i]] = 0;
            continue;
        }else high = a[i];
        d[high] = 0;
    }
    int ans = 0;
    rep(i,n+1) ans+=d[i];
    cout << ans << endl;
}

/*
void solve(int N, int M, vector<ll> H){
    vector<int> ans;
    ans = vector<int> (N, 1);
    int s, t;
    ll low_h;
    for (int i=0; i<M; i++){
        cin >> s >> t;
        if (H[s-1]==H[t-1]){
            ans[s-1]=0;
            ans[t-1]=0;
        }else{
            low_h = min(H[s-1], H[t-1]);
            if (H[s-1]==low_h) ans[s-1]=0;
            else ans[t-1] = 0;
        }
    }
    //cout << ans[0] << ans[1] << ans[2]<< ans[3]<< ans[4]<< ans[5]<<endl;
    cout << accumulate(ans.begin(), ans.end(), 0) << endl;
}

int main(){
    int N, M;
    cin >> N >> M;
    vector<ll> H;
    H = vector<ll>(N, 0);
    ll h;
    for (int i=0; i<N; i++){
        cin >> h; H[i] = h;
    }
   solve(N, M, H);
}
*/

Measured memory_bytes: 4840
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("-ffloat-store")
 
#define int  long long
#define rep(i,begin,end) for(__typeof(end)i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define F first
#define S second
#define sz(x) ((int)x.size())
#define pb push_back
#define pf push_front
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mod 1000000007
#define what_is(x) cerr << #x << " is " << x <<"\n";
#define sortA(v) sort(v.begin(), v.end())
#define sortD(v) sort(v.rbegin(), v.rend())
#define PI 3.14159265358979323846
#define vout(a) for(auto x:a) cout<<x<<" ";
#define INF 2000000000000000000 //2e18
 
// #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
 
 
// using namespace __gnu_pbds;
using namespace std;
 
using ll  = long long;
using vi  = vector<int>;
using pii = pair<int,int>;
using vii = vector<pii>;
using mi  = multiset<int>;
using mii = multiset<pii>;
 
int lcm(int a,int b) {return (a*(b/__gcd(a,b)));}



void solve()
{
    int n,m,t,i,k,r,l,u,v,w,j,s,pos,sum=0,flag=0,count=0;
    string S,T,U; 
    // int h;
    cin>>n;
    vi a(n);
    rep(i,0,n) cin>>a[i];
    vi b=a;
    sortD(b);
    if(a==b)
    {
        cout<<"1000";
        return;
    }
    vi buy(n);
    rep(i,0,n-1)
    {
        if(a[i]<a[i+1]) buy[i]++;
    }
    rep(i,n,1)
    {
        if(a[i-1]==a[i]&&buy[i]) buy[i-1]++;
    }
    // vout(buy)
    // cout<<"\n";
    int money=1000;
    int stocks=0;
    rep(i,0,n)
    {
        if(buy[i])
        {
            stocks+=money/a[i];
            money=money-(money/a[i])*a[i];
            // i++;
            // money+=stocks*a[i];
            // stocks=0;
        }
        else
        {
            if(buy[i-1])
            {
                money+=stocks*a[i];
                stocks=0;
            }
        }
        // cout<<money<<" ";
    }
    cout<<money;
}

 

signed main()
{
    #ifndef ONLINE_JUDGE 
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();
        if(t)cout<<"\n";
    }
    return 0;
}










/*
vector<vi> multiply(vector<vi> a,vector<vi> b)
{
    vector<vector<int>> c(2,vector<int>(2));
    rep(k,0,2)
    {
        rep(i,0,2)
        {
            rep(j,0,2)
            {
                c[i][j]+=(a[i][k]*b[k][j])%mod;
                c[i][j]%=mod;
            }
        }
    }
    return c;
}

vector<vi> binexp(vector<vi> a,int n)
{
    if(n==0)
    {
        vector<vector<int>> c(2,vector<int>(2));
        rep(i,0,2) rep(j,0,2) c[i][j]=(i==j);
        return c;
    }
    if(n==1) return a;
    if(n%2)
    {
        vector<vi> ans=binexp(a,n/2);
        return multiply(ans,multiply(ans,a));
    }
    else
    {
        vector<vi> ans=binexp(a,n/2);
        return multiply(ans,ans);
    }
}
*/

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

int main() {
	long N, S; cin >> N >> S;
	if(N<=S){
	    cout << (N<S ? -1 : N+1) << endl;
	    return 0;
	}
	long p;
	for(p=2; p*p<=N; ++p){
	    long m=N, sum=0;
	    while(m>0){
	        sum += m%p;
	        m /= p;
	    }
	    if(sum==S){
	        cout << p << endl;
	        return 0;
	    }
	}
	for(long t=min(N/p, S); t>0; --t){
	    long ans=(N-S+t)/t;
	    if((N-S+t)%t==0 && ans>max(t, S-t)){
	        cout << ans << endl;
	        return 0;
	    }
	}
	cout << -1 << endl;
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  int N, M;
  cin >> N >> M;
  vector<ll> seq(M);
  vector<ll> d(M-1);
  REP(i, M) {
    cin >> seq[i];
  }
  if (N >= M) {
    cout << 0 << endl;
    return 0;
  }
  sort(seq.begin(), seq.end());
  REP(i, M-1) {
    d[i] = abs(seq[i+1] - seq[i]);
  }
  sort(d.begin(), d.end());
  ll ans = 0;
  while (N > 1) {
    d.pop_back();
    N--;
  }
  REP(i, d.size()) {
    ans += d[i];
  }
  
  cout << ans << endl; 
}

Measured memory_bytes: 1792
#include <stdio.h>

int cmp(char[],char[]);

int main() {
  int n,i,j,k,m;
  char a[101][2],b[101][2],tmp[2];
  scanf("%d",&n);
  for(i=0; i<n; i++) {
    scanf("%s",a[i]);
    for(k=0; k<2; k++) b[i][k]=a[i][k];
  }
  for(i=0; i<n; i++) {
    for(j=n-1; j>i; j--) {
      if(a[j][1]<a[j-1][1]) {
	for(k=0; k<2; k++) tmp[k]=a[j][k];
	for(k=0; k<2; k++) a[j][k]=a[j-1][k];
	for(k=0; k<2; k++) a[j-1][k]=tmp[k];
      }
    }
  }
  for(i=0; i<n; i++) {
    m=i;
    for(j=i+1; j<n; j++) {
      if(b[j][1]<b[m][1]) m=j;
    }
    if(b[m][1]<b[i][1]) {
      for(k=0; k<2; k++) tmp[k]=b[i][k];
      for(k=0; k<2; k++) b[i][k]=b[m][k];
      for(k=0; k<2; k++) b[m][k]=tmp[k];
    }
  }
  int ck=1;
  for(i=0; i<n; i++) {
    if(a[i][0]!=b[i][0]) ck=0;
  }    
  for(i=0; i<n; i++) {
    if(i) printf(" ");
    printf("%c%c",a[i][0],a[i][1]);
  }
  printf("\nStable\n");
  for(i=0; i<n; i++) {
    if(i) printf(" ");
    printf("%c%c",b[i][0],b[i][1]);
  }
  if(ck) printf("\nStable\n");
  else printf("\nNot stable\n");
  return 0;
}




Measured memory_bytes: 2128
import math

x1,y1,x2,y2=map(int, input().split())

#line = math.sqrt(pow(x2-x1,2)+pow(y2-y1,2))

buf1=x2-x1
buf2=y2-y1

print(x2-buf2,y2+buf1,x1-buf2,y1+buf1)

Measured memory_bytes: 2940
# include <bits/stdc++.h>
 
/*
// ordered_set 
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
# define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
 
using namespace std;
 
typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;
 
# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define Sort(x)                                         sort(all(x))
# define InTheNameOfGod                                  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
 
const int xn = 2e3 + 10;
const int xm = - 20 + 10;
const int SQ = 320;
const int sq = 320 + 10;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod = 998244353;
const int TM = 3;
const int base = 257;

int n, ans = inf, sum, sz[xn];
pii dp[xn];
vector <int> adj[xn];
vector <pii> vec[xn];
string s;

void DFS(int v, int par = - 1){
	vec[v].clear();
	sz[v] = (s[v - 1] == '1');
	dp[v] = {0, 0};
	for (int u : adj[v]){
		if (u == par) continue;
		DFS(u, v);
		sz[v] += sz[u];
		dp[v].B += dp[u].B + sz[u];
		dp[u].A += sz[u];
		dp[u].B += sz[u];
		vec[v].push_back(dp[u]);
	}
	if (!SZ(vec[v])) return;
	int ind = 0;
	for (int i = 1; i < SZ(vec[v]); ++ i) if (vec[v][i].A > vec[v][ind].A) ind = i;
	bool flag = false;
	sum = 0;
	for (int i = 0; i < SZ(vec[v]); ++ i){
		if (i == ind) continue;
		flag |= (vec[v][i].B >=  vec[v][ind].A);
		sum += vec[v][i].B;
	}
	if (flag) dp[v].A = dp[v].B % 2;
	else{
		if (vec[v][ind].A <= sum) dp[v].A = dp[v].B % 2;
		else dp[v].A = vec[v][ind].A - sum;
	}
}

int main(){
    InTheNameOfGod;
    
    cin >> n >> s;
    for (int i = 0; i < n - 1; ++ i){
    	int v, u;
    	cin >> v >> u;
    	adj[v].push_back(u);
    	adj[u].push_back(v);
	}
	for (int i = 1; i <= n; ++ i){
		DFS(i);
		if (dp[i].A) continue;
		ans = min(ans, dp[i].B / 2);
	}
	if (ans == inf) kill(- 1);
	kill(ans);

    return 0;
}


Measured memory_bytes: 3960
#!/usr/bin/env python3
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
]
k = int(input())
print(a[k - 1])

Measured memory_bytes: 3060
N,M = map(int,input().split())
nes = []
count = 0
for i in range(N) :
    li = list(map(int,input().split()))
    nes.append(li)
favorite = [0] * M
for i in range(N) :
    for j in range(1,nes[i][0]+1) :
        favorite[nes[i][j]-1] += 1
for i in range(M) :
    if favorite[i] == N :
        count+=1
print(count)

Measured memory_bytes: 3064
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, H: "List[int]"):
    print(sum(sorted(H,reverse=True)[K:]))


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    H = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, H)

if __name__ == '__main__':
    main()


Measured memory_bytes: 30588
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  int N;
  double x;
  string u;
  cin >> N;
  double y = 0;
  double b = 0;
  for (int i = 0; i < N; i++) {
    cin >> x >> u;
    if (u == "JPY") y += x;
    else b += x;
  }
  double ret = y + b * 380000.0;
  printf("%.12f\n", ret);
}

Measured memory_bytes: 384