akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
#include<string.h>
#include<set>
#include<stdio.h>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include <cstdio>
#include <cstdlib>
#include<stack>
#include<vector>
long long a[100];
int main()
{
    int n;
    cin>>n;
    int a[10];
    int b[10];
    memset(b,0,sizeof(b));
    a[3]=n%10;
    n/=10;
    a[2]=n%10;
    n/=10;
    a[1]=n%10;
    n/=10;
    a[0]=n;
    int sum=0;
    if(a[0]+a[1]+a[2]+a[3]==7)
        cout<<a[0]<<"+"<<a[1]<<"+"<<a[2]<<"+"<<a[3]<<"=7"<<endl;
    else if(a[0]+a[1]+a[2]-a[3]==7)
        cout<<a[0]<<"+"<<a[1]<<"+"<<a[2]<<"-"<<a[3]<<"=7"<<endl;
    else if(a[0]+a[1]-a[2]+a[3]==7)
        cout<<a[0]<<"+"<<a[1]<<"-"<<a[2]<<"+"<<a[3]<<"=7"<<endl;
    else if(a[0]-a[1]+a[2]+a[3]==7)
        cout<<a[0]<<"-"<<a[1]<<"+"<<a[2]<<"+"<<a[3]<<"=7"<<endl;
     else if(a[0]-a[1]+a[2]+a[3]==7)
        cout<<a[0]<<"-"<<a[1]<<"+"<<a[2]<<"+"<<a[3]<<"=7"<<endl;
    else if(a[0]-a[1]-a[2]+a[3]==7)
        cout<<a[0]<<"-"<<a[1]<<"-"<<a[2]<<"+"<<a[3]<<"=7"<<endl;
    else if(a[0]-a[1]+a[2]-a[3]==7)
        cout<<a[0]<<"-"<<a[1]<<"+"<<a[2]<<"-"<<a[3]<<"=7"<<endl;
    else if(a[0]+a[1]-a[2]-a[3]==7)
        cout<<a[0]<<"+"<<a[1]<<"-"<<a[2]<<"-"<<a[3]<<"=7"<<endl;
    else if(a[0]-a[1]-a[2]-a[3]==7)
        cout<<a[0]<<"-"<<a[1]<<"-"<<a[2]<<"-"<<a[3]<<"=7"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD=1e9+7;
const double PI=3.14159265359;
 
 
vector<int> getPrimes(int stop){
    int sieveStop=ceil(sqrt(stop));
    vector<int> psj;
    for(int i=2; i<=sieveStop; i++){
        bool isP=true;
        for(int j=2; j<i && isP; j++){
            isP=i%j;
        }
        if(isP) psj.push_back(i);
    }
    
    vector<bool> primesb(stop+1,true);
    for(int j:psj){
        for(int i=2; i*j<=stop; i++){
            primesb[i*j]=false;
        }
    }
    vector<int> ans;
    for(int i=2; i<=stop; i++){
        if(primesb[i]) ans.push_back(i);
    }
    return ans;
}
 
int main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    auto pv=getPrimes(55555);
    //auto pvo=getPrimes(1000000);
    int n;
    cin>>n;
    
    vector<int> ans;
    for(int i=0; ans.size()<n; i++){
        if(pv[i]%5==1) ans.push_back(pv[i]);
    }
    for(int i:ans){
        cout<<i<<" ";
    }
    
    return 0;
    
    
}

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

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; }

const long long INF = 1LL<<60;
int N;
vector<long long> X;
vector<vector<int>> G;
long long all;
long long ave;
int amari;

int size[5100];
long long sum[5100];
long long dp[5100][5100];
long long sdp[5100][5100];

void rec(int v, int p = -1) {
    vector<int> chs;
    size[v] = 1;
    sum[v] = X[v];
    for (auto ch : G[v]) {
        if (ch == p) continue;
        rec(ch, v);
        chs.push_back(ch);
        size[v] += size[ch];
        sum[v] += sum[ch];
    }

    for (int i = 0; i <= chs.size(); ++i)
        for (int j = 0; j <= size[v]; ++j)
            sdp[i][j] = INF;
    sdp[0][0] = 0;
    int cur = 0;
    for (int i = 0; i < chs.size(); ++i) {
        int ch = chs[i];
        for (int j = 0; j <= cur; ++j) {
            for (int k = 0; k <= size[ch]; ++k) {
                chmin(sdp[i+1][j+k], sdp[i][j] + dp[ch][k]);
            }
        }
        cur += size[ch];
    }

    for (int k = 0; k <= size[v]; ++k) {
        chmin(dp[v][k], sdp[chs.size()][k] + abs(ave * size[v] + k - sum[v]));
        chmin(dp[v][k+1], sdp[chs.size()][k] + abs(ave * size[v] + k+1 - sum[v]));
    }
}

