akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.Scanner;

class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int i=1;
		int s;
		int[] data = new int[10000];
		while(true){
			s = scan.nextInt();
			if(s == 0){
				break;
			}
			else{
				data[i-1] = s;
			}
			i++;
		}
		for(int j=1; j<i; j++){
			System.out.println("Case " + j + ": " + data[j-1]);
		}
	}
}


Measured memory_bytes: 43652
#include <iostream>
#include <vector>
#include <limits>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <complex>
#include <iomanip>
#include <cassert>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <bitset>
#include <cstring>
#include <climits>
using namespace std;
#define nl '\n'
#define sp ' '
#define f first
#define s second
#define boost() cin.tie(0); cout.tie(0); cin.sync_with_stdio(0)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 21; // REMEMBER TO CHANGE
const int MOD = 1e9+7;
int N, dp[1<<MAXN];
bool mat[MAXN][MAXN];
int main(){
	boost();
	cin >> N;
	for(int i = 0;i<N;i++){
		for(int j = 0;j<N;j++){
			cin >> mat[i][j];
		}
	}
	dp[0] = 1;
	for(int mask = 0;mask<(1<<N);mask++){
		int paired = __builtin_popcount(mask);
		for(int i = 0;i<N;i++){
			if(mat[paired][i]&&!(mask&(1<<i))){
				int newmask = mask|(1<<i);
				dp[newmask] = (dp[newmask]+dp[mask])%MOD;
			}
		}
	}
	cout << dp[(1<<N)-1] << nl;
	return 0;
}

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

namespace fastIO {
	template<typename T> inline void read(T &x) {
		register char c = getchar();
		register bool flag = 0;
		while (!isdigit(c)) {
			flag |= c == '-';
			c = getchar();
		}
		x = c - '0';
		c = getchar();
		while (isdigit(c)) {
			x = x * 10 + c - '0';
			c = getchar();
		}
		if (flag) {
			x = -x;
		}
	}
}
using namespace fastIO;

int n;
vector<int> adj[100010];

int dfs(int x, int pre) {
	int adjx_size = adj[x].size(), ret = 0;
	for (int i = 0; i < adjx_size; ++i) {
		int y = adj[x][i];
		if (y != pre) {
			ret ^= dfs(y, x) + 1;
		}
	}
	return ret;
}

