akhauriyash/Code-Regression huggingface dataset:
-- https://github.com/minoki/my-atcoder-solutions
{-# LANGUAGE BangPatterns #-}
import Data.Char (isSpace)
import Data.List (unfoldr)
import Data.Maybe (fromMaybe)
import Control.Monad
import Control.Monad.ST
import Control.Monad.Trans.Maybe
import Control.Monad.Trans.Class (lift)
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import qualified Data.ByteString.Char8 as BS

-- 有向グラフに閉路があるか判定し、閉路があれば Nothing を返す。
-- 閉路がなければ最長路の長さを返す。
solve :: V.Vector [Int] -> Maybe Int
solve !edges = runST $ runMaybeT $ do
  let !n = V.length edges  -- 頂点の個数
  !vec <- UM.replicate n (-2 :: Int) -- -2: new, -1: DFSの最中, 正: チェック済み
  let dfs !x = do
        s <- UM.read vec x
        case s of
          -2 -> do
            -- x を通る閉路があるかチェックする
            UM.write vec x (-1)
            !v <- foldM (\ !a y -> max a <$> dfs y) 0 (edges V.! x)
            lift $ do let !v' = v + 1
                      UM.write vec x v'
                      return v'
          -1 -> mzero  -- コールスタックのどこかで dfs x が呼ばれている。閉路
          v -> return v
  mapM_ dfs [0..n-1]
  lift (U.maximum <$> U.unsafeFreeze vec)

main = do
  n <- readLn
  xs <- V.replicateM n $ do
    U.map (subtract 1) . U.unfoldrN (n-1) (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  let m = n * (n - 1) `quot` 2  -- グラフの頂点数
  let -- (i,j) (0 <= i < j < n) を 0 以上 m 未満の整数値にコードする
      makePair :: Int -> Int -> Int
      makePair i j | i' < j' = n * i' - (i' + 1) * i' `quot` 2 + j' - i' - 1
                   | otherwise = undefined
        where i' = min i j; j' = max i j
  -- 「試合 (i,j) よりも試合 (i',j') の方を後に行う場合に辺 makePair i j → makePair i' j' が存在する」ようなグラフを作る
  let edges :: V.Vector [Int]
      edges = V.create $ do
        !e <- VM.replicate m []
        V.forM_ (V.indexed xs) $ \(i,ys) -> do
          U.forM_ (U.zip ys (U.tail ys)) $ \(a,b) -> do
            -- (i,a) -> (i,b)
            let !b' = makePair i b
            -- VM.modify e (b' :) (makePair i a)
            t <- VM.read e (makePair i a)
            VM.write e (makePair i a) $! b' : t
        return e
  print $ fromMaybe (-1) $ solve edges


Measured memory_bytes: 103036
#pragma GCC optimize "O2"
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <queue>
// for iota, accumulate, partial_sum
// #include <numeric>
// #include <iomanip>
// #include <fstream>
// #include <deque>
// #include <cmath>
// #include <unordered_map>
// #include <utility>
// #include <unordered_set>
// #include <ctime>
// #include <stack>
// #include <bitset>
// #include <random>
// #include <cstring>
// #include <cassert>
// #include <complex>
using namespace std;
typedef unsigned long long int lu;
typedef long long int ll;
typedef long double ld;
#define v vector<ll>
#define vu vector<lu>
#define vvu vector<vector<lu>>
#define vld vector<ld>
#define vs vector<string>
#define pll pair<ll, ll>
#define vpll vector<pair<ll, ll>>
#define puu pair<lu, lu>
#define vpuu vector<pair<lu, lu>>
const lu MOD = 1000000007;
const ld PI = 2 * acos(0.0);
#define round(x, y) ((x + y - 1) / y)
#define ce(x, y) ((x + y - 1) / y)
#define amax(x, y) \
    if (y > x)     \
        x = y;
#define amin(x, y) \
    if (y < x)     \
        x = y;
#define lcm(x, y) ((x) * (y) / __gcd(x, y))
#define sq(x) ((x) * (x))
#define cb(x) ((x) * (x) * (x))

#define all(x) x.begin(), x.end()

v ga(ll n)
{
    v a;
    for (ll i = 0; i < n; i++)
    {
        ll p;
        // scanf("%lld", &p);
        cin >> p;
        a.push_back(p);
    }
    return move(a);
}

vu gau(lu n)
{
    vu a;
    for (lu i = 0; i < n; i++)
    {
        lu p;
        // scanf("%lu", &p);
        cin >> p;
        a.push_back(p);
    }
    return move(a);
}
vs gas(lu n)
{
    vs a;
    for (lu i = 0; i < n; i++)
    {
        string p;
        // scanf("%lu", &p);
        cin >> p;
        a.push_back(p);
    }
    return move(a);
}

template <typename T, typename A>
void pa(vector<T, A> const &a)
{
    for (T p : a)
    {
        // printf("%lu ", a[i]);
        cout << p << " ";
    }
    cout << "\n";
}

void yes()
{
    cout << "YES\n";
}

void no()
{
    cout << "NO\n";
}

void yesno(int f)
{
    if (f)
        yes();
    else
        no();
}

void solve()
{
    ll n;
    cin >> n;
    vector<v> dp(n, v(3, 0));
    for (ll i = 0; i < n; i++)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        if (i == 0)
        {
            dp[i][0] = a;
            dp[i][1] = b;
            dp[i][2] = c;
        }
        else
        {
            ll a2, b2, c2;
            b2 = max(dp[i - 1][0] + b, dp[i - 1][2] + b);
            a2 = max(dp[i - 1][1] + a, dp[i - 1][2] + a);
            c2 = max(dp[i - 1][0] + c, dp[i - 1][1] + c);
            dp[i][0] = a2;
            dp[i][1] = b2;
            dp[i][2] = c2;
        }
    }
    cout << max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]});
}

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

    solve();
    return 0;
}

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

