akhauriyash/Code-Regression huggingface dataset:
S = list(input())
K = int(input())

S2 = S * 2

singleCnt = 0
doubleCnt = 0
for i in range(len(S)-1):
  if S[i] == S[i+1]:
    S[i+1] = "1" # かぶらない文字に変換
    singleCnt += 1
if S[0] != S[-1]:
  ans = singleCnt * K
  
elif S[0] == S[-1]:
  for i in range(len(S2)-1):
    if S2[i] == S2[i+1]:
      S2[i+1] = "1" # かぶらない文字に変換
      doubleCnt += 1
  if S2[0] != S2[-1]:
    a, b = divmod(K, 2)
    if b == 0:
      ans = doubleCnt * (K // 2)
    else:  
      ans = doubleCnt * (K // 2) + singleCnt
  else:
    ans = (doubleCnt - singleCnt) * (K - 1) + singleCnt

print(ans)


Measured memory_bytes: 3064
#include <stdio.h>
#define MAX 100000
#define SENTINEL 2000000000

struct Card {
  char suit;
  int value;
};

struct Card L[MAX/2+2], R[MAX/2+2];

void merge(struct Card A[], int n, int left, int mid, int right) {
  int i, j, k;
  int n1 = mid - left;
  int n2 = right - mid;
  for(i=0;i<n1;i++) L[i] = A[left + i];
  for(i=0;i<n2;i++) R[i] = A[mid  + i];
  L[n1].value = R[n2].value = SENTINEL;
  i = j = 0;
  for(k=left; k<right; k++) {
    if(L[i].value <= R[j].value) {
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
    }
  }
}

void mergeSort(struct Card A[], int n, int left, int right) {
  if(left+1 < right) {
    int mid = (left+right) / 2;
    mergeSort(A,n,left,mid);
    mergeSort(A,n,mid, right);
    merge(A,n,left,mid,right);
  }
}

int partition(struct Card A[], int n, int p, int r) {
  int i, j;
  struct Card t, x;
  x = A[r];
  i = p-1;
  for(j=p; j<r; j++) {
    if(A[j].value <= x.value) {
      i++;
      t=A[i]; A[i]=A[j]; A[j]=t;
    }
  }
  t=A[i+1]; A[i+1]=A[r]; A[r]=t;
  return i+1;
}

void quickSort(struct Card A[], int n, int p, int r) {
  int q;
  if(p<r) {
    q = partition(A,n,p,r);
    quickSort(A,n,p,q-1);
    quickSort(A,n,q+1,r);
  }
}

int main() {
  int n, i, v;
  struct Card A[MAX], B[MAX];
  char S[10];
  int stable = 1;

  scanf("%d", &n);

  for(i=0;i<n;i++) {
    scanf("%s %d",S,&v);
    A[i].suit =  B[i].suit  = S[0];
    A[i].value = B[i].value = v;
  }

  mergeSort(A,n,0,n);
  quickSort(B,n,0,n-1);

  for(i=0;i<n;i++) {
    // マージソートとクイックソートの結果を比べる
    if(A[i].suit != B[i].suit) stable = 0;
  }

  if(stable==1) printf("Stable\n");
  else printf("Not stable\n");
  for(i=0;i<n;i++) {
    printf("%c %d\n",B[i].suit,B[i].value);
  }

  return 0;
}


Measured memory_bytes: 4028
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

struct UnionFind {
  const int n;
  V<> t; // root ? -sz : par
  UnionFind(int n) : n(n), t(n, -1) {}
  int find(int v) { return t[v] < 0 ? v : t[v] = find(t[v]); }
  void unite(int u, int v) {
    if ((u = find(u)) == (v = find(v))) return;
    if (-t[u] < -t[v]) swap(u, v);
    t[u] += t[v];
    t[v] = u;
  }
  bool same(int u, int v) { return find(u) == find(v); }
  int size(int v) { return -t[find(v)]; }
};

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  V<> a(n); for (auto&& e : a) cin >> e;
  V<> b(n); for (auto&& e : b) cin >> e;
  a.push_back(accumulate(begin(a), end(a), 0, [](int init, int x) { return init ^ x; }));
  b.push_back(accumulate(begin(b), end(b), 0, [](int init, int x) { return init ^ x; }));
  auto _a = a, _b = b;
  sort(begin(_a), end(_a));
  sort(begin(_b), end(_b));
  if (_a != _b) return cout << -1 << '\n', 0;
  map< int, V<> > mp;
  for (int i = 0; i <= n; ++i) if (i == n or a[i] != b[i]) {
    mp[a[i]].push_back(i);
    mp[b[i]].push_back(i);
  }
  UnionFind uf(n + 1);
  for (const auto& e : mp) {
    for (int i : e.second) {
      uf.unite(e.second[0], i);
    }
  }
  int res = 0;
  set<int> se;
  for (int i = 0; i <= n; ++i) if (i == n or a[i] != b[i]) {
    if (se.count(uf.find(i))) continue;
    se.insert(uf.find(i));
    if (uf.same(i, n)) {
      res += uf.size(i) - 1;
    } else {
      res += uf.size(i) + 1;
    }
  }
  cout << res << '\n';
}

Measured memory_bytes: 15472
import math
x,n  = map(int,input().split())
if n==0:
    print(x)
    exit()
p = [int(i) for i in input().split()]


max_ = max(p)
a= [i for i in range(2*max_+1)]

m=0
for i in p:
    a[i]=100000
min_=100000
for i in a:
    b = abs(i-x)
    if min_ > b:
        min_=b
        m = i
print(m)

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

int main(void)
{
    int a,b,c,x;
    int way = 0;

    cin >> a;
    cin >> b; 
    cin >> c; 
    cin >> x;

    for(int i = 0; i <= a; i++)
    {
        for(int j = 0; j <= b; j++)
        {
            for(int k = 0; k <= c; k++)
            {
                if(x == (500 * i + 100 * j + 50 * k ))
                {
                    way++;
                }
            }
        }
    }
    cout << way << endl;

    return 0;
}

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

int main(){
  int N,K,x=1;
  cin >> N >> K;
  for(int i=0;i<N;i++){
    if(x<K){
      x *= 2;
    }else{
      x += K;
    }
  }
  cout << x;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
    int W, H, x, y, r;
    cin >> W >> H >> x >> y >> r;
    
    if (x - r >= 0 && x + r <= W && y - r >= 0 && y + r <= H) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
    return 0;
}


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

map<string, int> mp;
string s;
int n;
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s;
        mp[s]++;
    }
    int mx = 0;
    for (auto it : mp) mx = max(mx, it.second);
    set<string> ss;
    for (auto it : mp) {
        if (it.second == mx) ss.insert(it.first);
    }
    for (auto s : ss) cout << s << '\n';
}

