akhauriyash/Code-Regression huggingface dataset:
using System;

class Plogram
{
    static void Main()
    {
        string str = Console.ReadLine();
        int num = int.Parse(str);

        int total = 0;
        string ans = "No";

        for(int i = 0; i<str.Length; i++)
        {
            total += int.Parse(str.Substring(i,1));
        }
        if(num%total==0)
        {
            ans = "Yes";
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() {
    int n, x, t;
    cin >> n >> x >> t;
    cout << n / x * t + (n % x > 0 ? t : 0) << endl;
}


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

signed main()
{
  int n, x;
  int sum = 0;
  int i, j, k;
  while (1){
    cin >> n >> x;
    if (n == 0 && x == 0){
      break;
    }
    for (i = 1; i < n - 1; i++){
      for (j = i + 1; j < n; j++){
        for (k = j + 1; k <= n; k++){
          if (i + j + k == x){
            sum++;
          } 
        }
      }
    }
    cout << sum << endl;
    sum = 0;
  }
  return (0);
}

Measured memory_bytes: 3032
//Author ::  ABHINAV3010 ::

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fast ios_base::sync_with_stdio(false)
typedef long long ll;
typedef pair<ll,ll> p;
ll mod=1000000007;
ll gcd(ll a,ll b)
{
    return (b==0)?a:gcd(b,a%b);
}
ll power(ll x, ll y, ll p=mod)
{ll res = 1;x = x % p;while (y > 0){if (y & 1){res = (res*x) % p;}y = y>>1;x = (x*x) % p;}return res;}
void gen(ll len,ll i,vector<string>&nums,char prev,string lun)
{
    if(i==len)
    {
        nums.pb(lun);
        return;
    }
    if(i==0)
    {
        for(char z='1';z<='9';z++)
        {
            gen(len,i+1,nums,z,lun+z);

        }
    }else if(prev=='0')
    {
        gen(len,i+1,nums,'0',lun+'0');
        gen(len,i+1,nums,'1',lun+'1');
    }else if(prev=='9')
    {
        gen(len,i+1,nums,'8',lun+'8');
        gen(len,i+1,nums,'9',lun+'9');
    }else
    {
        gen(len,i+1,nums,prev,lun+prev);
        char a=(char)prev+1;
        char b=(char)prev-1;
        gen(len,i+1,nums,a,lun+a);
        gen(len,i+1,nums,b,lun+b);

    }

}
int main()
{
fast;
vector<string>nums;
for(ll i=1;i<=10;i++)
{
    gen(i,0,nums,'?',"");
}
vector<ll>ans;
for(ll i=0;i<nums.size();i++)
{
    stringstream ss(nums[i]);
    ll val;
    ss>>val;
    ans.pb(val);
}
sort(all(ans));
ll x;
cin>>x;
cout<<ans[x-1]<<endl;


return 0;
}


Measured memory_bytes: 14960
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define fto(i, s, e) for(int i = s; i <= e; ++i)
#define fto1(i, s, e) for(int i = s; i < e; ++i)
#define fdto(i, s, e) for(int i = s; i >= e; --i)
#define fit(var, it) for(auto it = var.begin(); it != var.end(); ++it)
#define frit(var, it) for(auto it = var.rbegin(); it != var.rend(); ++it)

#define newl '\n'
#define bug1(x, i) cout << #x << '[' << i << "] = " << x[i] << newl
#define bug2(x, i, j) cout << #x << '[' << i << "][" << j << "] = " << x[i][j] << newl
#define bug3(x, i, j, k) cout << #x << '[' << i << "][" << j << "][" << k << "] = " << x[i][j][k] << newl

#define pc __builtin_popcountll

#define ll long long
#define ii pair<int, int>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define sz(v) int((v).size())

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

template<class T, class Cmp = less<T>> using oss = tree<T, null_type, Cmp, rb_tree_tag, tree_order_statistics_node_update>;

double const pi = acos(-1);
#define oo 1000000007
#define OO 1000000000000000003LL
#define maxn 100003

int n, x;
int a[maxn];

int main() {
	#ifdef KITTENS
		freopen("main.inp", "r", stdin);
		freopen("main.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0); cin.tie(nullptr);
	
	cin >> n >> x;
	vector<int> ans(1, 0);

	fto (i, 1, n) {
		cin >> a[i];
		ans.pb(ans.back()+a[i]);
	}

	ans.pb(oo);

	fto1 (i, 0, sz(ans)) {
		if (ans[i] > x) {
			cout << i << newl;
			return 0;
		}
	}

	cerr << 0.001*clock() << newl; return 0;
}

Measured memory_bytes: 256
#下，右，上，左
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(list(input()))

for y in range(H):
    for x in range(W):

        if S[y][x] == ".":
            continue

        cnt = 0

        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]

            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue
            
            flg = False

            if S[ny][nx] == "#":
                flg = True
                break
        if flg:
            continue
        else:
            print("No")
            exit()

print("Yes")

Measured memory_bytes: 3064
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;

int d,dep,m;
ll ans;
int c[20],c0[20];
ll f[20],a[20];

void dfs(int k,ll w,ll s){
	if (k==m){
		ans+=1ll*(w==d)*s;
		return;
	}
	if (abs(w-1ll*d)>a[k]*20) return;
	int i,cnt;
	for (i=0;i<20;i++){
		if (!k) cnt=c0[i];
		else cnt=c[i];
		if (!a[k]) cnt=i<10;
		if (!cnt) continue;
		dfs(k+1,w+a[k]*1ll*(i-10),s*1ll*cnt);
	}
}

void solve(int n){
	m=0;
	int i;
	for (i=0;i<n;i++){
		if (i>n-i-1) break;
		a[m++]=f[n-i-1]-f[i];
	}
	dfs(0,0,1);
}

int main(){
	int i,j;
	f[0]=1; for (i=1;i<=18;i++) f[i]=f[i-1]*10ll;
	for (i=0;i<=9;i++)
		for (j=0;j<=9;j++) c[i-j+10]++;
	for (i=0;i<=9;i++)
		for (j=1;j<=9;j++) c0[i-j+10]++;
	scanf("%d",&d);
	for (dep=1;dep<=19;dep++) solve(dep);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
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 MOD = 1000000007;
typedef long long ll;

int n,k,a,b;
string s,t;

int main() {
  cin >> a >> b;
  rep(i,100000){
    if(int(i*0.08)==a && int(i*0.1)==b){
    cout << i << endl;
    return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
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 N,K;
long long dp[100010];
int h[100010];

int main(){
    cin >> N >> K;
    for(int i = 0;i < 100010;i++){
        dp[i] = 1LL << 60;
    }   
    for(int i = 0;i < N;i++){
        cin >> h[i];
    }
    dp[0] = 0;
    for(int i = 0;i <= N;i++){
        for(int j = 1;j <= K;j++){
            chmin(dp[i + j],dp[i] + abs(h[i] - h[i + j]));
        }
    }
    cout << dp[N - 1] << '\n';
    return 0;
}

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

int main(){
    int m;
    cin >> m;
    long long d, c;
    long long digit = 0;
    long long all = 0;
    long long tmp = 0;
    for (int i = 0; i < m; i++) {
        cin >> d >> c;
        tmp += c * d;
        all += tmp / 9;
        tmp %= 9;
        digit += c;
    }
    if (tmp != 0) cout << all + digit - 1 << endl;
    else cout << all + digit - 2 << endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9+7;
int main(void){
    int N;
    cin>>N;
    ll ans = 1;
    for (int i=1;i<=N;i++){
        ans *= i;
        ans %= mod;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

        int[][] c = new int[3][3];
        int[] a = new int[3];
        int[] b = new int[3];

        for (int y = 0; y < 3; y++) {
            for (int x = 0; x < 3; x++) {
                c[y][x] = sc.nextInt();
                if (y == 0)
                    b[x] = c[y][x];
                else
                    a[y] = c[y][x] - b[x];
            }
        }

        boolean isAns = true;
        for (int y = 0; y < 3; y++) {
            for (int x = 0; x < 3; x++) {
                if (c[y][x] != a[y] + b[x]) {
                    isAns = false;
                    break;
                }
            }
        }

        System.out.println(isAns ? "Yes" : "No");
    }
}


Measured memory_bytes: 23124
#include<cstdio>
#include<iostream>
#include<string>

using namespace std;

int main(){
	while(1){
		string str;
		int a,buf,N=5,E=3,S=2,W=4,U=1,D=6,answer=0;
		cin>>a;
		if(a==0)return 0;
		for(int i=0;i<a;i++){
			cin>>str;
			if(str=="North"){
				buf=N;
				N=U;
				U=S;
				S=D;
				D=buf;
			}else if(str=="East"){
				buf=E;
				E=U;
				U=W;
				W=D;
				D=buf;
			}else if(str=="West"){
				buf=W;
				W=U;
				U=E;
				E=D;
				D=buf;
			}else if(str=="South"){
				buf=S;
				S=U;
				U=N;
				N=D;
				D=buf;
			}else if(str=="Left"){
				buf=S;
				S=W;
				W=N;
				N=E;
				E=buf;
			}else{
				buf=S;
				S=E;
				E=N;
				N=W;
				W=buf;
			}
			answer+=U;
		}
		printf("%d\n",answer+1);
	}
}

Measured memory_bytes: 1220
#include <iostream>

using namespace std;


int main(){
	long long res=0;
	long long n, k;
	cin >> n >> k;

	for(int m=k+1; m<=n; m++){
		int full = (n+1) / m;
		res += (m-k)*full;
		if((n+1)%m >= k)
			res += (n+1)%m - k;
		if(k==0)
			res--;
	}

	cout << res << endl;

	return 0;
}


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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = k; i < n; i++) {
		if (a[i] > a[i - k]) {
			cout << "Yes\n";
		} else {
			cout << "No\n";
		}
	}
}



Measured memory_bytes: 3964
N,A,B = map(int, input().split())
cnt = 0
res = 0
for i in range(1,N+1):
    sums = 0
    x = i
    while x > 0:
        sums += x%10
        x = x//10
    if A <= sums <= B:
        res += i
print(res)

Measured memory_bytes: 39408
#include <bits/stdc++.h>
using namespace std;
template <class T> inline void read(T &x) {
	x = 0; int c = getchar(), f = 1;
	for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
	for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, f[3005][3005], g[3005][3005][2]; char a[3005], b[3005];
void print(int x, int y) {if (x && y) print(g[x-1][y-1][0], g[x-1][y-1][1]), putchar(a[x]);}
int main() {
	scanf("%s%s", a+1, b+1);
	n = (int)strlen(a+1);
	m = (int)strlen(b+1);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			if (f[i-1][j] >= f[i][j-1])
				f[i][j] = f[i-1][j], 
				g[i][j][0] = g[i-1][j][0], 
				g[i][j][1] = g[i-1][j][1];
			else
				f[i][j] = f[i][j-1], 
				g[i][j][0] = g[i][j-1][0], 
				g[i][j][1] = g[i][j-1][1];
			if (a[i] == b[j] && f[i][j] < f[i-1][j-1]+1)
				f[i][j] = f[i-1][j-1]+1, g[i][j][0] = i, g[i][j][1] = j;
		}
	return print(g[n][m][0], g[n][m][1]), puts(""), 0;
}


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

int main() {
    string S;
    cin >> S;

    int ans = 0, start = 0;
    rep(i, S.size()) {
        if (S[i] == 'S')
            ++start;
        else {
            if (start == 0)
                ++ans;
            else
                --start;
        }
    }
    ans += start;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class B
{
	public static void Main() => (new Solver()).Solve();
}


public class Solver
{
	public void Solve()
	{
		int N = GetInt();
		int[] a = GetInts(N);

		int A = a.Max();
		int diff = A - a.Min();
		if(diff > 1)
		{
			Console.WriteLine("No");
		}
		else if(diff == 0)
		{
			Console.WriteLine(((A == N - 1) || (2 * A <= N)) ? "Yes" : "No");
		}
		else
		{
			int p = a.Count(x => x == (A - 1));
			int q = N - p;
			Console.WriteLine(((p < A) && ((A - p) * 2 <= q)) ? "Yes" : "No");			
		}
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(int N) => Enumerable.Range(0, N).Select(_ => GetInt()).ToArray();
	public static long[] GetLongs(int N) => Enumerable.Range(0, N).Select(_ => GetLong()).ToArray();
	public static double[] GetDoubles(int N) => Enumerable.Range(0, N).Select(_ => GetDouble()).ToArray();
	public static string[] GetStrings(int N) => Enumerable.Range(0, N).Select(_ => GetString()).ToArray();
}


Measured memory_bytes: 23264
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, M, K;

int main()
{
	scanf("%d%d%d", &N, &M, &K);
	bool ret = false;
	for (int n = 0; n <= N; ++n) {
		for (int m = 0; m <= M; ++m) {
			if (n * m + (N - n) * (M - m) == K) ret = true;
		}
	}
	puts(ret ? "Yes" : "No");
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#include<vector>
#include<queue>
#define ll long long
#define inf INT_MAX
main()
{
 ll int n;
 cin>>n;
 int b[n];
 int c[n];
 //cin>>b[];
 //vector<pair<int,int> > a; 
 for(int i=0;i<n;i++)
 {
 	cin>>b[i];
 	c[i]=b[i];
 	//a.push_back(make_pair(b[i],i));
 }
 sort(c,c+n);
 for(int i=0;i<n;i++)
 {
 	if(b[i]==c[n-1])
 	{
 		cout<<c[n-2]<<endl;
 	//	cout<<a[a.size()-2]<<endl;
	 }
	 else
	 {
	 	cout<<c[n-1]<<endl;
	 }
 }
}


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

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

    int check;
    check = 0;
    if(A==B) check++;
    if(A==C) check++;
    if(B==C) check++;

    string ans;
    if (check==1){
        ans = "Yes";
    }else{
        ans = "No";
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <algorithm>

using namespace std;


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

    cout << N * (N - 1) / 2 + M * (M - 1) / 2 << endl;

    return 0;
}

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

#define ll long long int
#define mod 1000000007

using namespace std;


int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    // int T;
    // cin >> T;
    // while(T){
    //     int n;
    //     cin >> n;
        
    //     T--;
    // }
    string s1,s2;
    cin >> s1 >>s2;
    if(s2.substr(0,s2.length()-1) == s1)
    cout << "Yes";
    else
    cout << "No";
}









Measured memory_bytes: 3648
from fractions import gcd
n, m = map(int, input().split())

a = list(map(int, input().split()))

ans = -1
b = [0] * n
for i in range(n):
    if a[i] % 2 != 0:
        ans = 0
        break

    else:
        b[i] = a[i] // 2


    if i == 0:
        num = format(a[i], 'b')[::-1].find('1')

    else:
        if format(a[i], 'b')[::-1].find('1') != num:
            ans = 0
            break
        else:
            num = format(a[i], 'b')[::-1].find('1')


if ans != 0:
    g = b[0]
    for i in range(1,n):

        g = (g*b[i]) // gcd(b[i],g)

    if g > m: ans = 0
    else:
        ans = (1 + (m-g)//(2*g))

print(ans)


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

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

ll modpow(ll a, ll n) {
	if (n == 0)
		return 1;
	else if (n % 2 == 0) {
		ll t = modpow(a, n / 2);
		return t * t % MOD;
	}
	else
      return a * modpow(a, n - 1) % MOD;
}

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

ll modfac2(ll a, ll b) {
	ll res = 1;
	while (a > b) {
		res = res * a % MOD;
		--a;
	}
	return res;
}

ll modcom(ll n, ll r) {
	return modfac2(n, n - r) * modinv(modfac2(r, 0)) % MOD;
}

int main() {
  ll n, a, b;
  cin >> n >> a >> b;
  
  ll ans = modpow(2, n) - 1 - modcom(n, a) - modcom(n, b);
  while (ans < 0)
    ans += MOD;
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
//#include<bits/stdc++.h>
#include<iostream>
#include <iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<numeric>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<list>
using namespace std;
int main(){
  long double a,b,x,l,ans;
  cin >> a >> b >> x;
  if(x <= a*a*b/2.0){
    l = 2.0*x/(a*b);
    ans = acos(l/(sqrt(l*l+b*b)));
  }
  else{
    l = 2.0*(a*a*b-x)/(a*a);
    ans = acos(a/(sqrt(l*l+a*a)));
  }
  long double PI=3.14159265358979323846;
  cout << fixed;
  cout << setprecision(10) << ans/(2*PI)*360.0 << endl;


  return 0;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))

int N, A, B;

void solve() {
    cin >> N >> A >> B;
    cout << min(A, B) << " " << max(A+B-N, 0) << endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 256
'use strict';
const main = input => {
  const s = input[0];
  switch (s) {
    case 'SUN':
      console.log(7);
      break;
    case 'MON':
      console.log(6);
      break;
    case 'TUE':
      console.log(5);
      break;
    case 'WED':
      console.log(4);
      break;
    case 'THU':
      console.log(3);
      break;
    case 'FRI':
      console.log(2);
      break;
    case 'SAT':
      console.log(1);
      break;
    default:
      break;
  }
}
main(require("fs").readFileSync("/dev/stdin", "utf8").split('\n'));

Measured memory_bytes: 21064
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-9;

	int n, m;
	int[][] w;

	void run(){
		sc.useDelimiter("[,]|(\\s)+");
		for(; sc.hasNext();){
			n=sc.nextInt();
			if(n==0){
				break;
			}
			m=sc.nextInt();
			w=new int[n][n];
			for(int i=0; i<n; i++){
				Arrays.fill(w[i], -1);
			}
			for(int i=0; i<m; i++){
				int a=sc.nextInt();
				int b=sc.nextInt();
				int c=sc.nextInt()/100;
				w[a][b]=w[b][a]=c;
			}
			solve();
		}
	}

	// w[i][j]=w[j][i]
	// w[i][j]=-1 -> E(i, j) not exist
	void solve(){
		init();
		LinkedList<E> list=new LinkedList<E>();

		for(int j=0; j<n-1; j++)
			for(int i=j+1; i<n; i++)
				if(w[j][i]!=-1)
					list.add(new E(j, i, w[j][i]));

		E[] es=list.toArray(new E[0]);
		Arrays.sort(es, new Comparator<E>(){
			@Override
			public int compare(E e1, E e2){
				return e1.w-e2.w;
			}
		});

		list.clear();
		int ans=0;
		for(E e : es){
			if(find(e.v1)!=find(e.v2)){
				union(e.v1, e.v2);
				ans+=e.w-1;
				list.add(e);
			}
		}
		println(""+ans);
	}

	int[] p, rank;

	void init(){
		p=new int[n];
		rank=new int[n];
		for(int i=0; i<n; i++){
			p[i]=i;
			rank[i]=0;
		}
	}

	int find(int x){
		if(p[x]==x)
			return x;
		else
			return p[x]=find(p[x]);
	}

	void union(int x, int y){
		x=find(x);
		y=find(y);
		if(rank[x]>rank[y]){
			p[y]=x;
		}else{
			p[x]=y;
			if(rank[x]==rank[y])
				rank[y]++;
		}
	}

	class E{
		int v1, v2, w;

		E(int v1, int v2, int w){
			this.v1=v1;
			this.v2=v2;
			this.w=w;
		}
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
#define REP(i,n) for (long i=0;i<(n);i++)
#define FOR(i,a,b) for (long i=(a);i<(b);i++)
#define RREP(i,n) for(long i=n;i>=0;i--)
#define RFOR(i,a,b) for(long i=(a);i>(b);i--)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl;
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl;
#define dump(x)  cerr << #x << " => " << (x) << endl;
#define CLR(vec) { REP(i,vec.size()) vec[i] = 0; } 
#define llINF (long long) 9223372036854775807
#define loINF (long) 2147483647
#define shINF (short) 32767
#define SORT(c) sort((c).begin(),(c).end())

using namespace std;
typedef vector<long> VI;
typedef vector<VI> VVI;
typedef pair<long,long> pr;
struct Order {
	bool operator() (pr const& a,pr const& b) const {
		return a.first > b.first || ((a.first == b.first) && (a.second > b.second));
	}
};
typedef priority_queue<pr,vector<pr>,Order> pq;

class Prim {
private:
	vector<vector<pr>> E; //隣接行列
	pq mincost;
	vector<bool> used;
	size_t V;
public:
	Prim() : V(0) {}

	Prim(size_t v) : 
		V(v),E(v,vector<pr>(0)),used(v,false){}
		
	size_t size() {return V;}

	void add_edge_directed(long start,long goal,long weight){
		E[start].push_back(pr(goal,weight));
	}

	void add_edge_undirected(long start,long goal,long weight){
		E[start].push_back(pr(goal,weight));
		E[goal].push_back(pr(start,weight));
	}

	long min_spanning_tree(void){
		long minval = 0;
		mincost.push(pr(0,0));
		while(1) {
			if (mincost.empty()) break;
			pr node = mincost.top();
			mincost.pop();
			if (used[node.second]) continue;
			minval += node.first;
			used[node.second] = true;

			REP(i,E[node.second].size()){
				if (!used[E[node.second][i].first])
					mincost.push(pr(E[node.second][i].second,E[node.second][i].first));
			}
					
		}

		return minval;
	}

};


int main(void){
	long V,E;
	long u,v,w;
	cin >> V >> E;
	Prim prim(V);

	REP(i,E){
		cin >> u >> v >> w;
		prim.add_edge_undirected(u,v,w);
	}

	cout << prim.min_spanning_tree() << endl;

	return 0;
}


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

#define lli long long int
#define REP(i,s,n) for(lli i=s;i<n;i++)
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define MOD (1000000007)
#define TO_STRING(VariableName) # VariableName
#define LOG(xx) if(DEBUG)cout<<TO_STRING(xx)<<"="<<xx<<" "<<endl;
#define LOG2(xx,yy) if(DEBUG)cout<<TO_STRING(xx)<<"="<<xx<<" "<<TO_STRING(yy)<<"="<<yy<<endl;
#define LOG3(xx,yy,z) if(DEBUG)cout<<TO_STRING(xx)<<"="<<xx<<" "<<TO_STRING(yy)<<"="<<yy<<" "<<TO_STRING(z)<<"="<<z<<endl;
#define LOG4(w,xx,yy,z) if(DEBUG)cout<<TO_STRING(w)<<"="<<w<<" "<<TO_STRING(xx)<<"="<<xx<<" "<<TO_STRING(yy)<<"="<<yy<<" "<<TO_STRING(z)<<"="<<z<<endl;

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

lli sum[200100];

void solve(){

	lli n;
	cin>>n;
	vector<lli> a(n);
	REP(i,0,n)cin>>a[i];

	REP(i,0,n){
		sum[i+1] = sum[i]+a[i];
		sum[i+1]%=MOD;
	}

	lli ans = 0;
	REP(i,0,n-1){
		ans += (a[i]*(sum[n]))%MOD;
		ans %= MOD;
		ans += (MOD-(a[i]*(sum[i+1]))%MOD);
		ans %= MOD;
	}
	cout<<ans<<endl;

}

int main(){
	
    // cout << fixxed << setprecision(5);
    lli t=1;
    //cin>>t;
    while(t--)solve();

    return 0;
}


Measured memory_bytes: 6424
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, Q;
  cin >> N >> Q;
  vector<ll> A(N), sum(N+1), odd(N+1), even(N+1);
  rep(i, N) {
    cin >> A[i];
    sum[i+1] = sum[i] + A[i];
    odd[i+1] = odd[i] + (i%2 ? A[i] : 0);
    even[i+1] = even[i] + (i%2 ? 0 : A[i]);
  }
  auto bsearch = [&](ll x) {
    auto test = [&](ll k) {
      int ub = upper_bound(all(A), x+k-1) - A.begin();
      int lb = lower_bound(all(A), x-k) - A.begin();
      int cnt = ub - lb;
      int ub2 = N - cnt;
      return ub <= ub2;
    };

    ll ok = 0, ng = longinf;
    while(abs(ok-ng) > 1) {
      ll mid = (ok+ng)/2;
      (test(mid) ? ok : ng) = mid;
    }
    return ok;
  };
  rep(q, Q) {
    ll x;
    cin >> x;
    ll k = bsearch(x);
    int ub = upper_bound(all(A), x+k-1) - A.begin();
    int lb = lower_bound(all(A), x-k) - A.begin();
    int cnt = ub - lb;
    int ub2 = N - cnt;
    ll ans = 0;
    ans += sum[N] - sum[ub2];
    if(ub != ub2) ans += sum[ub2] - sum[ub+(ub2-ub)/2];
    ans += (N%2 ? even : odd)[lb];
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 4864
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
ll MOD=1000000007;
const double PI = acos(-1);

int main(){
  int n,m; cin>>n>>m;
  vector<int>city(n,0);
  rep(i,m){
    int a,b; cin>>a>>b;
    a--; b--;
    city[a]++;
    city[b]++;
  }
  rep(i,n) cout << city[i] << endl;
}

Measured memory_bytes: 3608
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;

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

#define all(c) (c).begin(), (c).end()
#define pb push_back
#define mp make_pair
#define EXIST(v,i) (find(all(v), i) != (v).end())
#define ERASE(v,i) (v).erase(remove(all(v), i), (v).end())
#define INDEX(v,i) (find(all(v), i) - (v).begin())
#define rep(i,n) for(int i = 0; i < (int)n; ++i)
#define debug(x) cerr << #x << " = " << (x) << endl;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

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

int main() {
	for(vector<int> a(4), b(4); cin >> a[0] >> a[1] >> a[2] >> a[3] >> b[0] >> b[1] >> b[2] >> b[3];) {
		int hit = 0, blow = 0;
		rep(i,4) {
			if(a[i] == b[i])
				hit++;
			else {
				if(EXIST(a, b[i])) {
					blow++;
				}
			}
		}
		cout << hit << " " << blow << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a;
  cin >> a ;
  vector<int>v(a);
  vector<int>c(a);
  for(int i = 0; i < a ;i++) {
    cin >> v.at(i);
  }
  for(int i = 0; i < a ;i++) {
    cin >> c.at(i);
  }
  vector<int>s(a);
  int cou = 0;
  for(int i = 0; i < a ;i++) {
    s.at(i) = v.at(i) - c.at(i);
    if(s.at(i) > 0){
      cou += s.at(i);
  }
  }
  cout << cou << endl;
  }

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int[][] a = new int[3][3];
    boolean[][] s = new boolean[3][3];
    for(int i=0; i<3; i++) {
      String[] str = in.readLine().split(" ");
      for(int j=0; j<3; j++) {
        a[i][j] = Integer.parseInt(str[j]);
      }
    }
    
    int n = Integer.parseInt(in.readLine());
    int[] b = new int[n];
    for(int i=0; i<n; i++) {
      b[i] = Integer.parseInt(in.readLine());
      for(int j=0; j<3; j++) {
        for(int k=0; k<3; k++) {
          if(a[j][k]==b[i])
            s[j][k] = true;
        }
      }
    }
    System.out.println(bingo(s)?"Yes":"No");
  }
  
  private static boolean bingo(boolean[][] s) {
    boolean hantei = false;
    for(int i=0; i<3; i++){
      hantei |= s[i][0] && s[i][1] && s[i][2];
      hantei |= s[0][i] && s[1][i] && s[2][i];
    }
    hantei |= s[0][0] && s[1][1] && s[2][2];
    hantei |= s[0][2] && s[1][1] && s[2][0];
    return hantei;
  }
}

Measured memory_bytes: 24788
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <tuple>
#include <math.h>
#include <set>
#include <map>
using namespace std ;
using ll = long long ;
using ld = long double ;
using vll = vector<ll> ;
using vvll = vector<vll> ;
using vc = vector<char> ;
using vvc = vector<vc> ;
using vb = vector<bool> ;
using vvb = vector<vb> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end() 
const ll INF = 1e18 ;
const ll mod = 1e9+7 ;
const double pie = acos(-1); 
vll dx4 = {-1,0,1,0} ;
vll dy4 = {0,-1,0,1} ;
vll dx8 = {-1,0,1,1,1,0,-1,-1} ;
vll dy8 = {-1,-1,-1,0,1,1,1,0} ; 

void fix_cout(){cout << fixed << setprecision(20) ; }
ll gcd(ll a,ll b){if(b==0) return a ; return gcd(b,a%b) ; }
ll lcm(ll a,ll b){return a/gcd(a,b)*b ; }
void chmax(ll &a,ll b){if(a<b) a = b ; }
void chmin(ll &a,ll b){if(a>b) a = b ; }

int main(){
	ll n ; cin >> n ;
	cout << 10-n/200 << endl ;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define endl "\n";
#define M 1000000007
#define start ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define test ll t; cin>>t; while(t--)
typedef long long int ll;
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif

	start
	ll n;
	cin>>n;
	ll arr[n];
	for(ll i=0; i<n; i++)
		arr[i] = 0;
	for(ll i=1; i<n; i++)
	{
		ll x;
		cin>>x;
		arr[x-1]++;
	}
	for(ll i=0; i<n; i++)
		cout<<arr[i]<<endl;

	return 0;
}

Measured memory_bytes: 5180
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long ret = 100;
		for(int i = 1;;i++){
			ret += ret * 0.01;
			if(ret >= a){
				System.out.print(i);
				break;
			}
		}
	}
}

Measured memory_bytes: 35580
/*
1．dp table全体を適切な初期値で初期化せよ
２．初期条件を入力せよ
３．ループを回せ
４．解を出力せよ

*/
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

template<class T> inline bool chmin(T& a, T b){
    if(a > b){
        a = b;
        return 1;
    }
    return 0;
}
 
long long dp[100010];
long long h[100010];
 
long long INF = 1ll<<60;

int main(void){
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) cin >> h[i];
    
    for (int i = 0; i < 100010; i++) dp[i] = INF; //1
    
    dp[0] = 0; //2 スタート地点に至るコストは０
    
    //3 ループを回せ
    for (int i = 0; i < n; i++){
        chmin(dp[i+1], dp[i] + abs(h[i] - h[i+1]));
        chmin(dp[i+2], dp[i] + abs(h[i] - h[i+2]));
    }
    
    //4 解を出力せよ
    // 0-indexのため, n番目にいたる最小コストはdp[n-1]に記録されている
    cout << dp[n-1] << endl;
}


Measured memory_bytes: 1792
var a,b,c,d,e,n : longint ;
    ans,f,g,h,i,j : int64 ;
function max (x,z : int64 ) : int64 ;
begin
 if x>z then
  max:=x
 else
  max:=z;
end;
function min (x,z : int64 ) : int64 ;
begin
 if x>z then
  min:=z
 else
  min:=x;
end;
begin
 readln(n);
 for a:=1 to n do
  if a=1 then
   readln(f)
  else
   begin
    readln(g);
    h:=max(f,g);
    i:=min(f,g);
    while h mod i <>0 do
     begin
      j:= h mod i;
      h:=i;
      i:=j;
     end;
    ans:=f*(g div(i));
    f:=ans;
   end;
  writeln(f);
end.


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
long long n,vals[401],dp[401][401];

int main(){
	cin >> n;
	for(int i = 0 ; i < 401 ; i += 1){
		for(int j = 0 ; j < 401 ; j += 1){
			dp[i][j] = 1000000000000000000;
		}
	}
	for(int r = 1 ; r <= n ; r += 1){
		cin >> vals[r];
		dp[r][r] = 0;
		long long sum = 0;
		for(int l = r ; l > 0 ; l -= 1){
			sum += vals[l];
			for(int k = r ; k >= l  ; k -= 1){
				dp[l][r] = min(dp[l][r] , sum+dp[l][k-1]+dp[k][r]);
			}
		}
	}
	cout << dp[1][n] << endl;
}

Measured memory_bytes: 1536
/*pata hai na?*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

#include<bits/stdc++.h>
using namespace std;

#define     int          long long int
#define     ld           long double
#define     fast()       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)       x.begin(),x.end()
#define     mem(a,b)     memset(a,b,sizeof(a))
#define     gcd(a,b)     (__gcd((a),(b)))
#define     lcm(a,b)     (((a)*(b))/gcd((a),(b)))
#define     pb           push_back
#define     ins          insert
#define     pii          pair<int,int>
#define     F            first
#define     S            second
#define     makep        make_pair
#define     maket        make_tuple
#define     show(x)      for(auto c:x)cout<<c<<" ";cout<<"\n";
#define     show2(x)     for(auto c:x)cout<<c.F<<" "<<c.S<<"\n";

const ld pi=acos(-1);
const int inf=1e18,M=1e9+7;
const int N=1;

void solve()
{
    int n;
    cin>>n;

    int ans=n/2+n%2;
    cout<<ans;
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}



Measured memory_bytes: 256
// 2020-08-27 23:37:19
// clang-format off
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

// clang-format on
void answer() {
  ll a, b;
  cin >> a >> b;
  if (a > b) swap(a, b);
  ll l = 0, r = b - a + 1;
  while (l + 1 < r) {
    ll x = (l + r) / 2;
    if ((a + x / 2) * (a + (x + 1) / 2) < a * b)
      l = x;
    else
      r = x;
  }
  cout << 2 * (a - 1) + l << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int q;
  cin >> q;
  rep(_, q) answer();
  return 0;
}

Measured memory_bytes: 3624
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
#include<map>
#include<type_traits>
#include<tuple>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

int main(){
  string n;
  cin >> n;
  n = "ABC" + n;
  cout << n << endl;
}


Measured memory_bytes: 384
N = int(input())
A = list(map(int,input().split()))
print(" ".join(map(str,A)))

for i in range(1,N):
    v = A[i]
    j = i-1
    while (j>=0 and A[j]>v):
        A[j+1] = A[j]
        j-=1
    A[j+1]=v
    print(" ".join(map(str,A)))



Measured memory_bytes: 5596
#include <stdio.h>

int main(){
    char s[5];
    scanf("%s",s);
    bool answer=false;
    for(int i=0;i<3;i++){
        if(s[i]==s[i+1]){
            answer=true;
            break;
        }
    }
    if(answer) printf("Bad\n");
    else printf("Good\n");
}

Measured memory_bytes: 128
#include <stdio.h>
int main (void)
{
int a;
int s[26]={};
  
while(1){
scanf("%d",&a);
if(a==0)
break;
  
int i;
for(i=0;i<a;i++)
scanf("%d",&s[i]);
  
int ss[26]={};
int h=0;
  
while(s[h]!=0){
ss[h]=s[h];
h++;
}
  
int oha=32;
int j=0;
int aaa[32]={};
int k=0;
  
while(1){
oha=oha-(oha-1)%5;
aaa[j]=oha;
j++;
  
oha=oha-ss[k%h];
aaa[j]=oha;
k++;
j++;
  
if(oha<=0)
break;
}
for(i=0;i<j-1;i++)
printf("%d\n",aaa[i]);
printf("0\n");
  
}
return 0;
}

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

typedef vector<int> vint;

vint tovec(int h, int w){
	vint v(3);
	v[0] = h * h + w * w;
	v[1] = h;
	v[2] = w;
	return v;
}

int main(){
	vector<vint> tbl;
	for(int h = 1; h < 150; ++h)
	for(int w = h + 1; w < 150; ++w){
		tbl.push_back(tovec(h, w));
	}
	sort(tbl.begin(), tbl.end());
	
	int h, w;
	while(scanf("%d%d", &h, &w), h){
		const vint &v = *upper_bound(tbl.begin(), tbl.end(), tovec(h, w));
		printf("%d %d\n", v[1], v[2]);
	}
}

Measured memory_bytes: 1800
from functools import reduce

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a


#最小公倍数
def lcm(a,b):
  return a * b // gcd(a,b) 


if __name__ == "__main__":
    n = int(input())
    lst = []
    for i in range(n):
        lst.append(int(input()))
    print(reduce(lcm,lst))

Measured memory_bytes: 3572
#include<stdio.h>
int main(){
  int i,j,k;
  int d;	//365
  int c[26];
  int score[9490];
  int t[365] = {0};
  int day1[365] = {0};
  double x = 0.36787944117;
  int tmp1=-99999,tmp2=-99999;
  
  scanf("%d",&d);
  for(i=0;i<26;i++){
      scanf("%d ",&c[i]);
  }
  for(i=0;i<d*26;i++){
      scanf("%d ",&score[i]);
  }
  //st
  
  for(i=0;i<d;i++){
    for(j=0;j<26;j++){
      if(score[i*26+j]-c[j]>tmp1){
       	tmp1 =  score[i*26+j]-c[j];
        t[i] = j;
      }
    }
  }
  
  //en
  for(i=0;i<d;i++){
      printf("%d\n",t[i]+1);
  }
 return 0; 
}




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

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

  ll i = 2;
  ll ans = n - 1;
  while (i * i <= n) {
    if (n % i == 0) {
      ans = min(ans, (i - 1) + (n / i - 1));
    }
    i++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define fi first
#define se second 
using namespace std;
const LL INF = (LL) 1e18 + 5;
//const LL MOD = (LL) 1e9 + 7;
//const int MAXN = 200005;

LL n, a, b, c, d;
map<LL, LL> dp;

LL mul(LL a, LL b) {
	if (!a || !b) return 0;
	if (b > INF / a) return INF;
	return a * b;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int tc;
	cin >> tc;
	while (tc--) {
		cin >> n >> a >> b >> c >> d;
		
		LL ans;
		set<LL> vis;
		priority_queue<PLL, vector<PLL>, greater<PLL>> pq;
		pq.push(PLL(0, n));
		while (!pq.empty()) {
			PLL p = pq.top();
			LL dist = p.fi, v = p.se;
			pq.pop();
			if (vis.find(v) != vis.end()) {
				continue;
			}
			if (p.se == 0) {
				ans = dist;
				break;
			}
			
			vis.insert(v);
			pq.push(PLL(mul(d, v) + dist, 0));
			for (int i = -4; i <= 4; i++) {
				LL now = v + i, cost = d * abs(i);
				if (now % 2 == 0) {
					pq.push(PLL(dist + cost + a, now / 2));
				}
				if (now % 3 == 0) {
					pq.push(PLL(dist + cost + b, now / 3));
				}
				if (now % 5 == 0) {
					pq.push(PLL(dist + cost + c, now / 5));
				}
			}
		}
		
		cout << ans << '\n';
	}
	
	return 0;
}

Measured memory_bytes: 6976
using System;
using System.Collections.Generic;
using System.Linq;
using System.Collections;
using System.IO;

class Program
{
    static void Main(string[] args)
    {
        new Magatro().Solve();
    }
}

public class Scanner
{
    private StreamReader Sr;

    private string[] S;
    private int Index;
    private const char Separator = ' ';

    public Scanner(Stream stream)
    {
        Index = 0;
        S = new string[0];
        Sr = new StreamReader(stream);
    }

    private string[] Line()
    {
        return Sr.ReadLine().Split(Separator);
    }

    public string Next()
    {
        string result;
        if (Index >= S.Length)
        {
            S = Line();
            Index = 0;
        }
        result = S[Index];
        Index++;
        return result;
    }
    public int NextInt()
    {
        return int.Parse(Next());
    }
    public double NextDouble()
    {
        return double.Parse(Next());
    }
    public long NextLong()
    {
        return long.Parse(Next());
    }
    public decimal NextDecimal()
    {
        return decimal.Parse(Next());
    }
    public string[] StringArray(int index = 0)
    {
        Next();
        Index = S.Length;
        return S.Skip(index).ToArray();
    }
    public int[] IntArray(int index = 0)
    {
        return StringArray(index).Select(int.Parse).ToArray();
    }
    public long[] LongArray(int index = 0)
    {
        return StringArray(index).Select(long.Parse).ToArray();
    }
    public bool EndOfStream
    {
        get { return Sr.EndOfStream; }
    }
}

public class Magatro
{
    private int N, M;
    private List<int>[] Con;
    bool[] b;
    private void Scan()
    {
        Scanner scanner = new Scanner(Console.OpenStandardInput());
        N = scanner.NextInt();
        M = scanner.NextInt();
        Con = new List<int>[N];
        for (int i = 0; i < N; i++)
        {
            Con[i] = new List<int>();
        }
        for (int i = 0; i < M; i++)
        {
            int a = scanner.NextInt();
            int b = scanner.NextInt();
            Con[a - 1].Add(b - 1);
            Con[b - 1].Add(a - 1);
        }
    }

    public void Solve()
    {
        Scan();
        b = new bool[N];
        b[0] = true;
        var one = F();
        var two = F();
        two.Reverse();
        for(int i = 1; i < one.Count; i++)
        {
            two.Add(one[i]);
        }
        Console.WriteLine(two.Count);
        Console.WriteLine(string.Join(" ", two.Select(i=>i+1).ToArray()));
    }

    private List<int> F()
    {
        List<int> res = new List<int>();
        res.Add(0);
        int pos = 0;
        while (true)
        {
            bool flag = false;
            foreach(int i in Con[pos])
            {
                if (!b[i])
                {
                    pos = i;
                    res.Add(i);
                    b[i] = true;
                    flag = true;
                    break;
                }
            }
            if (!flag)
            {
                break;
            }
        }
        return res;
    }
}

Measured memory_bytes: 34820
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl

int main() {
    string s; cin >> s;
    rep(i, s.size()){
        cout << "x";
    }
    cout << endl;
}

Measured memory_bytes: 256
process.stdin.on("data",function(c){                                              
  (c+"").trim().split("\n").slice(1).some(function(a){                                     
    var n = a.split(" ").map(function(x){return x*x}).sort(function(x,y){return x-y});                                                                                  console.log(n[0]+n[1]===n[2]?'YES':'NO');                                       
  });                                                                               
}).resume();

Measured memory_bytes: 10524
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
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 ll INF = 1LL << 60;
//const int INF = 1001001001;

int main(void){
    int n,m;
    cin >> n >> m;
    if(n==m) cout << "Yes";
    else cout << "No";

    return 0;
}

Measured memory_bytes: 3608
//gauravsinghh
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define ld long double
#define db double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define sii set<int>
#define sll set<long long>
#define vii vector<int> 
#define vll vector<long long>
#define mii map<int,int>
#define mll map<long long, long long>
#define lob lower_bound
#define upb upper_bound
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define ins insert
#define mp make_pair
#define w(t) cin >> t;while(t--)
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define os cout<<" "
#define bitcount __builtin_popcount
#define gcd __gcd
#define endl "\n"
#define present(s,x) (s.find(x) != s.end()) 
#define cpresent(s,x) (find(all(s),x) != s.end()) 
#define ford(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++) 
#define fors(container, it, a, b) for(__typeof(container.begin()) it = a; it != b; it++) 
#define MOD 1000000007
#define MAXI (1<<32)
#define EPSILON 1e-9
#define PI 3.14159265358979323846
#define inf 999999999999999999
#define siz 100005
#define SIZ 1000005
#define SIZE 200005
#define fbo find_by_order
#define ook order_of_key
#define sz(s) (int)s.size()
#define mem(n,m) memset(n,m,sizeof(n))
#define rep(i,n) for(ll i = 0; i < n; i++)
#define ren(i,n) for(ll i = n-1; i >= 0; i--)
#define all(x) x.begin(),x.end()
#define fo(i, a, b) for(int i = a; i <= b; i++)
#define ffo(i, a, b) for(int i = a; i >= b; i--)
#define MAX 100005
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

void io_set() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}

bool comp(const pair<ll,ll>&a,const pair<ll,ll>&b){
	return a.ss < b.ss;
}

//ll p[20000005]={0};
//vector<ll>ans;
/*void sieve(){
    ll i,j;
    p[0]=p[1]=1;
    for(i=2;i*i<=20000005;i++){
        if(!p[i]){
            for(j=2*i;j<20000005;j+=i){
                p[j]=1;
            }
        }
    }
    fo(i,2,20000005){
        if(!p[i]){
            ans.pb(i);
        }
    }
}*/

signed main(){ 
    IOS
    //io_set();
    ll a,b;
    cin >> a >> b;
    double x = ((a+b)/2.0);
    cout << ceil(x) << endl;
    return 0;
}



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

using namespace std;

typedef long long int ll;

#define FOR(i,l,r) for(i=l;i<r;i++)

#define REP(i,n) FOR(i,0,n)

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

#define P pair<ll,ll>

#define F first

#define S second

signed main(){

  ll N,M,i,ans=0,A,B;cin>>N>>M;
  ll H[N];vector<bool>X(N,true);
  REP(i,N)cin>>H[i];
  REP(i,M){
    cin>>A>>B;
    if(H[A-1]>=H[B-1])X.at(B-1)=false;
    if(H[A-1]<=H[B-1])X.at(A-1)=false;
  }
  REP(i,N)if(X.at(i))ans++;
  cout<<ans<<endl;

  return 0;

}

Measured memory_bytes: 4424
//B.cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const ll mod=1e9+7;

int main(){
  int n;
  cin >> n;
  int a[n+1] = {0};
  int b;
  rep(i,n-1){
    cin >> b;
    a[b]++;
  }
  for(int i = 1; i <= n; i++){
    printf("%d\n", a[i]);
  }
  return 0;
}


Measured memory_bytes: 4436