using namespace std;

int main()
{
	int n, p;

	while (scanf("%d %d", &n, &p), n){
		vector<int> v(n);

		int index = 0;
		int stone = p;

		while (true){
			if (p){
				p--;
				v[index] += 1;

				if (p == 0 && v[index] == stone){
					break;
				}
			}
			else {
				p = v[index];
				v[index] = 0;
			}

			index++;
			index %= n;
		}

		printf("%d\n", index);
	}

	return (0);
}

Measured memory_bytes: 1172
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
int cnt[1234];
int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    cnt[a]++;
    cnt[b]++;
    cnt[c]++;
    if(cnt[5]==2&&cnt[7]==1)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int f[50];

int  fb(int n){
  if(n == 0 || n == 1){
    f[n] = 1;
    return f[n];
  }
  if(f[n] != 0)return f[n];
  f[n] = fb(n-1) + fb(n-2);
  return f[n];
}

int main(){
  int i,n;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    f[i]=0;
  }

  printf("%d\n",fb(n));

  return 0;
}


Measured memory_bytes: 2108
#include <bits/stdc++.h>
#define INF INT_MAX
#define ll  long long
#define ull unsigned long long
#define rep(i,n) for(ll i=0; i<n; ++i)
#define FOR(i, s, e) for(ll i=s; i<e; ++i)
#define MOD 1000000007
using namespace std;
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;}