Measured memory_bytes: 34688
#pragma GCC optimize ("O3")
#pragma GCC target("avx512f")
#pragma GCC optimize("unroll-loops")
#include <cstdio>
#define rep(i, n) for (int i = 0; i < n; i++)

int main() {
  unsigned int N, a[200000], b[200000], ans = 0;
  scanf("%u", &N);
  rep(i, N) scanf("%u", &a[i]);
  rep(i, N) scanf("%u", &b[i]);
  rep(i, N) rep(j, N) ans ^= a[i] + b[j];
  printf("%u\n", ans);
}

Measured memory_bytes: 3240
N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]
X = sorted(X, key = lambda x: x[1])

# a[i]はA[i]まで終わらせるためにかかる累積時間
a = [0] * N
a[0] = X[0][0]
for i in range(1, N):
	a[i] = a[i - 1] + X[i][0]

for j in range(N):
	if a[j] > X[j][1]:
		print("No")
		exit()
print("Yes")


Measured memory_bytes: 93912
#include <bits/stdc++.h>
#include <stdio.h>
#define ll long long
#define fr(i,p,n) for(ll i=p;i<n;i++)
#define fr1(i,p,n) for(ll i=p;i>=n;i--)
#define FAST ios::sync_with_stdio(0);
#define sz(v) (ll)v.size()
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define PI 3.14159265358979323846
#define mod 1000000007
#define mod1 998244353
#define precise cout << std::setprecision(12) << std::fixed;
#define endl "\n"
using namespace std;

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    FAST
    int t=1;
    //cin>>t;
    while(t--)
    {
        ll n,W;
        cin>>n>>W;
        ll w[n],v[n];
        fr(i,0,n) cin>>w[i]>>v[i];
        ll dp[n+1][W+1];
        fr(i,0,n+1)
        {
            fr(j,0,W+1)
            {
                if(i==0 || j==0) dp[i][j]=0;
                else if(j-w[i-1]>=0)
                {
                    dp[i][j]=max(dp[i-1][j],v[i-1]+dp[i-1][j-w[i-1]]);
                }
                else dp[i][j]=dp[i-1][j];
            }
        }
        cout<<dp[n][W]<<endl;
    }
    return 0;
}


Measured memory_bytes: 82384
from sys import stdin, setrecursionlimit


