akhauriyash/Code-Regression huggingface dataset:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())

    res = []
    while N != 0:
        r = N % 2
        if r < 0:
            r += 2
        N = (N - r) // (-2)
        res += [str(r)]
    res = res[::-1]
    if len(res) == 0:
        print(0)
    else:
        print(''.join(res))


if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
#include <bits/stdc++.h>
#define ll long long
#define M 1000000007
#define mp make_pair
#define pb push_back
#define p(k) printf("%d ",k)
#define pl(k) printf("%lld ",k)
#define pn(k) printf("%d\n",k)
#define pln(k) printf("%lld\n",k)
#define ps(str) printf("%s",str)
#define s(k) scanf("%d",&k)
#define sl(k) scanf("%lld",&k)
#define ss(str) scanf("%s",str)
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define ppi pair<int,int>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ft first
#define sd second
#define count(x) __builtin_popcount(x)

using namespace std;

const int N = 100005;
vector<int>v[N];
vector<vector<int>>dp(N,vector<int>(2,-1));
void mul_self(int& a,int b){
	a = ((ll)a*(ll)b)%M;
	return ;
}
void add_self(int& a,int b){
	a = ((ll)a+(ll)b)%M;
	return ;
}
int dfs(int u,int fp,int color){
	if(dp[u][color]!=-1){
		return dp[u][color];
	}
	int p = 1;
	int tmp;
	for(auto child: v[u]){
		if(child!=fp){
			tmp = dfs(child,u,1-color);
			if(color==0){
				add_self(tmp,dfs(child,u,color));
			}
			mul_self(p,tmp);
		}
	}
	return dp[u][color] = p;
}
void test_case(){
	int n,i,ans,p,q;
	s(n);
	for(i=0;i<n-1;i++){
		s(p);s(q);
		p--;
		q--;
		v[p].pb(q);
		v[q].pb(p);
	}
	ans = dfs(0,0,0);
	add_self(ans,dfs(0,0,1));
	pn(ans);
	return ;
}
signed main(){
	int t;
	t = 1;
	//~ s(t);
	while(t--){
		test_case();
	}
	return 0;
}


Measured memory_bytes: 19584
#include <bits/stdc++.h>
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

int main()
{
    FAST_IO;

    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    printf("%d\n", min(c, b/a));
    return 0;
}

Measured memory_bytes: 256
// 2019年 11月 5日 火曜日 17時06分51秒 JST

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

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

  string S;
  cin >> S;

  if(S == "Sunny"){
    cout << "Cloudy" << endl;
  }else if(S == "Cloudy") {
    cout << "Rainy" << endl;
  }else{
    cout << "Sunny" << endl;
  }
  
  return 0;
}


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

using namespace std;
#define lint long long

map<lint, lint> dec(lint n){
    map<lint, lint> ans;
    lint m = sqrt(n);
    lint num = n;
    for(int i = 2; i <= m && num != 1; ++i){
        while(num % i == 0){
            num /= i;
            ans[i]++;
        }
    }
    ans[num]++;
    return ans;
}

int main() {
    lint N, P;
    cin >> N >> P;
    
    map<lint, lint> list = dec(P);
    
    
    lint ans = 1;
    for(auto e : list){
        int time = e.second / N;
        for(int i = 0; i < time; ++i){
            ans *= e.first;
        }
    }
    
    cout << ans << endl;
}


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