int main() {
  int N; cin >> N;
  vector<int> L(N);
  rep(i,N) cin >> L[i];
  sort(L.begin(), L.end());
  ll ans = 0;
  for(int i=0; i<N-2; ++i) {
    for(int j=i+1; j<N-1; ++j) {
      auto it = lower_bound(L.begin()+j+1, L.end(), L[i]+L[j]);
      ans += distance(L.begin()+j+1, it);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import bisect
N = int(input())
L = [int(i) for i in input().split(' ')]
L.sort()

sum = 0
for i,k in enumerate(L):
  for j in range(i+1, N):
    sum += bisect.bisect_left(L,L[j] + k) - j - 1


print(sum)

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

const long long INF = 4e18;

int main() {
    long long n,X; scanf("%lld %lld", &n, &X);
    vector<long long> x(n+1);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &x[i+1]);
        x[i+1] += x[i];
    }
    long long ans = INF;
    for (int k = 1; k <= n; k++) {
        long long have = n, cand = 0;
        for (int cost = 3; have > 0; cost += 2) {
            int real_cost = max(5,cost);
            auto paint = have;
            if (paint > k) paint = k;
            cand += (x[have] - x[have-paint]) * real_cost;
            if (cand > INF) cand = INF;
            have -= paint;
        }
        ans = min(ans, cand + X*k);
    }
    printf("%lld\n", ans + X*n);

    return 0;
}


Measured memory_bytes: 1792
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=998244353;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	string s,t;cin>>s>>t;
	int n=s.size();
	for(int i=0;i<n;i++){
		s.pub(s[0]);
		s.erase(s.begin());
		if(s==t){cout<<"Yes"<<endl;return 0;}
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define ii int
#define jmp cout<<"\n"
#define vl vector<ll>
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define printv(v) for(auto x:v) cout<<x<<" "; jmp;
#define endll "\n"
#define SORT(v) sort(v.begin(),v.end())
#define REV(x)  reverse(x.begin(),x.end())
#define UNI(a) a.erase( unique( a.begin(), a.end() ), a.end() )
#define si(x) x.size()
#define ff first
#define ss second
#define iin insert
using namespace std;
ll ctr, mx;
ll dp[100005];
ll dfs(vector<vector<ll>>&g, ll s)
{
	//cout << ctr << " ";
	if (dp[s] != -1)
		return dp[s];
	ll ms = 0;
	for (auto x : g[s])
	{
		ms = max(ms, dfs(g, x));

	}
	return dp[s] = (ms + 1);
}
void solve()
{
	ll n, m, l, r;
	cin >> n >> m;
	vector<vector<ll> >adj(n + 1);
	for (ll i = 0; i < m; i++)
	{
		cin >> l >> r;
		adj[l].pb(r);
	}
	ll res = 0;
	memset(dp, -1, sizeof(dp));
	for (ll i = 1; i <= n; i++)
	{
		res = max(res, dfs(adj, i));
	}

	cout << res - 1  << endll;

}
int main()
{
	fast;
// #ifndef ONLINE_JUDGE
// 	freopen("input.txt", "r", stdin);
// 	freopen("output.txt", "w", stdout);
// #endif
	// ll t;
	// cin >> t;
	// while (t--)
	solve();
	return 0;
}


Measured memory_bytes: 8576
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
typedef long double ld;
#define rep(i,a,b) for(ll i=a ; i<b ; i++)
#define qrep(que, ite) for(auto ite=begin(que) ; ite!=end(que) ; ite++)
const int max_n = 1e5;
const ll mod = 1e9+7;
const ll INF = 1LL<<60;
const int inf = 1e5;
//typedef long double ld;
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; }
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) {
        return -par[root(x)];
    }
};
int main(){
  int N;  cin>>N;
  vector<ll> A(N),B(N);
  rep(i,0,N) cin>>A[i]>>B[i];
  ll sum=0;
  for(int i=N-1 ; i>=0 ; i--){
    A[i] += sum;
    sum += B[i]-(A[i] % B[i]);
    if(A[i]%B[i]==0) sum -= B[i];
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <numeric>

using namespace std;
#define ALL(x)			(x).begin(),(x).end()
#define REP(i, n)		for (int (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n)	for (int (i) = m ; (i) < (ll)(n) ; ++(i))
#define INF				(int)2e9
#define MOD				(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)		(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)		(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)	((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)		(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)		(!IsOdd((x)))						
#define M_PI			3.14159265358979323846
typedef long long		ll;
typedef pair<ll, string>	P;
typedef vector<ll>		VLL;
typedef vector<VLL>		VVLL;
typedef vector<VVLL>	VVVLL;

/*-----------------------------------------------------------------------------
　処理
 -----------------------------------------------------------------------------*/
int main()
{
	int N, R;
	cin >> N >> R;

	int ans;
	if (N < 10) {
		ans = 100 * (10 - N) + R;
	} else {
		ans = R;
	}

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


Measured memory_bytes: 256
h,w,k = map(int, input().split())
s = [ list(input()) for _ in range(h)]
a = [ [0]*w for _ in range(h)]
b = 1
e = 1
n_0 = []
for i in range(h):
    c = 0
    d = 0
    for j in range(w):
        if s[i][j]=="#" and c!=0:
            b+=1
        elif s[i][j]=="#" and c==0:
            c+=1
        a[i][j]+=b

        if i<h-1 and s[i+1][j]=="#":
            d=1
    if c==0:
        n_0.append(i)
        e = b+1
        e-=1
    elif d==1:
        e = b+1
        b +=1
    else:
        e = b+1
        e -=1
        b +=1

x = 1
for i in range(h):
    if i in n_0 and i!=h-1:
        x+=1
    elif i in n_0 and i==h-1:
        for j in range(x):
            results = map(str, a[i-x])
            answer = " ".join(results)
            print(answer)
    else:
        for j in range(x):
            results = map(str, a[i])
            answer = " ".join(results)
            print(answer)
        x = 1

Measured memory_bytes: 7872
import sys


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


sys.setrecursionlimit(20000000)


def main():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]
    AB = sorted(AB, key=lambda x: x[0])
    flag = AB[0][1]
    cnt = 1
    for i in range(M):
        if AB[i][0] >= flag:
            flag = AB[i][1]
            cnt += 1
        elif AB[i][1] > flag:
            continue
        else:
            flag = AB[i][1]
    print(cnt)


if __name__ == "__main__":
    main()


Measured memory_bytes: 61040
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e6 + 5;
const int mod = 1e9 + 7;

inline void add_mod(int &a,int b){ if((a+b)>=mod) a-=mod;}

ll f[MAXN][2][2];

int main(void)
{
	int n;
	scanf("%d",&n);
	
	f[0][0][0] = 1;
	for(int i=1; i<=n; ++i)
	{
		f[i][0][0] = f[i-1][0][0] * 8 %mod;
		f[i][0][1] = (f[i-1][0][1] * 9 + f[i-1][0][0]) %mod;
		f[i][1][0] = (f[i-1][1][0] * 9 + f[i-1][0][0]) %mod;
		f[i][1][1] = (f[i-1][1][1] * 10 + f[i-1][0][1] + f[i-1][1][0]) %mod;
	}
	printf("%lld",f[n][1][1]);
	return 0;
}

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

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifndef ONLINE_JUDGE
#define show(...) cerr << "[" << #__VA_ARGS__ << "] :", debug_out(__VA_ARGS__)
#else
#define show(...) 42
#endif


#define f first
#define s second
#define endl "\n"
#define pb push_back
#define  oo 0x3f3f3f3f
#define limit 1000000007
#define int long long int
#define mod(x,m) ((x%m+m)%m)
#define ll long long
#define all(v) v.begin(),v.end()
#define max3(x,y,z) max(x,max(y,z))
#define min3(x,y,z) min(x,min(y,z))
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define repb(i,a,b) for(int i=(a);i>=(b);i--)
#define fastio std::ios::sync_with_stdio(false)
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define input_from_file  freopen("input.txt", "r", stdin);

int dp[1<<21];


signed main(){
  //input_from_file;
  int n; cin>>n;
  int arr[25][25];
  for(int i=0;i<n;i++)
  for(int j=0;j<n;j++) cin>>arr[i][j];
  memset(dp,0,sizeof dp);
  dp[0] = 1;
  for(int mask=0;mask<(1<<n);mask++){
    int a = __builtin_popcount (mask);
    for(int b=0;b<n;b++)
     if( arr[a][b] && !(mask&(1<<b)) ) {
       int tmp = mask|(1<<b);
       dp[tmp] += dp[mask];
       dp[tmp] %= limit;
     }
  }
  cout<<dp[(1<<n)-1]<<endl;
}


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

#define dump(...) do{print_vars(cout<<"# "<<#__VA_ARGS__<<'=',__VA_ARGS__);cout<<endl;}while(0)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;

template<typename T,typename U>bool chmin(T& a,const U& b){return a>b?(a=b,1):0;}
template<typename T,typename U>bool chmax(T& a,const U& b){return a<b?(a=b,1):0;}

void print_vars(ostream&){}
template<typename Car,typename... Cdr>
void print_vars(ostream& os,const Car& car,const Cdr&... cdr){
	print_vars(os<<car<<(sizeof...(cdr)?",":""),cdr...);
}

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<int I,typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<int I,typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	os<<get<I>(t)<<(sizeof...(Cdr)?",":"");
	print_tuple<I+1,Cdr...>(os,t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<0,Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

void dfs(vvi& g,vi& nodes,int level)
{
	vi ls,rs;
	rep(i,nodes.size())
		(i%2==0?ls:rs).push_back(nodes[i]);
	for(int i:ls)
		for(int j:rs)
			g[i][j]=g[j][i]=level;
	if(ls.size()>=2)
		dfs(g,ls,level+1);
	if(rs.size()>=2)
		dfs(g,rs,level+1);
}

int main()
{
	#ifndef _GLIBCXX_DEBUG
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	constexpr char endl='\n';
	#endif

	for(int n;cin>>n&&n;){
		vvi g(n,vi(n));
		vi nodes(n); iota(all(nodes),0);
		dfs(g,nodes,1);
		rep(i,n)
			repi(j,i+1,n)
				cout<<g[i][j]<<"\n "[j+1<n];
	}
}


Measured memory_bytes: 1536
#include <cassert>
#include <iostream>
#include <functional>
#include <iomanip>
#include <set>
#include <unordered_map>
#include <queue>
#include <vector>
#include <deque>
#include <algorithm>
#include  <cstring>
#include <string>
#include <cmath> 
using namespace std;
typedef long long LL;
const int MAX = 210000;
const LL base = 1e9 + 7;


struct Node {
	int x, y, w;
};


int za[60][60];

LL path[65][60][60];
LL dp[2][60][60];
void solve() {

	LL result = 0;
	int n;
	LL k;
	cin >> n>>k;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> za[i][j];
			path[0][i][j] = za[i][j];
		}
	}
	for (int p = 1; p <= 60; ++p) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (p == 1 && i == 1 && j == 2) {
					int xxx= 1;
				}
				for (int g = 0; g < n; ++g) { 
					path[p][i][j] += path[p - 1][i][g] * path[p - 1][g][j];
					path[p][i][j] %= base;
				}
			}
		}
	}

	for (int i = 0; i < n; ++i) {
		dp[0][i][i] = 1;
	}

	int nt = 0;
	for (int p = 0; p <= 60; ++p) {
		LL tk = (1LL << p);
		if ( (k&tk) == 0) continue;
		int nt1 = (nt + 1) % 2;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				dp[nt1][i][j] = 0;
				for (int g = 0; g < n; ++g) {
					dp[nt1][i][j] += dp[nt][i][g] * path[p][g][j];
					dp[nt1][i][j] %= base;
				}
			}
		}
		nt = nt1;
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			result += dp[nt][i][j];
			result %= base;
		}
	}
	cout << result << endl;

}