def gcd(x, y):
    if x % y == 0:
        return y
    return gcd(y, x % y)


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a = [a[i] // 2 for i in range(n)]
    a = list(set(a))
    n = len(a)
    lcm = 1
    for i in range(n):
        lcm = lcm * a[i] // gcd(lcm, a[i])
    for i in range(n):
        if (lcm // a[i] % 2) == 0:
            print(0)
            exit()
    ans = m // lcm
    print(ans - ans // 2)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


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

long long A[4], N;

int main() {
	cin >> A[0] >> A[1] >> A[2] >> A[3] >> N;
	for (int i = 1; i < 4; i++) A[i] = min(A[i], 2LL * A[i - 1]);

	cout << (N % 2)*A[2] + (N / 2)*A[3] << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{
    string s;
    cin >> s;
    rep(i,2){
        if(s[i] == s[i+1] && s[i+1] == s[i+2]){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3728
import std.conv, std.functional, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


enum INF = 10L^^18;

long getCost(long a, int j) {
  if (j == 0 || j == 4) {
    return a;
  } else if (j == 1 || j == 3) {
    if (a == 0) {
      return 2;
    }
    if (a % 2 == 0) {
      return 0;
    }
    return 1;
  } else if (j == 2) {
    if (a % 2 == 1) {
      return 0;
    }
    return 1;
  } else {
    assert(false);
  }
}

int L;
long[] A;

void main() {
  try {
    for (; ; ) {
      L = readInt();
      A = new long[L];
      foreach (i; 0 .. L) {
        A[i] = readLong();
      }
      
      auto dp = new long[][](L + 1, 5);
      foreach (i; 0 .. L + 1) {
        dp[i][] = INF;
      }
      dp[0][] = 0;
      foreach (i; 0 .. L) {
        foreach (j; 0 .. 5) {
          chmin(dp[i + 1][j], dp[i][j] + getCost(A[i], j));
        }
        foreach (j; 0 .. 4) {
          chmin(dp[i + 1][j + 1], dp[i + 1][j]);
        }
      }
      writeln(dp[L][4]);
    }
  } catch (EOFException e) {
  }
}

Measured memory_bytes: 23036
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();int count=n;
        for(int i=0;i<=n;i++){
            int t=i;
            int c=0;
            while(t>0){
                c+=t%6;
                t/=6;
            }
            t=n-i;
            while(t>0){
                c+=t%9;
                t/=9;
            }
            count=Math.min(count,c);
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 22996
#include <stdio.h>

double zenka(double q)
{
    double x=q/2;
    
    while(x*x*x-q>=0.00001*q || x*x*x-q<=-0.00001*q)
    {
        x=x-((x*x*x)-q)/(3*x*x);
    }
    
    return x;
}

int main(void)
{
    int q;
    
    while(1)
    {
        scanf("%d",&q);
        if(q==-1) break;
        else
        {
            printf("%.6f\n",zenka(q));
        }
    }
    
    return 0;
}


Measured memory_bytes: 2732
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

LL N;

LL erase_bit(LL n, LL m)
{
	LL upper = (n >> (m + 1)) << m, lower = n % (1LL << m);
	return upper + lower;
}

LL push_bit(LL n, LL m, LL k)
{
	LL upper = (n - n % (1LL << m)) << 1, lower = n % (1LL << m);
	return upper + k * (1LL << m) + lower;
}

std::vector<LL>f(LL a, LL b, LL c)
{
	if (c == 1) return std::vector<LL>{a, b};

	LL diff_bit;
	std::vector<LL>res;
	rep(i, N)
	{
		if (((a ^ b) >> i) & 1)
		{
			diff_bit = i;
			break;
		}
	}
	auto res1 = f(erase_bit(a, diff_bit), erase_bit(a, diff_bit) ^ 1, c - 1), res2 = f(erase_bit(a, diff_bit) ^ 1, erase_bit(b, diff_bit), c - 1);
	for (auto i : res1) res.push_back(push_bit(i, diff_bit, (a >> diff_bit) & 1));
	for (auto i : res2) res.push_back(push_bit(i, diff_bit, (b >> diff_bit) & 1));
	return res;
}

int main()
{
	LL A, B;
	in >> N >> A >> B;

	LL cnt1 = 0, cnt2 = 0;
	rep(i, N)
	{
		if ((A >> i) & 1) ++cnt1;
		if ((B >> i) & 1) ++cnt2;
	}
	if (cnt1 % 2 == cnt2 % 2)
	{
		out << "NO" << std::endl;
		return 0;
	}

	out << "YES" << std::endl;
	auto ans = f(A, B, N);
	rep(i, (1LL << N)) out << ans[i] << (i < (1LL << N) - 1 ? " " : "\n");
}


Measured memory_bytes: 2400
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int n;
    
    cin >> n;
    
    string s, t;
    
    cin >> s >> t;
    
    string out;
    for(int i = 0; i < n; ++i)
    {
        out += s[i];
        out += t[i];
    }
    
    cout << out << endl;
    
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	 public static void main(String args[]) {
         Scanner sc = new Scanner(System.in);
         double a = sc.nextDouble();
         double b = sc.nextDouble();
         double c = Math.toRadians(sc.nextDouble());
         double s = a * b * Math.sin(c) / 2;
         double l = (a + b + Math.sqrt(a * a + b * b - 2 * a * b * Math.cos(c)));
         double h = b * Math.sin(c);
         System.out.println(s);
         System.out.println(l);
         System.out.println(h);    
	 }
}



Measured memory_bytes: 27900
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>
#include <ios>
#include <iomanip>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define print(x) cout<<(x)<<'\n'
#define print_vec(v) rep(i,v.size()){if(i!=0)cout<<" ";cout<<v[i];}cout<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";rep(i,v.size())cout<<" "<<v[i];cout<<'\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007 //10^9+7
#define fi first
#define sc second
using ll=long long;
using pi=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
using vstr=vector<string>;

void solve() {
    int n,m;
    cin >> n >> m; 
    vi c(m);
    rep(i,m) cin >> c[i];
    // dp[i] : 合計 i 円にしたときの最小枚数
    int dp[n+1];
    rep(i,n+1) dp[i] = n;
    dp[0] = 0; dp[1] = 1;

    rng(i,2,n+1){
        rep(j,m){
            if(c[j]>i){
                // dp[i] = dp[i-1]+1;
                continue;
            }else{
                dp[i] = min(dp[i], min(dp[i-1]+1, dp[i-c[j]]+1));
            }
        }
    }
    print(dp[n]);
}
 
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
    //int q; cin >> q;
	//while (q--)
		solve();
    return 0;
}


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

using namespace std;

#define MAX 100
#define INF (1<<29)

int N, cost[MAX][MAX];

int get_sat(set<int> &inv)
{
    int sat = 0;
    for (auto &i: inv) {
        int s = INF;
        for (auto &j: inv) {
            if (i == j) continue;
            s = min(s, cost[i][j]);
        }
        sat += s;
    }
    return sat;
}

map<set<int>, int> memo;

int dfs(set<int> inv)
{
    int res = 0;
    if (memo.count(inv) > 0) {
        return memo[inv];
    }
        
    if (inv.size() >= 2) {
        res = get_sat(inv);
    }
    for (int i = 0; i < N; i++) {
        bool ok = 1;
        for (auto &j: inv) {
            if (cost[i][j] == 0) {
                ok = 0;
                break;
            }
        }
        if (ok) {
            set<int> ninv = inv;
            ninv.insert(i);
            res = max(res, dfs(ninv));
        }            
    }
    return (memo[inv] = res);
}

int main()
{
    int M, a, b, c;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> a >> b >> c;
        a--; b--;
        cost[a][b] = cost[b][a] = c;
    }    
    cout << dfs(set<int>()) << endl;
    return 0;
}

Measured memory_bytes: 10044
import java.util.*;
import java.io.*;

class Main{
  public static void main(String arg[])throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    long m = (long)1e9 + 7;
    ArrayList <Integer> graph[] = new ArrayList[n];
    for(int i=0;i<n;i++)
      graph[i] = new ArrayList<Integer>();
    
    for(int i=0;i<n-1;i++){
      String inps[] = br.readLine().split(" ");
      int x = Integer.parseInt(inps[0]) - 1;
      int y = Integer.parseInt(inps[1]) - 1;
      graph[x].add(y);
      graph[y].add(x);
    }
    boolean traversed[] = new boolean[n];
    Node root = dfs(0,graph,m,traversed);
    System.out.println((root.b + root.w)%m);
    
  }
  static Node dfs (int curr, ArrayList <Integer> graph[], long m, boolean trav[]){
    //if(trav[curr]) return new Node(-1,0,0);
    long curr_b = 1;
    long curr_w = 1;
    trav[curr] = true;
    for(int j=0;j<graph[curr].size();j++){
      if(!trav[graph[curr].get(j)]){
        Node child = dfs(graph[curr].get(j), graph,m,trav);
        curr_b = (curr_b * child.w) %m;
        curr_w = (curr_w * (child.w + child.b)) % m;
      }
    }
    return new Node(curr,curr_b, curr_w);
  }
      
}
class Node{
  long b;
  long w;
  int ind;
  public Node(int i,long bl,long wh){
    ind  = i;
    b = bl;
    w = wh;
  }
}

Measured memory_bytes: 75956
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;

#define int long long

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,x,...) x
#define REP1(i, s, cond, cal) for (signed i = signed(s); i cond; i cal)
#define REP2(i, s, n) REP1(i, s, < signed(n), ++)
#define REP3(i, n) REP2(i, 0, n)
#define rep(...) CHOOSE((__VA_ARGS__,REP1,REP2,REP3))(__VA_ARGS__)
#define rrep(i, s) rep(i, s, >= 0, --)

#define all(c) begin(c), end(c)
template<typename T>bool maxup(T& a, T&& b) { if (a < b) { a = b; return true; }; }
template<typename T>bool maxup(T& a, T& b) { if (a < b) { a = b; return true; }; }
template<typename T>bool minup(T& a, T&& b) { if (a > b) { a = b; return true; }; }
template<typename T>bool minup(T& a, T& b) { if (a > b) { a = b; return true; }; }

#define X first
#define Y second

using VV = vector<vector<int>>;
using V = vector<int>;
using P = pair<int, int>;
using IP = pair<int, P>;

template<typename T>
inline void input(vector<T>& v) { for (auto& x : v) cin >> x; }
signed main() {
	string a, b, c; cin >> a >> b >> c;
	cout << a[0] << b[0] << c[0] << endl;
	system("pause");
}

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

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

int main()
{
    int n;
    cin >> n;
    int cont = 0, aux;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            aux = gcd(i,j);
            for (int k = 1; k <= n; k++)
            {
                cont+=gcd(aux,k);
            }
        }
    }

    cout<<cont<<endl;

    return 0;
}

Measured memory_bytes: 3608
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>
#include <functional>
//#include <boost/multiprecision/cpp_int.hpp>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)
#define llrep(i, n) for(ll i = 0; i < n; ++i)
#define llREP(i, m, n) for(ll i = m; i < n; ++i)
#define llrrep(i,n) for(ll i = n; i >= 0; --i)
#define llRREP(i, m, n) for(ll i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;
using pil = std::pair<int, long long>;
using pli = std::pair<long long, int>;
using plpii = std::pair<long long, std::pair<int, int>>;
using pdd = std::pair<double, double>;

const long long INF = 1000000000000000001;
const long long _MOD = 1000000007;
const long long MOD = 998244353;
const int ALPHABET = 27;
const double pi = 3.14159265358979;

using namespace std;
//namespace mp = boost::multiprecision;

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

	int n, k;
	cin >> n >> k;
	int* a = new int[n];
	rep(i, n) cin >> a[i];

	int* l = new int[n];
	int* r = new int[n];

	rep(count, k) {
		rep(i, n) {
			l[i] = i - a[i];
			r[i] = i + a[i];
		}
		sort(l, l + n);
		sort(r, r + n);

		rep(i, n) {
			a[i] = l + n - upper_bound(l, l + n, i);
			a[i] += lower_bound(r, r + n, i) - r;

			a[i] = n - a[i];
		}

		bool flag = 1;
		rep(i, n) {
			if (a[i] != n) {
				flag = false;
				break;
			}
		}
		if (flag) {
			break;
		}
	}

	rep(i, n) {
		cout << a[i] << " ";
	}
	cout << "\n";

	return 0;
}