int main() {
    cin >> N;
    X.resize(N);
    all = 0;
    for (int i = 0; i < N; ++i) cin >> X[i], all += X[i];
    ave = all / N;
    amari = all % N;
    G.assign(N, vector<int>());
    for (int i = 0; i < N-1; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for (int v = 0; v < N; ++v) for (int i = 0; i <= N; ++i) dp[v][i] = INF;
    rec(0);

    cout << dp[0][amari] << endl;
}



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

int main(){
  int n, w, s;
  cin >> n;
  w = 0;
  s = 0;
  for(int i = 0; i < n; i++, w += s){
    int l, r;
    cin >> l >> r;
    s = (r - l + 1);
  }
  cout << w << endl;
}
      
    


Measured memory_bytes: 256
#include <iostream>
#include <complex>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cassert>
#include <string>
#include <memory.h>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cctype>
#include <iomanip>
#include <sstream>
#include <cctype>
#include <fstream>
#include <cmath>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define ITER(c) __typeof((c).begin())
#define PB(e) push_back(e)
#define FOREACH(i, c) for(ITER(c) i = (c).begin(); i != (c).end(); ++i)
#define MP(a, b) make_pair(a, b)
#define PARITY(n) ((n) & 1)

typedef long long ll;
const int INF = 1000 * 1000 * 1000 + 7;
const double EPS = 1e-9;

typedef complex<double> P;

int main(){
  int N;
  cin >> N;
  vector<P> ps(N);
  REP(i, N) cin >> ps[i].real() >> ps[i].imag();

  bool ok = true;
  P center = (ps[0] + ps[N/2]) * 0.5;
  REP(i, N / 2){
    ok &= abs(center - (ps[i] + ps[N/2 + i]) * 0.5) < EPS;
  }
  
  if(ok && N % 2 == 0){
    printf("%.9f %.9f\n", center.real(), center.imag());
  }else{
    cout << "NA" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1260
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,sum = 0;
cin>>n>>m;
int A[m];
for(int i = 0 ;i < m ; i++){
    cin>>A[i];
    sum += A[i];
}
if(sum>n)
    cout<<-1<<endl;
else
    cout<<n - sum<<endl;
}


Measured memory_bytes: 3672
#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll; 

int main(void){
    ll n, m, x[1010], y[1010], z[1010];
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> z[i];
    
    ll dp[1010][10];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < 8; j++) {
            if (i == 0) dp[i][j] = 0;
            else dp[i][j] = -1e18;
        }
    }
    // +++, ++-, +-+, +--, -++, -+-, --+, ---
    for (ll i = 0; i < n; i++) {
        //cout << "i = " << i << endl;
        for (int j = min(i, m - 1); j >= 0; j--) {
            for (int p = 0; p < 8; p++) {
                dp[j + 1][p] = max(dp[j + 1][p], dp[j][p] + 
                ll(x[i] * pow(-1, p / 4) + y[i] * pow(-1, p / 2) + z[i] * pow(-1, p)));
                //cout << dp[j + 1][p] << " ";
            }
            //cout << endl;
        }
    }
    
    ll ans = 0;
    for (int i = 0; i < 8; i++) {
        ans = max(ans, dp[m][i]);  //cout << dp[m][i] << " ";
    }//cout << endl;
    
    cout << ans << endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int n;
int l[100];

signed main() {
	int i, j, k;
	
	cin >> n;
	rep(i, n) cin >> l[i];
	sort(l, l + n);
	
	int ans = 0;
	rep(i, n) {
		for (j = i + 1; j < n; j++) {
			for (k = j + 1; k < n; k++) {
				if (l[i] == l[j] || l[j] == l[k]) continue;
				if (l[k] >= l[i] + l[j]) continue;
				ans++;
			}
		}
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define rep(i,n) for(long long int i = 0; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
const int N = 1000000;

int main() {
    ll n; cin >> n;
    ll ans = 1;
    for (ll i = 1; i <= n; ++i) {
        if(n >= i * i)ans = i * i;
    }
    print(ans);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>

#define rep(i, n) for(int i=0; i<n; i++)
#define reps(i, s, n) for(int i=s; i<n; i++)
#define repd(i, n) for(int i=n-1; i>=0; i--)

using namespace std;

int factorial(int n) {
 
  int ret = 1;
  for (int i = n; i > 0; i--) ret *= i;
  
  return ret;
}

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

    vector<double> route;
    vector<vector<int>> city(n, vector<int>(2));

    rep(i, n) cin >> city[i][0] >> city[i][1];

    rep(i, n-1) reps(j, i+1, n) {
      int tmpx = city[i][0] - city[j][0];
      int tmpy = city[i][1] - city[j][1];
      route.push_back(sqrt(tmpx*tmpx + tmpy*tmpy));
    }

    double sum = 0;
    for (auto x: route) sum += x*(n-1)*2*factorial(n-2);
    printf("%.10lf\n", sum / factorial(n));
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdint>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

int const MAXN = 3e5;
int N, f[MAXN], m[MAXN], d[MAXN+1];

int main() {
  std::cin >> N;
  std::fill_n(m, N+1, 0);
  for(int i = 0; i < N; ++i) { int A; std::cin >> A; ++m[A-1]; }
  std::fill_n(d, N+1, 0);
  for(int i = 0; i < N; ++i) ++d[m[i]];

  int64_t sum = 0;
  for(int64_t x = 0; x < N; ++x) {
    sum += x*d[x];
    f[x] = sum/(x+1);
  }
  sum = d[N];
  for(int x = N-1; x >= 0; --x) {
    f[x] += sum;
    sum += d[x];
  }

  int ans = N;
  for(int k = 1; k <= N; ++k) {
    ans = std::min(ans, N/k);
    while(ans > 0 && k > f[ans-1]) --ans;
    std::cout << ans << std::endl;
  }
  return 0;
}


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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
signed main(){
    gearup;
    int h,w; cin >> h >> w;
    vvc c(h,vc(w));
    rep(i,h)rep(j,w)cin >> c[i][j];
    vvl dp(h+1,vl(w+1,0));
    dp[0][0]=1;
    rep(i,h){
        rep(j,w){
            if(i+1 < h && c[i+1][j]=='.')dp[i+1][j] = (dp[i+1][j] + dp[i][j])%MOD;
            if(j+1 < w && c[i][j+1]=='.')dp[i][j+1] = (dp[i][j+1] + dp[i][j])%MOD;
        }
    }
    out(dp[h-1][w-1]);
}


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

int main() {
	string s;
	cin >> s;
	if (s[0] == 'Y') {
		if (s[1] == 'A') {
			if (s[2] == 'K') {
				if (s[3] == 'I') {
					cout << "Yes" << endl; return 0;
				}
			}
		}
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
// This is the start of  template//
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long int
#define vll vector<int>
#define pb push_back
#define pll pair<int,int>
#define mp(a,b) make_pair(a,b)
#define ff first
#define ss second
void input(){
#ifndef ONLINE_JUDGE 
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout); 
#endif
}
#define INF LONG_LONG_MAX
#define mod 1000000007
#define array(a,n) vll a(n); rep(i,0,n) cin>>a[i];
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define cases int t; cin>>t; while(t--)
#define printall(a) rep(i,0,a.size()) cout<<a[i]<<" "; cout<<endl;
int power(int a,int n)
{
    if(n==0)
        return 1;
    if(n%2!=0)
    {
        return (a*power((a*a)%mod,n/2))%mod;
    }
    return power((a*a)%mod,n/2)%mod;
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  input();
  int n,ans;
  cin>>n;
  ans = (power(10,n) - (2*power(9,n))%mod + mod + power(8,n)+mod)%mod;
  cout<<ans<<endl;
}

//

Measured memory_bytes: 3648
N = int(input())
A, B = (int(i) for i in input().split())  
P = [int(i) for i in input().split()] 

p0 = 0
p1 = 0
p2 = 0

for pi in P:
    if pi <= A:
        p0 += 1
    if pi > A and pi <= B:
        p1 += 1
    if pi > B:
        p2 += 1

print(min(p0, p1, p2))

Measured memory_bytes: 3064
N, M = map(int, input().split())
A = []
B = []
C = []
D = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
for j in range(M):
    c, d = map(int, input().split())
    C.append(c)
    D.append(d)
for i in range(N):
    mdis_j = 1
    mdis = 10**9
    for j in range(M):
        tmp = abs(A[i]-C[j])+abs(B[i]-D[j])
        if mdis > tmp:
            mdis_j = j+1
            mdis = tmp
    print(mdis_j)


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

using namespace std;

#define MAX 51
#define MAX_M 5001
typedef pair<int,int> pii;

int main(){
    int X,Y,Z,N,E,A;
    while(cin >> X >> Y >> Z, X){
        pii M[MAX];
        vector<int> V(X);
        for(int i = 0 ; i < X ; i++){
            cin >> V[i];
        }
        for(int i = 0 ; i < MAX ; i++){
            M[i] = pii(-1,-1);
        }
        for(int i = 0 ; i < Z ; i++){
            cin >> N >> E >> A;
            M[N] = pii(E,A);
        }
        double dp[MAX][MAX_M] = {{0}};
        dp[0][0] = 1;
        for(int i = 0 ; i < Y ; i++){
            for(int j = 0 ; j < MAX_M ; j++){
                for(int k = 0 ; k < X ; k++){
                    int next = min(i+V[k], Y);
                    int v = M[next].first;
                    int v2 = M[next].second;
                    if(v == -1){
                        dp[next][j] += dp[i][j]/X;
                    }else if(v == 2){
                        dp[next][min(j+v2,MAX_M-1)] += dp[i][j]/X;
                    }else if(v == 3){
                        dp[next][max(j-v2,0)] += dp[i][j]/X;
                    }else{
                        next = min(next+v2,Y);
                        dp[next][j] += dp[i][j]/X;
                    }
                }
            }
        }
        double res = 0;
        for(int i = 0 ; i < MAX_M ; i++){
            res += i*dp[Y][i];
        }
        cout << (int)res << endl;
    }
    return 0;
}

Measured memory_bytes: 3188
{-# LANGUAGE RecursiveDo        #-}
{-# LANGUAGE OverloadedStrings  #-}
{-# LANGUAGE NumericUnderscores #-}

import qualified Data.ByteString.Char8 as C8
import Data.List
import Data.Char

f :: Int -> [Int] -> [Int]
f k hs@(h:_) = map (abs . subtract h) (take k hs)

g :: Int -> [Int] -> [Int] -> [Int] -> Int
g _ costs _      []                  = head costs
g k costs starts dists@(dist:dists') = g k costs' starts' dists'
  where cost    = minimum $ take k $ zipWith (\ c s -> c + abs (dist - s)) costs starts
        costs'  = cost : costs
        starts' = dist : starts

solve :: Int -> Int -> [Int] -> Int
solve n k h
    | n > k     = g k (reverse $ f k h) (reverse $ take k h) (drop k h)
    | otherwise = last $ f n h

main = do
  [n, k] <- unfoldr (C8.readInt . C8.dropWhile isSpace) <$> C8.getLine
  h      <- unfoldr (C8.readInt . C8.dropWhile isSpace) <$> C8.getLine
  print $ solve n k h


Measured memory_bytes: 62952
#pragma comment(linker, "/STACK:1024000000,1024000000")
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;

#define rep(i , a , b) for(register int i=(a);i<=(b);i++)
#define per(i , a , b) for(register int i=(a);i>=(b);i--)
#define ms(s) memset(s, 0, sizeof(s))
#define squ(x) (x)*(x)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll , ll> pi;
typedef unordered_map<int,int> un_map;
template<class T>
inline void read (T &x) {
    x = 0;
    int sign = 1;
    char c = getchar ();
    while (c < '0' || c > '9') {
        if ( c == '-' ) sign = - 1;
        c = getchar ();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar ();
    }
    x = x * sign;
}

const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll INF = ll(1e15);
const int mod = 1e9+7;
const double PI = acos(-1);
//#define LOCAL


int main(int argc, char * argv[])
{

    ll x,y;
    read(x);read(y);
    ll ans = INF;
    ans=min(ans,abs(x+y)+1);
    if(x>=y) ans=min(abs(x-y)+2,ans);
    else ans=min(ans,abs(x-y));
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;
 
template <class T> using V = vector<T>;
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
const long long INF = 1LL << 60;
 
using ll = long long;
using db = double;
using st = string;
using ch = char;
using bl = bool;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
using vbl = V<bl>;
 
 
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>(b);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;
 

vll dp(100100);

ll sum(ll n) {
  ll m=0;
  FOR(i,0,20){
    m+=n%10;
    n/=10;
    if(n==0){
      break;
    }
  }
  return m;
}
 
 
const int MAX = 510000;
const int MOD = 1000000007;
 
long long fac[MAX], finv[MAX], inv[MAX];
 
void Comuse() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
 
#define comuse Comuse()
 
ll combi(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
 
 
 
ll lcm(ll a,ll b){
  ll n;
  n=a/gcd(a,b)*b;
  return n;
}
 
 
/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
 
 
signed main() {
  ll n;
  	ci(n);
  FOR(i,0,1901000000){
    if(i%2==0){
      n*=3;
    }
    else{
      n/=3;
    }
  }
  co(3*n*n)
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include<cstdio>
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  string S;
  cin >> S;
  
  string ans = "Yes";
  for (int i = 0; i < 4; i++) {
    int cnt = count(cbegin(S), cend(S), S[i]);
    if (cnt != 2) {
      ans = "No";
    }
  }
  
  cout << ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+7;

const int alphabet = 26;
const int offset = 'a';

struct node {
    int val;
    node* nxt[alphabet];

    node () {
        val = 0;
        for (int i = 0; i < alphabet; i++) nxt[i] = nullptr;
    }
};

struct Trie {
    node* root;

    Trie() {
        root = new node();
    }

    void addString(const string& s) {
        node* tmp = root;

        for (int i = 0; i+1 < s.size(); i++) {
            if (tmp->nxt[s[i]-offset]==nullptr)
                tmp->nxt[s[i]-offset] = new node();
            tmp = tmp->nxt[s[i]-offset];
        }
        tmp->val |= 1<<(s.back()-offset);
    }

    int countPrefixes(const string& s) {
        vector< int >fr(alphabet, 0);
        for (char c : s) fr[c-offset]++;

        int ans = 0;
        node* tmp = root;
        for (int i = 0; i+1 < s.size(); i++) {
            for (int j = 0; j < alphabet; j++) {
                if (fr[j]==0) continue;
                ans += (tmp->val>>j)&1;
            }
            fr[s[i]-offset]--;
            if (tmp->nxt[s[i]-offset]==nullptr) break;
            tmp = tmp->nxt[s[i]-offset];
        }

        return ans;
    }

    ~Trie() {
        deleteSubtree(root);
    }

    void deleteSubtree(node* u) {
        for (int i = 0; i < alphabet; i++)
            if (u->nxt[i]!=nullptr) deleteSubtree(u->nxt[i]);
        delete u;
    }
};

string s[MAXN];

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

    int n;
    cin >> n;


    Trie trie;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        reverse(s[i].begin(), s[i].end());
        trie.addString(s[i]);
    }

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += trie.countPrefixes(s[i]);
    }

    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 270900
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define OUT(x) cout << (x) << endl;
#define OUTA(a, n) \
    REP(i, n) { cout << (a[i]) << (i == n - 1 ? "\n" : " "); }
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) \
    SORT(a);     \
    reverse(a.begin(), a.end())
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

typedef pair<ll, ll> ii;
typedef vector<ii> vp;
#define OUTA2(a, n) \
    REP(i, n) { cout << (a[i]).first << " " << (a[i]).second << endl; }

ll N;
vi A, B;

int main()
{
    cin >> N;
    A = vi(N);
    B = vi(N);
    REP(i, N)
    {
        cin >> A[i];
    }
    REP(i, N)
    {
        cin >> B[i];
    }

    ll ans = INF;
    REP(p, 1 << N)
    {
        vp X = vp(N);
        REP(i, N)
        {
            X[i] = ii(i, 0);
        }
        vi Y = vi(N);
        REP(i, N)
        {
            Y[i] = ((p >> i) & 1) ? B[i] : A[i];
        }
        ll cnt = 0;
        REP(i, N)
        {
            ll k = INF;
            for (ll j = i; j < N; ++j)
            {
                if ((j - i + X[j].second) % 2 == ((p >> X[j].first) & 1) and (k == INF or Y[X[j].first] < Y[X[k].first]))
                {
                    k = j;
                }
            }
            if (k == INF)
            {
                cnt = INF;
                break;
            }
            for (ll j = k; j > i; --j)
            {
                swap(X[j - 1], X[j]);
                X[j - 1].second = 1 - X[j - 1].second;
                X[j].second = 1 - X[j].second;
                ++cnt;
            }
        }
        REP(i, N - 1)
        {
            if (Y[X[i].first] > Y[X[i + 1].first])
            {
                cnt = INF;
            }
        }
        ans = min(ans, cnt);
    }
    if (ans == INF)
    {
        ans = -1;
    }

    OUT(ans)
}

Measured memory_bytes: 256
// Problem : K - Stones
// Contest : AtCoder - Educational DP Contest
// URL : https://atcoder.jp/contests/dp/tasks/dp_k?lang=en
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define Ma7moud_7amdy                                                                                                  \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(NULL);                                                                                                     \
    cout.tie(NULL)
#define Open_Sesame Open()
#define all(v) ((v).begin()), ((v).end())
#define allr(v) ((v).rbegin()), ((v).rend())
#define clr(arr, x) memset(arr, x, sizeof arr)
#define endl "\n"
#define watch(x) cout << #x << " = " << x << endl;
#define RT(x) return cout << (x), 0;
#define Accepted 0
typedef long long ll;
typedef vector<int> vi;
const int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
void Open() {
#ifndef ONLINE_JUDGE
	freopen("Input.txt", "r", stdin);
	freopen("Output.txt", "w", stdout);
#endif
}
const int mod = ll(1e9 + 7), N = 2000 + 5;
//“Nobody but you have to believe in your dreams to make them a reality.” ― Germany Kent
int n, a[101], k;
int mem[(int) 1e5+1][2];
bool stones(int rem = k, bool state = 0) {

	if (rem == 0)
		return state;

	int &ret = mem[rem][state];
	if (~ret)
		return ret;
	ret = state;

	for (int i = 0; i < n; i++) {
		if (rem - a[i] >= 0) {
			if (state)
				ret &= stones(rem - a[i], !state);
			else
				ret |= stones(rem - a[i], !state);
		}
	}
	return ret;
}
int main() {
	Ma7moud_7amdy
	;
	// Open_Sesame;
	clr(mem, -1);
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	cout << (stones() ? "First\n" : "Second");
}


Measured memory_bytes: 12200
#!/usr/bin/env python3
import sys

def _solve(counts, k, n, used=[]):
    ret = 0
    digits = 0
    while k >= 2 ** digits:
        digits += 1
    tmp = 0
    for idx, c in enumerate(counts):
        if not idx in used:
            if n - 2 * c > 0 and tmp + 2 ** idx <= k:
                ret += (2 ** idx) * (n - c)
                tmp += 2 ** idx
            else:
                ret += (2 ** idx) * c
    if digits > 0:
        last = counts[digits - 1]
        if n - 2 * last >= 0:
            most_bit = 2 ** (digits - 1)
            k_ = k - most_bit
            ret = max(ret, _solve(counts, k_, n, used + [digits - 1]) + most_bit * (n - last))
    return ret


def solve(N: int, K: int, A: "List[int]"):
    counts = [0] * 45
    for num in A:
        n = num
        idx = 0
        while n > 0:
            if n % 2 == 1:
                counts[idx] += 1
            idx += 1
            n //= 2
    ret = _solve(counts, K, N)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 16352
#include <iostream>
#include <vector>

using namespace std;

int main(){
    int N, M;
    while(cin >> N >> M && N>0 && M>0){
        vector<int> h(N);
        vector<int> w(M);
        for(int i = 0; i < N; i++){
            cin >> h[i];
        }
        for(int i = 0; i < M; i++){
            cin >> w[i];
        }
        vector<int> h_len(1500010, 0);
        for(int i = 0; i < N; i++){
            int tmp = 0;
            for (int j = 0; j < N - i; j++){
                tmp += h[i + j];
                h_len[tmp]++;
            }
        }
        vector<int> w_len(1500010, 0);
        for(int i = 0; i < M; i++){
            int tmp = 0;
            for (int j = 0; j < M - i; j++){
                tmp += w[i + j];
                w_len[tmp]++;
            }
        }
        int count = 0;
        for(int i = 1; i < 1500010; ++i){
            if(h_len[i] != 0){
                if(w_len[i] != 0){
                    count += (h_len[i] * w_len[i]);
                }
            }
        }
        cout << count << endl;
    }
}

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

bool pairCompare(const pair<int,int>& firstElof, const pair<int,int>& secondElof)
{
    return firstElof.second < secondElof.second;
}

int main() {
    cin.tie(0);
   	ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());

    int N, M;
    cin >> N >> M;

    int P[M],Y[M];
    for (int i = 0; i < M; i++) {
        cin >> P[i] >> Y[i];
    }
    
    map<int, vector<pair<int, int>>> cities;
    for(int i = 0; i < M; i++) {
        cities[P[i]].push_back({i, Y[i]});
    }

    int order[M];
    for (auto itr = cities.begin(); itr != cities.end(); itr++) {
        vector<pair<int, int>> c = itr->second;
        sort(c.begin(), c.end(), pairCompare);
        // cout << 'p' << itr->first << endl;
        for (int i = 0; i < c.size(); i++) {
            // cout << c[i].second << endl;
            order[c[i].first] = i;
        }
    }

    for (int i = 0; i < M; i++) {
        cout << setfill('0') << right << setw(6) << P[i] << setw(6) << order[i]+1 << endl;
    }

}



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

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

vs32 cnt(1024);

int  mycount(int x)
{
    int ret = 0;
    while (x)
    {
        ret += (x & 1);
        x >>= 1;
    }
    return ret;
}

void init()
{
    rep (i, 1024)
    {
        cnt[i] = mycount(i);
    }
}

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

    init();
    int n;
    cin >> n;
    vs32 f(n, 0);
    rep (i, n)
    {
        int temp;
        rep (j, 10)
        {
            cin >> temp;
            f[i] = (f[i] << 1) | temp;
        }
    }

    vector< vs32 > c(n, vs32(11));
    rep (i, n)
    {
        rep (j, 11)
        {
            cin >> c[i][j];
        }
    }

    int ans = -(int)1e9;
    int sum = 0;
    rep (i, 1024)
    {
        if (cnt[i] == 0) continue;
        sum = 0;
        rep (j, n)
        {
            sum += c[j][cnt[f[j] & i]];
        }
        ans = MAX(sum, ans);
    }

    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 256
x, y, z = map(int, input().split())

a = abs(y-x) + abs(z-y)
b = abs(z-x) + abs(y-z)
c = abs(x-y) + abs(z-x)
d = abs(z-y) + abs(x-z)
e = abs(x-z) + abs(y-x)
f = abs(y-z) + abs(x-y)

print(min(a,b,c,d,e,f))

Measured memory_bytes: 3064
# -*- coding: utf-8 -*-

k, x = map(int, input().split())

min_x = max(x - k + 1, -1000000)

max_x = min(x + k - 1, 1000000)

ans = []
for i in range(x - k + 1, x + k):
    ans.append(str(i))

print(' '.join(ans))

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

int gcd(int p,int q){
    if(p%q == 0){
        return q;
    }
        return gcd(q,p%q);
}

int main(){
    int k,a,b; cin >> k >> a >> b;
    bool f = false;
    for(int i = a;i<=b;i++){
        if(i%k == 0){
            f = true;
        }
    }

    if(f){
        cout << "OK" << endl;
    }else{
        cout << "NG" << endl;
    }
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(ll i=(a);i<(b);i++)
#define per(i,a,b) for(ll i=(b)-1;i>=(a);i--)
ll a,b,n;
int main() {
    ios_base::sync_with_stdio(0);
    cin>>a>>b>>n;
    ll x=min(b-1,n);
    cout<<a*x/b-a*(x/b)<<"\n";
}


Measured memory_bytes: 3612
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
import math
import bisect
import numpy as np
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(1000000)
# MOD = 10 ** 9 + 7
# INF = float("inf")


def bfs(s, n, g):
    que = deque([])
    que.append(s)
    check = [-1] * n
    check[s] = 0
    while que:
        u = que.popleft()
        for v in g[u]:
            if check[v] == -1:
                check[v] = check[u] + 1
                que.append(v)
    if -1 in check:
        return True
    else:
        return False


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    gg = deque([])
    for _ in range(m):
        a, b = [int(i) - 1 for i in input().split()]
        g[a].append(b)
        g[b].append(a)
        gg.append((a, b))
    ans = 0
    for i in range(m):
        a, b = gg.popleft()
        g[a].remove(b)
        g[b].remove(a)
        if bfs(0, n, g):
            ans += 1
        g[a].append(b)
        g[b].append(a)
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 19896
#include <iostream>
#include <string>
#include <vector>
using ll=long long;
using namespace std;

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

    int ans=0;
    int state=0;
    int a,b;
    for(int i=0;i<N;i++){
        cin>>a>>b;
        if(a==b){
            state++;
        }else{
            state=0;
        }
        if(state==3){
            ans=1;
        }
    }

    if(ans){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }

    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <iomanip>

using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }
#define INF 1LL<<60

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> s(M), c(M);
    REP(i, M) cin >> s[i] >> c[i];

    vector<int> ans(N);
    vector<bool> input(N, false);
    REP(i, M)
        if(s[i]==1 && c[i] != 0 && !input[s[i]-1]) {
            ans[0] = c[i];
            input[s[i]-1] = true;
        } else if (s[i]==1 && c[i] == 0 && N>=2) {
            cout << -1 << endl;
            return 0;
        }
         else if((input[s[i]-1]==false) || (input[s[i]-1]&&ans[s[i]-1]==c[i])) {
            ans[s[i]-1] = c[i];
            input[s[i]-1] = true;
        } else {
            cout << -1 << endl;
            return 0;
        }
    if(ans[0] == 0 && N>=2) ans[0] = 1;

    REP(i, N) cout << ans[i];
    cout << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <iostream>
#include <math.h>
#include <time.h>
#include <unistd.h>
#include <algorithm>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <string>
 
#ifndef ONLINE_JUDGE
	#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#else
	#define DEBUG(x) do {} while(0);
#endif
 
#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(), (x).end()
#define PER(i, N) for(int (i) = (N)-1; (i) >= 0; (i)--)
#define REP(i, N) for(int (i) = 0; (i) < (int)(N); (i)++)
 #include <iomanip>
using namespace std;
typedef long long ll;
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}
template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>;
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }

int n,m,X;
int C[22];
int A[22][22];
void solve(istream& cin, ostream& cout) {
	cin>>n>>m>>X;
	REP(i, n) {
		cin >> C[i];
		REP(j, m) cin >>A[i][j];
	}
	int ans = 1<<30;
	REP(i, 1<<n) {
		bool good = true;
		int cprice = 0;
		REP(j, n) {
			if(i&(1<<j)) {
				cprice += C[j];
			}
		}
		REP(k, m) {
			int skill = 0;
			REP(j, n) {
				if(i&(1<<j)) {
					skill += A[j][k];
				}
			}
			if(skill < X) good = false;
		}
		if(good) {
			ans = min(ans, cprice);
		}
	}
	if(ans==1<<30) {
		cout <<-1<<endl;
	} else {
		cout <<ans<<endl;
	}
}


int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	solve(cin, cout);
	/*
	{
		istringstream instr("2\n2\n14");
		solve(instr, cout);
	}
 */
	return 0;
}


Measured memory_bytes: 3168
#include <iostream>
using namespace std;
int main( void )
{
	while ( !cin.eof() )
	{
		int n;
		cin >> n;
		if ( cin.eof() )
			break;

		int kotae = 0;

		for ( int a = 0; a <= 9; a++ )
		for ( int b = 0; b <= 9; b++ )
		for ( int c = 0; c <= 9; c++ )
		for ( int d = 0; d <= 9; d++ )
			if ( a + b + c + d == n )
				kotae++;

		cout << kotae << endl;

	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<algorithm>
#include<functional>
#include <string>
#include<iomanip>
#include<cstdio>
#include<math.h>
#include<set>
#include<stack>
#include<map>
#include<queue>
#include<cstring>
#include<vector>
typedef long long int ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EREP(i,n) for(int i=(n-1);i>=0;--i)
#define D(n,retu) REP(i,n){cin>>retu[i];}
#define mod 1000000007
#define MIN -93193111451418101
#define INF 931931114518101
using namespace std;
typedef pair<ll, ll>P;
template<typename T>
void fill_all(T& arr, const T& v) {
	arr = v;
}
template<typename T, typename ARR>
void fill_all(ARR& arr, const T& v) {
	for (auto& i : arr) { fill_all(i, v); }
}
#define MAX_NUM 50
long long comb[MAX_NUM + 1][MAX_NUM + 1];

ll par[100000], depth[100000];
static void calc_comb()
{
	for (uint32_t i = 0; i <= MAX_NUM; i++) {
		for (uint32_t j = 0; j <= i; j++) {
			if ((j == 0) || (i == j)) {
				comb[i][j] = 1;
			}
			else {
				comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
			}
		}
	}
}
#define yo 100001
//------------------変数-----------------------//
ll n;
map <ll,ll>a;
//-------------------関数----------------------//

int main() {
	cin >> n;
	REP(i, n) {
		ll hoge; cin >> hoge;
		a[hoge]++;
	}
	ll cnt = 0;
	for (auto it = a.begin(); it != a.end(); it++) {
		if (it->second % 2 == 1)cnt++;
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    int n,m,x;
    cin >> n >> m >> x;
    vector<int> a(n+1);
    vector<int> zahyou(m);
    rep(i,m){
         cin >> zahyou.at(i);
        a.at(zahyou.at(i))++;
    }
    

    int cnt_1=0;
    int cnt_2=0;

    for(int i=0; i<=x; i++){
        cnt_1 += a.at(i);
    }
    for(int i=x; i<=n; i++){
        cnt_2 += a.at(i);
    }
    if(cnt_1>cnt_2) cout << cnt_2<<endl;
    else    cout << cnt_1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define what_is(x) cerr << #x << " is " << x << endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define st first
#define nd second
#define endl '\n'

typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5+5;
const int INF = 1e9;
const int MOD = 1e9+7;

int n;

int main()
{
	IOS
	//freopen("input.txt", "r", stdin);
	cin >> n;
	int x = (n+1)/2;
	double ans = 1.0*x / n;
	cout << fixed << setprecision(9);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define REP(i, n) for (int i = 0; i < (n); i++)

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);

int main() {
  int n;
  cin >> n;
  vector<int> ans(n + 1, 0);
  for (int i = 2; i < n + 1; i++) {
    int j;
    cin >> j;
    ans[j]++;
  }
  for (int i = 1; i < n + 1; i++) {
    cout << ans[i] << endl;
  }
  return 0;
}

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

public class Main {
  
  public static void main(String[] args) {
    long INF = (long) 1e18 + 7l;
    // System.out.println(new Pair(2, 3).compareTo(new Pair(3, 2)));
    Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    // FastReader in = new FastReader();
    PrintWriter out = new PrintWriter(System.out);
    
    int n = in.nextInt();
    Pair[] ps = new Pair[n];
    for (int i = 0; i < n; i++) {
      ps[i] = new Pair(in.nextInt(), in.nextInt());
    }

    Arrays.sort(ps, (a, b) -> (a.a + a.b - b.a - b.b));


    // dp[i][j]: min height with j actors chosed from the actors ending at i 
    // int[][] dp = new int[n + 1][n + 1];
    // for (int i = 1; i <= n; i++) {Arrays.fill(dp[i], INF);}
    // for (int i = 1; i <= n; i++) {dp[0][i] = 0;}

    long[] dp = new long[n + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
      // for (int j = 1; j <= i; j++) {
      for (int j = i; j > 0; j--) {
        // dp[i][j] = dp[i - 1][j];
        // if (ps[i - 1].a >= dp[i - 1][j - 1]) dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + ps[i - 1].b);
        if (ps[i - 1].a >= dp[j - 1]) dp[j] = Math.min(dp[j], dp[j - 1] + ps[i - 1].b);
      }
      // Jren.p(dp);
    }

    for (int i = n; i > 0; i--) {
      if (dp[i] < INF) {System.out.println(i); return;}
    }
    





    }
  


  static class Pair implements Comparable<Pair> {
    int a, b;
    Pair (int aa, int bb) {a = aa; b = bb;}
    @Override
    public int compareTo(Pair y) {
      return 0;
    }
    @Override
    public String toString() {
      return "(" + a + ", " + b + ")";
    }
  }

  

  
  

  static class FastReader {

    public BufferedReader br; 
    StringTokenizer st; 

    public FastReader() {br = new BufferedReader(new InputStreamReader(System.in));} 

    String next() { 
      while (st == null || !st.hasMoreElements()) { 
          try {st = new StringTokenizer(br.readLine());} 
          catch (IOException e) {e.printStackTrace();} 
      } 
      return st.nextToken(); 
    } 

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

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

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

    String nextLine() {
      String str = ""; 
        try {str = br.readLine();} 
        catch (IOException e) {e.printStackTrace();} 
        return str; 
  }
}

} 

  



  
  


  















Measured memory_bytes: 36912
#include<bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll INF=(1LL<<62);
const ld pi=acosl((ld)-1);
const ll mod = 1000000007;
// const ll mod = 1234567;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
#define endn "\n"
#define TO_STRING(VariableName) # VariableName

template <typename T>ostream &operator<<(ostream &out,const vector<T> &v) {rep(i,(int)v.size()-1)cout<<v[i]<<" ";cout<<v[(int)v.size()-1];return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const map<T1, T2> &p) {out << "(" << p.first << ", " << p.second << ")";return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const pair<T1, T2> &p){out << "(" << p.first << ", " << p.second << ")";return out;}
template<class T>void debag(const T &obj){cout<<obj<<endl;}

bool solve(){
	string s,t;cin>>s>>t;
	t.pop_back();
	cout<<(s==t ? "Yes" : "No")<<endl;
	return false;
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout<<fixed<<setprecision(30);
  solve();
}


Measured memory_bytes: 3588
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;

int main() {
    int N;
    cin >> N;
    bool B = false;

    vector<int>vec(N);

    for (int i = 0; i < N; i++) {
        cin >> vec.at(i);
       
        if (vec.at(i) % 2 == 0 && !(vec.at(i) % 3 == 0 || vec.at(i) % 5 == 0)) {
            
                B = true;
            
            
        }
    }

    if (B == true) {
        cout << "DENIED"<< endl;
    }
    else {
        cout << "APPROVED" << endl;
    }

   

}

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

using namespace std;

typedef long long	ll;

const int N = int(2e5 + 100);
ll a[N];
int n;
const ll inf = ll(1e18);

ll calc(ll p){
	ll tot = 0LL;

	for(int i = 0 ; i < n ; i++){
		if(a[i] == 0){
			if(a[i] <= p){
				tot += ll(n - 1LL);
			}
		}else{
			ll m = p / a[i];

			if(a[i] * m > p){
				m--;
			}

			if(a[i] * m > p){
				m += 2;
			}

			if(a[i] < 0){
				tot += (a + n) - lower_bound(a, a + n, m);
				// if(p == -7){
				// 	printf("%d sums %d\n", i, (a + n) - lower_bound(a, a + n, m));
				// }
			}else{
				// if(p == -7){
				// 	printf("%d sums %d\n", i, upper_bound(a, a + n, m) - a);
				// }

				tot += upper_bound(a, a + n, m) - a;
			}

			if(a[i] * a[i] <= p){
				tot--;
			}
		}
	}

	return (tot >> 1LL);
}

int main(){
	ll k;

	scanf("%d %lld", &n, &k);

	for(int i = 0 ; i < n ; i++){
		scanf("%lld", &a[i]);
	}

	sort(a, a + n);

	ll lo = -inf;
	ll hi = inf;
	ll r = -1LL;

	while(lo <= hi){
		ll mid = (lo + hi) >> 1LL;
		ll res = calc(mid);
		// printf("%lld[%lld, %lld] gives %lld\n", mid, lo, hi, res);

		if(res >= k){
			r = mid;
			hi = mid - 1LL;
		}else{
			lo = mid + 1LL;
		}
	}

	printf("%lld\n", r);

	return 0;
}

Measured memory_bytes: 1792
N, K = map(int, input().split())
As = list(map(int, input().split()))

def getDistNexts(As):
    lenA = len(As)
    poss = dict()
    for i, A in enumerate(As):
        if A not in poss:
            poss[A] = i + lenA

    distNexts = [0]*(lenA)
    for i in reversed(range(lenA)):
        distNexts[i] = poss[As[i]] - i
        poss[As[i]] = i
    return distNexts

distNexts = getDistNexts(As)

NK = N*K

iNow = 0
dist = 0
hists = [-1] * N
hists[0] = 0
isSkipped = False
while dist + distNexts[iNow] + 1 < NK:
    dist += distNexts[iNow] + 1
    iNow = dist % N
    if not isSkipped and hists[iNow] != -1:
        period = dist - hists[iNow]
        dist += (NK-1-dist) // period * period
        isSkipped = True
    hists[iNow] = dist

Ss = []
setS = set()
for _ in range(NK-dist):
    A = As[iNow]
    if A in setS:
        S = ''
        while S != A:
            S = Ss.pop()
            setS.remove(S)
    else:
        Ss.append(A)
        setS.add(A)
    iNow = (iNow+1)%N

if Ss:
    print(' '.join(map(str, Ss)))


Measured memory_bytes: 47248