int main() {
	const int inId = 0;
	const int outId = 0;
	if (inId>0) {
		cerr << "redirect stdin to input " << inId << endl;
		string s = "input";
		s += to_string(inId);
		s += ".txt";
		auto r = freopen(s.c_str(), "r", stdin);	
		if (r == nullptr) {
			cerr<< "invalid input file "<< s;
		}
	}
	if (outId>0) {
		cerr << "redirect stdout to stdout " << outId << endl;
		string s = "stdout";
		s += to_string(outId);
		s += ".txt";
		auto r = freopen(s.c_str(), "w", stdout);
		if (r == nullptr) {
			cerr<< "invalid output file "<< s;
		}		
	}
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // close sync between cout and printf
	cout.precision(10);
	solve();
}
 

Measured memory_bytes: 2048
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>

int main(){
    long long X; std::cin >> X;
    long long ans = 0;
    for (int i = 1; i <= X; ++i) {
        for (int j = 2; j < 11; ++j) {
            int tmp = std::pow(i, j);
            if (ans < tmp && tmp <= X)
                ans = tmp;
        }
    }
    std::cout << ans << std::endl;

    return 0;
}

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

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#define dumpv(...)
#endif

#define rep(i, n) for (int i = 0; i < (n); i++)
#define mins(x, y) (x = min(x, y))
#define maxs(x, y) (x = max(x, y))
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
const int MOD = 1e9 + 7;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

void solve() {
  ll n;
  cin >> n;
  if (n % 2 == 1) {
    cout << 0 << endl;
    return;
  }
  ll ans = 0;
  dump(n);
  n /= 2;
  while (n >= 5) {
    ans += (n / 5);
    n /= 5;
    dump(n, ans);
  }
  cout << ans << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  // freopen("temp.1", "r", stdin);
  solve();
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LLP;

int main() {

  ll N, W;
  cin >> N >> W;
  vector<ll> w(N), v(N);
  rep(i,N) cin >> w[i] >> v[i];

  ll w1 = w[0];
  rep(i,N) w[i] -= w1;

  ll dp[N+1][N+1][3 * N + 1];
  rep(i,N+1) rep(j,N+1) rep(k,3*N+1) dp[i][j][k] = -1;
  
  rep(i,N+1) dp[i][0][0] = 0;

  for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) for (int k = 0; k <= 3 * N; k++) {
    if (dp[i - 1][j][k] >= 0) dp[i][j][k] = dp[i - 1][j][k];
    if (k - w[i - 1] >= 0 && dp[i - 1][j - 1][k - w[i - 1]] >= 0) {
      dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k - w[i - 1]] + v[i - 1]);
    }
  }
  
  ll ans = dp[N][0][0];

  for (int j = 1; j <= N; j++) {
    W -= w1;
    for (int k = 0; k <= min(3 * N, W); k++) {
      ans = max(ans, dp[N][j][k]);
    }
  }

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

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

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

    int answer = 0;
    for (int i = 1; i <= (int)n / 2; i++)
    {
        if (i != n - i)
        {
            answer++;
        }
    }

    cout << answer << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100003,INF=1<<30;