Measured memory_bytes: 6032
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
  int n,i=0,s[10000],flag=0,maxi=0,a,b,j,temp=0,te=0;
  cin>>n;
  for(i=0;i<n;i++)
  {
      scanf("%d",&s[i]);
  }
  for(i=0;i<n;i++)
    for(j=i+1;j<n;j++)
  {
      temp=s[i]*s[j];
      if(temp<10)
      {
          if(maxi<temp) maxi=temp;
      }
      else{  te=temp;
      while(temp!=0)
      {   a=temp%10;
          temp/=10;
          if(temp==0) break;
          if((a-1)==temp%10) flag=1;
          else {flag=0;break;}
      }
      if(flag)
      {
          if(maxi<te) maxi=te;
      }
      }
  }
  if(maxi==0) puts("-1");
  else
  printf("%d\n",maxi);
 return 0;
}

Measured memory_bytes: 3244
#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    int max_income;
    unordered_map<string, int> umap;
    string str;

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

        if (umap.count(str)){
            umap[str] += 1;
        }
        else{
            umap[str] = 1;
        }
    }

    cin >> M;
    for (int i = 0; i < M; ++i){
        cin >> str;

        if (umap.count(str)){
            umap[str] -= 1;
        }
        else{
            umap[str] = -1;
        }
    }

    max_income = 0;
    for(auto itr = umap.begin(); itr != umap.end(); ++itr){
        max_income = max(max_income, itr->second);
    }

    cout << max_income << "\n";

    return 0;
}