int main() {
	read(n);
	for (int i = 1; i < n; ++i) {
		int x, y;
		read(x), read(y);
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	puts(dfs(1, 0) ? "Alice" : "Bob");
}

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

int main(){
    long long n;
    cin >> n;
    long long mx = -1;
    int ans = 0;
    for(long long i=1; i<=sqrt(n); i++)
    {
        mx = max(std::__gcd(n, i),mx);
    }
    if(n%mx==0) mx = max(n/mx, mx);
    if(mx == 1) mx = max(n, mx);

    while(mx>0){
        mx = (mx - mx % 10) / 10;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
open System

let rot n (c: char) =
    int c
    |> (+) n
    |> function
        | c when c > 90 -> (c - 90) + 64
        | c -> c
    |> char 

[<EntryPoint>]
let main _ =
    let n = Console.ReadLine() |> Int32.Parse
    Console.ReadLine()
    |> Seq.map (rot n >> string)
    |> String.concat ""
    |> printfn "%s"
    0

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

using Int = long long int;
using UInt = unsigned long long int;

int main(void) {
    int a, b, c;
    cin >> a >> b >> c;
    if (c >= a && c <= b) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<cctype>
#include<cstring>
#include<list>
#include<map>
#include<sstream>
#include<set>
#include<string>
#include<vector>
typedef long long ll;
using namespace std;
#define MN 300005
#define MM 600005
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define F2(i,a,b) for(int i=a;i<(b);++i)
#define RF(i,a,b) for(int i=a;i>=(b);--i)
#define fast  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
int main()
{
   long long n,m;
   cin>>n>>m;
   cout<<min(n%m,m-(n%m))<<endl;
   return 0;
}


Measured memory_bytes: 256
#include "iostream"
#include "vector"
#include "string"
#include "algorithm"
#include "math.h"
 
using namespace std;
typedef long long ll;
 
ll power_int(ll a, int b)
{
  ll x = 1;
  while (b > 0)
  {
    x *= a;
    b--;
  }
  return x;
}
 
vector<int> decompPrimeMatrix(ll n)
{
  const int SIZE = 1000010;	//ここは変える
  vector<int> ans(SIZE);
  ll i = 2;
  while (i < SIZE)
  {
    if (n == 1)
    {
      break;
    }
    if (n % i == 0)
    {
      ans[i]++;
      n /= i;
    }
    else
    {
      i++;
    }
  }
  return ans;
}
 
int main()
{
  ll n, p;
  ll ans = 1;
  cin >> n >> p;
  if (n == 1)
  {
    cout << p << "\n";
  }
  else
  {
    vector<int> v = decompPrimeMatrix(p);
    for (int i = 1; i < 1000010; i++)
    {
      ans *= power_int(i, (v[i] / n));
    }
    cout << ans << "\n";
  }
}

Measured memory_bytes: 4096
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。
string upper(string str);       // 英字を大文字に変換する。
string lower(string str);       // 英字を小文字に変換する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define pb            push_back
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())
#define rvsort(v)     sort(rall((v)))
#define vi            vector<int>
#define GCD(a,b)      __gcd((a),(b))
#define LCM(a,b)      (a)/GCD((a),(b))*(b)

const int INF = 1e9;

// code
// ------------------------------------------------
int main() {

  int n,k;

  cin >> n >> k;
  int i = 0;
  while(1)
  {
    n /= k;
    i++;
    if(n == 0)
      break;    
  }
  
  cout << i;


  return 0;
}

// funcの実体
// ------------------------------------------------
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

string upper(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(97 <= *itr && *itr <= 122)
    {
      *itr = *itr - 32;
    }
  }
  return str;
}

string lower(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(65 <= *itr && *itr <= 90)
    {
      *itr = *itr + 32;
    }
  }
  return str;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){

	long long N,K,X,Y,total;
  	scanf("%lld%lld%lld%lld",&N,&K,&X,&Y);
  	if(N>K){
  		total=(K*X)+(N-K)*Y;
    }
    if(K>=N){
    	total=N*X;
    }
  	printf("%lld\n",total);
  	return 0;
}


Measured memory_bytes: 1724
import java.util.*;
 
public class Main {
  public static void main (String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    int ans = K;

    for(int i = 1 ; i < N ; i++){
      ans = ans * (K - 1);
    }

    System.out.println(ans);
  }
}

Measured memory_bytes: 21972
#include<iostream>
#include<string.h>
using namespace std;
int n,i;
long long m,a,r,c,h;
string s[100000];
int main()
{ 
  cin >> n;
  for(i=0;i<n;i++){
    cin >> s[i];
    if(strncmp("M",&s[i][0],1)==0) {m++;
                                 }
    if(strncmp("A",&s[i][0],1)==0) {a++;
                                 }
    if(strncmp("R",&s[i][0],1)==0) {r++;
                                 }
    if(strncmp("C",&s[i][0],1)==0) {c++;
                                 }
    if(strncmp("H",&s[i][0],1)==0) {h++;
                                 }
  }
  printf("%lld",m*a*r+m*a*c+m*a*h+m*r*c+m*r*h+m*c*h+a*r*c+a*r*h+a*c*h+r*c*h);
}

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

int main() { 
  int d, n;
  cin >> d >> n;
  if(n == 100) n++;
  if(d == 0){
    cout << n << endl;
  }else if (d == 1){
    cout << 100*n << endl;
  }else{
    cout << 10000*n << endl;
  }

}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
const long long INF = LLONG_MAX / 2;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i,r,n) for(ll int i = (ll)(r); i < (ll)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ll long long int
#define ALL(x) x.begin(),x.end()
using namespace std;
ll ans = 0, sum = 0, n, k, counter = 0, w, h;
string s;
vector<ll> v;
vector < pair<ll, ll > > vp;
vector<vector<ll> > vv(50, vector<ll>(50, INF));
vector<string> vs;

/*--------------------template--------------------*/


int main() {
	ll a, b, c, d, e;
	cin >> a >> b >> c;
	d = b / c;
	if (c == 1) {
		 e= b - a + 1;
	}else if (a%c == 0) {
		e = d + 1 - a / c;
	}
	else {
		e = d - a / c;
	}
	ans = e;
	cout << ans << endl;
}

Measured memory_bytes: 256
from sys import stdin

D, N = map(int, stdin.readline().rstrip().split())

if D == 0:
    if N == 100:
        print(101)
    else:
        print(N)
elif D == 1:
    if N == 100:
        print(10100)
    else:
        print(100*N)
elif D == 2:
    if N == 100:
        print(1010000)
    else:
        print(10000*N)
    


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

int main() {

    double A, B, H, M;
    cin >> A >> B >> H >> M;
    double ax, ay, bx, by;
    double pi = M_PI;
    double atheta = pi/2 - 2*pi*((60.0*H + M)/(12.0*60.0));
    double btheta = pi/2 - 2*pi*(M/60.0);
    ax = A * cos(atheta);
    ay = A * sin(atheta);
    bx = B * cos(btheta);
    by = B * sin(btheta);
    
    cout << setprecision(20) << sqrt(pow(ax-bx,2) + pow(ay-by,2)) << endl;
}




Measured memory_bytes: 4124
#include<stdio.h>
int main()
{
   int n,a,b,r,i=1;
   scanf("%d",&n);
   scanf("%d %d",&a,&b);

   for(i=1; i<=b; i++)
   {
       r=n*i;
       if(r>b)
       {
           r = r-n;
           break;
       }
   }
   if(r>=a && r<=b)
    printf("OK");
   else
    printf("NG");
    return 0;
}


Measured memory_bytes: 1728
#include<stdio.h>
int main(void)
{
	int a,i,n,s,x,max,min;       
	scanf("%d",&n);
	while(n!=0) {
		a=0;
		max=0; min=10000;
		for(i=1;i<=n;i++) {
			scanf("%d",&s);
			if(s>max) {
				max=s;
			}
			if(s<min) {
				min=s;
			}
			a+=s;
		}
		x=(a-max-min)/(n-2);
		printf("%d\n",x);
	scanf("%d",&n);
	}
	return 0;
}

Measured memory_bytes: 600
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
 
typedef long long ll;
 
 
int main(){
	string s,t;
	cin >>s;
	cin >> t;
	
	int res = 0;
	for(int i=0;i<3;++i){
		if(s[i] == t[i] ) res++;
	}
	cout << res <<endl;
	
	
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
 
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;
 
#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second
 
int main(int argc, char **argv) {
	int a, b;
	cin >> a >> b;
	cout << (a == b ? a * 2 : max(a, b) * 2 - 1) << endl;
	return 0;
}
 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
void solve(){
    
}
int main() {
  int n;
  cin>>n;
  bool ok=false;
  while(n>0){
    int k=n%10;
    if(k==7)
      ok=true;
    n=n/10;
  }
  if(ok)
    cout<<"Yes";
  else
    cout<<"No";
  
  return 0;
}

Measured memory_bytes: 3640
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define F first
#define S second
#define _sz(x) (int)x.size()

using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;

const int N = 1e5 + 20 ;
int n , a , b , h[N] ;

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

	cin >> n >> a >> b ;

	a -= b ;

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

	int low = -1 , high = 1e9 + 20 ;

	while (high - low > 1) {
		int mid = (low + high) / 2 ;
	
		ll sum = 0 ;

		for (int i = 0 ; i < n ; i ++) {
			int v = max(0ll , h[i] - 1ll * b * mid) ;

			sum += (v + a - 1) / a ;
		}

		if (sum <= mid) high = mid ;
		else low = mid ;
	}

	cout << high << '\n' ;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
 
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is >> a.first >> a.second; }
template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os << a.first << " " << a.second; }
template<typename T> istream& operator>>(istream& is, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) is >> vc[i]; return is; }
template<typename T> ostream& operator<<(ostream& os, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) os << vc[i] << endl; return os; }
 