int main(){
    
    int N,M;cin>>N>>M;
    
    vector<int> cnt(M+2,0),yaku[M+1];
    
    for(int i=1;i<=M;i++){
        for(int j=1;j*j<=i;j++){
            if(i%j==0){
                yaku[i].push_back(j);
                if(j*j!=i) yaku[i].push_back(i/j);
            }
        }
    }
    
    for(int i=0;i<N;i++){
        int a,b;cin>>a>>b;
        if(a==b){
            for(int j=0;j<yaku[a].size();j++){
                int c=yaku[a][j];
                cnt[c]++;
                cnt[c+1]--;
            }
        }else if(a-1<=b-a+1){
            cnt[1]++;
            cnt[b+1]--;
        }else if(b-a+1<=20){
            set<int> S;
            
            for(int i=a;i<=b;i++){
                for(int j=0;j<yaku[i].size();j++){
                    int c=yaku[i][j];
                    S.insert(c);
                }
            }
            for(set<int>::iterator it=S.begin();it!=S.end();it++){
                cnt[*it]++;
                cnt[*it+1]--;
            }
            
        }else{
            
            cnt[1]++;
            cnt[b-a+2]--;
            cnt[a]++;
            cnt[b+1]--;
            
            int now=2;
            while(1){
                int l=(a+now-1)/now,r=b/now;
                if(l<=b-a+1){
                    if(r>b-a+1){
                        cnt[b-a+2]++;
                        cnt[r+1]--;
                    }
                    break;
                }else{
                    cnt[l]++;
                    cnt[r+1]--;
                }
                now++;
            }
        }
    }
    
    for(int i=2;i<=M;i++){
        cnt[i]+=cnt[i-1];
    }
    
    for(int i=1;i<=M;i++){
        cout<<cnt[i]<<endl;
    }
}




Measured memory_bytes: 10880
#include<iostream>

int main(){
  int a,b;
  std::cin >> a >> b;
  if(a < b){
    std::cout << "a < b" << std::endl;
  }else if(a > b){
    std::cout << "a > b" << std::endl;
  }else{
    std::cout << "a == b" << std::endl;
  }
  return 0;
}

Measured memory_bytes: 3036
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#include<set> 
#include<math.h>
#define pai arccos(-1);
#define keta(n) cout << fixed << setprecision((n));
#define ll long long;

int func(int x){
  int sum = 0;
  while(x>0){
    sum += x%10;
    x /= 10;
  }
  return sum;
}

int main(){
  int n;
  cin>>n;
  int d = n;
  for(int i=1;i<n;i++){
    int a= func(i);
    int b= func(n-i);
    d = min(d,a+b);
  }
  
  cout<<d;
        


}


Measured memory_bytes: 3604
/**
 *      author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *      created : 2019-11-24 22:06:13
**/

#include <iostream>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
#include <bitset>
#include <cassert>
#include <cctype>
#include <functional>
#include <iomanip>
#include <random>
#include <utility>

using namespace std;

using int64 = long long;
#define debug(_) cerr << #_ << ": " << (_) << '\n'
template<typename T> inline void chmin(T &a, T b) { if (a > b) a = b; return; }
template<typename T> inline void chmax(T &a, T b) { if (a < b) a = b; return; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& vec) { os << '{'; for (size_t i = 0; i < vec.size(); ++i) { os << vec[i]; if (i != vec.size() - 1) os << ','; } os << '}'; return os; }
template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) { return os << '{' << p.first << " " << p.second << '}'; }

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

  int n, m; cin >> n >> m;
  string s; cin >> s;

  vector<int> ans;

  reverse(s.begin(), s.end());
  //debug(s);

  int cur = 0;

  while (cur < n) {
    int next = -1;
    int res = (int) s.size() - 1 - cur;
    //debug(res);
    
    for (int i = min(m, res); i >= 1; --i) {
      if (s[cur + i] == '0') {
        next = i;
        break;
      }
    }
    if (next == -1) {
      cout << -1 << endl;
      return 0;
    } else {
      cur += next;
      ans.emplace_back(next);
    }
  }

  reverse(ans.begin(), ans.end());

  for (int xx : ans) {
    cout << xx << " ";
  }

  return 0;
}

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

using namespace std;