Measured memory_bytes: 256
#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <iomanip>
#include <utility>
#include <cstdlib>
#include <sstream>
#include <bitset>
#include <vector>
#include <cstdio>
#include <ctime>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;

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

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define sz size()

const double EPS = 1e-10;
const int INF = 100000000;

int main(){
    int n,a,b,c,x;
    while(cin>>n>>a>>b>>c>>x){
        if(n==0 && a==0 && b==0 && c==0 && x==0)break;
        int num=0;
        vi y;
        rep(i,n){
            int tmp;
            cin>>tmp;
            y.pb(tmp);
        }
        
        int count=0;
        while(1){
            count++;
            if(y[num]==x){
                num++;
                if(num>=n){
                    cout<<count-1<<endl;
                    break;
                }
            }
            x=(a*x+b)%c;
            if(count>=10001){
                cout<<"-1"<<endl;
                break;
            }
        }

    }
    
    return 0;
}

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

int main(){
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  //大文字ー小文字の文字コード差 = 32
  s.at(k-1) += 32;
  cout << s << endl;
  return 0;
}

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

using namespace std;

#define int long long
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define INF 1e9
#define LINF 1e18

typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> Pi;
typedef pair<P, P> PP;

const int MOD = 1e9 + 7;
const int dy[]={0, 0, 1, -1};
const int dx[]={1, -1, 0, 0};

template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

int m[101];

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

    int n, x;
    cin >> n >> x;
    int mini = INF;
    rep(i, n) {
        cin >> m[i];
        x -= m[i];
        chmin(mini, m[i]);
    }
    cout << n + x / mini << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int func(string s,string t){
	bool a[26],b[26];
	fill(a,a+26,false);
	fill(b,b+26,false);
	rep(i,s.size())a[(int)(s[i]-'a')]=true;
	rep(i,t.size())b[(int)(t[i]-'a')]=true;
	int res=0;
	rep(i,26)res+=(int)(a[i]&b[i]);
	return res;
}

int main(){
	string s;
	int n;
	cin>>n;
	cin>>s;
	int ans=0;
	loop(i,1,s.size()){
		int tmp=func(s.substr(0,i),s.substr(i,s.size()));
		ans=max(ans,tmp);
	}
	cout<<ans<<endl;
	return 0;
}

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

string s;

int solve ()
{
	int cnt = 0;
	char last = '-';

	for (int i = 0; i < s.size(); i++)
		if (s[i] != last)
		{
			last = s[i];
			cnt++;
		}

	return cnt - 1;
}

int main ()
{
	cin >> s;

	cout << solve() << '\n';

	return 0;
}

Measured memory_bytes: 512
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define F first
#define S second
#define ld long double
#define built __builtin_popcountll
#define mst(a,i) memset(a,i,sizeof(a))
#define all(x) x.begin(),x.end()
#define itit(it,a) for(auto it=(a).begin(); it!=(a).end(); it++)
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define repr(i,a,b) for(ll i=a; i>b; i--)
#define reprr(i,a,b) for(ll i=a; i>=b; i--)
#define pi 3.14159265358979323846264338327950288419716939937510582097494459230
ll max3(ll x,ll y,ll z) {return max(max(x,y),z);}
ll min3(ll x,ll y,ll z) {return min(min(x,y),z);}
const ll N=1e5+10,M=2e5+10,M2=1e6+10,mod=1e9+7,inf=1e17+10;
const int INF=1e9+7;
void add(int& a, int b) {a+=b;if(a>=mod){a-=mod;}}

#define trace(...) cerr<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
    cerr<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
    const char *comma=strchr(names+1,',');
    cerr.write(names,comma-names)<<" : "<<arg1<<" | ";
    __f(comma+1,args...);
}

int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
//assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
ll power(ll x,ll n){ll result=1;while(n>0){if(n%2==1)result=(result*x)%mod; x=((x%mod)*(x%mod))%mod;n=n/2;}return result;}


int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin >> n >> k;
    int p[n+1];
    int pref[n+1]={0};
    rep(i,1,n+1){
        cin >> p[i];
    }
    rep(i,1,n+1) pref[i]=pref[i-1]+p[i];
    ld maxi=0;
    for(int i=k; i<=n; i++){
        maxi=max(maxi,(ld)(pref[i]-pref[i-k]+k));
    }
    cout << fixed << setprecision(20) << 1.0*maxi/2;
    return 0;
}