#define ForEach(it,c) for(__typeof (c).begin() it = (c).begin(); it != (c).end(); it++)
#define ALL(v) (v).begin(), (v).end()
#define UNQ(s) { sort(ALL(s)); (s).erase( unique( ALL(s)), (s).end());}

typedef long long int64;
typedef pair< int , int > Pi;
typedef pair< int , Pi > Pii;
const int INF = 1 << 30;

int dp[3001][3001];

int main(){
  int N, T, S;
  cin >> N >> T >> S;
  vector< int > A(N), B(N);
  for(int i = 0; i < N; i++){
    cin >> A[i] >> B[i];
  }
  int ret = 0;
  for(int i = 1; i <= T; ++i){
    for(int j = 1; j <= N; ++j){
      dp[i][j] = max( dp[i - 1][j], dp[i][j - 1]);
      int prev = i - B[j - 1];
      if(prev >= 0 && (prev >= S || i <= S)) dp[i][j] = max( dp[i][j], dp[prev][j - 1] + A[j - 1]);
    }
    ret = max( ret, dp[i][N]);
  }
  cout << ret << endl;
}

Measured memory_bytes: 36392
#define _CRT_SECURE_NO_WARNINGS

#define N (1<<17)
#define MODULO (1000000007)

#include <cstdio>
#include <iostream>
#include <fstream>
#include <sstream>
#include <queue>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;

int n;
long long a[N], b[N];
long long inc;

int main()
{
	scanf("%d", &n);
	for (int i = 0;i < n;i++)
	{
		scanf("%lld%lld", &a[i], &b[i]);
	}
	for (int i = n - 1;i >= 0;i--)
	{
		long long ct = a[i] + inc;
		long long cn = b[i] - (ct%b[i]);
		if (cn == b[i])
		{
			cn = 0LL;
		}
		inc += cn;
	}
	printf("%lld\n", inc);
	//system("pause");
	return 0;
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using Int = int_fast64_t;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	Int w, h, ans = 0; cin >> w >> h;
	priority_queue<pair<Int, bool>> pq;
	for(Int i=0; i<w; ++i){
		Int p; cin >> p;
		pq.push(make_pair(p, 0));
		ans += p * (h+1);
	}
	for(Int i=0; i<h; ++i){
		Int q; cin >> q;
		pq.push(make_pair(q, 1));
		ans += q * (w+1);
	}
	Int rw = w, rh = h, ne = (h+1)*w + (w+1)*h;
	while(ne > (w+1)*(h+1) - 1){
		pair<Int, bool> p = pq.top(); pq.pop();
		if(!p.second){
			Int de = min(rh, ne-w*h+1);
			ne -= de;
			ans -= de * p.first;
			--rw;
		}else{
			Int de = min(rw, ne-w*h+1);
			ne -= de;
			ans -= de * p.first;
			--rh;
		}
	}
	cout << ans << "\n";
}

Measured memory_bytes: 6384
Main(myin());
function myin(){return require("fs").readFileSync("/dev/stdin", "utf8").trim();}
function myout(t){console.log(t);}//standard output
function myerr(t){console.error(t);}//standard error
//[no]param
//不明値:何もしない  1:数値へ変換  2:半角SPで分割  3:改行で分割  4:半角SPで分割し、数値配列へ
//5:改行で分割し、数値配列へ  6:1文字に分割  7:1文字に分割し、数値配列へ
//8:半角SPで結合　9:改行で結合　0:文字なしで結合
function myconv(i,no){switch(no){case 1:return parseInt(i);case 2:return i.split(" ");case 3:return i.split("\n");case 4:return i.split(" ").map((a)=>Number(a));case 5:return i.split("\n").map((a)=>Number(a));case 6:return i.split("");case 7:return i.split("").map((a)=>Number(a));case 8:return i.join(" ");case 9:return i.join("\n");case 0:return i.join("");default:return i;}}
function Main(input) {
  input = myconv(input,3);
  var N = myconv(input[0],4)[0];
  var M = myconv(input[0],4)[1];
  var AC = 0;
  var WA = 0;
  input.shift();
  var accepted = new Set();
  var waList = {};
  for(var i = 0; i < M; i++){
    var p = myconv(input[i],2)[0];
    var s = myconv(input[i],2)[1];
    //myerr(p + " " + s);
    if(!accepted.has(p) && s == "WA"){
      if(waList[p] == null){
         waList[p] = 1;
         }else{
         waList[p]++;
         }
      
      continue;
    }
    if(!accepted.has(p) && s == "AC"){
       AC++;
      if(waList[p] != null){
         WA += waList[p];
         }
      
      accepted.add(p);
    }
  }
  myout(AC + " " + WA);
}

Measured memory_bytes: 32868
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#define MP make_pair
using ll = long long;
using namespace std;

