akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define quick                    \
    ios::sync_with_stdio(false); \
    cin.tie(0);
#define time cerr << (0.1 * clock()) / CLOCKS_PER_SEC << endl;
#define mod 1000000007
typedef long long ll;
typedef pair<ll, ll> pl;
#define forn(n) for (ll i = 0; i < ll(n); i++)

// Inverse Modular Multiplicative
ll inverseModular(ll num, ll m) {
    ll x0 = 1, y0 = 0, x1 = 0, y1 = 1;
    ll x = m, y = num;
    while (y != 1) {
        ll buffx0 = x1, buffy0 = y1;
        ll div = x / y;
        x1 = x0 - (div * x1);
        y1 = y0 - (div * y1);
        x0 = buffx0;
        y0 = buffy0;
        div = y;
        y = x % y;
        x = div;
        if (y == 0) {
            cout << "The numbers are not co-prime" << endl;
            return 0;
        }
    }
    if (y1 < 0) {
        y1 += m;
    }
    return y1;
}

// Algo for modularExponentiation
ll modularExponentiation(ll a, ll n) {
    ll ans = 1;
    a %= mod;
    while (n) {
        if (n % 2) {
            ans = (ans * a) % mod;
        }
        a = (a * a) % mod;
        n /= 2;
    }
    return ans;
}

// Function to return gcd of a and b
ll gcd(ll a, ll b) {
    if (a == 0) return b;
    return gcd(b % a, a);
}

// Pre Compute Factorial%mod
vector<ll> preComputeFact() {
    vector<ll> fact;
    fact.pb(1);
    fact.pb(1);
    forn(2000005) { fact.pb((fact[i + 1] * (i + 2)) % mod); }
    return fact;
}

// Pre Compute Inverse Factorial%mod
vector<ll> preComputeFactInverse(vector<ll>& fact) {
    vector<ll> invFact(2);
    invFact[0] = 1;
    invFact[1] = 1;
    forn(2000005) {
        invFact.pb((invFact[i + 1] * inverseModular(i + 2, mod)) % mod);
    }
    return invFact;
}

ll nCr(ll n, ll r, vector<ll>& fact, vector<ll>& invfact) {
    ll temp = (fact[n] * invfact[r]) % mod;
    temp = (temp * invfact[n - r]) % mod;
    return temp;
}

void solve() {
    auto fact = preComputeFact();
    auto inv = preComputeFactInverse(fact);
    ll n, m;
    cin >> n >> m;
    ll ans = fact[m];
    ans = (ans * inv[m - n]) % mod;
    for (ll i = 1; i <= n; ++i) {
        ll temp = nCr(n, i, fact, inv);
        temp = (temp * fact[m - i]) % mod;
        temp = (temp * inv[m - n]) % mod;
        if (i & 1) {
            ans = (ans - temp + mod) % mod;
        } else {
            ans = (ans + temp) % mod;
        }
    }
    ans = (ans * fact[m]) % mod;
    ans = (ans * inv[m - n]) % mod;
    cout << ans << '\n';
}

int main() {
    quick;
    solve();
    // ll t;
    // cin >> t;
    // while (t--) {
    //     solve();
    // }
}

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

using namespace std;

int main(){
  vector<int> a(5);
  int sum=0;
  for(int i=0;i<5;i++){
    cin >> a[i];
    sum+=a[i];
    if(a[i]%10==0){
      a[i]=10;
    }
    else{
      a[i]%=10;
    }
  }
  sort(a.rbegin(),a.rend());
  for(int i=0;i<4;i++){
    if(a[i]!=10){
      sum+=10-a[i];
    }
  }
  cout << sum << endl;
}


Measured memory_bytes: 256
#!/usr/bin/python3
# -*- coding:utf-8 -*-
import numpy

def main():
  n, k = map(int, input().strip().split())
  Ps   = numpy.array(input().strip().split(), dtype=int)
  Es   = numpy.zeros(n+1)
  max = -1
  for i, P in enumerate(Ps):
    Es[i] = 0.5 * (P+1) + Es[i-1]
  max = -1
  for i in range(n-k+1):
    x = Es[i+k-1] - Es[i-1]
    if max < x:
      max = x
  print(max)

if __name__=='__main__':
  main()

Measured memory_bytes: 32012
###############################################################
#ダイクストラ法
#計算量O(logV*(V+E)) （V=頂点の個数 E=辺の個数）
#辺の重みが負である場合には使えない
n,x,y=map(int,input().split())
graph={i:{} for i in range(1,n+1)}


#graphの隣接行列表示
for i in range(1,n):
    graph[i][i+1]=1
    graph[i+1][i]=1
    
graph[x][y]=1
graph[y][x]=1

#graph表示完成
import heapq
def dijkstra(s,graph,n):
    #ｓからのグラフの最短最短距離をまとめたデータを返す
    dist=[10**20 for i in range(n+1)]
    dist[s]=0
    pq=[]
    heapq.heapify(pq)
    #全ての接点を一度優先度付きキューに挿入する
    heapq.heappush(pq,(0,s))
    while pq:
        x=heapq.heappop(pq)
        node,mini_dis=x[1],x[0]
        for point in graph[node].keys():
            w=graph[node][point]
            #nodeからpointに対して伸びる辺の長さ
            newlen=dist[node]+w
            if newlen<dist[point]:
                heapq.heappush(pq,(newlen,point))
                dist[point]=newlen

    return dist

ans_dis=[0 for i in range(n)]

for i in range(1,n+1):
    sub=dijkstra(i,graph,n)
    for j in range(1,n+1):
        dis=sub[j]
        ans_dis[dis]+=1