Measured memory_bytes: 3456
#include<iostream>
#include<vector>
#include <math.h>
using namespace std;
using ll = long long;
int main() {
    int n;
    cin >> n;
    ll add_one = 0, add_two = 0;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    for(int i = 0; i < n; i++){
        if(a[i] > b[i])
            add_one += a[i] - b[i];
        if(a[i] < b[i])
            add_two +=(b[i] - a[i]) / 2;
    }
    cout << (add_one  <= add_two ? "Yes" : "No") << endl;
}


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

int main()
{
  	int n,d;
  cin>>n>>d;
  int ct=0;
  for(int i=0;i<n;i++)
  {
    	int x,y;
    cin>>x>>y;
    if(pow(y,2)+pow(x,2)<=pow(d,2))
      ct++;
  }
  
  cout<<ct<<endl;
}

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

int main() {
  int a, b;
  cin >> a >> b;
  
  char ans;
  if(a + b == 15) ans = '+';
  else if(a * b == 15) ans = '*';
  else ans = 'x';
  
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main
{

    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        int W = scan.nextInt();
        int H = scan.nextInt();
        String c = scan.next();
        int s = 1;
        int k = 1;

        for (int i = 0; i != H; i++) {
            for (int y = 0; y != W; y++) {
                if (s == 1 && k == 1 || s == 1 && k == H || s == W && k == 1 || s == W && k == H) {
                    System.out.print("+");

                } else if (H - (H / 2) == k && W - (W / 2) == s) {
                    System.out.print(c);

                } else if (k == H || k == 1) {

                    System.out.print("-");
                } else if (s == W || s == 1) {
                    System.out.print("|");

                } else {
                    System.out.print(".");

                }

                s++;

            }
            System.out.println();
            s = 1;
            k++;

        }

    }
}



Measured memory_bytes: 26216
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) (v).begin(),(v).end()
typedef pair<int, int> P;
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const ll MOD = 1e9+7;

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

    double ans;
    if (N%2) ans = (double) ((int)N/2 + 1) / N;
    else ans = 0.5;

	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
H, W, K = list(map(int, input().split()))

c = [list(input()) for i in range(H)]

cnt = 0
for i in range(2**H):
    for j in range(2**W):
        cnt_black = 0
        for k in range(H):
            if (i >> k) & 1:
                continue
            for l in range(W):
                if (j >> l) & 1:
                    continue
                if c[k][l] == '#':
                    cnt_black += 1
        if cnt_black == K:
            cnt += 1

print(cnt)