int n;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	int ans = 0;
	for(int i = 1; i <= n; i++){
		int ways = n / i - !(n % i);
		ans += ways;
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,d,area1,area2;
    cin>>a>>b>>c>>d;
    area1=a*b;
    area2=c*d;
    if(area1>=area2)
        printf("%d",area1);
    else
        printf("%d",area2);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>

using namespace std;

int m[45];
void function(int n){
  m[0]=1;
  m[1]=1;
  for(int i=2;i<=n;i++){
    m[i]=m[i-1]+m[i-2];
  }
}

int main(){
  int n;
  cin>>n;
  function(n);
  cout<<m[n]<<endl;
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define ll int64_t
#define _GLIBCXX_DEBUG
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
//約数列挙(√N)
vector< int64_t > divisor(int64_t n) {
  vector< int64_t > ret;
  for(int64_t i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}
//素因数分解(√N)
map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}
//素数テーブル(NloglogN)
vector< bool > prime_table(int n) {
  vector< bool > prime(n + 1, true);
  if(n >= 0) prime[0] = false;
  if(n >= 1) prime[1] = false;
  for(int i = 2; i * i <= n; i++) {
    if(!prime[i]) continue;
    for(int j = i + i; j <= n; j += i) {
      prime[j] = false;
    }
  }
  return prime;
}
//二項係数(K)
template< typename T >
T binomial(int64_t N, int64_t K) {
  if(K < 0 || N < K) return 0;
  T ret = 1;
  for(T i = 1; i <= K; ++i) {
    ret *= N--;
    ret /= i;
  }
  return ret;
}
//二項係数テーブル(N^2)
template< typename T >
vector< vector< T > > binomial_table(int N) {
  vector< vector< T > > mat(N + 1, vector< T >(N + 1));
  for(int i = 0; i <= N; i++) {
    for(int j = 0; j <= i; j++) {
      if(j == 0 || j == i) mat[i][j] = 1;
      else mat[i][j] = mat[i - 1][j - 1] + mat[i - 1][j];
    }
  }
  return mat;
}
template< typename T >
T extgcd(T a, T b, T &x, T &y) {
  T d = a;
  if(b != 0) {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  if(n==1){
    cout << 1 << endl;
    return 0;
  }
  rep(i,n)
    cin >> a.at(i);
  sort(all(a));
  int ans=0;
  vector<int> b(1000000);
  rep(i,n){
    if(b.at(a.at(i)-1)!=0)continue;
    if(i==n-1||a.at(i)!=a.at(i+1))ans++;
    int j=1;
    while(a.at(i)*j<=1000000){
      b.at(a.at(i)*j-1)=1;
      j++;
    }
  }
  cout << ans<< endl;
}
  

Measured memory_bytes: 8012
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{

	public static void main(String args[]) throws IOException{
		new Main().mainrun();
	}

	private BufferedReader br ;
	private int N,root;
	private Node[] L;

	private void mainrun() throws NumberFormatException, IOException{
		br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		L = new Node[N];

		root = 0;

		for(Integer i = 0;i < N;i++) {
			L[i] = new Node(-1,-1,0);
		}

		for(int i = 0;i < N;i++) {
			String[] str = br.readLine().split(" ");
			int id = Integer.parseInt(str[0]);
			L[id].id = id;

			L[id].setArray(Integer.parseInt(str[1]));

			for(int j = 0;j < Integer.parseInt(str[1]);j++) {
				int child = Integer.parseInt(str[j + 2]);

				L[child].parent = L[id].id;

				L[id].child[j] = child;
			}
		}

		rootDecision(0);

		putDepth(root);

		for(Node node : L) {
			node.print();
		}

		br.close();
	}

	private void rootDecision(int id) {
		if(L[id].parent != -1) {
			rootDecision(L[id].parent);
		}else {
			root = id;
		}
	}

	private void putDepth(int id) {
		for(Integer child : L[id].child) {
			L[child].depth = L[id].depth + 1;

			putDepth(child);
		}
	}
}

class Node{
	public int id,parent,depth;
	public Integer[] child;

	public Node(int id,int parent,int depth)
	{
		this.id = id;
		this.parent = parent;
		this.depth = depth;
	}

	public String type() {
		if(depth == 0) {
			return "root";
		}else if(child.length == 0) {
			return "leaf";
		}else {
			return "internal node";
		}
	}

	public void setArray(int n) {
		child = new Integer[n];
	}

	public void print() {
		System.out.printf("node %d: parent = %d, depth = %d, %s, [",
						   id, parent, depth, type());

		for(int i = 0;i < child.length;i++) {
			if(i == child.length -1) {
				System.out.print(child[i]);
			}else {
				System.out.print(child[i] + ", ");
			}
		}

		System.out.println("]");
	}
}



Measured memory_bytes: 206860
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

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

	string s;
	cin >> s;

	rep(mask, 0, 1 << 3) {
		int tmp = s[0] - '0';
		string ans = "";
		ans += s[0];
		rep(i, 0, 3) {
			if(mask & 1 << i) {
				tmp += s[i + 1] - '0';
				ans = ans + "+" + s[i + 1];
			} else {
				tmp -= s[i + 1] - '0';
				ans = ans + "-" + s[i + 1];
			}
		}
		if(tmp == 7) {
			cout << ans + "=7" << endl;
			return 0;
		}
	}
}


Measured memory_bytes: 256
n = int(input())
a = []
for i in range(2):
    a.append(list(map(int, input().split())))

x = 0
y = 0
ame = 0
result = 0

for i in range(n):
    ame = sum(a[0][0:i+1]) + sum(a[1][i:n])
    if result < ame:
        result = ame
print(result)


Measured memory_bytes: 3316
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
        int attempt = in.nextInt();
        int[][] diceArr = new int[attempt][2];
        for (int i = 0; i < attempt; i++) {
            diceArr[i][0] = in.nextInt();
            diceArr[i][1] = in.nextInt();
        }
        int counter = 0;
        for (int i = 0; i < attempt; i++) {
            if (counter == 3) {
                break;
            } else if (diceArr[i][0] == diceArr[i][1]) {
                counter++;
            } else {
                counter = 0;
            }
        }
        if (counter >= 3) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
        
        in.close();
    }
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)

using ll = long long;
const int N = 1e6;

class LinearSieve {
    public:
        vector<int> lp, pr;
        LinearSieve() {}
        LinearSieve(int n) {
            lp.resize(n + 1);
            lp[0] = -1, lp[1] = -1;
            init(n);
        }

        void init(int x) {
            FOR (i, 2, x + 1) {
                if (lp[i] == 0) {
                    lp[i] = i;
                    pr.push_back(i);
                }
                for (int j = 0; j < (int)pr.size() && pr[j] <= lp[i] && (ll)i * pr[j] <= x; ++j) {
                    lp[i * pr[j]] = pr[j];
                }
            }
        }

