akhauriyash/Code-Regression huggingface dataset:
# https://atcoder.jp/contests/abc137/tasks/abc137_d
# 全然わからん ソートしてgreedyに報酬高いやつから突っ込めるだけ突っ込んで見る←だめでした

# 解説AC
# 後ろから問題を見ていくと良いかも？
# 前から貪欲ではなぜ行けないのか？→残り日付が遠い中で最大の報酬 よりも 残り日付が近い中で最大の報酬を選んだほうが最適になる可能性があるから
# では後ろから貪欲は？→残り日付が近いなかで最大の報酬はその時点で最適な選択肢となることが確定できる。→OK
# だけどi日後までの候補に絞ってソートし直すと O(MNlogN)の計算量になる
# →priority queueで高速化
# つまり i 日後を考えるときに、それが可能となる候補をqueに追加 (最大logNがM回必要)
# その中で最大の報酬をもたらすものをpop (最大logNがM回必要)
# 日付のソートでNlogNかかる。
# この問題の計算量はO((M+N)logN)である


from heapq import heapify, heappop, heappush, heappushpop
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


N, M = read_ints()
AB = read_tuple(N)

# AB.sort()
from collections import defaultdict
ilimb = defaultdict(lambda: [])
for a, b in AB:
    ilimb[a].append(b)

q = PriorityQueue([])
l = 0  # ABのindex
ans = 0

# for i in range(1, M + 1):
#     for j in range(l, N):
#         a, b = AB[j]
#         if a > i:  # i日以内に支払われない
#             l = j  # ココらへんに実装のバグがありそう
#             break
#         q.push(-b)  # pythonでは最小ヒープのため
#     if q:  # qが空のときはしょうがないのでskip
#         ans -= q.pop()

for i in range(1, M + 1):
    for b in ilimb[i]:
        q.push(-b)  # pythonでは最小ヒープのため
    if q:  # qが空のときはしょうがないのでskip
        ans -= q.pop()

print(ans)


Measured memory_bytes: 38160
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

int main() {
    int c[3][3];
    rep(i, 3) {
        rep(j, 3) {
            cin >> c[i][j];
        }
    }

    if( (c[0][1] + c[1][0] == c[0][0] + c[1][1]) && (c[0][2] + c[1][0] == c[0][0] + c[1][2]) 
        && (c[0][1] + c[2][0] == c[0][0] + c[2][1]) && (c[0][2] + c[2][0] == c[0][0] + c[2][2]) ) {
            cout << "Yes";
    }
    else {
        cout << "No";
    }

    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define LLINF 9223372036854775807
#define MOD ll(1e9+7)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr<<#x<<": "<<x<<endl


int main(){
    ll n;
    cin >> n;

    map<string,ll> mp;
    ll ans = 0;
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        sort(all(s));
        mp[s]++;
        ans += mp[s]-1;
    }

    cout << ans << endl;
    return 0;

}


Measured memory_bytes: 11136
N = int(input())
A = list(map(int, input().split()))

A.sort()

edge = [0] * 2
for i in range(2):
    while True:
        l = len(A)
        if len(A) < 2:
            print(0)
            exit(0)

        if A[l-2] == A[l-1]:
            edge[i] = A.pop()
            A.pop()
            break

        A.pop()

print(edge[0] * edge[1])


Measured memory_bytes: 85860
#include <stdio.h>
#include <math.h>

int main()
{
    int monsterHealth, attacksDone, attacksAmount, killingAttack;
    scanf("%d %d",&monsterHealth, &attacksDone);

    attacksAmount = monsterHealth / attacksDone;
    killingAttack = attacksAmount * attacksDone;

    if (killingAttack  < monsterHealth)
    {
        attacksAmount++;
    }

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

    return 0;
}


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

typedef long long ll;

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

    vector<int> d(N);
    for(int i=0;i<N;i++){
        cin>>d.at(i);
    }

    sort(d.begin(),d.end());
    int m=0;
    m=N/2;
    int l=0;
    int r=0;
    l=d.at(m-1);
    r=d.at(m);

    if(l==r){
        cout<<0<<endl;
    }
    else{
        cout<<r-l<<endl;
    }
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<int> p(n+1);
    FOR(i,1,n+1) cin>>p[i];
    int cnt=0;
    FOR(i,1,n+1){
      if(i-1>=1 && i+1<=n){
        vector<int> ans;
        ans.push_back(p[i-1]);
        ans.push_back(p[i]);
        ans.push_back(p[i+1]);
        sort(begin(ans),end(ans));
        if(ans[1]==p[i]) cnt++;
      }
    }
    cout<<cnt<<endl;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi; 
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;

#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ini(a, i) memset(a, i, sizeof(a))
#define contains(c, i) ((c).find(i) != (c).end())
#define present(i, c) (find(all(c), i) != (c).end())

#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i <= n; i++)
#define repa(i, a, b) for(int i = (a); i < (b); i++)
#define repd(i, n) for(int i = (n)-1; i >= 0; i--)

#define TRACE(x...) x
#define watch(x) TRACE(cerr << #x" = " << x << endl)
#define watch_all(x) TRACE(cerr << #x" = "; for(auto __i : x) cerr << __i << " "; cerr << endl)

//=========================

#define INF 0x3F3F3F3F

const int MAXN = (int) 1e6;
const int MAXN2 = (int) 2e5;

int N;
int A[MAXN2+1];
bool ok[MAXN2+1];
int pn[MAXN+1];

vector<int> prime; // lista de primos ate sqrt(MAXN)

// all primes from 2 to sqrt(N)
void getprimes() {
    int n = sqrt(MAXN)+1; // soh analisa primos ate sqrt(MAXN)
    prime.clear(); prime.reserve(n);
    prime.push_back(2);
	for(int k = 3; k <= n; k += 2) {
		bool is_prime = true;
		for(int j = 0; j < sz(prime); j++) if (k % prime[j] == 0) {
	        is_prime = false;
	        break;
		}
		if (is_prime) prime.push_back(k);
	}
}