for i in range(1,n):
    print(ans_dis[i]//2)
        




Measured memory_bytes: 87260
using System;using System.Linq;

class A {
	static void Main() {
		var n = Console.ReadLine();
		var N = n.Count((a) => a == 'N');
		var W = n.Count((a) => a == 'W');
		var S = n.Count((a) => a == 'S');
		var E = n.Count((a) => a == 'E');
		if(((N == 0 && S == 0) || (N >= 1 && S >= 1)) && ((W == 0 && E == 0) || (W >= 1 && E >= 1))) {
			Console.WriteLine("Yes");
		} else {
			Console.WriteLine("No");
		}
	}
}

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

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, k;
	cin >> n >> k;
	vector<int> p(n);
	for(int i = 0; i < n; i++) cin >> p[i];
	vector<bool> ok(n-k, true);
	set<int> z;
	for(int i = 0; i < k; i++) z.insert(-p[i]);
	for(int i = k; i < n; i++){
		z.insert(-p[i]);
		if(*z.begin() != -p[i]) ok[i-k] = false;
		z.erase(-p[i-k]);
	}
	z.clear();
	for(int i = 0; i < k; i++) z.insert(p[n-1-i]);
	for(int i = k; i < n; i++){
		z.insert(p[n-1-i]);
		if(*z.begin() != p[n-1-i]) ok[n-i-1] = false;
		z.erase(p[n-1-i+k]);
	}
	vector<bool> nothing(n-k+1, false);
	bool has_nothing = false;
	int last = 0;
	for(int i = 1; i < n; i++){
		if(p[i] < p[i-1]){
			last = i;
		}
		if(i >= k-1){
			if(last <= i-(k-1)){
				nothing[i-(k-1)] = true;
				has_nothing = true;
			}
		}
	}
	int ans = 0;
	if(!nothing[0]) ans++;
	if(has_nothing) ans++;
	for(int i = 0; i < n-k; i++){
		if(!nothing[i+1] && !ok[i]){
			ans++;
		}
	}
	cout << ans << '\n';
}

Measured memory_bytes: 10368
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<complex>
#include<cfloat>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define EPS (1e-10)
using namespace std;

typedef unsigned int uint;
typedef long long ll;

int encode(char *buff, int &len){
  int ret = 0;
  len = 0;
  while(true){
    if(*buff == 'r'){
      ret <<= 2;
      ret += 0;
    }else if(*buff == 'g'){
      ret <<= 2;
      ret += 1;
    }else if(*buff == 'b'){
      ret <<= 2;
      ret += 2;
    }else{
      return ret;
    }
    buff++;
    len++;
  }
  return ret;
}

void print(int now, int len){
  REP(i,len){
    int t = (now >> (2 * i)) & ((1<<2) - 1);
    if(t == 0) putchar('r');
    if(t == 1) putchar('g');
    if(t == 2) putchar('b');
  }
  puts("");
}

int main(){
  char buff[64];
  int change[1<<6];

  memset(change, -1, sizeof(change));
  REP(i,3) REP(j,3) REP(k,3)
    if(i != j && j != k && i != k)
      change[i | (j << 2)] = (k | (k << 2));

  while(fgets(buff,sizeof(buff),stdin), *buff != '0'){
    int len;
    int now = encode(buff,len);

    int ans[3];
    REP(i,3){
      int tmp = 0;
      REP(j,len){
	tmp <<= 2;
	tmp += i;
      }
      ans[i] = tmp;
    }

    

    set<int> s;
    queue<int> q;
    int n = 0;
    q.push(now);
    q.push(-1);
    s.insert(now);

    while(true){
      now = q.front();

      bool f = false;
      REP(i,3){
	if(ans[i] == now){
	  printf("%d\n",n);
	  f = true;
	  break;
	}
      }
      if(f) break;

      q.pop();
      
      if(q.empty()){
	puts("NA");
	break;
      }

      if(now == -1){
	n++;
	q.push(-1);
	continue;
      }

      //printf("now: "); print(now,len);

      REP(i,len-1){
	int cc   = (now >> (i * 2)) & ((1<<4) - 1);

	if(change[cc] != -1){
	  int next = now & ~(((1<<4)-1) << (i * 2));
	  next |= (change[cc] << (i * 2));
	  //print(next, len);
	  if(s.find(next) == s.end()){
	    s.insert(next);
	    q.push(next);
	  }
	}
      }
    }

  }
  return 0;
}

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

using namespace std;

#define endl "\n"
typedef long long int lli;

#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
lli w[110], v[110];

lli memo[110][100010];
lli dp(int pos, lli weight){
	if(memo[pos][weight] != -1)
		return memo[pos][weight];

	if(pos == 0 || weight == 0)
		return 0;

	if(w[pos] > weight)
		return memo[pos][weight] = dp(pos-1, weight);
	return memo[pos][weight] = max(dp(pos-1, weight), v[pos]+dp(pos-1,weight-w[pos]));
}

int main(){
	int N,W; cin >> N >> W;
	w[0] = v[0] = 0;
	for(int i=1; i<=N; i++)
		cin >> w[i] >> v[i];

	memset(memo, -1, sizeof(memo));
	cout << dp(N, W) << endl;

	return 0;
}



Measured memory_bytes: 86144
#include <iostream>
#include <string>
#include <queue>
#include <set>

char change (char c1, char c2);
bool simple_check(std::string str); 
void bfs(std::string str); 


int main(void) {
    std::string str; 

    std::cin >> str;
    while (str != "0") {
        bfs(str); 
        std::cin >> str;
    }

    return 0;
}

char change (char c1, char c2) {
    char new_c;
    if (c1 != 'r' && c2 != 'r') {
        new_c = 'r'; 
    } else if (c1 != 'g' && c2 != 'g') {
        new_c = 'g'; 
    } else if (c1 != 'b' && c2 != 'b') {
        new_c = 'b'; 
    } else {
        std::cerr << "????????????" << std::endl;
    }
    return new_c;
}

bool simple_check(std::string str) {
    bool flag = true;
    for (int i = 0; i < str.size() - 1; i++) {
        if (str[i] != str[i + 1]) {
            flag = false;
        }
    }
    return flag;
}