Measured memory_bytes: 9144
#include <iostream>
#include <algorithm>
#include <math.h> 
#include <string>
#include <iomanip>
#include <queue>
using namespace std;
int main() {
	int n;
    cin >> n;
    bool a = false;
    for(int i = 0; i <= n/4; i++){
        for(int j = 0; j <= n/7; j++){
            if(4*i + 7*j == n) a = true;
        }
    }

    if(a == true) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

#define bit(b, i) (((b) >> (i)) & 1)

LL n, a[200000], b[20][200000], ans;

int main() {
	cin >> n;
	inc(i, n) { cin >> a[i]; }
	
	inc(k, 20) {
		int p = n;
		dec(i, n) {
			b[k][i] = p;
			if(bit(a[i], k)) { p = i; }
		}
	}
	
	inc(i, n) {
		LL mi = n;
		inc(k, 20) {
			if(bit(a[i], k)) {
				setmin(mi, b[k][i]);
			} else {
				LL l = b[k][i];
				if(l < n) { l = b[k][l]; }
				setmin(mi, l);
			}
		}
		ans += (mi - i);
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 33024
S = list(map(int, input().rstrip()))

plan_0 = [i % 2 for i in range(len(S))]
plan_1 = [i % 2 for i in range(1, len(S)+1)]

x = sum([(plan_0[i] - S[i]) != 0 for i in range(len(S))])
y = sum([(plan_1[i] - S[i]) != 0 for i in range(len(S))])

print(min(x, y))

Measured memory_bytes: 6304
from bisect import bisect_left as bl
from bisect import bisect_right as br

n = int(input())
alst = [float(input()) for _ in range(n)]
sorted_alst = sorted(alst)
for a in alst:
  li = bl(sorted_alst, a)
  ri = br(sorted_alst, a)
  print(li * 3 + (ri - li - 1))


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

int main(){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  
  if (a + b > c + d) cout << "Left" << endl;
  else if (a + b < c + d) cout << "Right" << endl;
  else cout << "Balanced" << endl;  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#include <cstdlib> 
#include <math.h>
#include<cstdio>
#include<cstring>
#define FOR(I, A, B) for (ll I = (A); I <= (B); I++)
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fo(i,n) for(ll i=0;i<n;i++)
#define sz(a) ll((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(auto i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define dbg(x) cout << #x << " = " << x << endl
#define dbg2(x,y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define dbg3(x,y,z) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl
#define dbg4(x,y,z,q) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #q << " = " << q << endl
#define scan(char_array) scanf("%[^\n]s",&char_array);
const ll MOD=1000000007;
int main(){
	ll n,k;
	cin>>n>>k;
	ll our=1;
	FOR(i,1,100){
		our=(our*10)%MOD;

	}
	ll pre1[n+1];
	ll pre2[n+1];
	pre1[0]=0;
	FOR(i,1,n){
		pre1[i]=(pre1[i-1]+i)%MOD;
	}
	pre2[n]=n;
	for(ll j=n-1;j>=0;j--){
		pre2[j]=(pre2[j+1]+j)%MOD;
	}

	
    ll ans=0;
    ll aa,bb;
    ll cc;
    FOR(i,k,n+1){
    	aa=pre1[i-1];
    	bb=pre2[n-i+1];
    	//dbg2(aa,bb);
    	cc=(bb-aa+1+MOD)%MOD;
    	ans=(ans+cc)%MOD;


    }
    cout<<ans<<endl;






	

}

Measured memory_bytes: 6716
n=int(input())
a=[]
for i in range(n):
    a.append(list(map(int, input().split())))
a.sort(key=lambda x:(-x[2],x[0]+x[1]))
for i in range(101):
    for j in range(101):
        ansh=[0]*n
        for k,(x,y,h) in enumerate(a):
            ansh[k]=h+abs(i-x)+abs(j-y)
            if h==0:ansh[k]=min([ansh[k],max(ansh[:k])])
        if len(set(ansh))==1:
             print(i,j,ansh[1])

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

int main(){
	int a,b; cin>>a>>b;
	bool flg=false;
	if(a%3==0) flg=true;
	if(b%3==0) flg=true;
	if((a+b)%3==0) flg=true;
	if(flg) cout<<"Possible"<<endl;
	else cout<<"Impossible"<<endl;
}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define pi 2.0*acos(0.0)
#define INTM 1e18
#define mod 1e9+7
#define FOR(i,j,n)    for(ull i=j;i<n;i++)
#define RFOR(i,j,n)    for(ll i=j;i>=n;i--)

typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;

int main(){
    ull n;
    cin>>n;
    ull ans = 0;
    if(n & 1) {cout<<0<<endl; return 0;}
    while(n/5){
        ull ops = n/5;
        ans += (ops/2);
        n /= 5;
    }
    cout<<ans<<endl;
}


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

long long c;
long long v[100000];
int n;
long long x[100000];
long long d[100000];

long long solve() {
	long long ans = 0;
	long long curr = 0;
	for (int i = 0; i < n; i++) {
		curr += v[i];
		ans = max(ans, curr - x[i]);
	}
	return ans;
}

long long solve1() {
	set<pair<long long, int> > st;
	long long curr = 0;
	for (int i = 0; i < n; i++) {
		curr += v[i];
		d[i] = curr - x[i];
		st.insert({-d[i], i});
	}
	long long ans = 0;
	long long sum = 0;
	for (int i = n - 1; i > 0; i--) {
		sum += v[i];
		st.erase({-d[i], i});
		ans = max(ans, sum + (-(st.begin()->first)) - 2 * (c - x[i]));
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> n >> c;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> v[i];
	}
	
	long long ans = 0;
	ans = max(ans, solve());
	ans = max(ans, solve1());
	
	reverse(v, v + n);
	reverse(x, x + n);
	for (int i = 0; i < n; i++) {
		x[i] = c - x[i];
	}
	ans = max(ans, solve());
	ans = max(ans, solve1());
	cout << ans;
	
	return 0;
}

Measured memory_bytes: 8832
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <vector>
#include <stdio.h>
#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <bitset>
#include <set>
#include <map>
#include <random>
#include <time.h>
#include <cassert>

#define prev askdnsajd
#define rank asasdmdnasd
#define next lsjndajbs
#define hash asmdklansd
#define index asdklnas
#define right sld
#define left sldl
using namespace std;

typedef long long ll;
typedef long double dbl;

template<class T>
void print(vector<T> s){
    for (T x : s)
        cout << x << " ";
    cout << endl;
}

const int mod = 1e9 + 7;
const int maxn = 1e5 + 7;

int color[maxn];
vector<int> s[maxn];

ll dfs(int v, int k, bool ok){
	color[v] = 1;
	ll answer = 1, cnt = 0;
	for (int u : s[v]){
		if (color[u] == 0){
			answer = answer * dfs(u, k, true) % mod;
			cnt++;
		}
	}
	if (ok)
		for (ll i = 0; i < cnt; i++)
			answer = answer * (k - 2 - i) % mod;
	else
		for (ll i = 0; i < cnt; i++)
			answer = answer * (k - 1 - i) % mod;
	return answer;
}

int main(){
    srand(17);
    ios_base::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; i++){
    	int a, b;
    	cin >> a >> b;
    	s[a - 1].push_back(b - 1);
    	s[b - 1].push_back(a - 1);
    }
    cout << k * dfs(0, k, false) % mod << endl;
    return 0;
}


Measured memory_bytes: 12032
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[][] A = new int[n][m];
        int[] b = new int[m];
        int[] Ab = new int[n];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                A[i][j] = sc.nextInt();
            }
        }
        for(int i=0;i<m;i++){
            b[i] = sc.nextInt();
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                Ab[i] += A[i][j]*b[j];
            }
            System.out.println(Ab[i]);
        }
    }
}


Measured memory_bytes: 40280
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
if n == 1:
    print(0)
else:
    l = factorization(n)
    dic = []
    for i in range(len(l)):
        tmp = l[i][0]
        dic.append(tmp)
        while n >= tmp:
            tmp *= l[i][0]
            if n < tmp:
                break
            dic.append(tmp)
    dic.sort()
    cnt = 0
    while n != 1:
        flag = True
        for i in range(len(dic)):
            if n%dic[i] == 0:
                n //= dic[i]
                cnt += 1
                dic.pop(i)
                flag = False
                break
        if flag:
            break
    print(cnt) 

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