vector<int> p; // primos
vector<int> e; // expoentes

// fatoracao de 'n' em fatores p^e
void getfactors(int n) {
	if(sz(prime) == 0) getprimes();
    p.clear(); e.clear();    
    rep(i, sz(prime)) {
        if(prime[i] > n / prime[i]) break; // soh analisa primos ate sqrt(n)
        if(n % prime[i] == 0) {
            p.pb(prime[i]); e.pb(0);
            while(n % prime[i] == 0) n /= prime[i], e.back()++;
        }
    }
    if (n != 1) p.pb(n), e.pb(1);
}

vector<int> d; // divisores

// all divisors of 'n'
void getdivisors(int n) {   
    getfactors(n);
    d.clear(); d.pb(1);
    rep(i, sz(p)) {
        int r = sz(d);
        rep(j, e[i]) rep(k, r) d.pb(p[i] * d[k+j*r]);
    }    
}

void check_divisors() {
    rep(i, N) {
        ok[i] = true;
        getdivisors(A[i]);
        for(int x : d) {
            if(x == A[i]) ok[i] &= (pn[x] == 1);
            else ok[i] &= (pn[x] == 0);
        }
    }
}

void run_test() {
    cin >> N;
    ini(pn, 0);
    rep(i, N) cin >> A[i], pn[A[i]]++;
    check_divisors();
    int ans = 0;
    rep(i, N) ans += ok[i];
    cout << ans << endl;
}

//=========================

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	//int t = 1, _t; cin >> _t; while(t <= _t) { cout << "Case #" << t++ << ": "; run_test(); }
	// int t; cin >> t; while(t--) run_test();
	run_test();
	return 0;	
}


Measured memory_bytes: 8548
#include <stdio.h>

int gcd(int x,int y){
    if(x%y == 0) return y;
    gcd(y,x%y);

}

int main() {
    int x, y;
    scanf("%d %d", &x, &y);
    printf("%d",gcd(x, y));
    printf("\n");
    return 0;
}


Measured memory_bytes: 2108
#include <cstdio>
#include <algorithm>
#include <vector>
#define N 100005
using namespace std;
int n, m, p[N], y[N];
vector<int> vt[N];

int main() {
	int i, k;
	scanf("%d%d", &n, &m);
	for(i=0; i<m; i++) {
		scanf("%d%d", &p[i], &y[i]);
		vt[p[i]].push_back(y[i]);
	}
	for(i=1; i<=n; i++) sort(vt[i].begin(), vt[i].end());
	for(i=0; i<m; i++) {
		k = lower_bound(vt[p[i]].begin(), vt[p[i]].end(), y[i]) - vt[p[i]].begin();
		printf("%06d%06d\n", p[i], k+1);
	}
	return 0;
}

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

typedef long long ll;

int main() {
  int N; cin >> N;
  int x[101],y[101],h[101];
  for ( int i = 0; i < N; i++ ) cin >> x[i] >> y[i] >> h[i];

  for ( int posY = 0; posY <= 100; posY++ ) {
    for ( int posX = 0; posX <= 100; posX++ ) {
      int needH = -1;
      for ( int i = 0; i < N; i++ ) {
	if ( h[i] > 0 ) {
	  int tmp = h[i] + abs(x[i]-posY) + abs(y[i]-posX);
	  if ( needH == -1 ) {
	    needH = tmp;
	  }else{
	    if ( needH != tmp ) {
	      needH = -2;
	      break;
	    }
	  }
	}
      }
      if ( needH == -2 ) continue;

      for (  int i = 0; i < N; i++ ) {
	if ( h[i]  == 0 ) {
	  int dist = abs(x[i]-posY) + abs(y[i]-posX);
	  //cout << "dist" << " " << dist << endl;
	  if ( needH > dist ) {
	    needH = -2;
	    break;
	  }
	}
      }
      if( needH == -2 ) continue;

      cout << posY << " " << posX << " " << needH << endl;
      return 0;
    }
  }


  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){

    int a, b, c, d=0;
    cin >> a >> b >> c;

    for(int i=a; i<=b; i++){
    if (c%i==0) d++;
}
    cout << d << endl;

    return 0;
}
    /*男なら チンポで語れよ 安倍晋三*/


Measured memory_bytes: 3096
def iscall(num):
  if num == 2 or num == 4 or num == 5 or num == 7 or num == 9:
    return 'hon'
  elif num == 0 or num == 1 or num == 6 or num == 8:
    return 'pon'
  elif num == 3:
    return 'bon'

N = list(input())

ans = iscall(int(N[-1]))
print(ans)

Measured memory_bytes: 61808
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}

fn main() {
    let n = read::<u64>();
    println!("{}", n*(n-1)/2);
}


Measured memory_bytes: 4352
#include <stdio.h>

int main(void){
  int a,b,i,j;
while(1){
 scanf("%d  %d",&a,&b);
 if(a==0&&b==0) break;
 else{
     for(i=1;i<=a;i++){
           if(i%2!=0){  //?\???°?????????
                      for(j=1;j<=b;j++){
                                          if(j%2!=0)printf("#"); //?\???°???
                                          else printf("."); //??¶??°???  
                                        }  
                      }
           else {  //??¶??°?????????
                      for(j=1;j<=b;j++){
                                          if(j%2!=0)printf("."); //?\???°???
                                          else printf("#"); //??¶??°???  
                                        }
                  }
               printf("\n");
                      }     //for?????¬???
           }//else?????¬???
                printf("\n");
                      }     //while?????¬???
  return 0;
}