void bfs(std::string str) {
    std::pair<std::string, int> now;
    std::queue<std::pair<std::string, int> > que; 
    std::set<std::string> st; 

    //use in while loop
    std::string str_cp;
    char remained_color;

    que.push(std::make_pair(str, 0));
    st.insert(str);


    while (! que.empty()) {
        now = que.front();
        que.pop();

        // ??¨?????????????????????break?????????
        if (simple_check(now.first) == true) {
            std::cout << now.second << std::endl; 
            return;
        }


        for (int i = 0; i < str.size() - 1; i++) {
            str_cp = now.first;
            if (str_cp[i] != str_cp[i + 1]) {
                remained_color = change(str_cp[i], str_cp[i + 1]);
                str_cp[i] = remained_color;
                str_cp[i + 1] = remained_color;
            }
            if (st.count(str_cp) == 0) {
                que.push(std::make_pair(str_cp,now.second + 1)); 
                st.insert(str_cp);
            }
        }
    }

    std::cout << "NA" << std::endl;
    return; 
}

Measured memory_bytes: 4584
A, B, C, K = map(int, input().split())

ans = 0
if K >= A:
    ans += A
    K -= A
else:
    ans += K
    K = 0

if K > 0 and B > 0:
    if K >= B:
        K -= B
    else:
        K = 0

if K > 0 and C > 0:
    if K >= C:
        K -= C
        ans -= C
    else:
        ans -= K
        K = 0

print(ans)

Measured memory_bytes: 9112
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define umii            unordered_map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define rep(i,st,end)   for(int i=st;i<end;i++)
#define w(x)            int x; cin>>x; while(x--)
//mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

void s_g_c()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int32_t main()
{
	s_g_c();
	int n, x, t;
	cin >> n >> x >> t;
	int ans = n / x;
	if (n % x != 0)
		ans++;
	cout << ans*t << endl;
	return 0;
}

Measured memory_bytes: 3600
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
using namespace std;

#define ll long long
#define INF (1 << 30)
#define INFLL (1LL << 60)

#define FOR(i,a,b) for(ll i = (a);i<(b);i++)
#define REP(i,a) FOR(i,0,(a))
#define MP make_pair

int main() {
	char a, b;
	cin >> a >> b;
	if(a == 'D'){
		if(b == 'H') cout << "D" << endl;
		else cout << "H" << endl;
	}else{
		cout << b << endl;
	}
	return 0;
}

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

#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)


using namespace std;
using ll = long long;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<double> vote(n);
    double sum = 0;
    for (auto &a:vote) {
        cin >> a;
        sum += a;
    }

    int ans = 0;
    for (auto &a:vote) {
        if (a / sum >= 1.0 / (4.0 * m)) {
            ans++;
        }
    }

    cout << (ans >= m ? "Yes" : "No") << endl;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);

    solve();
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();
        StringBuilder sb1 = new StringBuilder();
        for(int i = 0; i < W; i++){
            if(i < A){
                sb1.append("1");
            }else{
                sb1.append("0");
            }
        }
        String baseStr = sb1.toString();
        for(int i = 0; i < B; i++){
            System.out.println(baseStr);
        }
        StringBuilder sb2 = new StringBuilder();
        for(int i = 0; i < W; i++){
            if(A <= i){
                sb2.append("1");
            }else{
                sb2.append("0");
            }
        }
        String baseStr2 = sb2.toString();
        for(int i = B; i < H; i++){
            System.out.println(sb2.toString());
        }
    }
}


Measured memory_bytes: 25684
import itertools

def solve():
    N = int(input())
    P = tuple(map(int, input().split()))
    Q = tuple(map(int, input().split()))

    permutations = list(itertools.permutations(range(1,N+1)))
    p = permutations.index(P)
    q = permutations.index(Q)
    return abs(p-q)

print(solve())

Measured memory_bytes: 8052
include Math
X = gets.to_i

# $count = 0
#
# def move(x, y, count)
#   theta = (PI / 2) + X * ( PI / 180 ) * $count
#   complex = Complex(1 - x, 0 - y) * Complex(cos(theta).to_c,sin(theta)to_c) + Complex(x, y)
#   p complex
#   x = complex.real
#   y = complex.imag
#   return $count if x.to_i == 0 && y.to_i == 0
#   $count += 1
#   move(x, y, $count)
# end
#
# move(0, 0, $count)
# p $count
#
# #
# # theta = (PI / 2) + X * ( PI / 180 ) * $count
# # x = (1-x) * cos(theta) + (y * sin(theta)) + x
# # p x.to_i
# # y = (1-x) * sin(theta) - y * cos(theta) + y

result = 0
for i in 1..Float::INFINITY
  break result = i if i * X % 360 == 0
end
puts result


Measured memory_bytes: 14352
#include<stdio.h>
static const int N = 100;
int min(int a, int b){ return a < b ? a : b; }
int main(){
  int i, j, k, l;
  int n, p[N+1], m[N+1][N+1];
  scanf("%d", &n);
  for ( i = 1; i <= n; i++ ){
    scanf("%d %d", &p[i-1], &p[i]);
  }
  for ( i = 1; i <= n; i++ ) m[i][i] = 0;
  for ( l = 2; l <= n; l++ ){
    for ( i = 0; i <= n-l+1; i++ ){
      j = i+l-1;
      m[i][j] = (1<<21);
      for ( k = i; k <= j-1; k++ ){
        m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]);       
      }
    }
  }
  printf("%d\n", m[1][n]);
  return 0;
}



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

using namespace std;
typedef long long ll;

ll gcd(ll a,ll b){
    return b ? gcd(b, a % b) : a;
}