int main()
{
  int N;
  cin >> N;
  vector<int>A(N);
  int odd=0;
  int even=0;
  for(int i=0; i < N; i++){
    cin >> A[i];
    if(A[i] % 2 == 0)
      even++;
    else
      odd++;
  }

  int k=0;
  k = pow(2, even);
  cout << pow(3, N) - k << endl;
  return 0;
}


Measured memory_bytes: 256
import bisect
N = int(input())
enable = set()

k = 0
while(6**k <= N):
    enable.add(6**k)
    k += 1
k = 0
while(9**k <= N):
    enable.add(9**k)
    k += 1


enable = list(enable)
enable.sort()

ans = 10**9
l = len(enable)
for i in range(l):
    n = N
    tmp = 0
    while(n != 0):
        id = bisect.bisect_right(enable, n) - 1
        if id != 0 and n % enable[id] > 2 and n % enable[id] < 6:
            id -= 1
        n -= enable[id]
        tmp += 1
    enable.pop()

    ans = min(tmp, ans)

print(ans)


Measured memory_bytes: 3064
#pragma GCC optimize("O2,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
#define pb(X) push_back(X)
#define x first
#define y second
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
using namespace std;

typedef pair<int, int> pii;

int n;

int main() {
	string s;
	cin >> s;
	
	vector<vector<int>> dp(s.length() + 1,vector<int>(2));
	dp[0][0] = 0, dp[0][1] = 1;
	for (int i = 0; i < s.length(); ++i) {
		int d = s[i] -'0';
		dp[i + 1][0] = min(dp[i][0] + d, dp[i][1] + 10 - d);
		dp[i + 1][1] = min(dp[i][0] + d + 1, dp[i][1] + 9 - d);
	}
	cout << dp[s.length()][0];
	return 0;
}