int main() {
  int N;
  cin >> N;
  vector<int> H(N);
  rep(i, N) cin >> H[i];
  int ans = 1;
  for (int i = 1; i < N; i++) {
    bool can = true;
    for (int j = 0; j < i; j++) {
      if (H[i] < H[j]) {
        can = false;
        break;
      }
    }
    if(can) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fastio     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define debug(x)   cerr<<#x<<": "<<x<<endl;
#define all(x)     (x).begin() , (x).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define endl       '\n'
#define MAX        1000000
typedef long long int ll;
using namespace std;

const ll mod = 1e9+7;


const double pi = acos(-1);

void solve(){
	int n;
	cin>>n;
	cout<<fixed<<setprecision(20);
	cout<<(2*n*pi);
}





int main(){
    fastio
    int test=1;
    while(test--)
        solve();
    return 0;
}


Measured memory_bytes: 3796
#include <cstdio>
using namespace std;
#define SQ(X) (X)*(X)
int main(void){
  int x,a,b;
  scanf("%d%d%d",&x,&a,&b);
  puts(SQ(x-a)<SQ(x-b)?"A":"B");
  return 0;
}
  

Measured memory_bytes: 128
import math

# inputList=[]
# for i in range(6):
#     inputNum = input()
#     inputList.append(inputNum)
inputa = input().split()
# inputb = input().split()

# inputa = [int(n) for n in inputa]
# inputa.sort()

a = int(inputa[0])
b = int(inputa[1])
# c = int(inputa[2])

# x = int(inputb[0])
# y = int(inputb[1])


print(int(bool(a%b)))


Measured memory_bytes: 38256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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

typedef long long ll;
typedef pair<ll, ll> p;


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  vector<int> x(5);
  rep(i, 5) cin >> x[i];
  rep(i, 5){
    if(x[i] == 0){
      cout << i + 1 << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 3632
import bisect
N,M,K=[int(s) for s in input().split()]
A=[int(s) for s in input().split()]
B=[int(s) for s in input().split()]
Asum=[0 for i in range(N+1)]
Bsum=[0 for i in range(M+1)]
for i in range(N):
  Asum[i+1]=Asum[i]+A[i]
for i in range(M):
  Bsum[i+1]=Bsum[i]+B[i]
ans=[0 for i in range(N+1)]
t=bisect.bisect_right(Bsum,K)-1
ans[0]=t
for i in range(1,N+1):
  if Asum[i]>K:
    break
  while Bsum[t]+Asum[i]>K:
    t-=1
  ans[i]=i+t
print(max(ans))
  



Measured memory_bytes: 48940
from sys import stdin

N = int(stdin.readline().rstrip())
B = [int(x) for x in stdin.readline().rstrip().split()]

impossible = False
A = []
match = -1

for i in range(N):
    for j in range(len(B)):
        if B[j] == j + 1:
            match = j
    if match == -1:
        impossible = True
        break
    else:
        A.append(B.pop(match))
        match = -1

if impossible:
    print(-1)
else:
    for i in range(N):
        print(A.pop(-1))


Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

namespace CSharp
{
    static class Program
    {
        static void Main(string[] args)
        {
            long h, w;
            ReadLong(out h, out w);
            long ans = h == 1 || w == 1 ? 1 : (h * w) / 2 + (h * w) % 2;
            Console.WriteLine(ans);
        }

        #region Helpers

        static int[] ReadIntArray() => Console.ReadLine().Split().Select(s => int.Parse(s)).ToArray();
        static long[] ReadLongArray() => Console.ReadLine().Split().Select(s => long.Parse(s)).ToArray();

        static int[] ReadLineIntArray(int count) => Enumerable.Repeat(0, count).Select(_ => int.Parse(Console.ReadLine())).ToArray();
        static long[] ReadLineLongArray(int count) => Enumerable.Repeat(0, count).Select(_ => long.Parse(Console.ReadLine())).ToArray();

        static string ReadString() => Console.ReadLine();
        static int ReadInt() => int.Parse(Console.ReadLine());
        static long ReadLong() => long.Parse(Console.ReadLine());

        static void ReadInt(out int first)
        {
            var array = ReadIntArray();
            first = array[0];
        }

        static void ReadInt(out int first, out int second)
        {
            var array = ReadIntArray();
            first = array[0];
            second = array[1];
        }

        static void ReadInt(out int first, out int second, out int third)
        {
            var array = ReadIntArray();
            first = array[0];
            second = array[1];
            third = array[2];
        }

        static void ReadInt(out int first, out int second, out int third, out int fourth)
        {
            var array = ReadIntArray();
            first = array[0];
            second = array[1];
            third = array[2];
            fourth = array[3];
        }

        static void ReadLong(out long first)
        {
            var array = ReadLongArray();
            first = array[0];
        }

        static void ReadLong(out long first, out long second)
        {
            var array = ReadLongArray();
            first = array[0];
            second = array[1];
        }

        static void ReadLong(out long first, out long second, out long third)
        {
            var array = ReadLongArray();
            first = array[0];
            second = array[1];
            third = array[2];
        }

        static void ReadLong(out long first, out long second, out long third, out long fourth)
        {
            var array = ReadLongArray();
            first = array[0];
            second = array[1];
            third = array[2];
            fourth = array[3];
        }

        #endregion
    }
}

Measured memory_bytes: 13268