int main() {
    ll n, k;
    cin >> n >> k;
    ll x,y,m;
    cin >> x;
    m = x;
    for(int i = 0; i < n - 1; i++) {
        cin >> y;
        m = max(m, y);
        x = gcd(x, y);
    }
    if(k%x==0 && m>=k){
        cout << "POSSIBLE" << endl;
    }else {
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

    int H = scanner.nextInt();
    int W = scanner.nextInt();
    int K = scanner.nextInt();
    char[][] S = new char[H][W];
    for (int i = 0; i < H; i++) {
      S[i] = scanner.next().toCharArray();
    }
    int[][] cumsum = new int[H + 1][W + 1];
    for (int i = 1; i <= H; i++) {
      for (int j = 1; j <= W; j++) {
        cumsum[i][j] = cumsum[i][j - 1];
        if (S[i - 1][j - 1] == '1') cumsum[i][j]++;
      }
    }
    for (int j = 1; j <= W; j++) {
      for (int i = 1; i <= H; i++) {
        cumsum[i][j] += cumsum[i - 1][j];
      }
    }

    int min = 1_000_000;
    for (int i = 0; i < 1 << (H - 1); i++) {
      int num = i;
      int count = Integer.bitCount(num);

      int[][] csum = new int[count + 1][W + 1];
      int j = 0;
      int top = 1;
      int bottom = 1;
      while (num > 0) {
        while (num % 2 == 0) {
          num /= 2;
          bottom++;
        }
        for (int k = 1; k <= W; k++) {
          csum[j][k] = cumsum[bottom][k] - cumsum[top - 1][k];
        }
        j++;
        bottom++;
        top = bottom;
        num /= 2;
      }
      for (int k = 1; k <= W; k++) {
        csum[j][k] = cumsum[H][k] - cumsum[top - 1][k];
      }

      int max = foo(csum, count + 1, W + 1, K);
      min = Math.min(min, count + max);
    }
    System.out.println(min);
  }

  private static int foo(int[][] csum, int H, int W, int K) {
    for (int i = 0; i < H; i++) {
      for (int j = 1; j < W; j++) {
        if (csum[i][j] - csum[i][j - 1] > K) return 1_000_000;
      }
    }
    int num = 0;
    int left = 0;
    for (int i = 0; i < W; i++) {
      int max = 0;
      for (int j = 0; j < H; j++) {
        max = Math.max(max, csum[j][i] - csum[j][left]);
      }
      if (max > K) {
        num++;
        left = i - 1;
      }
    }
    return num;
  }
}


Measured memory_bytes: 35964
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	int a;
	string s;
	cin >> a >> s;
	if (a >= 3200) {
		cout << s << endl;
		return 0;
	}
	else {
		cout << "red" << endl;
		return 0;
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=2e5+5;
LL a[maxn]; LL b[maxn];
int main(void)
{
	int n; scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i],&b[i]);
	sort(a+1,a+1+n); sort(b+1,b+1+n);
	LL res;
	if(n&1)
	{
		res=(b[(n+1)/2]-a[(n+1)/2])+1;
	}
	else
	{
		res=(b[n/2]-a[n/2])+(b[n/2+1]-a[n/2+1]);
		res=res+1; 
	}
	printf("%lld\n",res);
	return 0;
}

Measured memory_bytes: 6808
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
using namespace std;
 
int main()
{
    string str;
    cin >> str;
    if(str[2]==str[3] && str[4]==str[5]){
        cout<<"Yes";
    }else{
        cout<<"No";
    }
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){

  int n;
  int i;
  double result = 0.0, a;

  scanf("%d", &n);

  for (i = 0; i < n; i++){
    scanf("%lf", &a);
    a = 1 / a;
    result += a;
  }
  result = 1 / result;

  printf("%f\n", result);

  return 0;
}

Measured memory_bytes: 128
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    a, b = list(map(int, input().rstrip('\n').split()))
    cnt = 0
    t = 1
    while t < b:
        cnt += 1
        t += (a - 1)
    print(cnt)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 38256
import fractions
from functools import reduce