int main(void)
{
  int A,B;
  cin >> A >> B;
  if(A>=13)
    cout << B;
  else if(A>=6&&A<=12)
    cout << B/2;
  else
    cout << 0;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>

using namespace std;

#define mod 1000000007

int main()
{
	string a, b, c;
	cin >> a >> b >> c;
	cout << (char)toupper(a[0]) << (char)toupper(b[0]) << (char)toupper(c[0]) << endl;
	return 0;
}

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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

int N;
double V[100];

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

  std::cin >> N;

  for(int i=0;i<N;++i){
      std::cin >> V[i];
  }

  std::sort(V, V + N);

  double res = V[0];

  for(int i=1;i<N;++i){
      res = (res + V[i]) / 2;
  }

  printf("%.10f\n", res);
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static final int MOD = 1000000007;
    static final int INF = 1 << 30;

    Main() {
        Scanner sc = new Scanner(System.in);
        long ans = 1;
        int N = sc.nextInt();
        for(int i=1;i<=N;i++){
            ans*=i;
            ans%=MOD;
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        new Main();
    }
}


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

int main(){
    int num=100000;
    int n;
    cin>>n;
    for(int a=0;a<n;a++){
        num+=num/20;
        if(num%1000!=0){
            num-=num%1000;
            num+=1000;
        }
    }
    cout<<num<<endl;
    return 0;
}

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

using namespace std;




int main ()

{
set<int> s;
int n;
int f;

set<int>::iterator it1 = s.end();
set<int>::iterator it = s.end();

scanf("%d",&n);
for(int i =0;i<n;i++)
{

  scanf("%d",&f);

  it1 = s.find(f);

  if(it1 == it)
        s.insert(f);
  else
    s.erase(it1);

}


printf("%d",s.size());





}










Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    int ans = 100;
    int flag = 0;
    rep(k, S.length()) {
        if(S[k] != S[0]) flag = 1;
    } 
    if (flag == 0) {
        cout << "0" << endl;
        return 0;
    }
    string tmp = S;
    rep(i, S.length()) {
        S = tmp;
        rep(j, S.length()) {
            int flag = 0;
            rep(k, S.length()) {
                if (S[k] == S[i] && k > 0) S[k-1] = S[i];
            }
            S[S.length()-1-j] = S[i];
            rep(k, S.length()) {
                if(S[k] != S[i]) flag = 1;
            }
            //cout << S << endl;
            if (flag == 0) {
                ans = min(ans, j+1);
                //dump(ans);
                break;
            }
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
import decimal,math
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 10
N=int(raw_input())
f=map(int,raw_input().split())
cc=Counter(f)
dp=[]
for i in range(N+2):
	x=[]
	for j in range(N+2):
		y=[]
		for k in range(N+2):
			y.append(0)
		x.append(y)
	dp.append(x)

# print dp[0][0]	
for k in range(0,N+1):			
	for j in range(0,N+1):			
		for i in range(0,N+1):
			if(i==0 and j==0 and k==0):
				dp[i][j][k]=0			
			elif(i+j+k<=N):
				# print (i+j+k)
				dp[i][j][k] = N
				if(i>=1):
					dp[i][j][k]+=dp[i-1][j][k]*(i)
				if(j>=1):	
					 dp[i][j][k]+=dp[i+1][j-1][k]*(j)
				if(k>=1):	 
					 dp[i][j][k]+=dp[i][j+1][k-1]*(k)
				# print dp[i][j][k],	 
				dp[i][j][k]=dp[i][j][k]/float(i+j+k)
				# print dp[i][j][k]
# print dp
print dp[cc[1]][cc[2]][cc[3]]				


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


int main(){
  
    int w,a,b , x=0;

   scanf("%d %d %d",&w , &a , &b);
     
      if(a > b)
         {
         x = a - (b+w);
         printf("%d",x);
		 } else{
		 
      if(a+w >= b )
      {
          printf("0");	
	  }else{
	  	   x = b - (a+w) ;
	  	   printf("%d",x);
	  	    
	  }
	  
	   }  
     
}
  
   	


Measured memory_bytes: 256
//int a = stoi(c); 文字列をintへ
//小文字から大文字
//transform(a.begin(), a.end(), a.begin(), ::toupper);
//途中の出力をそのまま残さない
//数値計算 個数以外はdouble
//map<キー,値> p は辞書。p[キー] = 値
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//絶対値 abs()
//入力は空白で切れる
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//while(N)で回すとき、Nはコピーを作っておく
//小文字に対応する文字コード：S[i] - 'a'
//文字コード→小文字：(char)(数字+'a')
//グラフの距離:隣接行列で扱う
//等価なものに変換する思考
//bool型　初期値はTrue
//島渡りの問題：中間ノードに着目
//配列はvector<>を使う：意味わからないエラーがなくなる。
//背反な事象にちゃんとわける
//チェックリストはマップを使う
//数が大きい時の比較はstring型で行う
//全て0になったか調べたい->0になるたびにcntする
//またはかかつか
//例外処理は最初にする
//x = p^m + q^n...の約数の個数:(n+1)*(m+1)....
//N!のどの素因数で何回割れるか
//⇔1~Nまでの数がそれぞれどの素因数で何回割り切れるかの和
//パズルの問題->一般化して全探索
//数が大きい時のせぐふぉはコードテストで試してみる
//スペルミスに注意
//stack<ll> s;
//s.push(要素);s.top();s.pop();
//queue<ll> q;
//q.push(要素);q.front();q.pop();
//同じ作業繰り返す系の問題：収束先を見つける
//関係性は隣接行列で記録
//過半数：N/2.0で判定
//ある量からある量を引く系の問題：端から定義してやる
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
using namespace std;

//円周率
const double PI = 3.14159265358979323846;
//割るやつ
const ll MOD = (pow(10, 9) + 7);

// K進数でのNの桁数
ll dig(ll N, ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// a,bの最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

//a,bの最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

//階乗計算
ll f(ll n) {
	if (n == 0 || n == 1) return 1;
	else return (n * f(n - 1));
}

//Nのd桁目の数
ll dignum(ll N, ll d) {
	ll x = pow(10, d);
	N %= x;
	ll y = pow(10, d - 1);
	N /= y;
	return N;
}

//Nをdで何回割れるか
ll divcnt(ll N, ll d) {
	ll ans = 0;
	while (1) {
		if (N%d == 0) {
			ans++;
			N /= d;
		}
		else break;
	}

	return ans;
}

//素数判定
bool prime(ll num) {
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false;
	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2) {
		if (num % i == 0) return false;
	}
	return true;
}

//フィボナッチ数列
vector<ll> memo(pow(10, 6) + 1);
ll fibo(ll n) {
	if (n == 1) return 1;
	else if (n == 2) return 1;
	else if (memo[n] != 0) return memo[n];
	else return memo[n] = fibo(n - 1) + f(n - 2);
}

int main() {
	ll K, A, B; cin >> K >> A >> B;

	for (int n = A; n <= B; n++) {
		if (n % K == 0) {
			cout << "OK" << endl;
			return 0;
		}
	}

	cout << "NG" << endl;
}

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

int main(void) {
	using namespace std;
	long long N, A, B;
	cin >> N >> A >> B;
	if(N == 1) {
		if(A != B) {
			cout << "0\n";
		} else {
			cout << "1\n";
		}
	} else if(A <= B) {
		if(N == 2) {
			cout << "1\n";
		} else {
			if(A == B) {
				cout << "1\n";
			} else {
				cout << ((N - 2) * (B - A) + 1) << '\n';
			}
		}
	} else {
		cout << "0\n";
	}
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
const int mod = 1000000007;
long long modpow(long long a, long long n){
  long long r = 1;
  while (n) {
    r = r * ( (n%2)?a:1 ) %mod;
    a = a * a % mod;
    n >>= 1;
  }
  return r;
}
int main(void){
    ll n;cin>>n;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];
    map<ll,ll> mp,mp2;
    rep(i,n){
        mp.clear();
        ll x=a[i];
        for(int i=2;i<=sqrt(x);i++){
            while(x%i==0){
                mp[i]++;
                x/=i;
            }
        }
        if(x>1) mp[x]++;
        for(auto& p:mp){
            chmax(mp2[p.first],p.second);
        }
    }
    ll l=1;
    for(auto& p:mp2){
        ll x=p.first,y=p.second;
        rep(i,y){
            l*=x;
            l%=mod;
        }
    }
    ll res=0;
    for(int i=0;i<n;i++){
        (res+=l*modpow(a[i],mod-2)%mod)%=mod;
    }
    cout<<res<<endl;
}

Measured memory_bytes: 896
using System.Collections.Generic;
using System.Linq;
using System;
using static System.Console;

class Program
{
  static void Main() => new Program().solve();

  void solve()
  {
    var param = ReadLine().Split(' ').Select(int.Parse).ToArray();
    var n = param[0];
    var l = param[1];

    var im = Enumerable.Range(1, n).Select(i => l + i - 1);
    var min = im.OrderBy(i => Math.Abs(i)).First();
    var all = im.Sum();

    var ans = all - min;
    WriteLine(ans);
  }
}

Measured memory_bytes: 13396
import java.util.*;

class Main {
	Scanner sc;

	Main() {
		sc = new Scanner(System.in);
	}
	
	void calc() {
		long N = sc.nextLong();
		for (long i = (long)Math.sqrt(N); i > 0; i--) {
			if (N%i==0) {
				System.out.println(i-1+(N/i)-1);
				return;
			}
		}
	}

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

Measured memory_bytes: 23764
import java.util.*;

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

		for (int i = 0; i < n; i++) {
			double ai = sc.nextInt();
			answer += Math.ceil(d / ai);
		}

		System.out.println(answer);
  }
}


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

int main(void){
   int N;
   string S;
   cin >>N>>S;
   int cnt=0;
   rep(i,N-2){
       if(S[i]=='A'&&S[i+1]=='B'&&S[i+2]=='C'){
           cnt++;
       }
   }
   cout<<cnt<<endl;
   
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int,int>
#define ff first
#define ss second
#define boost ios::sync_with_stdio(false);cin.tie(nullptr)
#include "string"
	

const int N = 5e5 + 5;
const int M = 1e9 + 7;
int mod(int m){
   m%=M;
   return (m+M)%M;
}

int power(int x,int y) {
   int res = 1;
   x = mod(x);
   while (y > 0) {
      if (y & 1)
         res =mod(res*x);
      y = y>>1;
      x = mod(x*x);
   }
   return mod(res);
}

int f[N],invf[N];
void fact(){
   f[0]=f[1]=1;
   for(int i=2;i<N;i++)
      f[i]=mod(f[i-1]*i);

   invf[N-1]=power(f[N-1],M-2);
   for(int i=N-1;i>0;i--)
      invf[i-1]=mod(invf[i]*i);

}

int nCr(int n,int r) {
   if(r>n)
      return 0;
   int ans = f[n];
   ans = mod(ans*invf[n-r]);
   ans = mod(ans*invf[r]);
   return ans;
}

int nPr(int n,int r) {
   if(r>n)
      return 0;
   int ans = f[n];
   ans = mod(ans*invf[n-r]);
   return ans;
}


int32_t main(){
	boost;
	fact();
	int n,m;
	cin>>n>>m;
	int ans = 0;
	int sign = 1;
	for(int i=0;i<=n;i++){
		int tt = mod(nCr(m,i)*nCr(n,i));
		tt = mod(tt*f[i]);
		tt = mod(tt*nPr(m-i,n-i));
		tt = mod(tt*nPr(m-i,n-i));
		//cout<<i<<" "<<tt<<endl;
		ans = mod(ans + sign*tt);
		sign *= -1;
	}	
	cout<<ans<<endl;
}

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

using namespace std;
#define rep(i, s, n) for (int i = s; i < (int)(n); i++)

int main()
{
    const char E = 'E';
    const char W = 'W';

    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        if (s.at(i) == E)
            cnt++;
    }
    int ans = cnt;
    for (int i = 0; i < n - 1; i++) {
        if (s.at(i) == W)
            cnt++;
        if (s.at(i + 1) == E)
            cnt--;
        ans = min(ans, cnt);
    }

    cout << ans << endl;
}


Measured memory_bytes: 900
// author: erray
#include<bits/stdc++.h>
 
using namespace std;
 
int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int ans = 0, cur = 0;
  for (int i = 0; i < 3; ++i) {
    char c;
    cin >> c;
    if (c == 'R') ++cur;
    else cur = 0;
    ans = max(ans, cur);
  } 
  cout << ans;
}

Measured memory_bytes: 3644
d = {1:2, 2:3, 3:1}
while True:
    h = int(input())
    if h == 0:
        break
    h = [h] + [int(input()) for _ in range(4)]
    if len(set(h)) == 3 or len(set(h)) == 1:
        print(*[3]*5, sep='\n')
        continue
    for c in h:
        print([2, 1][d[c] in h])

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

int main() {
  int h, w; cin >> h >> w;
  vector<string> board(h);
  for (auto& e: board) cin >> e;

  vector<bool> rowIncludeSharp(h), colIncludeSharp(w);
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (board[i][j] == '#') {
        rowIncludeSharp[i] = true;
        colIncludeSharp[j] = true;
      }
    }
  }
  for (int i = 0; i < h; i++) {
    if (rowIncludeSharp[i]) {
      for (int j = 0; j < w; j++) {
        if (colIncludeSharp[j]) {
          cout << board[i][j];
        }
      }
      cout << endl;;
    }
  }
}

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