Measured memory_bytes: 55940
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int N = Integer.parseInt(scan.nextLine());
		String S = scan.nextLine();
		String[] s = S.split("",0);
		int r = 0;
		int b = 0;
		for(int i=0;i<N;i++){
			if(s[i].equals("R")){
				r++;
			}
			else{
				b++;
			}
		}
		if(r>b){
			System.out.println("Yes");
		}
		else{
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 22612
import java.lang.*;
import java.io.*;
import java.util.*;


public class Main {

	public static void main(String[] args) throws java.lang.Exception {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskA solver = new TaskA();
		solver.solve(in, out);
		out.close();
	}
}


class TaskA {

	void solve(InputReader in, PrintWriter out) {
		int n = in.nextInt(), k = in.nextInt();
		long ans = 1;

		for (int i=0; i<n; ++i) {
			if (i == 0)
				ans *= k;
			else
				ans *= (k - 1);
		}

		out.println(ans);
	}
}

class InputReader {
	public BufferedReader reader;
	public StringTokenizer tokenizer;


	public InputReader(InputStream stream) {
		reader = new BufferedReader(new InputStreamReader(stream), 32768);
		tokenizer = null;
	}

	public String next() {
		while (tokenizer==null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 21588
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define sim template < class c
#define int long long
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << '\n'; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef tree< pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
const ll MOD = 1e9 + 7 ;
const ll N = 2e5 + 10 ;
const ll INF = 1e18 + 10 ;
signed main(){
    fastio
    int n ;
    cin >> n ;
    int ans = 0 ;
    for(int i = 1; i < n + 1; i++){
        int x ;
        cin >> x ;
        if ( i & 1 && x & 1 ) ans++ ;
    }
    cout << ans << endl;
    return 0; 
}

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

using namespace std;
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using vs=vector<string>;

#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define repr(i, a, n) for (int i = (n); i >= (a); --i)

template<typename T,typename U>
void Inparray(T &f,U n){
  for(int i=0;i<n;i++) cin>>f[i];
}

template<typename T,typename U>
void Printarray(T f,U n){
  for(int i=0;i<n;i++) i!=n ? cout<<f[i]<<" " : cout<<f[i];
}

void flagfunc(bool flag,string A,string B){
  flag ? cout<<A<<endl : cout<<B<<endl;
}

void flag2func(bool flag){
  flag ? cout<<"Yes"<<endl : cout<<"No"<<endl;
}

void flag3func(bool flag){
  flag ? cout<<"YES"<<endl : cout<<"NO"<<endl;
}

int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  vector<int> v1={1,3,5,7,8,10,12},v2={4,6,9,11},v3={2};
  int x,y;cin>>x>>y;
  int a=0,b=0;
  rep(i,0,v1.size())if(x==v1[i])a=1;
  rep(i,0,v2.size())if(x==v2[i])a=2;
  rep(i,0,v3.size())if(x==v3[i])a=3;
  rep(i,0,v1.size())if(y==v1[i])b=1;
  rep(i,0,v2.size())if(y==v2[i])b=2;
  rep(i,0,v3.size())if(y==v3[i])b=3;
  //cout<<a<<b<<endl;
  flag2func(a==b);
}

Measured memory_bytes: 256
#pragma GCC optimize (2)
#pragma G++ optimize (2)
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MAX 3005
using namespace std;
//char nc()
//{
//	static char buf[100000],*p1=buf,*p2=buf;
//	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
char nc(){return getchar();}
int read()
{
	int x=0,y=1;
	char c=nc();
	while(!isdigit(c))
	{
		if(c=='-')y=-1;
		c=nc();
	}
	while(isdigit(c))
	{
		x=(x<<1)+(x<<3)+(c^48);
		c=nc();
	}
	return x*y;
}
int n;
long long mod,C[MAX][MAX],g[MAX][MAX];
long long mo(long long x)
{
	return x<mod?x:x-mod;
}
long long quick_pow(long long x,long long y,long long p)
{
	long long re=1;
	while(y)
	{
		if(y&1) re=re*x%p;
		x=x*x%p;
		y>>=1;
	}
	return re;
}
int main()
{
	n=read();mod=read();
	C[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=mo(C[i-1][j]+C[i-1][j-1]);
	}
	for(int i=0;i<=n;i++)
	{
		g[i][0]=1;
		for(int j=1;j<=i;j++)
			g[i][j]=(g[i-1][j-1]+g[i-1][j]*(j+1))%mod;
	}
	long long ANS=0;
	for(int i=0;i<=n;i++)
	{
		long long tp1=quick_pow(2,n-i,mod),tp2=quick_pow(2,quick_pow(2,n-i,mod-1),mod);
		long long sm=0,now=1;
		for(int j=0;j<=i;j++)
			sm=(sm+now*g[i][j])%mod,now=now*tp1%mod;
		if(!(i&1)) ANS=(ANS+C[n][i]*tp2%mod*sm)%mod;
		else ANS=mo(ANS-C[n][i]*tp2%mod*sm%mod+mod);
	}
	printf("%lld",ANS);
	return 0;
}


Measured memory_bytes: 95920
n=int(input())
a=[]
a1=0
a2=0
for i in range(n):
    k=int(input())
    a.append(k)
    if a1<k:
        a2=a1
        a1=k
    elif a2<k:
        a2=k

for i in range(n):
    if a[i]==a1:
        print(a2)
    else:
        print(a1)

Measured memory_bytes: 12532
#include <iostream>
using namespace std;
int main(void){
    int a, b, result;
    
    cin >> a >> b;
    
    if(a == 1){
        if(b == 2){
            result = 3;
        }
        if(b == 3){
            result = 2;
        }
    }
    
    if(a == 2){
        if(b == 1){
            result = 3;
        }
        if(b == 3){
            result = 1;
        }
    }
    
    if(a == 3){
        if(b == 2){
            result = 1;
        }
        if(b == 1){
            result = 2;
        }
    }
    
    cout << result << endl;
    
    return 0;
}


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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cout<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<int, int> P;
struct Edge{ll from, to, cost;};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}

ll N, Q;
llvec v[200001];
ll c[200001];

ll dfs(ll from, ll to){
  c[to] += c[from];
  rep(i, v[to].size()){
    if(v[to][i]!=from){
      dfs(to, v[to][i]);
    }
  }
}

/**************************************
** A main function starts from here  **
***************************************/
int main(){
  cin >> N >> Q;
  rep(i, N-1){
    ll a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }

  llvec count(N+1, 0);

  rep(i, Q){
    ll q, a;
    cin >> q >> a;
    c[q]+=a;
  }

  dfs(0, 1);
  
  rep(i, N){
    cout << c[i+1] << endl;
  }

  
  
  return 0;
}


Measured memory_bytes: 25856
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:52:55 2019

@author: Owner
"""

import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break

"""
N = int(input())
H = list(map(int, input().split()))

def main():
    cnt = 0
    tmp_max =0
    for n in range(N):
        if tmp_max <=H[n]:
            tmp_max = H[n]
            cnt+=1
    print(cnt)
 
if __name__ == '__main__':
    main()

Measured memory_bytes: 24184
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 800 + 7;
const int MOD = 1e9 + 7;

int dis[N][N];
pair<int, int> q[N*N];
string s[N];
int n, m, k;
int dr[] = {0, -1, 0, 1};
int dc[] = {1, 0, -1, 0};

bool valid(int r, int c)
{
	return r >= 0 && c >= 0 && r < n && c < m && s[r][c] != '#';
}

void bfs(int sr, int sc)
{
	memset(dis, 63, sizeof dis);
	int h = 0, t = 0;
	dis[sr][sc] = 0;
	q[t++] = {sr, sc};
	while (h < t)
	{
		int r = q[h].first;
		int c = q[h].second;
		h++;
		for (int i=0; i<4; i++)
		{
			int R = r + dr[i];
			int C = c + dc[i];
			if (valid(R, C) && dis[R][C] > dis[r][c] + 1)
			{
				dis[R][C] = dis[r][c] + 1;
				q[t++] = {R, C};
			}
		}
	}
}

int best(int r, int c)
{
	int A = min(r, n-1-r);
	int B = min(c, m-1-c);
	return (min(A, B) + k - 1) / k;
}

int main()
{
	ios::sync_with_stdio(false);
	
	memset(dis, 63, sizeof dis);


	cin >> n >> m >> k;
	for (int i=0; i<n; i++)
		cin >> s[i];
	for (int i=0; i<n; i++)
		for (int j=0; j<m; j++)
			if (s[i][j] == 'S')
				bfs(i, j);
	int ans = n*m;
	for (int i=0; i<n; i++)
		for (int j=0; j<m; j++)
			if (dis[i][j] <= k)
				ans = min(ans, best(i, j) + 1);
	cout << ans << "\n";
	return 0;
}

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


int main()
{
	int n;
	cin>>n;
	int ans = 0;
	for(size_t i = 0; i<9; i++)
	{
		if(n%(i+1)==0&&n/(i+1)<10)
		{
			ans = 1;
			break;
		}
	}
	if(ans==1)
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
using namespace std;
int dp[105][10005];
int main(){
      int n,sum,a,b;
      cin >> n >> sum;
      for (int i = 0;i < n;i++){
            cin >> a >> b;
            for (int j = 0;j<= sum;j++){
                  if(j>=b) dp[i+1][j] = max(dp[i][j],dp[i][j-b]+a);
                  else dp[i+1][j] = dp[i][j];
            }
      }
      cout <<dp[n][sum]<<endl;
}



Measured memory_bytes: 7020
#include <iostream>

int main() {
    char userInput; 

    std::cin >> userInput;

    if (userInput >= 65 && userInput <= 90) {
        std::cout << "A\n"; 
    }
    else if (userInput >= 97 && userInput <= 122) {
        std::cout << "a\n"; 
    }
    
    return 0;
}

Measured memory_bytes: 3584
#include <stdio.h>
#include <stdlib.h>

int	desc(const void *a, const void *b)
{
	long *v1 = (long *)a;
	long *v2 = (long *)b;

	return (*v2 - *v1);
}

int	main(void)
{
	int		n;
	long	a[100000];
	long	side[2] = {};

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%ld", &a[i]);
	}
	qsort(a, n, sizeof(long), desc);
	for (int i = 1; i < n; i++)
	{
		if (a[i - 1] == a[i])
		{
			if (side[0] == 0)
			{
				side[0] = a[i];
			}
			else
			{
				side[1] = a[i];
				break;
			}
			i++;
		}
	}
	printf("%ld\n", side[0] * side[1]);
	return (0);
}


Measured memory_bytes: 1788
h, w = map(int, input().split())

mat = []
for _ in range(h):
    road = list(map(int, input().split()))
    mat.append(road)

ans = 10**9
for i in range(h):
    for j in range(w):
        total = 0
        for m in range(h):
            for n in range(w):
                dis = min(abs(m-i), abs(n-j))
                total += dis * mat[m][n]
        if total < ans:
            ans = total

print(ans)


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

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 1 << 30;
const ll INFL = 1223372036854775807;
const ll mod = 1000000007;		




int main() {

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

	cout << (a - c)*(b - d) << endl;

	return 0;


}

Measured memory_bytes: 256
import java.util.Scanner;

class Main
{
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		while (true)
		{
			int change = 1000 - sc.nextInt(),
				count = 0;
			if (change == 1000) break;
			while (change > 0)
			{
				if (change >= 500)		change -= 500;
				else if (change >= 100)	change -= 100;
				else if (change >= 50)	change -= 50;
				else if (change >= 10)	change -= 10;
				else if (change >= 5)	change -= 5;
				else if (change >= 1)	change -= 1;
				count++;
			}
			System.out.println(count);
		}
	}
}

Measured memory_bytes: 12000
def main():
    N = int(input())
    A = [0 for x in range(N)]
    for i in range(N):
        A[i] = list(map(int, input().split(" ")))
    sortedA = sorted(A, key=lambda x: x[1])
    s = [0 for _ in range(N)]
    for i, x in enumerate(sortedA):
        if i == 0:
            s[i] = x[0]
        else:
            s[i] = s[i-1]+x[0]

        if s[i] > x[1]:
            return 'No'
    return 'Yes'


if __name__ == "__main__":
    print(main())

Measured memory_bytes: 59788
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <numeric>
#include <functional>
#include <tuple>

template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
  if (lhs > rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
  if (lhs < rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

// [l, r) from l to r
struct frep {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { ++i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr l, r;
  constexpr frep(int l_, int r_): l(std::min<int>(l_, r_)), r(r_) {}
  constexpr itr begin() const { return l; }
  constexpr itr end() const { return r; }
};

// [l, r) from r to l
struct brep {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { --i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr r, l;
  constexpr brep(int l_, int r_): r(std::max<int>(l_, r_) - 1), l(l_ - 1) {}
  constexpr itr begin() const { return r; }
  constexpr itr end() const { return l; }
};

template <class T>
inline T scan() {
  T res;
  std::cin >> res;
  return res;
}

int main() {
  int N;
  std::cin >> N;
  std::vector<int> H(N), P(N);
  for (int i: frep(0, N)) {
    std::cin >> H.at(i) >> P.at(i);
  }
  std::vector<int> order(N);
  std::iota(order.begin(), order.end(), 0);
  std: sort(order.begin(), order.end(), [&](int i, int j) {
    return H.at(i) + P.at(i) < H.at(j) + P.at(j);
  });
  std::vector<std::vector<long long>> dp(N + 1, std::vector<long long>(N + 1, 1ll << 60));
  dp.at(0).at(0) = 0;
  for (int i: frep(0, N)) {
    int t = order.at(i);
    for (int j: frep(0, N)) {
      chmin(dp.at(i + 1).at(j), dp.at(i).at(j));
      if (dp.at(i).at(j) <= H.at(t)) {
        chmin(dp.at(i + 1).at(j + 1), dp.at(i).at(j) + P.at(t));
      }
    }
  }
  std::cout << std::lower_bound(dp.at(N).begin(), dp.at(N).end(), 1ll << 60) - dp.at(N).begin() - 1 << std::endl;
  return 0;
}


Measured memory_bytes: 197888
#include <iostream> 
#include <bits/stdc++.h>
#include <vector> 
#include <algorithm> 
#include <string>
#include <cmath>
#include <iomanip> 
#include<climits> 
#include <utility>   
#include <set>
#include <numeric> 
#include <iterator>
#include <map> 
using namespace std; 
#define ll long long int
#define M 1000000007

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    ll x;
    cin>>x;
    int p=0;
    for(int i=-1000;i<1000;i++)
    {
        for(int j=-1000;j<1000;j++)
        {
            if(pow(i,5) - pow(j,5) == x)
            {
                cout<<i<<" "<<j<<endl;
                p=1;
                break;
            }
        }
        if(p==1)
        break;
    }
}

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

int main()
{
    double PI = acos(-1);
    int a, b, h, m;
    cin >> a >> b >> h >> m;

    double c = 30 * h + 0.5 * m;
    double d = 6 * m;
    double e = abs(c - d);
    if (e > 180)
    {
        e = 360 - e;
    }
    double radian = e * PI / 180.0;
    double ans = sqrt(b * b + a * a - 2 * b * a * cos(radian));
    printf("%.20f\n", ans);
    return 0;
}


Measured memory_bytes: 4176
#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin() , v.end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }
const ll INF = 999999999999999;
const ll MOD = 1000000007;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, ans = 0, w, l;
vector<PP> gragh[200010];
vl visited1(200010, 0), cost(200010, INF);
void dfs1(ll x, ll k) {
	visited1[x] = 1;
	cost[x] = k;
	for (PP i : gragh[x]) {
		if (visited1[i.first] == 0) {
			dfs1(i.first, k + i.second);
		}
	}
}
void input() {
	cin >> n;
	rep(i, n-1) {
		cin >> a >> b >> c;
		gragh[a].push_back({ b,c });
		gragh[b].push_back({ a,c });
	}
}
void solve() {
	dfs1(0, 0);

	a = 0;
	rep(i, n) {
		if (a < cost[i]) {
			a = cost[i];
			b = i;
		}
	}

	visited1 = vl(n, 0);
	cost = vl(n, 0);
	dfs1(b, 0);
	sort(all(cost));
	reverse(all(cost));

	cout << cost[0] << endl;

}

int main() {
	input();
	solve();
}


Measured memory_bytes: 19116
fun main(args: Array<String>) {
    val len = readLine()!!.toInt()
    val lines = readLine()!!.split(" ").map {it.toInt()}

    var count = 0

    for (i in 0 until len) {
        if (i == 0) {
            count++
            continue
        }

        if (lines.subList(0, i).max()!! <= lines[i]) {
            count++
        }
    }
    print(count)
}

Measured memory_bytes: 37932
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define repr(i,n) for(int i=(n-1);i>=0;i--)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;

int main() {
    ll sub = 998244353;
    ll n;
    cin >> n;

    vector<ll> vec(n);
    map<int,int> mp;
    ll tmp = 0;
    rep(i,n){
        cin >> vec.at(i);
        mp[vec.at(i)]++;
        if(tmp < vec.at(i)){
            tmp = vec.at(i);
        }
    }

    if(vec.at(0) != 0){
        cout << 0 << endl;
        return 0;
    }
    if(mp[0] > 1){
        cout << 0 << endl;
        return 0;
    }
    rep(i,tmp){
        if(mp[i] == 0){
            cout << 0 << endl;
            return 0;
        }
    }

    ll ans = 1;
    ll tmp2 = 1;
    rep(i,tmp){
        tmp2 = 1;
        if(i==0){
            continue;
        }
        rep(j, mp[i+1]){
            tmp2 = tmp2  * mp[i] % sub;
            //ans *= mp[i] % sub;
        }
        ans = ans * tmp2 % sub;
        //cout << "tmp2 = " << tmp2 << endl;
        //cout << "ans = " << ans << endl;
    }

    cout << ans << endl;

}


Measured memory_bytes: 5760
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")

#include <cstdio>
#include <vector>
#include <bitset>

using namespace std;

using int64 = long long;

constexpr int64 MOD = 1e9 + 7;

template<typename T> inline void fastin(T &num) {
  bool negative = false;
  T c;
  num = 0;
  c = getchar_unlocked();
  for (; (c > 47 && c < 58); c = getchar_unlocked()) num = (num << 3) + (num << 1) + c - 48;
}

int main() {
  //ios_base::sync_with_stdio(false);
  //cin.tie(nullptr);

  int n; fastin(n);
  int64 a[n];
  for (int i = 0; i < n; ++i) fastin(a[i]);

  bool dp[n][61];

  for (int i = 0; i < n; ++i) {
    bitset<61> bs(a[i]);
    for (int j = 0; j < 61; ++j) {
      dp[i][j] = bs.test(j);
    }
  }

  int64 dp2[n][61];

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 61; ++j) {
      if (i == 0) {
        dp2[i][j] = dp[i][j];
      } else {
        dp2[i][j] = dp[i][j] + dp2[i - 1][j];
      }
    }
  }

  int64 ans = 0;

  for (int i = 1; i < n; ++i) {
    bitset<61> bs(a[i]);
    for (int j = 0; j < 61; ++j) {
      if (bs.test(j)) {
        ans += (1LL << j) % MOD * (i - dp2[i - 1][j]) % MOD;
      } else {
        ans += (1LL << j) % MOD * dp2[i - 1][j] % MOD;
      }
    }
  }

  ans %= MOD;

  printf("%lld", ans);

  return 0;
}


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


int main(){
  ll n;cin >> n;
  if( n%1000 == 0 ){
    cout << 0 << endl;
  }else{
    cout << 1000 - n%1000 << endl;
  }
  return 0;
}


Measured memory_bytes: 3592
d={48:'light fly',51:'fly',54:'bantam',57:'feather',60:'light',64:'light welter',69:'welter',75:'light middle',81:'middle',91:'light heavy'}
while True:
    try:
        w=float(input())
    except:
        break
    for k,v in sorted(d.items()):
        if w<=k:
            print(d[k])
            break
    else:
        print("heavy")

Measured memory_bytes: 7316
#include <iostream>
#include <sstream>

int main() {
    int n;
    while (std::cin >> n && n) {
        std::string s1, s2;
        std::cin >> s1;

        for (int i = 0; i < n; i++) {
            s1 += 'a';
            s2 = "";
            char pre = s1[0];
            s1.erase(s1.begin(), s1.begin() + 1);
            int count = 1;
            for (char cur : s1) {
                if (pre == cur) {
                    count++;
                } else {
                    std::stringstream ss("");
                    ss << count, s2 += ss.str() + pre;
                    pre = cur, count = 1;
                }
            }
            s1 = s2;
        }
        std::cout << s1 << std::endl;
    }
}

Measured memory_bytes: 3104
n=int(input())
d=list(map(int,input().split()))
d.sort()
gn=0
a=d[int(n/2)]-d[int((n/2)-1)]-1

if d[int(n/2)]!=d[int((n/2)-1)]:
  for i in d:
    if i==d[int(n/2)]:
      gn+=1
  if gn>=1:
    a+=1
  print(a)
     
else:
  print(0)

Measured memory_bytes: 14428
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v; return v;}

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vector<int> > Mat;
typedef tuple<int, int, int, int> T;

const int MOD = (int)1e9+7;
const int INF = (int)1e9;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

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

    ll a, b, c;
    cin >> a >> b >> c;
    
    ll ans = 0;
    if(a%2 == 1 && b%2 == 1 && c%2 == 1) ans = min({a*b, b*c, c*a});

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
A = [int(input()) for i in range(N)]

G = [1]
for i in range(N):
    G.append(A[G[-1]-1])
    
ans = 0
for i in G:
    if i==2:
        break
    ans += 1
else:
    ans = -1
    
print(ans)

Measured memory_bytes: 13520
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  string s[n],x;
  int ar[n+1],arr[n+1]={0};
  for(int i=0;i<n;i++)
    cin>>s[i]>>ar[i];
  cin>>x;
  ar[n]=0;
  for(int i=n-1;i>=0;i--)
     arr[i] = ar[i+1]+arr[i+1];
  for(int i=0;i<n;i++)
      if(x==s[i])
        cout<<arr[i]<<endl;
    return 0;
}

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