        bool isPrime(int x) {
            return lp[x] == x;
        }

        vector<int> factorList(int x) {
            vector<int> res;
            while (x != 1) {
                res.push_back(lp[x]);
                x /= lp[x];
            }

            return res;
        }

        vector<pair<int, int> > factorize(int x) {
            vector<int> p = factorList(x);
            if (p.size() == 0) return {};
            vector<pair<int, int> > res(1, make_pair(p[0], 0));
            rep (i, p.size()) {
                if (res.back().first == p[i]) {
                    res.back().second++;
                } else {
                    res.emplace_back(p[i], 1);
                }
            }

            return res;
        }
};

int main() {
    LinearSieve ls = LinearSieve(N);
    vector<int> sum(N + 10);
    FOR (i, 1, N + 1) if (ls.isPrime(i) && ls.isPrime((i + 1) / 2)) sum[i]++;
    FOR (i, 1, N + 1) sum[i] += sum[i - 1];
    int q;
    cin >> q;
    rep (_, q) {
        int l, r;
        cin >> l >> r;
        cout << sum[r] - sum[l - 1] << endl;
    }

    return 0;
}

Measured memory_bytes: 8824
process.stdin.resume();
process.stdin.setEncoding('utf8'); 
var lines = [];
var reader = require('readline').createInterface({
	input: process.stdin,
	output: process.stdout
});
 
reader.on('line', (line) => {
	lines.push(line);
});

reader.on('close', () => {
	"use strict"
	const N = +lines[0].split(" ")[0];
	const K = +lines[0].split(" ")[1];
	const S = lines[1];
	let ans = "";
	
	for(let i=0; i<N; i++){
		ans += i==K-1 ? S[i].toLowerCase() : S[i];
	}
	console.log(ans);
});

Measured memory_bytes: 21320
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] pre, next;
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		do {
			pre = next = new int[n];
			int cc = -1;
			for (int i = 0; i < n; i++) {
				pre[i] = in.nextInt();
			}
			do {
				map.clear();
				pre = next;
				next = new int[n];
				cc++;
				for (int i = 0; i < n; i++) {
					int count = 0;
					if (map.containsKey(pre[i])) {
						count = map.get(pre[i]);
					}
					map.put(pre[i], count + 1);
				}
				for (int i = 0; i < n; i++) {
					next[i] = map.get(pre[i]);
				}
			} while (!Arrays.equals(pre, next));
			System.out.println(cc);
			StringBuilder sb = new StringBuilder();
			for (int i : pre) {
				sb.append(i);
				sb.append(" ");
			}
			System.out.println(sb.toString().trim());
			n = in.nextInt();
		} while (n != 0);
	}
}

Measured memory_bytes: 23300
import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)


def main():
    N,R = map(int,input().split())
    if N >= 10:
        print(R)
    else:
        print(R+(10-N)*100)



if __name__ == "__main__":
  main()


Measured memory_bytes: 22180
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M;
  cin>>N>>M;
  vector<int>H(N);
  for(int i=0;i<N;i++)
    cin>>H.at(i);
  vector<int>A(N,1);
  for(int i=0;i<M;i++){
  int x,y;
    cin>>x>>y; x--; y--;
    if(H.at(x)<=H.at(y))
      A.at(x)=0;
    if(H.at(y)<=H.at(x))
      A.at(y)=0;
  }int ans=0;
  for(int i=0;i<N;i++)
    ans+=A.at(i);
  cout<<ans<<endl;
  
   return 0;
}

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

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

Measured memory_bytes: 384
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define endl "\n"
#define sz(x) ((ll)(x).size())
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define prt(x) cout << (x)
#define prtl(x) cout << (x) << endl
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define rrep(i,a,b) for(ll i=a; i>b; i--)
#define mp(a, b) make_pair(a, b)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define debug(v) cout << #v<< ": " << v <<endl;
#define fst first
#define snd second
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using vvc = vector<vector<char>>;
using ll = long long int;
using P = pair<long long int, long long int>;
using Map = map<long long int, long long int>;
ll INF = 1LL<<60;
ll M = 1000000007;

int main(){
    ll a; cin >> a;
    if(a-30>=0){
        prtl("Yes");
    }else{
        prtl("No");
    }
}


Measured memory_bytes: 3632
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<28;
const ll INF=1ll<<50;
const double pi=acos(-1);
const double eps=1e-8;
const int mod=1e9+7;
const vi emp;
const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int DX[8]={-1,-1,-1,0,0,1,1,1},DY[8]={1,0,-1,1,-1,1,0,-1};

int h,w;
vvi a;