typedef long long s64;

int main()
{
	//freopen("1.in","r",stdin);
	int a,b,c;s64 k;
	cin>>a>>b>>c>>k;
	b-=a;
	if(k%2)b=-b;
	cout<<-b;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int inf=2147483647,dx[]={-1,0,1,0},dy[]={0,-1,0,1};// 上 左 下 右
const int N=100005,M=1000005,mod=1000000007;
const long long llinf=9223372036854775807ll;
double n,a[105],sum,av,minv,ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	av=sum/n;
	minv=99999;
	for(int i=1;i<=n;i++)
	{
		double d=a[i]-av;
		if(d<0)
			d=-d;
		if(d<minv)
		{
			minv=d;
			ans=i;
		}
	}
	cout<<ans-1;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N = 100005;
int node[N] = {0};
vector<P> e[N];
void dfs(int v, int len=0, int prev=-1) {
    //printf("v:%d\n",v);
    int clr=0;
    if(prev!=-1) clr = node[prev];
    if(len%2==1) clr = !clr;
    node[v] = clr;
    for(int i=0;i<e[v].size();i++) {
        if(e[v][i].first==prev) continue;
        dfs(e[v][i].first,e[v][i].second ,v);
    }
}
int main() {
    int n; cin >> n;
    rep(i, n-1) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    node[0] = 0;
    dfs(0);
    rep(i, n) {
        printf("%d\n",node[i]);
    }
}


Measured memory_bytes: 8320
//Tenka1 Programmer Beginner Contest 2019
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k;
    string s = {};
    char c[15] = {};
    string r = {};
    cin >> n >> s >> k;
    //cout << s[k] << endl;
    for (int i = 0; i < n; i++)
    {
        c[i] = s[i];
        if (c[i] != s[k - 1])
        {
            c[i] = '*';
        }
    }
    for (int i = 0; i < n; i++)
    {
        r += c[i];
    }

    cout << r << endl;
}


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