#define fast_in_out     ios_base::sync_with_stdio(false);cin.tie(0);
#define nl              printf("\n")
using namespace std;
int arr[102][102];

int main()
{
    fast_in_out
    int r,c,i,sum;
    cin>>r>>c;
    //int arr[r][c];

    for(int j=0;j<r;j++)
    {
        //sum=0;
        for(i=0;i<c;i++){
            cin>>arr[j][i];
            arr[j][c]+=arr[j][i];
            arr[r][i]+=arr[j][i];
        }
        arr[r][c]+=arr[j][i];
        //=sum;
    }
    for(int j=0;j<=r;j++){
        for(i=0;i<=c;i++){
            cout<<arr[j][i];
            if(i==c)cout<<'\n';
            else cout<<" ";
        }
        //cout<<'\n';
    }

    return 0;
}



Measured memory_bytes: 3212
#include <stdio.h>
int main(){
  long int N;
  long int i;
  long int ans=0;
  scanf("%ld",&N);
  
  for(i=1;i<=N;i++){
    if(i%3 != 0 && i%5 != 0){
      ans+=i;
    }
  }
  printf("%ld\n",ans);
  
  return 0;
}

Measured memory_bytes: 1728
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

b = np.median((A - np.arange(1, N+1)))
ans = np.inf
for i in [b-1, b, b+1]:
    ans = min(np.abs(A - i - np.arange(1, N+1)).sum(), ans)