Measured memory_bytes: 572
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
struct Data{
  ll a,b,c;
  Data(ll a,ll b,ll c):a(a),b(b),c(c) {}
};
int main(){
  ll d;
  cin>>d;
    d--;
  ll m=d;
  int cnt=0;
  while(d){
    d/=2;
    cnt++;
  }
  ll now=1;
  V<Data> ans;
  if((1<<cnt)-1==m){
  for(int i=0;i<19;i++){
    ans.emplace_back(20-i-1,20-i,0);
   }
   for(int i=0;i<cnt;i++){
       ans.emplace_back(20-i-1,20-i,now);
       now*=2;
   }
 }else{
   for(int i=0;i<19;i++){
    ans.emplace_back(20-i-1,20-i,0);
   }
   for(int i=0;i<cnt-1;i++){
       ans.emplace_back(20-i-1,20-i,now);
       now*=2;
   }
   d=m;
   now=1;
   V<int> t;
   while(d){
     t.push_back(d%2);
     now*=2;
     d/=2;
   }
   now/=2;
   int ind=20;
   reverse(all(t));
    ans.emplace_back(1,ind,now);
   for(int i=1;i<t.size();i++){
     if(t[i]==1){
       ans.emplace_back(1,20-(t.size()-i-1),now+1);
       now+=(1<<(t.size()-i-1));
     }
   }
 }
 cout<<20<<" "<<ans.size()<<"\n";
 for(int i=0;i<ans.size();i++){
  cout<<ans[i].a<<" "<<ans[i].b<<" "<<ans[i].c<<"\n";
 }
}


Measured memory_bytes: 3652
#include <iostream>

using namespace std;

int Fairfield(int y,int m,int d){
  if(m <= 2){
    y--;
    m += 12;
  }
  return 365*y+y/4-y/100+y/400+153*(m+1)/5+d-428;
}

int main(){
  int y1,m1,d1,y2,m2,d2;

  while(true){
    cin >> y1 >> m1 >> d1 >> y2 >> m2 >> d2;

    if(y1 == -1 && m1 == -1 && d1 == -1 && 
       y2 == -1 && m2 == -1 && d2 == -1) break;

    cout << Fairfield(y2,m2,d2) - Fairfield(y1,m1,d1) << endl;
  }

  return 0;
}

Measured memory_bytes: 1156
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,d,e;
    cin>>a>>b>>c>>d>>e;
    if(a==0)
    {
        cout<<1;
    }
    else if(b==0)
    {
        cout<<2;
    }
    else if(c==0)
    {
        cout<<3;
    }
    else if(d==0)
    {
        cout<<4;
    }
    else
    {
        cout<<5;
    }
}


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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define intll int long long
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main() {
  intll n,d ; 
  cin >> n >> d ;
  int ans = 0 ;
  
  rep(i,n){
    intll x,y ;
    cin >> x >> y ;
    intll now = x*x + y*y ;
    if(d*d >=  now ) ans++ ;
  }
  
  cout << ans ;
  
}


Measured memory_bytes: 3652
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include <cassert>
#include <numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int,int> P;

int dp[1<<12+5][1005];

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> o(m,0);
    int a[m];
    rep(i,m){
        int b;
        cin >> a[i] >> b;
        rep(j,b){
            int c;
            cin >> c;
            o[i]+=1<<(c-1);
        }
    }
    rep(i,1<<n)rep(j,m+1){
        dp[i][j]=INF;
    }
    dp[0][0]=0;
    rep(i,1<<n){
        rep(j,m){
            chmin(dp[i][j+1],dp[i][j]);
            chmin(dp[i|o[j]][j+1],dp[i][j]+a[j]);
        }
    }
    if(dp[(1<<n)-1][m]==INF)cout << -1 << endl;
    else cout << dp[(1<<n)-1][m] << endl;
}

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

int main() {
 int N, A ;
  cin >> N >> A ;
  
  for(int i = 0; i < 20; i++){
    if (N >= 500)
      N = N - 500;
    else
      break;
  }
  if(N <= A)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

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

int main(){
  int n;
  vector<int> nums;
  vector<int> b;
  cin >> n;

  for(int i=0;i<n;i++){
    int tmp;
    cin >> tmp;
    if(i%2==1){
      b.push_back(tmp);
    } else {
      b.insert(b.begin(),tmp);
    }
  }
  if(n%2==1){
    for(int i=0;i<n-1;i++)
      cout << b[i] << " ";
    cout << b[n-1] << endl;
  } else {
    for(int i=0;i<n-1;i++)
      cout << b[n-1-i] << " ";
    cout << b[0] << endl;
  }
}


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

const ll mod = 1000000007;
const double eps = 1e-8;

bool used[201010] = {};

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

    used[0] = true;
    if (N % 2 == 0) used[N/2] = true;

    int a = 0, b = 1;
    for (int i=0; i<M; ++i) {
        cout << a + 1 << " " << b + 1 << endl;
        if (i == M-1) break;

        used[(int)abs(a - b)] = true;
        used[N - (int)abs(a - b)] = true;

        a = (a - 1 + N) % N;
        b = (b + 1) % N;
        while (used[(int)abs(a - b)]) {
            b = (b + 1) % N;
        }
    }
    return 0;
}

Measured memory_bytes: 3756
n = int(input())
li = []
for i in range(n):
    li.append(input().split())

a = 0
for i in range(n):
    if li[i][1] == "JPY":
        a += int(li[i][0])
    elif li[i][1] == "BTC":
        a +=float(li[i][0])*380000.0
print(a)

Measured memory_bytes: 3060
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)


function count_red(C, N)
    count = 0
    for i in 1:N
        if C[i] == 'R'
            count += 1
        end
    end
    return count
end