#define COUNTOF(array) (sizeof(array) / sizeof(array[0]))    
#define OUT(P) cout << (P) << endl    
#define OUT2(P1, P2) cout << (P1) << " " << (P2) << endl    
#define PRINT_ARRAY(P) for(int i=0; i<P.size(); i++) cout << P[i] << endl;    
#define PRINT_ARRAY_INLINE(P) do { for(int i=0; i<P.size(); i++) cout << P[i] << " "; cout << endl; } while(0)    
#define PRINT_ARRAY_WITH_LABEL(L, P) do { cout << L << ": "; PRINT_ARRAY_INLINE(P); cout << endl; } while(0)    
typedef long long ll;    
const long DIVIDE = 1e9+7;

int sum_digits(int num);    
template <class T>    
vector<T> copy_vector(vector<T> vec);    
long gcd(long a, long b);    
long lcm(long a, long b);
// ****** print functions ****** //
template <class T, class U>
void print_pairs(const vector<pair<T, U>> pairs);
template <class K, class V>
void print_map(const map<K, V> m);

vector<vector<long>> comb(int n, int r) {
    vector<vector<long>> v(n+1, vector<long>(n+1, 0));
    for(int i=0; i<v.size(); i++) {
        v[i][0] = 1;
        v[i][i] = 1;
    }
    for(int i=1; i<v.size(); i++) {
        for(int j=1; j < i; j++) {
            v[i][j] = (v[i-1][j-1] + v[i-1][j]) % DIVIDE;
        }
    }
    return v;
}

long order(long n, long k) {
    long rtn = 1;
    for(long i=0; i<k; i++) {
        rtn *= (n - i);
    }
    return rtn;
}
int main() {    
    long n, k;
    cin >> n >> k;

    long hole = n - k + 1;

    vector<vector<long>> comb_ = comb(2000, 2000);
    for(long i=1; i<=k; i++) {
        long c1 = comb_[hole][i];
        long c2 = comb_[k-1][i-1];
        //long comb = order(hole, i) / order(i, i);
        //long comb2 = order(k-1, i-1) / order(i-1, i-1);
        cout << (c1 * c2) % DIVIDE << endl;
    }
    
    return 0;    
}    

/******************************/    
/***** DECRARED FUNCTIONS *****/    
/******************************/    

int sum_digits(int num) {    
    int rtn = 0;    
    while(num != 0) {    
        int tmp = num % 10;    
        rtn += tmp;    
        num /= 10;    
    }    
    return rtn;    
}    

// vectorのコピー    
template <class T>    
vector<T> copy_vector(vector<T> vec) {    
    vector<T> rtn;    
    rtn.reserve(vec.size());    
    copy(vec.begin(), vec.end(), back_inserter(rtn));    
    return rtn;    
}    

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

long lcm(long a, long b) {
    long gcd_ = gcd(a, b);
    return (a * b) / gcd_;
}

template <class T, class U>
void print_pairs(const vector<pair<T, U>> &pairs) {
    for(int i=0; i<pairs.size(); i++) { 
        cout << "(" << pairs[i].first << ", " << pairs[i].second << ")" << " "; 
    } 
    cout << endl;
}

template <class K, class V>
void print_map(const map<K, V> &m) {
    for(auto it=m.cbegin(); it!=m.cend(); it++) {
        cout << it->first << ": " << it->second << endl;
    }
}


Measured memory_bytes: 31616