print(int(ans))


Measured memory_bytes: 34220
s = input()
r = 0
if s[0] == '1':
  r += 900
else:
  r += 100
if s[1] == '1':
  r += 90
else:
  r += 10 
if s[2] == '1':
  r += 9
else:
  r += 1 
print(r)

Measured memory_bytes: 2940
using System.Linq;
using static System.Console;
using static System.Math;
class Z { static void Main() => new KK(); }
class KK
{
	long[] GL => ReadLine().Split().Select(long.Parse).ToArray();
	readonly int N;
	readonly int[] cnt = new int[50];
	public KK()
	{
		var I = GL;
		N = (int)I[0];
		var K = ToBits(I[1] + 1);
		var A = GL.Select(ToBits).ToArray();
		var good = new bool[50];
		for (var a = 0; a < 50; a++)
		{
			for (var i = 0; i < N; i++) if (A[i][a]) cnt[a]++;
			good[a] = cnt[a] <= N - cnt[a];
		}
		var ans = Calc(new bool[50]);
		for (var i = 0; i < 50; i++) if (K[i])
			{
				var x = new bool[50];
				for (var j = 0; j < i; j++) x[j] = good[j];
				for (var j = i + 1; j < 50; j++) x[j] = K[j];
				ans = Max(ans, Calc(x));
			}
		WriteLine(ans);
	}
	long Calc(bool[] x)
	{
		var sum = 0L;
		for (var a = 0; a < 50; a++) sum += (x[a] ? N - cnt[a] : cnt[a]) * (1L << a);
		return sum;
	}
	static bool[] ToBits(long x)
	{
		var ans = new bool[50];
		for (var i = 0; i < 50; i++) ans[i] = (x & (1L << i)) != 0;
		return ans;
	}
}


Measured memory_bytes: 41092
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define Cout(s) cout << s << endl;
using ll = long long;
using P = pair<int, int>;
#define INF 10000000;

ll MOD = 1e9 + 7;

int gcd(int x, int y)
{
    return y != 0 ? gcd(y, x % y) : x;
}

int lcm(int x, int y)
{
    return x * y / gcd(x, y);
}


int main()
{

    int n, m;
    cin >> n >> m;
    vector<int> X(m);
    vector<int> a(m - 1);
    REP(i, m)
    cin >> X[i];

    sort(X.begin(), X.end());

    if (n >= m)
    {
        Cout(0);
    }
    else if (n == 1)
    {
        Cout(abs(X[m - 1] - X[0]));
    }
    else
    {
        REP(i, m - 1)
        {
            a[i] = abs(X[i + 1] - X[i]);
        }
        sort(a.rbegin(), a.rend());
        int ans = 0;
        for (int i = n - 1; i < m - 1; i++)
        {
            ans += a[i];
        }

        Cout(ans);
    }

    return 0;
}


Measured memory_bytes: 1152