function main()
    N = parseInt(readline())
    C = collect(chomp(readline()))
    idx = 1
    red_count = count_red(C, N)
    #=for i in 0:N - red_count
        if C[N - i] == 'R'
            if C[i + idx] == 'W'
                C[i + idx] = 'R'
                C[N - i] = 'W'
            else
                C[i + ]
                =#

    ans = red_count
    for i in 1:red_count
        if C[i] == 'R'
            ans -= 1
        end
    end
    println(ans)

end


main()

Measured memory_bytes: 163764
from math import sqrt
n = list(map(int, input().split(' ')))
c = 0
for i in range(n[0]):
    x = list(map(int, input().split(' ')))
    s = sqrt(x[0]**2 + x[1]**2)
    if s <= n[1]:
        c +=1
print(c)

Measured memory_bytes: 9196
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;

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

    int s = 0, t[100];
    for (int i = 0; i < n; i++) {
        cin >> t[i];
        s += t[i];
    }

    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int p, x;
        cin >> p >> x;
        p--;
        cout << s - t[p] + x << '\n';
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <bits/stdc++.h>
#include <algorithm>
#include <complex>
#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(7)<<(x)
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

using namespace  std;
using ll = long long;
const ll mod = 1e9 + 7;
typedef pair<ll, ll> pairs;
typedef complex<ll> G;
const int N=2e5+5;

const int INF = 1e9+5;


void done() {


    char p;
    cin >> p;
    if(islower(p)) cout << 'a' << '\n';
    else cout << 'A';

}
void solve() {


}

void another() {

}
int main() {

    done();


}


Measured memory_bytes: 3592
#pragma GCC optimize ("-O3","unroll-loops")
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>


#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<'\n';
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()
//#define double long double

using namespace std;

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

const int MOD = 1e9 + 7;
const ll INF = 1e9;
const double pi = acos(-1);
const double EPS = 1e-10;
typedef pair<int, int>P;
const int MAX = 100020;

struct point { double x, y; };
vector<point>v;
double dist(point p1, point p2) {
	return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
double calc(point p, vector<point>& v,int K) {
	vector<double>d;
	REP(i, v.size()) {
		d.push_back(dist(p, v[i]));
	}
	VSORT(d);
	VREVERSE(d);
	double ans = 0;
	REP(i, K)ans += d[i];
	return ans;
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N, K; cin >> N >> K;
	REP(i, N) {
		double x, y; cin >> x >> y;
		v.push_back({ x,y });
	}
	point p = { 0,0 };
	double step = 10000;
	double ans = 1e17;
	REP(t, 300) {
		step /= 2.0;
		double angle;
		point nex = p;
		REP(i, 2000) {
			double theta = 2 * pi * i / 2000.0;
			point tmp = { p.x + step * cos(theta),p.y + step * sin(theta) };
			double res = calc(tmp, v, K);
			if (ans > res) {
				nex = tmp;
				ans = res;
			}
		}
		p = nex;
	}
	print(ans);
}




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


template <typename t>
inline void print ( const t & v){
    cout << "Printing Container: " << endl;
    for (auto i :v){
        cout << i << " ";
    }
    cout << endl;
}


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

    vector <ll> v;
    while (N--){
        ll no;
        cin >> no;
        v.push_back(no);
    }

    vector <ll> temp = v;
    sort (temp.begin(), temp.end());
    ll Max = temp[temp.size() -1 ];
    ll Lower = temp[temp.size() - 2];


    for ( ll i=0; i<v.size(); i++){
        if ( v[i] == Max){
            cout << Lower << endl;
        }
        else {
            cout << Max << endl;
        }
    }

    return 0;
}



Measured memory_bytes: 4848
import sys
from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())
def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]
def exit():
    import sys
    sys.exit(0)
def perm_sub(li, used):
    if len(li) == len(used):
        return [deque()]
    k = []
    for i in range(len(li)):
        if i in used:
            continue
        used.add(i)
        sub_list = perm_sub(li, used)
        for sub in sub_list:
            sub.appendleft(li[i])
        k.extend(sub_list)
        used.discard(i)
    return k
def perm_li(li):
    return perm_sub(li, set())
def perm_n(n):
    return perm_sub(list(range(n)), set())
def join_i(li, sep=""):
    return sep.join([str(e) for e in li])
def li2n(li):
    n, base = 0, 1
    for i in range(len(li)-1, -1, -1):
        n += li[i] * base
        base *= 10
    return n
def sli2ili(li):
    return [int(s) for s in li] 

cs = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k']


def solve(n, s, mx):
    if len(s) == n:
        return [s]
    result = []
    for co in range(ord('a'), mx+2):
        c = chr(co)
        mx = max(mx, co)
        r = solve(n, s+c, mx)
        result.extend(r)
    return result

r = solve(load(), 'a', ord('a'))

for e in r:
    print(e)