N,M = map(int,input().split())
A = list(set((map(lambda x : int(x) // 2,input().split()))))

def lcm(a,b):
  return (a * b) // fractions.gcd(a, b)
def gcd_list(numbers):
  return reduce(fractions.gcd, numbers)
def lcm_list(numbers):
  return reduce(lcm, numbers, 1)

LCM = lcm_list(A)
ans = (M // LCM + 1) // 2

for a in A[1:]:
  if (LCM // a) % 2 == 0:
    ans = 0
    break
    
print(ans)

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

int main(){
  string S;
  cin >> S;
  int N=S.size(),ans=0;
  S = S + "E";
  for(int i=0;i<N;i++){
    if(S[i] != S[i+1]){
      ans ++;
    }
  }
  cout << ans-1 << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include<algorithm>
#include<string>
#include<vector>
#include <math.h>
#include <iomanip>

using namespace std;

int main()
{
	string s1,s2,s3;
	cin >> s1 >> s2 >> s3;
	cout << s1[0] << s2[1] << s3[2] << endl;
}

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

int main(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if(a == 1 || b == 1 || c == 1 || d == 1){
        if(a == 4 || b == 4 || c == 4 || d == 4){
            if(a == 7 || b == 7 || c == 7 || d == 7){
                if(a == 9 || b == 9 || c == 9 || d == 9){
                    cout << "YES" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


ans = 0
divisors = make_divisors(N)

for d in divisors:
    m = (d - 1)
    if m and (N//m == N % m):
        ans += m

print(ans)


Measured memory_bytes: 39024
#include <cstdio>

using namespace std;

int a[1 << 10][1 << 10];
int ans[1 << 10][1 << 10];

int main() {
    int n, m, i, j, k;
    
    scanf("%d %d", &n, &m);
    
    a[1][1] = 1;
    
    for (i = 1; i < 10; i++) {
        int c = (1 << i);
        for (j = 0; j < c; j++) {
            for (k = 0; k < c; k++) {
                a[j + c][k] = a[j][k];
                a[j][k + c] = a[j][k];
                a[j + c][k + c] = 1 - a[j][k];
            }
        }
    }
    
    for (i = 0; i < (1 << n); i++) {
        int p = 0;
        for (j = 0; j < (1 << m); j++) {
            if (i == 0 || j == 0) {
                ans[i][j] = a[i][j];
            } else {
                ans[i][j] = (a[i - 1][j] ^ p ^ a[i][j]);
                p ^= ans[i][j];
            }
        }
    }
    
    for (i = 1; i < (1 << n); i++) {
        for (j = 1; j < (1 << m); j++) {
            printf("%d", ans[i][j]);
        }
        puts("");
    }
    
    return 0;
}


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

const int maxe = 2e5+5;

ll t=1, n, x, k;
int arr[maxe];
void solve(){
	cin >> n;
	ll maxval = 0;
	ll ans = 0;
	for(int i=0; i<n; i++){
		cin >> x;
		if(x < maxval) ans += maxval-x;
		else maxval = max(x, maxval);
	}
	cout << ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	while(t--){
		solve();
	}
    return 0;
}


Measured memory_bytes: 3572
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        N: i32,
        M: i32,
        A: [i32; M],
    }
    let sum: i32 = A.iter().sum();
    let ans = if N - sum >= 0 { N - sum } else { -1 };
    println!("{}", ans);
}


Measured memory_bytes: 2240
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;

const int MAX = 200000;
const int X = 64;

int main(){
    unsigned long long N,K;
    int A[MAX][X];

    cin >> N >> K;
    for(int i = 0;i < N;i++){
        cin >> A[i][0];
        A[i][0]--;
    }

    for(int i = 1;i < X;i++){
        for(int j = 0;j < N;j++){
            A[j][i] = A[A[j][i - 1]][i - 1];
        }
    }

    int ans = 0;
    int cnt = X - 1;

    while(K){
        while(K >= (1ULL << cnt)){
            ans = A[ans][cnt];
            K -= (1ULL << cnt);
        }
        cnt--;
    }

    cout << ans + 1 << endl;

    return 0;
}

Measured memory_bytes: 53084
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func oneInt() int {
	var a int
	fmt.Scan(&a)
	return a
}
func oneStr() string {
	var a string
	fmt.Scan(&a)
	return a
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func scanNums() (nums []int) {
	s := nextLine()
	numStr := strings.Split(s, " ")

	for _, n := range numStr {
		i, _ := strconv.Atoi(n)
		nums = append(nums, i)
	}
	return nums
}

func scanStrings() (strs []string) {
	s := nextLine()
	list := strings.Split(s, " ")
	strs = append(strs, list...)
	return strs
}

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

func pow(p, q int) int {
	return int(math.Pow(float64(p), float64(q)))
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func strSearch(a []string, b string) bool {
	for i := 0; i < len(a); i++ {
		if a[i] == b {
			return true
		}
	}
	return false
}

func sortAsc(a []int) []int {
	sort.Ints(a)
	return a
}

func sortDesc(a []int) []int {
	sort.Sort(sort.Reverse(sort.IntSlice(a)))
	return a
}

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

func lcm(a, b int) int {
	if a == 0 && b == 0 {
		return 0
	}
	return a * b / gcd(a, b)
}

func permutation(n int, k int) int {
	v := 1
	if 0 < k && k <= n {
		for i := 0; i < k; i++ {
			v *= (n - i)
		}
	} else if k > n {
		v = 0
	}
	return v
}

func factorial(n int) int {
	return permutation(n, n-1)
}

func combination(n int, k int) int {
	return permutation(n, k) / factorial(k)
}

func homogeneous(n int, k int) int {
	return combination(n+k-1, k)
}



func main() {
	N := oneInt()
	var as []int
	for index := 0; index < N; index++ {
		as = append(as, oneInt())
	}
	var asc []int
	asc =append(asc, as...)
  maxValue := max(as...)
	sortedAs := sortDesc(as)

	var isMulti bool
	var secondBig int
	if sortedAs[1] == maxValue {
		isMulti = true
	} else {
		isMulti = false
		secondBig = sortedAs[1]
	}

	for index := 0; index < N-1; index++ {

		if asc[index] == maxValue {
			if isMulti {
				fmt.Println(maxValue)
			} else {
				fmt.Println(secondBig)
			}
		} else {
			fmt.Println(maxValue)
		}
	}

	if asc[N-1] == maxValue {
		if isMulti {
			fmt.Print(maxValue)
		} else {
			fmt.Print(secondBig)
		}
	} else {
		fmt.Print(maxValue)
	}

}


Measured memory_bytes: 8832
n, m = map(int,input().split())
h = list(map(int, input().split()))
ab = [list(map(int,input().split())) for i in range(m)]

flag = [1]*n

for i in ab:
  if h[i[0]-1] > h[i[1]-1]:
    flag[i[1]-1] = 0
  elif h[i[0]-1] < h[i[1]-1]:
    flag[i[0]-1] = 0
  else:
    flag[i[1]-1] = 0
    flag[i[0]-1] = 0

print(flag.count(1))

Measured memory_bytes: 31884
#include <bits/stdc++.h>
//#include "Header.h"

#define pi 3.14159265358979323846264

#define ll long long
#define fori(n) for(long long i=0;i<n;i++)
#define forj(n) for(long long j=0;j<n;j++)

#define sp(n) setprecision(n)
#define d7 1000000007
#define mkp make_pair
#define mkt make_tuple

using namespace std;

bool isPrime(long long k){
    if(k<=1){return false;}
    if(k==2){return true;}
    if(k%2==0){return false;}
    long long i = 3;
   while (i*i <= k) {if (k % i == 0) {return false;}i += 2;}
return true;
}

ll binomialCoeff(ll n, ll k){
    ll C[n + 1][k + 1];ll i, j;
    for (i = 0; i <= n; i++){
        for (j = 0; j <= min(i, k); j++)
        {if (j == 0 || j == i) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]);}}
    return C[n][k];
 }

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

ll srihrg(ll n,ll k,ll m){
    ll ans;
    ans=1;
    fori(k){
        ans=(ans*n)%m;
    }
    return ans;
}

ll kk=1;
void dfsi(vector<bool> &vis, vector<ll> adj1[], ll n, ll start, vector<ll> &pre, vector<ll> &pos){
    vis[start]=true;
    pre[start]=kk;kk++;
    for(ll i: adj1[start]){
        if(!vis[i]){
            vis[i]=true;
            dfsi(vis,adj1,n,i,pre,pos);
        }
    }
    pos[start]=kk;kk++;
}

void bfsi(vector<ll> &dis, vector<ll> adj[], ll s, vector<ll> &parent){
    dis[s]=-1;
    queue<ll> q;
    q.push(s);
    while(!q.empty()){
        ll z=q.front();
        q.pop();
        for(ll v:adj[z]){
            if(dis[v]==0){
            q.push(v);
            dis[v]=-dis[z];
                parent[v]=z;}
        }
    }
}

void make_set(ll v, vector<ll> &parent, vector<ll> &krank) {
    parent[v] = v;
    krank[v] = 0;
}

ll find_set(ll v,vector<ll> &parent, vector<ll> &krank) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v], parent, krank);
}

void union_sets(ll a, ll b,vector<ll> &parent, vector<ll> &krank) {
    a = find_set(a,parent,krank);
    b = find_set(b,parent,krank);
    if (a != b) {
        if (krank[a] < krank[b])
            swap(a, b);
        parent[b] = a;
        if (krank[a] == krank[b])
            krank[a]++;
    }
}

void dijkstra(ll s, vector<ll> &dist, vector<ll> &parent, ll n, vector<pair<ll,ll>> adj[]){
    dist[s]=0;
    vector<bool> u(n,false);
    fori(n){
        ll v=-1;
        forj(n){
            if(!u[j] &&(v==-1||(dist[j]<dist[v]))) v=j;
        }
        if(dist[v]==d7) break;
        u[v]=true;
        for(auto j:adj[v]){
            ll a,b;
            a=j.first;
            b=j.second;
            if(dist[v]+b<dist[a]){
                dist[a]=dist[v]+b;
                parent[a]=v;
            }
        }
    }
}


int main(int argc, const char * argv[]) {
 //cout<<"Om\n";
 //Praise to Lord
 //make cin/cout faster
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
// code now
   
    ll n;
    ll k;
    cin>>n>>k;
    if(n%k==0){cout<<n/k;}
    else{
        cout<<n/k+1;
    }
    
//code ends
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(){
  int n;
  cin >> n;
  int cnt = 0;
  for(int i=0;i<n;i++){
    int l,r;
    cin >> l >> r;
    cnt += r-l+1;
  }

  cout << cnt << endl;
}


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

int main(){
	int a,b,i;
	cin>>a>>b;
	
	for(i=1;i<=1500;i++){
		if(floor(i*0.08)==a && floor(i*0.1)==b){
			cout<<i<<endl;
			return 0;	
		}
	}
	
	cout<<-1<<endl;
	return 0;
} 

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  int numNum;
  int a[200];
  int i;
  int guCount = 0;
  int wariCount = 0;
  
  scanf("%d\n",&numNum);
  for(i=0;i<numNum;i++){
   scanf("%d ",&a[i]);
  }
  
  while(1){
    for(i=0;i<numNum;i++){
      if(a[i]%2 == 0){
        guCount += 1; 
      }
      a[i] = a[i]/2;
    }
    if(guCount == numNum){
      wariCount += 1;
      guCount = 0;
    }
    else{
      break;
    }
  }
  
  
 //printf("%d\n",numNum);
 //printf("%d %d %d",a[0],a[1],a[2]);
 
 printf("%d",wariCount);
  
 
 return 0; 
}

Measured memory_bytes: 128
// 以下のソースを勉強する.
// zscoder氏.
// https://atcoder.jp/contests/dp/submissions/3937814
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL h[123321];
LL dp[123321];

int main(){
    
    // 1. 入力情報取得.
    int N, K;
    scanf("%d %d", &N, &K);
    for(int i = 0; i < N; ++i) scanf("%d", &h[i]);
    
    // 2. dp更新.
    dp[0] = 0;
    for(int i = 1; i < N; i++){
        dp[i] = 1e18;
        for(int j = 1; j <= K; j++){
            if(i - j >= 0) dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
        }
    }
    // for(int i = 0; i < N; ++i) printf("dp[%d]=%d ", i, dp[i]);
    // printf("\n");
    
    // 3. 出力.
    printf("%d\n", dp[N - 1]);
    return 0;
}

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

int main(){
  int a, b, c , d; cin >> a >> b >> c >> d;
  
  if(abs(a - c) <= d){
    cout << "Yes";
  }
  else{
    if(abs(a - b) <= d && abs(b - c) <= d){
      cout << "Yes";
    }else{
      cout << "No";
    }
  }

	return 0;
}


Measured memory_bytes: 256
def gcd(a, b):
    '''ユークリッド互除法を使った最大公約数の求め方'''
    while b != 0:
        a, b = b, a % b
    return(a)


def lcm(a, b):
    '''最小公倍数の求め方'''
    return a * b // gcd(a, b)

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

print(lcm(A,B))

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

int main(){
    int n;
    cin >> n;
    int a[n];
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    int b[n] = {};
    int cnt=0;
    for(int i=n-1; i>=0; i--){
        int t = n/(i+1);
        int sum = 0;
        for(int j=2; j<=t; j++){
            sum += b[(i+1)*j-1];
        }
        sum %= 2;
        if(sum != a[i]){
           b[i] = 1;
           cnt++;
        }
    }
    cout << cnt << endl;
    for(int i=0; i<n; i++){
        if(b[i]) cout << (i+1) << ' ' ;
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 2432
N, A = map(int, input().split())
X = list(map(int, input().split()))
dp = [[[0] * 3001 for i in range(51)] for j in range(51)]

dp[0][0][0] = 1

for i in range(N):
  for j in range(N):
    for k in range(0, 2501):
      dp[i+1][j][k] += dp[i][j][k]
      dp[i+1][j+1][k+X[i]] += dp[i][j][k]

ans = 0
for n in range(1, N+1):
  ans += dp[N][n][n*A]

print(ans)

Measured memory_bytes: 102620
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        //when the game ends, the string must be "abab..."
        //the first letter and last letter cannot be changed
        
        boolean startStringIsOdd = (s.length()%2!=0);
        boolean endStringIsOdd = (s.charAt(0)==s.charAt(s.length()-1));
        System.out.println(startStringIsOdd^endStringIsOdd ? "First" : "Second");
    }
}

Measured memory_bytes: 25756
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,n,m;
	cin>>a>>n>>m;
	int k=0,ans=0,p=1,ka,q=0;

	for(int i=1;i<=m;i++){
		k=i;
		k+=a;
		ka=k;
		for(int j=1;j<n;j++){
			k=k*ka;
		}
		for(int j=0;j<8;j++){
			q+=(k-((k/(p*10))*(p*10)))/p;
			p=p*10;
		}
		p=1;
		if(k>m){
			break;
		}
	
		if(q==i){
			ans++;
		}
		q=0;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 3116
# import bisect
# from collections import Counter, defaultdict, deque, namedtuple
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    s = input()
    l = len(s)

    if l % 2 == 0:
        for i in range(l//2):
            if s[i*2:i*2+2] != "hi":
                print('No')
                sys.exit()
    else:
        print('No')
        sys.exit()

    print('Yes')


if __name__ == '__main__':
    main()

Measured memory_bytes: 38384
/**
*author: Ritchie Zhang
*date:2020/5/2
**/
#include <bits/stdc++.h> 
using namespace std; 
int main()
{
	int k,m,i;
	cin >> k;
	int a, b;
	cin >> a >> b;
	for (i = 1; i <= 1000; i++)
	{
		m = k * i;
		if (m>=a&&m<=b)
		{
			cout << "OK" << endl;
			break;
		}
		if (m>b)
		{
			cout << "NG" << endl;
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 3624
/*
      HET PAGHADAR
      DA-IICT
      @HET262
*/
 
#include<bits/stdc++.h>
using namespace std;
 
typedef long double ld;
typedef long long ll;
 
typedef vector<ll> vec; 
#define INF LLONG_MAX
 
#define P pair<ll,ll>
 
#define PP pair<int,int>
#define pb push_back
 
#define ff first
#define ss second
 
#define int long long int
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
#define N 200005
#define MOD 1000000007


signed main()
{
      FAST;
      
      ll n;
      cin>>n;
      
      ll tt=ceil((ld)n/(ld)1.08);
      if((ll)(tt*1.08)==n)    cout<<tt;
      else  cout<<":(";
      
      
      
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

int main() {
	int n, q; scanf("%d%d", &n, &q);
	std::string s; cin >> s;
	
	std::vector<char> t(q), d(q);
	for(int i = 0; i < q; i++) cin >> t[i] >> d[i];
	
	int L = -1, R = n;
	for(int i = q - 1; i >= 0; i--) {
		char A = t[i], B = d[i];
		
		if(L == -1) {
			if(A == s.front() and B == 'L') L = 0;
		} else if(L < n) {
			if(B == 'L' and L + 1 < s.size() and A == s[L + 1]) L++;
			else if(B == 'R' and A == s[L]) L--;
		}
		
		if(R == n) {
			if(A == s.back() and B == 'R') R = n - 1;
		} else if(R >= 0) {
			if(B == 'L' and A == s[R]) R++;
			else if(B == 'R' and R and A == s[R - 1]) R--;
		}
	}
	
	if(L < R) {
		printf("%d\n", R - L - 1);
	} else {
		printf("%d\n", 0);
	}
	return 0;
}


Measured memory_bytes: 900
import collections

n = int(input())
l = list(map(int, input().split()))
l = sorted(l, reverse=True)

i = 1
a = 0
b = 0
while i < n:
    if l[i] == l[i-1]:
        if a == 0:
            a = l[i]
        else:
            b = l[i]
            break
        i += 2
    else:
        i += 1

print(a*b)

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



int main() {
int N, M;
cin >> N >> M;
int food[100][100];

for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
food[i][j] = 0;
}
}

for(int i = 0; i < N; i++){
    int K;
cin >> K;
for(int j = 0; j < K; j++){
int tabe;
cin >> tabe;
tabe--;
food[i][tabe] = 1;
}
}
int count = 0;
for(int i = 0; i < M; i++){
    bool check = 1;
for(int j = 0; j < N; j++){
if(food[j][i] != 1) check = 0;
}
if(check == 1)count++;
}


cout << count << endl;

}

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

int main(){
    ll N;
    cin >> N;
    int ans = 11;
    double r = sqrt(N);
    for (int i = 1; i <= r; i++) {
        if (N % i != 0) continue;
        ll b = N / i;
        int digit = 1;
        while (b >= 10) {
            digit++;
            b /= 10;
        }
        ans = min(ans, digit);
    }
    cout << ans << endl;
}

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

int main()
{
    string s;
    cin >> s;
    char alfa[26] = {'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'};
    int ans[26] = {};
    for(int i = 0; i < s.size(); i++){
        for(int j = 0; j < 26; j++){
            if(s[i] == alfa[j]){
                ans[j]++;
            }
        }
    }
    for(int i = 0; i < 26; i++){
        if(ans[i]%2 != 0){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD (1E9+7)
#define PI 3.1415926535897932384

std::ostream &operator<<(std::ostream &out, const vector<int> &tgt)
{
	string s;
	for (int i = 0; i<tgt.size(); i++) {
		s += (to_string(tgt[i]) + ((i != tgt.size() - 1) ? " " : ""));
	}
	out << s;
	return out;
}

int main() {
	int n, k;
	ll ans = 1;
	cin >> n >> k;
	rep(i, n-1) {
		ans *= (k - 1);
	}
	ans *= k;
	cout << ans << endl;
}	


Measured memory_bytes: 256
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.next());
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(scan.next());
            if (map.containsKey(a)) {
                map.put(a, map.get(a) + 1);
            } else {
                map.put(a, 1);
            }
        }

        long ans = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            ans += entry.getKey() * entry.getValue();
        }

        int q = Integer.parseInt(scan.next());
        for (int i = 0; i < q; i++) {
            int b = Integer.parseInt(scan.next());
            int c = Integer.parseInt(scan.next());
            if (map.containsKey(b)) {
                int count = map.get(b);
                ans += (c - b) * count;

                if (map.containsKey(c)) {
                    map.put(c, map.get(c) + count);
                } else {
                    map.put(c, count);
                }
                map.put(b, 0);
            }
            System.out.println(ans);
        }
        scan.close();

    }

}


Measured memory_bytes: 71176
#include <iostream>
#include <string>
using namespace std;
int main()
{
    char well[110][110];
    int rol[110],cow[110];
    fill(rol,rol+110,0);
    fill(cow,cow+110,0);
    int n,m;
    cin >> n >> m;
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<m;++j)
        {
            cin >> well[i][j];
        }
    }
    for(int i=0;i<n;++i)
    {
        int j;
        for(j=0;j<m;++j)
        {
            if(well[i][j]=='#')
                break;
        }
        if(j==m)
            rol[i]=1;
    }
    for(int i=0;i<m;++i)
    {
        int  j;
        for( j=0;j<n;++j)
            if(well[j][i]=='#')
                break;
        if(j==n)
            cow[i]=1;
    }
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<m;++j)
            if(!rol[i]&&!cow[j])
                cout << well[i][j];
        if(!rol[i])
        cout << endl;
    }
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int main(){
  string a,b;cin>>a>>b;
  ll na=a.size(),nb=b.size();
  ll i=0,j=0;
  while(i<na||j<nb){
    if(i<na){
      cout<<a[i];
      i++;
    }
    if(j<nb){
      cout<<b[j];
      j++;
    }
    
  }
  cout<<endl;
}

Measured memory_bytes: 256
n = int(input())
s = input()
r = []
g = []
b = []
for i, item in enumerate(s):
    if item=="R":
        r.append(i)
    elif item=="G":
        g.append(i)
    else:
        b.append(i)
if (not r) or (not g) or (not b):
    print(0)
else:
    count = 0
    for low,mid,high in [(r,g,b), (r,b,g), (g,r,b), (g,b,r), (b,r,g), (b,g,r)]:
        for m in mid:
            ind = len(high) - 1
            for l in low:
                if l >= m:
                    continue
                while (l+high[ind] > m*2) and (ind>0):
                    ind -= 1
                if m < high[ind]:
                    if l+high[ind] == m*2:
                        count += 1
    print(len(r)*len(g)*len(b) - count)

Measured memory_bytes: 74216
N = int(input())
X = list(map(int, input().split()))
 
ans = 10**9
m = min(X)
M = max(X)
for i in range(m, M+1):
  s = 0
  for j in range(N):
    s += (X[j]-i)**2
  ans = min(ans, s)
  
print(ans)

Measured memory_bytes: 9224
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
	for (auto &i : v) is >> i;
	return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
	const string delimiter = "\n";
	REP(i, v.size())
	{
		os << v[i];
		if (i != v.size() - 1) os << delimiter;
	}
	return os;
}
/*--------------------template--------------------*/

int n;
vi w;
int dp[333][333];
vector<vector<bool>> del;

int del_all(int left, int right)
{
	if (dp[left][right] >= 0) return dp[left][right];
	int res = 0;
	if (left > right) res = 0;
	else if (left == right) res = 1;
	else
	{
		FOR(i, left + 1, right)
		{
			if (del_all(left, i) && del_all(i, right)) res = 1;
			if (abs(w[left] - w[right - 1]) <= 1 && del_all(left + 1, right - 1)) res = 1;
		}
	}
	return dp[left][right] = res;
}

int dp2[333];

int solve(int p)
{
	if (dp2[p] >= 0) return dp2[p];
	if (p == n) return 0;
	int res = 0;
	chmax(res, solve(p + 1));
	FOR(i, 1, n + 1)
	{
		if (del[p][i])
		{
			chmax(res, i - p + solve(i));
		}
	}
	return dp2[p] = res;
}

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	while (cin >> n, n)
	{
		MS(dp, -1);
		MS(dp2, -1);
		w.resize(n);
		REP(i, n) cin >> w[i];
		int ans = 0;
		del.clear();
		del.resize(n + 1, vector<bool>(n + 1));
		REP(i, n + 1)REP(j, i)
		{
			if (del_all(j, i))
			{
				del[j][i] = true;
			}
		}
		cout << solve(0) << endl;
	}
	return 0;
}

Measured memory_bytes: 3644
# -*- coding: utf-8 -*-
"""
Created on Tue Sep  8 01:07:55 2020

@author: liang
"""

N, K = map(int, input().split())
H = [int(x) for x in input().split()]
H.sort()

if N > K :
    ans = sum(H[:N-K])
else:
    ans = 0
print(ans)

Measured memory_bytes: 30824
#include <bits/stdc++.h>
using namespace std;
#define e1 first
#define e2 second
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false)
#define eb emplace_back
#define OUT(x) {cout << x; exit(0); }
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define scanf(...) scanf(__VA_ARGS__)?:0
typedef long long int ll;
typedef unsigned long long ull;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair <PLL, int> PLLI;
typedef pair <PLL, PLL> PP;
typedef pair <PII, int> PPI;
typedef pair <ll, int> PLI;
typedef unsigned int ui;
const int inf = 1e9+9;
const int mod = 924844033;
int n, m;
#define maxn 1000100
int jest[2][maxn];
int main()
{
	boost;
	cin >> n >> m;
	FOR(i, 1, m) {
		int a, b;
		cin >> a >> b;
		if (a > b) swap(a, b);
		if (a == 1) jest[0][b] = 1;
		if (b == n) jest[1][a] = 1;
	}
	FOR(i, 1, m) {
		if (jest[0][i] && jest[1][i]) OUT("POSSIBLE");
	}
	cout << "IMPOSSIBLE";
}


Measured memory_bytes: 5120
import std.stdio, std.algorithm, std.string, std.conv, std.array;

void main() {
    int calc(int base, int rate) {
        return base * (100 + rate) / 100;
    }

    for(;;) {
        auto input = readln.chomp.split(" ").map!(to!int).array;
        if ( input == [0, 0, 0] ) break;
        immutable x = input[0], y = input[1], s = input[2];

        int res = 0;

        for( int i=1; i<s; ++i ) {
            for( int j=1; j<s; ++j ) {
                if ( calc(i, x) + calc(j, x) == s ) {
                    res = max(res, calc(i, y) + calc(j, y));
                }
            }
        }

        res.writeln;
    }
}

Measured memory_bytes: 1076