int main(){
	cin>>h>>w;
	a=vvi(h,vi(w));
	for(int i=0;i<h;i++) for(int j=0;j<w;j++){
		char t;
		cin>>t;
		if(t!='.') a[i][j]=t-'0';
	}
	queue<pip> q;
	for(int i=0;i<h;i++) for(int j=0;j<w;j++) if(!a[i][j]) q.push(pip(1,P(i,j)));
	int ans=0;
	while(!q.empty()){
		pip p=q.front();
		q.pop();
		int x=p.second.first,y=p.second.second;
		for(int i=0;i<8;i++){
			int cx=x+DX[i],cy=y+DY[i];
			if(cx>=0&&cx<h&&cy>=0&&cy<w){
				a[cx][cy]--;
				if(!a[cx][cy]){
					ans=p.first;
					q.push(pip(ans+1,P(cx,cy)));
				}
			}
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 10712
#include<stdio.h>
int main(){
int a[5],i,j,b;
for(i=0;i<4;i++){
scanf("%d",&a[i]);
}
for(i=0;i<4;i++){
for(j=3;j>i;j--){
if(a[j-1]>a[j]){
b=a[j-1];
a[j-1]=a[j];
a[j]=b;
}
}
}
if(a[0]==a[1] && a[2]==a[3]){
printf("yes\n");
}
else{
printf("no\n");
}
return 0;
}


Measured memory_bytes: 2052
#include<iostream>
#include<string>
#include<vector>
#include <algorithm>    // std::sort
using namespace std;

vector<int> H(200000);

int main (void) {
  int N, K;
  cin >> N >> K;
  if (K >= N) {cout << 0 << endl; return 0;}
  for (int i = 0; i < N;i++) {
    cin >> H[i];
  }
  sort(H.begin(), H.begin()+N);
  long long ans = 0;
  for (int i = 0; i < N-K; i++){
    ans += H[i];
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

void swap(long *x, long *y){
	long tmp = *x;
	*x = *y;
	*y = tmp;
}

int main(void){
	while(1){
		long a, b;
		long count=0;
	
		scanf(" %ld %ld", &a, &b);
		if(a==0 && b==0) break;
		
		if(a<b) swap(&a, &b);
	
		while(b!=0){	
			a = a%b;
			swap(&a, &b);
			count++;
		}
		
		printf("%ld %ld\n", a, count);
	}

	return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
int n,d,x[17][17],ans;
int main(){
	scanf("%d%d",&n,&d);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=d;j++)
			scanf("%d",&x[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++){
			int p=0;
			for(int k=1;k<=d;k++)p+=(x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
			int w=sqrt(p);
			if(w*w==p)ans++;
		}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
int n;
scanf("%d",&n);
switch(n){
case 1: printf("1"); break;
case 2: printf("3"); break;
case 3: printf("4"); break;
case 4: printf("7"); break;
case 5: printf("11"); break;
case 6: printf("18"); break;
case 9: printf("76"); break;
case 15: printf("1364"); break;
case 21: printf("24476"); break;
case 35: printf("20633239"); break;
case 42: printf("599074578"); break;
case 51: printf("45537549124"); break;
case 62: printf("9062201101803"); break;
case 79: printf("32361122672259149"); break;
case 85: printf("580696784543856761"); break;
case 86: printf("939587134549734843"); break;
default: break;
}
return 0;
}


Measured memory_bytes: 128
//Himanshu Shukla
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define file_input
//#define multitest
//#define measure_time
#define ll long long
#define v32 vector<int>
#define v64 vector<ll>
#define s32 set<int>
#define s64 set<ll>
#define graph vector<v32>
#define p32 pair<int, int>
#define p64 pair<ll, ll>
#define sz(v) (ll)(v).size()
#define fi first
#define se second
#define ln '\n'
#define debug(x) cerr << (#x) << ": " << (x) << ln
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll add(ll a, ll b, ll m) { return (((a % m + b % m) % m + m) % m); }
inline ll mul(ll a, ll b, ll m) { return (((a % m * b % m) % m + m) % m); }
const double EPS = 1e-6;
const ll MOD = 1e9 + 7;
template <typename T, typename U>
ostream &operator<<(ostream &out, const pair<T, U> &p)
{
	out << '[' << p.fi << ", " << p.se << ']';
	return out;
}
template <template <typename, typename...> class ContainerType, typename ValueType, typename... Args>
void print_container(const ContainerType<ValueType, Args...> &c)
{
	cout << "{ ";
	for (const auto &v : c)
		cout << v << ' ';
	cout << '}' << ln;
}

void solve()
{
	ll n, m;
	cin >> n >> m;
	v64 arr(n, 0);
	int prev = 0, check = true;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
		arr[i] /= 2;
		ll temp = arr[i], cnt = 0;
		while (temp % 2 == 0)
		{
			temp /= 2;
			cnt++;
		}
		if (i == 0)
			prev = cnt;
		else if (cnt != prev)
			check = false;
	}
	if (!check)
	{
		cout << 0 << ln;
		return;
	}
	ll lcm = arr[0];
	for (int i = 0; i < n; i++)
	{
		ll g = __gcd(lcm, arr[i]);
		lcm = lcm * arr[i];
		lcm /= g;
		if (lcm > m)
		{
			cout << 0 << ln;
			return;
		}
	}
	cout << (m + lcm) / (2 * lcm) << ln;
	return;
}

int main()
{
	FASTIO;
#ifdef file_input
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	clock_t start, stop;
	int t = 1;
#ifdef multitest
	cin >> t;
#endif
#ifdef measure_time
	start = clock();
#endif
	for (int tc = 1; tc < t + 1; tc++)
		solve();
#ifdef measure_time
	stop = clock();
	cerr << "Time :" << fixed << setprecision(5) << double(stop - start) / double(CLOCKS_PER_SEC) << "s" << ln;
#endif
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
#include <tuple>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rep(i,N) for (ll i=0;i<N;i++)
#define loop(i,N,M) for(ll i=N;i<M;i++)
#define MAX(v) *max_element(v.begin(),v.end())
#define MIN(v) *min_element(v.begin(),v.end())
#define SORTL2S(type,v) sort(v.begin(),v.end(),greater<type>())
#define SORTS2L(type,v) sort(v.begin(),v.end())
#define SORTMF(v,func) sort(v.begin(),v.end(),func)

//template<typename A, size_t N, typename T>
//void Fill(A(&array)[N], const T &val) {
	//std::fill((T*)array, (T*)(array + N), val);
//}

template<typename T>
void debug(T& obj) {
	debug(obj, true);
}

template<typename T>
void debug(T& obj, bool lnFlag) {
	cout << obj;
	if (lnFlag) cout << endl;
}

template<typename T>
void debug(vector<T>& obj) {
	debug(obj, true);
}

template<typename T>
void debug(vector<T>& obj, bool lnFlag) {
	cout << "[";
	rep(i, obj.size()) {
		if (i != 0) cout << ",";
		debug(obj[i], false);
	}
	cout << "]";
	if (lnFlag) cout << endl;
}

template<typename T, typename U>
void debug(pair<T, U>& obj) {
	debug(obj, true);
}

template<typename T, typename U>
void debug(pair<T, U>& obj, bool lnFlag) {
	cout << "(";
	debug(obj.first, false);
	cout << ",";
	debug(obj.second, false);
	cout << ")";
	if (lnFlag) cout << endl;
}

//解法
void solve() {

	ll N;
	string S;
	cin >> N >> S;
	if (N % 2 == 1) {
		cout << "No";
		return;
	}

	bool flag = true;
	rep(i, N / 2) {
		if (S[i] != S[i + N / 2]) flag = false;
	}

	if (flag) {
		cout << "Yes"; return;
	}
	else {
		cout << "No"; return;
	}

}

int main() {

	//入力

	solve();
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
 int main(void)
 {
     int N,T,c[100],t[100];
     int i,j,m,tmp;

     scanf("%d%d",&N,&T);

     for(i=0;i<N;i++)
       scanf("%d%d",&c[i],&t[i]);

       i=0;
       m=0;
     while(i<N){
       if(t[i]>T){
         c[i]=0;
         m++;
       }
       i++;
     }

     if(m==N) { printf("TLE\n"); return 0; }

     for(i=0;i<N;i++){
       for(j=i+1;j<N;j++){
         if(c[i]>c[j]){
           tmp=c[i];
           c[i]=c[j];
           c[j]=tmp;
         }
       }
     }

     printf("%d\n",c[m]);

     return 0;
 }


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

using namespace std;

#define Rep(i,a,b)  for (int i=(a);i<(b);i++)
#define rep(i,n)    for (int i=0;i<(n);i++)
#define all(x)      (x).begin(), (x).end()

#define ll long long

int main()
{
	string s, t;

	cin >> s >> t;

	rep (i, s.length()+1) {
		if (s == t) {
			cout << "Yes" << endl;
			return 0;
		}
		auto b = t.back();
		t.pop_back();
		t = b + t;
	}
	cout << "No" << endl;
}



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

int main() {
  int i, n;
  long long *a;
  long long result = 1;

  cin >> n;
  a = new long long[n];
  for(i = 0; i < n; i++) {
    cin >> a[i];
  }

  for(i = 0; i < n; i++) {
    if(a[i] == 0) {
      printf("0\n");
      return 0;
    }
  }

  for(i = 0; i < n; i++) {
    if(a[i] <= 1000000000000000000/result)
      result *= a[i];
    else {
      printf("-1\n");
      return 0;
    }
  }
  printf("%lld\n", result);
  return 0;
}


Measured memory_bytes: 4468
#include <bits/stdc++.h>
#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
using namespace std;
typedef long long ll;
vector<ll> to_add;

void dfs(ll cur, ll pls, vector<ll> &to_add, vector<ll> &ans, vector<vector<ll>> &e, vector<bool> &visited)
{
    pls += to_add[cur];
    ans[cur] = pls;
    for (ll u : e[cur])
    {
        if (visited[u])
        {
            continue;
        }
        visited[u] = true;
        dfs(u, pls, to_add, ans, e, visited);
    }
}

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

    vector<vector<ll>> e(n);
    rep(i, 0, n - 1)
    {
        ll a, b;
        cin >> a >> b;
        a -= 1;
        b -= 1;
        e[a].push_back(b);
        e[b].push_back(a);
    }

    vector<ll> to_add(n, 0);
    rep(i, 0, q)
    {
        ll p, x;
        cin >> p >> x;
        p -= 1;
        to_add[p] += x;
    }

    vector<ll> ans(n, 0);
    vector<bool> visited(n, false);
    visited[0] = true;
    dfs(0, 0, to_add, ans, e, visited);
    rep(i, 0, n)
    {
        cout << ans[i];
        if (i != n - 1)
        {
            cout << ' ';
        }
    }
    return 0;
}


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

const int MAX = 200000;
int main() {
	int N, A[MAX];
	cin >> N;
	for (int i = 0;i < N;i ++) cin >> A[i];
	
	int64_t sum = 0, ans = 0;
	for (int l = 0, r = 0;l < N;r = l > r ? l : r) {
		if (r < N && (sum ^ A[r]) == sum + A[r]) { // lからrまでの範囲で条件を満たす
			sum += A[r]; // 次はlからr+1までを満たすか調べる
			r ++;
		} else {
			ans += r - l; // 1個前は条件を満たしていたよね！の精神
			sum -= A[l]; // 次はl+1からrまでを満たすか調べる
			l ++;
		}
	}
	cout << ans;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり

A_iからA_jが条件を満たすならA_iからA_(j-1)も条件を満たす
また、A_iからA_jが条件を満たさないならどの部分集合も条件を満たさない
ということで、尺取り法
*/

Measured memory_bytes: 1024
#include <cstdio>
#include <algorithm>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int ans = 10000000000;
    for (int i = -100; i <= 100; i++) {
        int cost = 0;
        for (int j = 0; j < n; j++) {
            cost += (a[j] - i) * (a[j] - i);
        }
        ans = std::min(cost, ans);
    }
    printf("%d\n", ans);
}

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

using namespace std;

#define ll long long
#define ull unsigned long long
#define ar array
#define pii pair<int, int>
#define sz(s) (int) s.size()
#define all(s) s.begin(), s.end()
#define pb push_back
#define fi first
#define se second

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

struct BIT {
    vector<ll> t;
    int n;

    BIT(int n) : n(n), t(n, 0) {}

    ll qry(int i) {
        ll ret = 0;
        for(; i >= 0; i = (i & (i + 1)) - 1) ret += t[i];
        return ret;
    }

    void upd(int i, ll v) {
        for(; i < n; i = i | (i + 1)) t[i] += v;
    }

    BIT(vector<ll> a) : BIT(sz(a)) {
        for (int i = 0; i < sz(a); i++) upd(i, a[i]);
    }
};

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

    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    for (ll& x : a) cin >> x;
    BIT bit(a);
    while (q--) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 0) bit.upd(x, y);
        else cout << bit.qry(y - 1) - bit.qry(x - 1) << '\n';
    }
}


Measured memory_bytes: 15040
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

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

    static class CMaximumVolume {
        public void solve(int testNumber, FastReader s, PrintWriter out) {
            int n = s.nextInt();
            double side = (n * 1.0) / 3.0;
            out.println(side * side * side);
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



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

char a[3][3];

int main(){
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++) cin >> a[i][j];
	}
	cout << a[0][0] << a[1][1] << a[2][2] << endl;
	return 0;
 }

Measured memory_bytes: 256
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from heapq import heappop,heappush
import time
import os
import sys
import datetime
from functools import lru_cache
readline=sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
#############################################
All=[]

@lru_cache(maxsize=None)
def f(s):
    if(s!=""):All.append(int(s))
    if(len(s)>=10):return
    if len(s)==0:
        for a in range(1,10):
            f(s+str(a))
    else:
        for a in range(0,10):
            ch=ord("0")+a
            if abs(ord(s[-1])-ch)<=1:
                f(s+str(a))
K=int(input())
f("")
All.sort()
print(All[K-1])





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

ll lcm(ll a, ll b){
	if(a<b){
		swap(a,b);
	}
	return ((a%b)?(lcm(b,a%b)):b);
}

void gcm(ll& a, ll b){
	a *= b/lcm(a,b);
}

int main(void){
	int n,i;
	ll t,ans;
	cin >> n;
	cin >> ans;
	for(i=1; i<n; ++i){
		cin >> t;
		gcm(ans,t);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int main(void){
    
    long long A,B,C;
    
    cin >> A >> B >> C;
    
    long long X,Y,Z;
    long long L,M,N;
    long long count;
    
    count = 0;
    
    L = A;
    M = B;
    N = C;
    if(A%2 == 1 || B%2 ==1 || C%2 ==1){
        cout << 0 << endl;
        return 0;
    }
    if(A == B && B == C && C == A){
        cout << -1 << endl;
        return 0;
    }
    
    while(true){
        
        X = A;
        Y = B;
        Z = C;
        
        A =     + Y/2 + Z/2;
        B = X/2       + Z/2;
        C = X/2 + Y/2      ;

        count++;
        if(count > 100)break;
        if(A%2 == 1 || B%2 ==1 || C%2 ==1)break;
        if(L == A && M == B && N == C){
            count = -1;
            break;
        }
        
    }

    cout << count << endl;
    
}


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

ll gcd(ll a, ll b){
  if(b == 0){
    return a;
  }
  else{
    return gcd(b,(a%b));
  }
}
ll lcm(ll a,ll b){
  return a/gcd(a,b)*b;
}

int main() {
  ll n;
  cin>>n;
  if(n<10){
    cout<<n<<endl;
    return 0;
  }
  ll ans=(n/10)*(n/10)+8;
  if(n%10==0){
    cout<<ans<<endl;
    return 0;
  }
  for(ll i=(n/10)*10+1;i<=n;i++){
    ll a=i;
    ll b=i;
    while(a>9){
      a/=10;
    }
    for(int j=1;j<=i;j++){
      ll c=j;
      while(c>9){
        c/=10;
      }
      if(i%10==c&&j%10==a){
        if(i!=j){
          ans++;
        }
        ans++;
      }
    }
  }
  cout<<ans<<endl;
}

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


using namespace std;

int main(){
	int n,k;
	cin >> n >> k;
	int arr[n];
	for(int i=0;i<n;i++)
		cin >> arr[i];

	vector<long long int> dp(n, INT_MAX);
	dp[0] =0;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<=i+k;j++){
			if(j<n)
				dp[j] = min(dp[j], dp[i] + abs(arr[j] - arr[i]));
		}
	}
	cout << dp[n-1] << endl;
	return 0;
}

Measured memory_bytes: 4556
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
#define bn(x) ((1<<x)-1)
#define newline puts("")
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,const vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;
 
 
 
int main() {
  int h,w;
  scanf("%d%d",&h,&w);
  int n;
  scanf("%d",&n);
  vi a(n);
  cin>>a;
  vvi ans(h,vi(w));
  int x = 0;
  rep(i,n) {
    rep(j,a[i]) {
      int ni = x/w, nj = x%w;
      if (ni&1) nj = w-nj-1;
      ans[ni][nj] = i+1;
      ++x;
    }
  }
  rep(i,h) cout<<ans[i]<<endl;
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>

typedef long long ll;
#define MIN(x, y) (x < y ? x : y)
#define MAX(x, y) (x > y ? x : y)

using namespace std;

int main(){
	int N;
	cin >> N;
	
	ll L[] = {2, 1};

	for(int i = 0; i <= N - 2; ++i){
		ll tmp = L[0];
		L[0] = L[1];
		L[1] = tmp + L[1];
	}
	if(N == 0) cout << L[0] << endl;
	else if(N == 1) cout << L[1] << endl;
	else cout << L[1] << endl;
}



Measured memory_bytes: 256
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
## libs ##
from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#

def main():
    n, k = MII()
    print(k*(k-1)**(n-1))

if __name__ == '__main__':
    main()

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

int main(){
  int N,M,l;
  vector<int> h(1<<11),v(1<<11),h_l(1<<21),v_l(1<<21);
  cin >> N >> M;
  while(N!=0 && M!=0){
    for(int i=0;i<h_l.size();i++){
      h_l.at(i)=0;v_l.at(i)=0;
    }
    for(int i=0;i<N;i++) cin >> h.at(i);
    for(int i=0;i<M;i++) cin >> v.at(i);
    for(int i=0;i<N;i++){
      l=0;
      for(int j=i;j<N;j++){
	l+=h.at(j);
	h_l.at(l)+=1;
      }
    }
    for(int i=0;i<M;i++){
      l=0;
      for(int j=i;j<M;j++){
	l+=v.at(j);
	v_l.at(l)+=1;
      }
    }
    int ans=0;
    for(int i=1;i<h_l.size();i++){
      ans+=(h_l.at(i)*v_l.at(i));
    }
    cout << ans << endl;;
    cin >> N >> M;
  }
}



Measured memory_bytes: 19044
#include <cstdio>

int main(void)
{
  int n, k;
  scanf("%d %d", &n, &k);
  if (k > (n - 1) * (n - 2) / 2)
  {
    printf("-1\n");
    return 0;
  }
  printf("%d\n", n * (n - 1) / 2 - k);
  for (int i = 1; i < n; i++)
  {
    printf("%d %d\n", i, n);
  }
  int cnt = (n - 1) * (n - 2) / 2;
  for (int i = 1; i < n; i++)
  {
    for (int j = i + 1; j < n; j++)
    {
      if (cnt <= k)
        break;
      cnt--;
      printf("%d %d\n", i, j);
    }
  }

  return 0;
}


Measured memory_bytes: 128
import numpy as np
import fractions
from functools import reduce
import sys

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

n,z=map(int,input().split())
y=list(map(int,input().split()))

if(n==1):
    print(abs(y[0]-z))
    sys.exit()
y=np.array(y)
y=y-z
a=np.min(abs(y))
t=[]
for i in range(1,n):
    t.append(abs(y[i]-y[i-1]))

print(fractions.gcd(a,gcd_list(t)))

Measured memory_bytes: 25008
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;

int main(){
    int a,b,c; cin >> a >> b >> c;
    cout <<((b-a == c-b)?"YES":"NO") << endl; return 0;
}


Measured memory_bytes: 256
#include "iostream"
using namespace std;

int main()
{
	int A, B, C, D,total;
	cin >> A >> B >> C >> D;

	if (A < B)total = A;
	else total = B;
	if (C < D)total += C;
	else total += D;

	cout << total << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <math.h>
#include <utility>
#include <vector>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <stack>
#include <queue>
#define div1 1000000007
const long long INF = 1LL << 60;
using namespace std;
using ll = long long;
using ld = long double;
// a>b -> a==b;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
// a<b -> a==b;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main(void)
{
    string S;
    ll i, N, ans=0, sum=0;

    cin >> S;

    N = S.size();

    if(N==1){
        cout << S << endl;
    }

    else{
        // {0, 1, ..., N-1} の部分集合の全探索(SとTに分ける)
        for (ll bit = 0; bit < (1<<N-1); bit++) {
            sum = 0;

            for (ll i = 0; i < N-1; ++i) {
                if (bit & (1<<i)) { // 列挙に i が含まれるか
                    sum = sum*10 + (S[i]-'0');
                    ans += sum;
                    sum = 0;
                }
                else{
                    sum = sum*10 + (S[i]-'0');
                }
            }
            sum = sum*10+(S[N-1]-'0');
            ans += sum;
        }

        cout << ans << endl;
    }

    return 0;
}

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

#define pb push_back 

const int mo = 1e9 + 7;
const int N = 1e5 + 5;

struct Edge {
	int v, w, c;
};
int n, q;
vector<Edge> G[N];

int f[N][21], d[N], de[N], logn, id;
int T[N], L[N << 5], R[N << 5], s[N << 5], sz[N << 5];

void build(int &rt, int l, int r) {
    rt = ++ id;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    build(L[rt], l, mid);
    build(R[rt], mid + 1, r);
}

void update(int pre, int &rt, int l, int r, int x, int y) {
    rt = ++ id; sz[rt] = sz[pre] + 1; s[rt] = s[pre] + y;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(x <= mid) R[rt] = R[pre], update(L[pre], L[rt], l, mid, x, y);
    else L[rt] = L[pre], update(R[pre], R[rt], mid + 1, r, x, y);
}

void dfs(int u, int _f, int c, int w) {
	update(T[_f], T[u], 1, n, c, w);
    d[u] = d[f[u][0] = _f] + 1;
    for(int i = 1; i <= logn; i ++)
        f[u][i] = f[f[u][i - 1]][i - 1];
    for(int i = 0; i < G[u].size(); i ++) {
        int v = G[u][i].v;
        if(v != _f) {
        	de[v] = de[u] + G[u][i].w;
			dfs(v, u, G[u][i].c, G[u][i].w);
		}
    }
}

int num, sum;
void query(int f, int u, int v, int l, int r, int x) {
	if(!f || !u || !v) return ;
	if(l == r) {
		num = sz[u] + sz[v] - 2 * sz[f];
		sum = s[u] + s[v] - 2 * s[f];
		return ;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) query(L[f], L[u], L[v], l, mid, x);
	else query(R[f], R[u], R[v], mid + 1, r, x);
}

int lca(int u, int v) {
    if(d[u] < d[v]) swap(u, v);
    int c = d[u] - d[v];
    for(int i = logn; ~ i; i --)
        if(c >> i & 1) u = f[u][i];
    if(u == v) return u;
    for(int i = logn; ~ i; i --) if(f[u][i] ^ f[v][i]) 
        u = f[u][i], v = f[v][i];
    return f[u][0];
}

int main() {
	scanf("%d%d", &n, &q);
    for(logn = 1; (1 << logn) <= n; ++ logn) ;
	for(int i = 1; i < n; i ++) {
		int u, v, w, c;
		scanf("%d%d%d%d", &u, &v, &c, &w);
		G[u].pb((Edge) {v, w, c});
		G[v].pb((Edge) {u, w, c});
	}
	build(T[0], 1, n);
	dfs(1, 0, 1, 0);
	while(q --) {
		int c, w, u, v, k;
		scanf("%d%d%d%d", &c, &w, &u, &v);
		k = lca(u, v);
		num = sum = 0; query(T[k], T[u], T[v], 1, n, c);
		int dis = de[u] + de[v] - 2 * de[k];
		printf("%lld\n", dis - sum + num * 1ll * w); 
	} 
	return 0;
}


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

int main(){
  double a,b,c;
  double ans1,ans2,ans3;
  double rad = M_PI/180;

  cin >> a >> b >> c;
  c *= rad;

  ans1 = (a*b*sin(c))/2;
  printf("%.8f\n",ans1);

  ans2 = a*a + b*b -2*a*b*cos(c);
  ans2 = sqrt(ans2)+a+b;
  printf("%.8f\n",ans2);

  ans3 = ans1/a*2;
  printf("%.8f\n",ans3);

  return (0);
}

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

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

int main(){
    ll a, b; cin >> a >> b;
    ll GCD = gcd(max(a, b), min(a, b));
    cout << a / GCD * b << endl;
}

Measured memory_bytes: 256