Measured memory_bytes: 13144
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define outy printf("Yes\n")
#define outn printf("No\n")
#define outf printf("First\n")
#define outs printf("Second\n")
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define FORD(a,b,c) for(int a=b;a>=c;a--)
#define FORL(a,b) for(int a=head[b];a;a=nxt[a])
#define in(a)  a=read()
#define in2(a,b)  in(a),in(b)
#define in3(a,b,c)  in2(a,b),in(c)
#define in4(a,b,c,d)  in2(a,b),in2(c,d)
#define out(a) printf("%d\n",a)
#define out2(a,b) printf("%d %d\n",a,b)
#define out3(a,b,c) printf("%d %d %d\n",a,b,c)
#define out4(a,b,c,d) printf("%d %d %d %d\n",a,b,c,d)
#define outl(a) printf("%lld\n",a)
#define outl2(a,b) printf("%lld %lld\n",a,b)
#define outl3(a,b,c) printf("%lld %lld %lld\n",a,b,c)
#define outl4(a,b,c,d) printf("%lld %lld %lld %lld\n",a,b,c,d)
#define clr(x,y) memset(x,y,sizeof(x))
il long long read(){
    char c;long long s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
/*------------------------------------------------------------*/
#define mod 1000000007
#define maxn 200010
#define inf 0x7fffffff
#define ll long long
/*------------------------------------------------------------*/
struct node{int v,id;}a[maxn];
bool cmp1(node a,node b){return a.v<b.v;}
int ans[maxn];
int main(){
	int n;
	in(n);
	FOR(i,1,n)in(a[i].v),a[i].id=i;
	sort(a+1,a+n+1,cmp1);
	FOR(i,1,n){
		if(i<=(n-1)/2+1)ans[a[i].id]=a[(n-1)/2+2].v;
		 else ans[a[i].id]=a[(n-1)/2+1].v;
	}
	FOR(i,1,n)out(ans[i]);
}


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

int main() {
    int d, g, p[10], c[10], ans = 1e9;
    cin >> d >> g;
    rep(i, d) cin >> p[i] >> c[i];
    
    rep(mask, (1 << d)) {
        int sum = 0, num = 0, rest_max = -1;
        rep(i, d) {
            if (mask >> i & 1) {
                sum += 100 * (i+1) * p[i] + c[i];
                num += p[i];
            } else {
                rest_max = i;
            }
        }
        if (sum < g) {
            int Max = 100 * (rest_max + 1);
            int need = (g - sum + Max - 1) / Max;
            if (need >= p[rest_max]) continue;
            num += need;
        }
        ans = min(ans, num);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string.h>
#include<string>
#include<set>
#include<limits.h>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<list>
#include<functional>
#include<stack>
#include<deque>
#include<queue>
using namespace std;

signed main() {
	int n, y; cin >> n >> y;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n - i; j++) {
			if (i * 1000 + j * 5000 + (n - i - j) * 10000 == y) {
				cout << (n - i - j) << " " << j << " " << i << endl;
				return 0;
			}
		}
	}
	puts("-1 -1 -1");
}

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

typedef enum {
  Left = 'L',
  Right = 'R',
  Up = 'U',
  Down = 'D',
} Mode;

class Point {
  public:
    Point() = default;
    Point(int _x, int _y) { x = _x; y = _y; }
    int x;
    int y;
    int manhattan() const { return abs(x) + abs(y); }
};

int ngoal;
vector<Point> goal;
vector<int> arm;

bool has_smaller_manhattan(const Point& a, const Point& b)
{
  return a.manhattan() < b.manhattan();
}

bool is_solvable(const vector<Point>& g)
{
  bool parity = g.at(0).manhattan() % 2 == 0;
  for (int i = 1; i < (int)g.size(); i++) {
    if (parity != (g.at(i).manhattan() % 2 == 0)) {
      return false;
    }
  }
  return true;
}

void print_arm(const vector<int>& a)
{
  cout << a.size() << '\n';
  cout << a.at(0);
  for (int i = 1; i < (int)a.size(); i++) {
    cout << ' ' << a.at(i);
  }
  cout << '\n';
}

int main()
{
  cin >> ngoal;
  goal.resize(ngoal);
  for (int i = 0; i < ngoal; i++) {
    cin >> goal.at(i).x >> goal.at(i).y;
  }
  if (!is_solvable(goal)) {
    cout << "-1" << endl;
    return 0;
  }

  // prepare arm
  int len = max_element(goal.begin(), goal.end(), has_smaller_manhattan)->manhattan();
  if (len % 2 == 0) {
    arm.push_back(1);
  }
  int sumarm = 0;
  int tmparm = 1;
  while (sumarm < len) {
    sumarm = sumarm | tmparm;
    arm.push_back(tmparm);
    tmparm = tmparm << 1;
  }
  sort(arm.rbegin(), arm.rend());
  print_arm(arm);

  // determine modes
  for (auto& g : goal) {
    for (const auto& a : arm) {
      if (abs(g.x) < abs(g.y)) {
        if (0 < g.y) {
          cout << 'U';
          g.y -= a;
        } else {
          cout << 'D';
          g.y += a;
        }
      } else {
        if (0 < g.x) {
          cout << 'R';
          g.x -= a;
        } else {
          cout << 'L';
          g.x += a;
        }
      }
    }
    assert(g.x == 0);
    assert(g.y == 0);
    cout << '\n';
  }

  return 0;
}


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

using namespace std;


const int Nmax = 100005;

int n , a[Nmax] , b[Nmax];

vector < pair < int , int > > L;

int main()
{
    long long s1 , s2;
    cin >> n;
    s1 = s2 = 0;
    for(int i = 1 ; i <= n ; i++)
            cin >> a[i] >> b[i] , L.push_back({a[i] + b[i] , i});
    sort(L.begin() , L.end());
    int j = 0;
    for(int i = n ; i >= 1 ; i--)
        if(i % 2)
            s1 += a[L[j++].second];
    else s2 += b[L[j++].second];
    cout << s1 - s2 << "\n";
    return 0;
}


Measured memory_bytes: 1912
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <string>
#include <string.h>
#include <stack>
#include <queue>
#include <set>
using namespace std;

const int MAX_N=10000;
int n,k,p;

int main(){
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> k >> p;
		cout << (k%p?k%p:p) << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3100
#include "bits/stdc++.h"
#include <set>

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define int long long
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
#define mod 1000000007
#define INF 10e10
template <typename T>

void print(T x)
{
	std::cout << x << " ";
}
template <typename T>

void println(T x)
{
	std::cout << x << "\n";
}

signed main(void) {
	int n;
	cin >> n;
	vector<string>s(n);
	map<char, int>ansmp;
	rep(i, n) {
		cin >> s[i];
	}
	rep(j, s[0].size()) {
		ansmp[s[0][j]]++;
	}
	rep1(i, n) {
		map<char, int>tmpmp;
		rep(j, s[i].size()) {
			tmpmp[s[i][j]]++;
		}
		for (char c = 'a'; c <= 'z'; c++) {
			ansmp[c] = min(ansmp[c], tmpmp[c]);
		}
	}
	string ans;
	for (char c = 'a'; c <= 'z'; c++) {
		rep(i, ansmp[c]) {
			ans += c;
		}
	}
	println(ans);
}

Measured memory_bytes: 3644
#10:35
t = int(input())
import heapq
def tr(score,number):
  try:
    if use[number] > score:
      use[number] = score
      heapq.heappush(now,[score,number])
  except:
    use[number] = score
    heapq.heappush(now,[score,number])
for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  now = [[0,n]]
  ans = n * d
  use = {n:0}
  while True:
    sc,num = heapq.heappop(now)
    ans = min(ans,sc+num*d)
    if use[num] < sc:
      continue
    if num == 1:
      print(ans)
      break
    
    if num % 2 == 0:
      tr(sc+a,num//2)
    else:
      tr(sc+a+d,(num-1)//2)
      tr(sc+a+d,(num+1)//2)
    
    if num % 3 == 0:
      tr(sc+b,num//3)
    elif num % 3 == 1:
      tr(sc+b+d,(num-1)//3)
    else:
      tr(sc+b+d,(num+1)//3)
   
    if num % 5 == 0:
      tr(sc+c,num//5)
    elif num % 5 == 1:
      tr(sc+c+d,(num-1)//5)
    elif num % 5 == 2:
      tr(sc+c+2*d,(num-2)//5)
    elif num % 5 == 3:
      tr(sc+c+2*d,(num+2)//5)
    else:
      tr(sc+c+d,(num+1)//5)

Measured memory_bytes: 83392
h,w=map(int,input().split())
n=int(input())
p=0
k=0
ans=[[0 for i in range(w)]for i in range(h)]
a=list(map(int,input().split()))
for i in range(h*w):
	if a[k]!=0:
		a[k]-=1
		ans[i//w][i-i//w*w]=k+1
	else:
		k+=1
		a[k]-=1
		ans[i//w][i-i//w*w]=k+1
for i in range(h):
	if i%2==0:
		print(*ans[i])
	else:
		print(*ans[i][::-1])




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

int main(int argc, char const *argv[])
{
	int n;
	cin>>n;
	long long a[n],r=1LL,ans[n]={};
	for (int i = 0; i < n; ++i)
	{
		cin>>a[i];
		ans[0]+=r*a[i];
		r*=-1LL;
	}
	cout<<ans[0];
	for (int i = 1; i < n; ++i)
	{
		ans[i]=2*a[i-1]-ans[i-1];
		cout<<" "<<ans[i];
	}
	cout<<endl;
	return 0;
}


Measured memory_bytes: 2816
n = int(input())
H = [int(h) for h in input().split()]
sec= 0
final_max = 0
start = False
for i in range(n-1):
  if H[i] >= H[i+1]:
    if start:
      sec += 1
    else:
      start = True
      sec = 1
  else:
    if start:
      start = False
      final_max = max(sec, final_max)
final_max = max(sec, final_max)
print(final_max)

Measured memory_bytes: 14252
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
ab = [LIST() for _ in range(N-1)]
px = [LIST() for _ in range(Q)]

tree = defaultdict(list)
for a, b in ab:
	tree[a-1].append(b-1)
	tree[b-1].append(a-1)

dic = defaultdict(int)

for p, x in px:
	dic[p-1] += x

ans = [0]*N

checked = [0]*N
checked[0] = 1

q = deque([])
q.append(0)

while q:
	n = q.popleft()
	ans[n] += dic[n]
	for node in tree[n]:
		if checked[node]:
			continue
		ans[node] += ans[n]
		checked[node] = 1
		q.append(node)

print(*ans)


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

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

    if(S.at(K-1)=='A') S.at(K-1) = 'a';
    else if(S.at(K-1)=='B') S.at(K-1) = 'b';
    else if(S.at(K-1)=='C') S.at(K-1) = 'c';

    cout << S << endl;

    return 0;
}

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

using namespace std;

int main()
{
    string s;
    int N;
    cin >> N;
    cin >> s;
    int r = 0, b = 0;
    for (int i = 0; i < N; i++)
    {
        if(s[i] == 'R')
        {
            r++;
        }
        else
        {
            b++;
        }
    }
    cout << (r > b ? "Yes" : "No") << endl; 

    return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> d(n);
    for (int i = 0; i < n; i++) {
        cin >> d.at(i);
    }
    
    sort(d.begin(), d.end());
    
    int ans = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (ans < d.at(i)) {
            ans = d.at(i);
            cnt ++;
        }
    }
    
    cout << cnt << endl;
}

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

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int n = in.nextInt();
		int m = in.nextInt();
		int[][] t = new int[m][10];
		for (int i = 0; i < m; i++) {
			int k = in.nextInt();
			for (int j = 0; j < k; j++)
				t[i][j] = in.nextInt();
		}
		int[] s = new int[m];
		for (int i = 0; i < m; i++)
			s[i] = in.nextInt();
		System.out.println(solve(n, m, t, s));
		in.close();
	}

	private static int solve(int n, int m, int[][] t, int[] s) {
		int r = 0;
		for (int i = 0; i < Math.pow(2, n); i++)
			if (SolveTest(n, m, t, s, i))
				r++;
		return r;
	}

	private static boolean SolveTest(int n, int m, int[][] t, int[] s, int c) {
		for (int i = 0; i < m; i++) {
			int x = 0;
			for (int j = 0; j < n; j++) {
				if (t[i][j] == 0)
					break;
				x += (c >> (t[i][j] - 1)) % 2;
			}
			if (x % 2 != s[i])
				return false;
		}
		return true;
	}

}

Measured memory_bytes: 24916
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define rrep(i,n) for(int (i) = (n) - 1; (i) >= 0; --(i)) //Reversi rep
#define nfor(i,a,b) for(int (i) = (a); (i) < (b); ++(i)) //Natural for
#define rfor(i,a,b) for(int (i) = (b) - 1; (i) >= (a); --(i)) //Reversi for
#define ll long long
#define mod (1000000007)
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define yes cout << "yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;
#define no cout << "no" << endl;

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

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

int main()
{
    int n,k;
    string s;
    cin >> n >> s >> k;
    rep(i, n){
        if (s[i] != s[k - 1]) {
            s[i] = '*';
        }
    }
    cout << s << endl;
    return 0;
}


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

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


int main(){
    fast;
    char ch;
    cin>>ch;
    if(ch>='A' && ch<='Z'){
        cout<<'A'<<endl;
    }
    else{
        cout<<"a"<<endl;
    }
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define fo(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
#define rd read()
#define maxn 200001
#define gc getchar()
#define mem(a,b) memset(a,b,sizeof(a))
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define pb push_back
#define db double
#define pu puts(" ")
using namespace std;
const int p=998244353;
int read()
{
	int x=0,f=1;
	char ch=gc;
	while(!isdigit(ch))
	{
		if(ch=='-')f=-1;
		ch=gc;
	}
	while(isdigit(ch))x=x*10+ch-48,ch=gc;
	return x*f;
}
void print(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10+48);
}
int qp(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=(ll)ans*a%p;
		a=(ll)a*a%p;
		b>>=1;
	}
	return ans;
}
int a[maxn],n,m;
int main()
{
    n=rd,m=rd;
    fo(i,1,m)a[i]=rd;
	sort(a+1,a+m+1);
	printf("%d\n",max(0,a[m]*2-1-n));
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;

int n, m, a[100009], b[100009];

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

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		b[i] = a[i] / 2;
	}
	long long cur = b[0];
	for (int i = 1; i < n; i++) {
		int tmp = gcd(cur, b[i]);
		cur *= b[i];
		cur /= tmp;
		if (cur > m) {
			cout << 0 << E;
			return 0;
		}
	}
	bool flag = false;
	for (int i = 0; i < n; i++) {
		if ((cur / b[i]) % 2 == 0) {
			flag = true;
			break;
		}
	}
	if (flag) {
		cout << 0 << E;
	}
	else {
		cout << (m - cur) / (cur + cur) + 1 << E;
	}
	//system("pause");
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
#define endl "\n"
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
#define all(x) x.begin(), x.end()
#define pb push_back
#define eb emplace_back

using namespace std;
using ll=long long;
// using ll=int;

const ll mod = (ll)(1e9+7);

typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;

int main(){

    /*
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("myoutput.txt", "w", stdout);
    #endif
    */

    fast;
    ll t = 1;
    // cin >> t;
    while(t--){
        ll arr[32] = {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};
        ll k; cin >> k;
        cout << arr[k-1] << endl;
        
    }
    // cerr << (double)clock()/CLOCKS_PER_SEC << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fname "B"
#define ll long long
#define ui unsigned int
#define ull unsigned long long
#define bug(x) cerr << (#x) << " = " << (x) << '\n'
#define REP0(i, n) for(int i = 0, _n = (n); i < _n; ++i)
#define REP1(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define REPB0(i, n) for(int i = (n) - 1; i >= 0; --i)
#define REPB1(i, n) for(int i = (n); i > 0; --i)
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define FORB(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define X first
#define Y second

using namespace std;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef pair<float, float> ff;
typedef pair<double, double> dd;
ll sqr(int x) {return (ll)x*x;}
int pw(int a, int b)
{
	if (!b) return 1;
	else {
		if (b%2 == 0) return sqr(pw(a, b/2));
		return a*(sqr(pw(a, b/2)));
	}
}

int main()
{
	if (fopen(fname".INP", "r")) {
		freopen(fname".INP", "r", stdin);
		freopen(fname".OUT", "w", stdout);
	}
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n, k;
	cin >> n >> k;
	cout << k*pw(k - 1, n - 1);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <cmath>
#include <bits/stdc++.h>
#include <limits>

#define MOD 1000000007

using namespace std;

int main(void){
    // Your code here!
    int a, b, c, d;
    
    cin >> a >> b >> c >> d;
    if((abs(b - a) <= d && abs(c - b) <= d) || abs(a - c) <= d)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<vector>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=4e18;
const ll MOD=998244353;
const double EPS=1e-7;

ll N;
string S;
int main(){
    cin>>N;
    cin>>S;
    if(S.length()%2==0 && S.substr(0,S.length()/2)==S.substr(S.length()/2,S.length()/2)){
        cout<<"Yes";
    }else{
        cout<<"No";
    }
    return 0;
}

Measured memory_bytes: 256
import Data.List
import Text.Printf

card = zip ['S','H','C','D'] [1..]

cmp (a,b) (c,d) =
  let c0 = compare (lookup a card) (lookup c card)
      c1 = compare b d
  in
    if c0 == EQ
    then c1
    else c0

icnv :: [String] -> (Char,Int)
icnv (a:b:_) =
  let a' = a!!0
      b' = read b
  in
    (a', b')

ans :: [(Char,Int)] -> [(Char,Int)] -> [(Char,Int)]
ans [] t = t
ans ii@(i:is) tt@(t:ts)
  | cmp i t == EQ  = ans is ts
  | cmp i t == GT  = t:(ans ii ts)


main = do
  n <- getLine
  let n' = read n :: Int
  c <- getContents
  let i  = map icnv $ map words $ lines c :: [(Char,Int)]
      i' = sortBy cmp i

      t  = sortBy cmp [ (a,b) | a <- ['C','D','H','S'], b <- [1..13] ]
      o  = ans i' t

  mapM_ (\(a,b) -> printf "%c %d\n" a b) o

Measured memory_bytes: 4160
import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int a = scan.nextInt();
        int b = scan.nextInt();

        System.out.println(a / b);
        System.out.println(a % b);
        double f = (double) a / (double) b;
        System.out.printf("%.8f\n", f);
    }
}



Measured memory_bytes: 26484
from itertools import accumulate
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
while K > 0 and not all(a == N for a in A):
    imos = [0] * (N + 1)
    for i, a in enumerate(A):
        imos[max(0, i - a)] += 1
        imos[min(N, i + a + 1)] -= 1
    A = list(accumulate(imos))[:-1]
    K -= 1
print(*A)


Measured memory_bytes: 180124
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <numeric>
#include <queue>
#include <numeric>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <map>
#include <functional>
#include <limits>
#include <set>
#define rep(i,a,b) for((i)=a;i<(int)(b);i++)
#define max(a,b) (a < b ? b : a)
#define min(a,b) (a > b ? b : a)
#define AAA (1000000007)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;




int main() {
	int i, j, k;
	ll N, M, K;

	ll A, B;
	cin >> A >> B >> K;
	if (A > K) {
		A -= K;
		cout << A << " " << B;
		return 0;
	}
	K -= A;
	A = 0;
	if (B > K) {
		B -= K;
		cout << A << " " << B;
		return 0;
	}
	cout << "0 0";

	return 0;
}


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

#define ONLINE_JUDGE
#define ll long long
#define PI 3.14159265359
#define fore(i, l, r) for(int i = int(l); i < int(r); ++i)
#define pb(a) push_back(a)

//////////// Solution /////////////////////////////////

int h[20];

void solve() {
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> h[i];
	}
	int ans = 1;
	int mx = h[0];
	for (int i = 1; i < n; ++i) {
		if (mx <= h[i]) {
			++ans;
			mx = h[i];
		}
	}

	cout << ans << '\n';
}

	/////////// End Solution ///////////////////////////////////////

	//////// Initialization ////////////////////////////////////

int main() {

		#ifndef ONLINE_JUDGE
	FILE *FIN = freopen("/home/danil/prog/input.txt", "r", stdin);
	clock_t time_start = clock();
		#endif

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

	solve();

		#ifndef ONLINE_JUDGE
	fclose(FIN);
	cerr << "\x1b[031m\n-----------------\nTime=" << (ll)((double)(clock()-time_start) / CLOCKS_PER_SEC * 1000) << "ms\n\x1b[0m";
		#endif

	return 0;
}

	//////// End Initialization ///////////////////////////////////////

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

void eratosthenes(int N, int* arr){
  for(int i=0; i < N; i++){
    arr[i] = 1;
  }
  for(int i=2; i < sqrt(N); i++){
    if(arr[i]){
      for(int j=0; i * (j + 2) < N; j++){
        arr[i*(j+2)] = 0;
      }
    }
  }
}

int main(void){
  const int NMAX = 100011;
  const int QMAX = 1000001;
  const int MOD = 1e9+7;
  int dp[NMAX][2]; // dp[idx][自分が素因数(0)か肩(1)か]
  int isprime[QMAX];
  for(int i = 0; i < NMAX; i++) for(int j = 0; j < 2; j++) dp[i][j] = 0;
  eratosthenes(QMAX, isprime);



  int N; cin >> N;
  vector<int> q(N);
  for(int i = 0; i < N; i++) cin >> q[i];
  q.push_back(0);

  if(isprime[q[0]])
    dp[0][0] = 1;

  for(int i = 0; i < N-1; i++){
    for(int j = 0; j < 2; j++){
      if(j == 0){
        dp[i+1][1] = (dp[i+1][1] + dp[i][j]) % MOD;
        if(q[i+1] > q[i] && isprime[q[i+1]]){
          dp[i+1][0] = (dp[i+1][0] + dp[i][j]) % MOD;
        }
      }else{
        if((i == 0 || q[i+1] > q[i-1]) && isprime[q[i+1]]){
          dp[i+1][0] = (dp[i+1][0] + dp[i][j]) % MOD;
        }
      }
    }
  }
  cout << (dp[N-1][0] + dp[N-1][1]) % MOD << endl;
  return 0;
}



Measured memory_bytes: 8420
using System;
class p
{
  static void Main()
  {
    int N = int.Parse(Console.ReadLine());
    string[] input = Console.ReadLine().Split(' ');
    int D = int.Parse(input[0]);
    int X = int.Parse(input[1]);
    
    int count = X;
    for (int i = 0; i < N; i++) {
      int c = 0;
      int n = int.Parse(Console.ReadLine());
      for (int j = 0; ; j++) {
        int d = n * j + 1;
        if (d <= D) { c++; }
        else { break; }
      }
      count += c;
    }
    Console.WriteLine(count);
  }
}

Measured memory_bytes: 11092
N, K = map(int, input().split())
p = list(map(int, input().split()))

m = [(e + 1) / 2 for e in p]

t = sum(m[0:K])
result = t
for i in range(N - K):
    t -= m[i]
    t += m[i + K]
    if t > result:
        result = t
print(result)


Measured memory_bytes: 25060
'use strict';

var fs = require('fs'),
    length = fs.fstatSync(process.stdin.fd).size,
    buffer = new Buffer(length),
    bytesRead = fs.readSync(process.stdin.fd, buffer, 0, length, 0),
    input = buffer.toString('utf8', 0, bytesRead).split('\n');
main();
function main() {
  var i = Number(input[0]);
  console.log(Math.pow(i, 3));
}


Measured memory_bytes: 17492