akhauriyash/Code-Regression huggingface dataset:
#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;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int,int> pii;
typedef pair <ll,ll> pll;

#define un(x)           x.erase(unique(all(x)), x.end())
#define xx              first
#define yy              second
#define pb              push_back
#define all(v)          v.begin(),v.end()

#define D(x)            cerr << #x " = " << x << '\n'
#define DBG             cerr << "Hi!" << '\n'

#define CLR(a)          memset(a,0,sizeof(a))
#define SET(a)          memset(a,-1,sizeof(a))

// inline int setBit(int n,int pos) { return n = n | (1 << pos); }
// inline int resetBit(int n,int pos) { return n = n & ~(1 << pos); }
// inline bool checkBit(int n,int pos) { return (bool)(n & (1 << pos)); }

// int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
// int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1};

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// unsigned int num = rng();
// shuffle(V.begin(), V.end(), rng);

/******************************************************************************************/

const int MAX = 500010;
// const int INF = 0x3f3f3f3f;
// const int MOD = 1000000007;

// inline int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
// inline int sub(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
// inline int mul(int a, int b) { return (a * 1LL * b) % MOD; }


void impossible() {
    cout << -1 << '\n';
    exit(0);
}

ll a[MAX], c[MAX];

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

    // freopen("in", "r", stdin); 
    // freopen("out", "w", stdout);
    
    int n;
    cin >> n;
    for(int i=0;i<=n;i++) {
        cin >> a[i];
        c[i] = c[i - 1] + a[i];
    }

    if(n == 0) {
        if(a[0] == 1) cout << 1 << '\n';
        else impossible();
        return 0;
    }

    if(a[0]) impossible();
    
    ll pr = 1;
    ll ans = 1;
    for(int i=1;i<=n;i++) {
        ll tot = c[n] - c[i - 1];
        pr = min(tot, pr + pr);
        ans += pr;
        pr -= a[i];
        if(i == n){
            if(pr != 0) impossible();
        }
        else if(i < n) {
            if(pr <= 0) impossible();
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5172
#include <stdio.h>
int main(void)
{
int n;
int i = 0;
int x[10000];
int min = 1000000;
int max = -1000000;
long sum = 0;

scanf("%d",&n);

while(n > i){
scanf("%d",&x[i]);
sum += x[i];
i++;
}

for (i = 0; n > i; i++){
if (min > x[i])
min = x[i];

if(max < x[i])
max = x[i];
}
printf("%d %d %ld\n",min,max,sum);

return 0;
}

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

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

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

    return arr
def wa(x):
    return x*(x+1)/2

ans = []
n = int(input())
if n == 1:
    print(0)
else:
    fac = factorization(n)
    for i in range(len(fac)):
        j = 1
        while True:
            if wa(j) <= fac[i][1] and fac[i][1] < wa(j+1):
                break
            else:
                j += 1
        ans.append(j)
    print(sum(ans)) 

Measured memory_bytes: 9508
#include<stdio.h>
#define N 100
void swap(int*,int*);

int main(){
  int data[N],i,j,n,minj,count=0;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d",&data[i]);
  }

  for(i=0;i<n;i++){
    minj=i;
    for(j=i;j<n;j++){
      if(data[j]<data[minj]){
	minj=j;
      }
    }
      if(i!=minj){
	swap(&data[i],&data[minj]);
	count++;
	  }
  }
  
 for(i=0;i<n;i++){
   printf("%d",data[i]);
   if(i!=n-1)
     printf(" ");
 }
 printf("\n%d\n",count);

 return 0;
    
}

void swap(int*x,int*y){
  int data;

  data=*x;
  *x=*y;
  *y=data;
}



Measured memory_bytes: 2104
#include<bits/stdc++.h>
#define ll          long long int
#define ull         unsigned long long int
#define pb(x)       push_back(x)
#define pob()		pop_back()
//#define sort(a)     sort(a.begin(),a.end())
#define done        return 0

#define toUp(ch)    toupper(ch)
#define isUp(ch)    isupper(ch)  //prototype int isupper(int ch)
#define toLow(ch)   tolower(ch)
#define isLow(ch)   islower(ch)
#define isX(ch)     isxdigit(ch) //hexadecimal digits (0-9 && a-f && A-F)
#define isN(ch)     isdigit(ch)  //decimal digits(0-9)
#define isS(ch)     isspace(ch)  //whitespace
#define isP(ch)     ispunct(ch)  //check punctuations !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~.
#define isPr(ch)    isprint(ch)  //check \n \t \b
#define isA(ch)     isalpha(ch)  //alphabets
#define AtoN(ch)    atol(ch)     // string to integer
#define AtoF(ch)    atof(ch)     //string to double
//https://stackoverflow.com/questions/5590381/easiest-way-to-convert-int-to-string-in-c
//https://www.geeksforgeeks.org/converting-strings-numbers-cc/

/*----------[ string to integer ]--------------
string str;  int x=0;
stringstream demo(str);
demo >> x;
cout<< x <<endl;
*/

/*----------[ integer to string ]--------------
string name;  int x=345;
stringstream demo;
demo << x;
name=demo.str();
cout<< name <<endl;
*/
using namespace std;

int main()
{
    double n,m,x,s=0,k;
    ll i,t=0;
    vector<double>a;
    cin>>n>>m;
    for(i=0;i<n;i++){
        cin>>x;
        a.push_back(x);
        s+=x;
    }
    k=s/(4*m);
    for(i=0;i<n;i++){
        if(a[i]>=k){
            t++;
            if(t==m){
                cout<<"Yes"<<endl;
                done;
            }
        }
    }
    cout<<"No"<<endl;
    done;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  ll n,w;
  cin>>n>>w;
  ll a[n+1],b[n+1];
  ll i=0;
  a[0]=0;
  b[0]=0;
  for(i=1;i<=n;i++)
  {
    cin>>a[i]>>b[i];
  }
  ll dp[n+1][w+1];
  ll j=0;
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=w;j++)
        {
          if(i==0||j==0)
            dp[i][j]=0;
          else
          if(j<a[i])
            dp[i][j] = dp[i-1][j];
          else
            dp[i][j] = max(b[i]+dp[i-1][j-a[i]],dp[i-1][j]);
        }
    }
  /*for(i=0;i<=n;i++)
  {
    for(j=0;j<=w;j++)
      cout<<dp[i][j]<<" ";
    cout<<"\n";
  }*/
  cout<<dp[n][w]<<"\n";
}

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

long long n, s, a[100000], b[100000];
int main(){
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
	reverse(a, a+n);
	reverse(b, b+n);
	for(int i = 0; i < n; i++){
		a[i] += s;
		if(a[i] % b[i] == 0) continue;
		s += b[i] - (a[i] % b[i]);
	}
	cout << s;
}

Measured memory_bytes: 1792
n = int(input())
lst = list(map(int, input().split()))
lst.append(0)
lst.insert(0, 0)

dist = []
for i in range(n+1):
  dist.append(abs(lst[i+1]-lst[i]))

sum_dist = sum(dist)
for i in range(n):
  ans = sum_dist-(dist[i]+dist[i+1])
  ans += abs(lst[i]-lst[i+2])
  print(ans)

Measured memory_bytes: 91076
# # Make IO faster
# import sys
# input = sys.stdin.readline

# # get single (or) multiple str
# X = input()

# # get single int
# N = int(input())
# # get multiple int (e.g., 2)
# X, Y = map(int, input().split())
# # get multiple int (e.g., 2) for N lines
# XY = [list(map(int, input().split())) for _ in range(N)]

# from IPython import embed; embed(); exit();

# 全部入り
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


ans = 0
N, D = MAP()
for i in range(N):
    x, y = MAP()
    dist = sqrt(x ** 2 + y ** 2)
    if dist <= D:
        ans += 1
print(ans)


Measured memory_bytes: 27164
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
ll MOD=1000000007;
ll mod=998244353;
int inf=1000000000;
ll INF=10000000000000000;


int main(){
    int n;
    cin >> n;
    if (n<10) cout << n << endl;
    else if (n<100) cout << 9 << endl;
    else if (n<1000) cout << 9+n-99 << endl;
    else if (n<10000) cout << 909 << endl;
    else if (n<100000) cout << 909+n-9999 << endl;
    if (n==100000) cout << 90909 << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 999999999
const int mod = 1000000007;
ll cnt = 0;
 
int main(){
 ll n;  cin >> n;
 

 for(int i=1;i<=n;i++){
    if( i*(i+1)/2 >= n){
        cout << i << endl;
        return 0;
    }
 }
}

Measured memory_bytes: 256
#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() {
    int n; cin >> n;
    int k; cin >> k;

    vector<ll> x(n+1, 0);
    rep(i, n) cin >> x.at(i);

    ll res = 10000000000LL;
    for(int i=0; i<n-k+1; i++){
       ll r = abs(x.at(i)) + abs(x.at(i)-x.at(i+k-1));
       ll l = abs(x.at(i+k-1)) + abs(x.at(i)-x.at(i+k-1)); 
       res = min(res, min(r, l)); 
    }

    cout << res << endl;

}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,x;
	cin>>n;
	for(int times=0;times<n;times++){
		cout<<"Case "<<times+1<<':'<<endl;
		cin>>x;
		for(int i=0;i<10;i++){
			x=x*x%1000000/100;
			cout<<x<<endl;
		}
	}
}

Measured memory_bytes: 1160
#include <iostream>
#include <string>

using namespace std;

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

    if((*A.rbegin() == *B.begin()) && (*B.rbegin() == *C.begin()))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
  int n, a=1, b=1;
  cin >> n;
  vector<string> A(n);
  rep(i, n) cin >> A[i];
  sort(A.begin(), A.end());
  string s = A[0];
  for(int i=1; i<n; i++){
    if(s == A[i]){
      a++;
    if(b<a){
      b = a;
    }
    }
    else {
      a = 1;
      s = A[i];
    }

  }
  //cout << b << endl;
  s = A[0];
  int c = 1;
  if(b == 1){
     rep(i, n) cout << A[i] << endl; 
   }
  for(int i = 1; i<n; i++){

   if(A[i] == s) {
      c++;
      if(c == b) {
      cout << A[i] << endl;
      s = A[i];
      c = 1;
    }    
    }
    else{
      c = 1;
      s = A[i];
    }
    
  }
}

Measured memory_bytes: 14208
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    int a;
    cin >> a;
    int yo,sa,ni,i;
    yo = a/1000;
    sa = (a/100)%10;
    ni = (a/10)%10;
    i = a%10;

    if(yo + sa + ni + i == 7) cout << yo<<'+'<<sa<<'+'<<ni<<'+'<<i<<'='<<7 <<endl;
    else if(yo + sa + ni - i == 7) cout << yo<<'+'<<sa<<'+'<<ni<<'-'<<i<<'='<<7 <<endl;
    else if(yo + sa - ni + i == 7) cout << yo<<'+'<<sa<<'-'<<ni<<'+'<<i<<'='<<7 <<endl;
    else if(yo - sa + ni + i == 7)cout << yo<<'-'<<sa<<'+'<<ni<<'+'<<i<<'='<<7 <<endl;
    else if(yo + sa - ni - i == 7) cout << yo<<'+'<<sa<<'-'<<ni<<'-'<<i<<'='<<7 <<endl;
    else if(yo - sa - ni + i == 7)cout << yo<<'-'<<sa<<'-'<<ni<<'+'<<i<<'='<<7 <<endl;
    else if (yo - sa -ni - i == 7)cout << yo<<'-'<<sa<<'-'<<ni<<'-'<<i<<'='<<7 <<endl;
    else if(yo - sa + ni -i == 7)cout << yo<<'-'<<sa<<'+'<<ni<<'-'<<i<<'='<<7 <<endl;
}

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

int main() {
	int n;
	cin >> n;
	for ( int i = 0; i < n; i++ ){
		deque<int>b,c;
		bool endflag = false;
		int dummy;
		cin >> dummy;
		b.push_back( dummy );
		cin >> dummy;
		c.push_back( dummy );
		for ( int j = 0; j < 8; j++ ){
			cin >> dummy;
			if ( !endflag ) {
				if ( c.size() - 1 ) {
					if ( b[b.size() -1] > c[c.size() -1] ) {
						if ( dummy > b[b.size()-1] )	b.push_back( dummy );
						else if ( dummy > c[c.size()-1] )	c.push_back( dummy );
						else {
							cout << "NO" << endl;
							endflag = true;
						}
					} else {
						if ( dummy > c[c.size()-1] )	c.push_back( dummy );
						else if ( dummy > b[b.size()-1] )	b.push_back( dummy );
						else {
							cout << "NO" << endl;
							endflag = true;
						}
					}
				} else {
					if ( dummy > b[b.size()-1] )	b.push_back( dummy );
					else	c.push_back( dummy );
				}
			}
		}
		if( !endflag )	cout << "YES" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1192
#include <stdio.h>

// Sample Input
// 1819
// 2003
// 876
// 2840
// 1723
// 1673
// 3776
// 2848
// 1592
// 922
// Output for the Sample Input
// 3776
// 2848
// 2840

int main(){
	int i = 0, j, num[10], dumy;

	while(i < 10){

		scanf("%d",&num[i]);
		
		if(num[i]>10000)
			continue;

		i++;
	}
	for(i = 0; i < 10; i++){
		for(j = i + 1; j < 10; j++){
			if(num[i] < num[j]){
				dumy = num[i];
				num[i] = num[j];
				num[j] = dumy;
			}
		}
	}

	for(i = 0; i < 3; i++){
		printf("%d\n", num[i]);
	}

    return 0;
}

Measured memory_bytes: 600
import java.util.*;
import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		Main ins = new Main(in);
		ins.calc();
		ins.showResult();
	}

	int H, W, M;
	int[] h, w;
	Set<Integer>[] rows, cols;

	Main(BufferedReader in) throws IOException {
		String[] tokens = in.readLine().split(" ");
		H = Integer.parseInt(tokens[0]);
		W = Integer.parseInt(tokens[1]);
		M = Integer.parseInt(tokens[2]);
		h = new int[M];
		w = new int[M];
		for (int i = 0; i < M; ++i) {
			tokens = in.readLine().split(" ");
			h[i] = Integer.parseInt(tokens[0]) - 1;
			w[i] = Integer.parseInt(tokens[1]) - 1;
		}

		rows = new Set[H];
		cols = new Set[W];
		for (int i = 0; i < H; ++i) {
			rows[i] = new HashSet<>();
		}
		for (int i = 0; i < W; ++i) {
			cols[i] = new HashSet<>();
		}

		for (int i = 0; i < M; ++i) {
			rows[h[i]].add(i);
			// cols[w[i]].add(i);
		}
	}

	int colFirst() {
		Set<Integer>[] rows, cols;
		rows = new Set[H];
		cols = new Set[W];
		for (int i = 0; i < H; ++i) {
			rows[i] = new HashSet<>();
		}
		for (int i = 0; i < W; ++i) {
			cols[i] = new HashSet<>();
		}
		for (int i = 0; i < M; ++i) {
			cols[w[i]].add(i);
		}

		// 要素数最大の行を求める
		int maxCol = 0;
		int maxColCount = -1;
		for (int i = 0; i < W; ++i) {
			if (cols[i].size() > maxColCount) {
				maxCol = i;
				maxColCount = cols[i].size();
			}
		}
		// この行で爆破される対象を除いて，カウントする
		Set<Integer> col = cols[maxCol];
		for (int i = 0; i < M; ++i) {
			if (!col.contains(i)) {
				rows[h[i]].add(i);
			}
		}

		int maxRow = -1;
		int maxRowCount = -1;
		for (int i = 0; i < H; ++i) {
			if (rows[i].size() > maxRowCount) {
				maxRow = i;
				maxRowCount = rows[i].size();
			}
		}
		int result = maxColCount;
		if (maxRow >= 0) {
			result += maxRowCount;
		}

		return result;

	}

	int rowFirst() {
		Set<Integer>[] rows, cols;
		rows = new Set[H];
		cols = new Set[W];
		for (int i = 0; i < H; ++i) {
			rows[i] = new HashSet<>();
		}
		for (int i = 0; i < W; ++i) {
			cols[i] = new HashSet<>();
		}
		for (int i = 0; i < M; ++i) {
			rows[h[i]].add(i);
		}
		// 要素数最大の行を求める
		int maxRow = 0;
		int maxRowCount = -1;
		for (int i = 0; i < H; ++i) {
			if (rows[i].size() > maxRowCount) {
				maxRow = i;
				maxRowCount = rows[i].size();
			}
		}
		// この行で爆破される対象を除いて，カウントする
		Set<Integer> row = rows[maxRow];
		for (int i = 0; i < M; ++i) {
			if (!row.contains(i)) {
				cols[w[i]].add(i);
			}
		}
		int maxCol = -1;
		int maxColCount = -1;
		for (int i = 0; i < W; ++i) {
			// System.out.println(cols[i].size());
			if (cols[i].size() > maxColCount) {
				maxCol = i;
				maxColCount = cols[i].size();
			}
		}
		int result = maxRowCount;
		if (maxCol >= 0) {
			result += maxColCount;
		}

		return result;
	}

	void calc() {

		int rowFirst = rowFirst();
		int colFirst = colFirst();
		int result = Math.max(rowFirst, colFirst);
		System.out.println(result);
	}

	void showResult() {
	}
}

Measured memory_bytes: 344212
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	int n;
	cin>>n;
	int m=(n+1)/2;
	cout<<setprecision(15)<<double(m)/double(n)<<endl;
}

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

using namespace std;

vector<long long> seg;

long long query(int ql, int qr, int lb, int rb, int id) {
  if (qr <= lb || rb <= ql) return 0;
  if (ql <= lb && rb <= qr) return seg[id];
  int m = (lb + rb) / 2;
  return max(query(ql, qr, lb, m, 2 * id), query(ql, qr, m, rb, 2 * id + 1));
}

void modify(int i, long long x, int lb, int rb, int id) {
  if (i < lb || rb <= i) return;
  if (rb - lb == 1) {
    seg[id] = x;
    return;
  }
  int m = (lb + rb) / 2;
  modify(i, x, lb, m, 2 * id);
  modify(i, x, m, rb, 2 * id + 1);
  seg[id] = max(seg[2 * id], seg[2 * id + 1]);
}

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

  int n;
  cin >> n;
  vector<int> h(n), a(n);
  seg = vector<long long>(4 * n);
  for (int i = 0; i < n; i++) cin >> h[i];
  for (int i = 0; i < n; i++) cin >> a[i];

  vector<long long> dp(n);
  for (int i = 0; i < n; i++) {
    dp[i] = a[i] + query(1, h[i], 1, n + 1, 1);
    modify(h[i], dp[i], 1, n + 1, 1);
  }
  cout << query(1, n + 1, 1, n + 1, 1) << '\n';
  return 0;
}

Measured memory_bytes: 9728
def solv_quadratic_equation(a, b, c):
    """ 2次方程式を解く  """
    D = (b**2 - 4*a*c) ** (1/2)
    x_1 = (-b + D) / (2 * a)
    x_2 = (-b - D) / (2 * a)


    return x_1, x_2





n=int(input())
N=n
a = []
while n % 2 == 0:

    a.append(2)
    n //= 2
f = 3
while f * f <= n:
    if n % f == 0:

        a.append(f)
        n //= f
    else:
        f += 2
if n != 1:

    a.append(n)

aa=set(a)
g=0
for i in aa:
    x1,x2=solv_quadratic_equation(1,1,-2*a.count(i))
    g=int(max(x1,x2))+g



print(g)


Measured memory_bytes: 63616
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<pii>>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

ll gcd(ll a, ll b) {
    return (a % b == 0) ? b : gcd(b, a % b);
}

int main() {
    ll A, B;
    cin >> A >> B;
    cout << A * B / gcd(A, B) << endl;
    return 0;
}


Measured memory_bytes: 256
_ = gets
cards = gets.chomp.split.map(&:to_i)

cards.sort!.reverse!

alice_cards, bob_cards = cards.partition.with_index { |_, i| i.even? }
alice_score = alice_cards.reduce(:+)
bob_score = bob_cards.reduce(:+)

result = alice_score - bob_score

puts result


Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
 
int main() {
    ll n;
    cin >> n;
    vector<int> vec;
    while(true){
        vec.push_back(n%26);
        n=(n-1)/26;
        if(n==0) break;        
    }
    rep(i,vec.size()){
        int a=vec[vec.size()-i-1];
        if(a==0) a=26;
        char c='a'-1+a;
 
        cout << c;
    }
 
}

Measured memory_bytes: 3624
import java.util.Scanner;

public class Main {
	static char[][] mapC;
	static boolean[][] mapB;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h, w;
		while ((h = sc.nextInt()) != 0 && (w = sc.nextInt()) != 0) {
			mapC = new char[h + 2][w + 2];
			mapB = new boolean[h + 2][w + 2];
			for (int i = 0; i < h; i++) {
				String str = sc.next();
				for (int j = 0; j < w; j++) {
					mapC[i + 1][j + 1] = str.charAt(j);
				}
			}
			int ans = 0;
			for (int i = 1; i < h + 1; i++) {
				for (int j = 1; j < w + 1; j++) {
					if (!mapB[i][j]) {
						ans++;
						distribution(i, j);
					}
				}
			}
			System.out.println(ans);
		}
	}

	static void distribution(int i, int j) {
		mapB[i][j] = true;
		if (!mapB[i - 1][j] && mapC[i - 1][j] == mapC[i][j]) {
			distribution(i - 1, j);
		}
		if (!mapB[i + 1][j] && mapC[i + 1][j] == mapC[i][j]) {
			distribution(i + 1, j);
		}
		if (!mapB[i][j - 1] && mapC[i][j - 1] == mapC[i][j]) {
			distribution(i, j - 1);
		}
		if (!mapB[i][j + 1] && mapC[i][j + 1] == mapC[i][j]) {
			distribution(i, j + 1);
		}
	}
}

Measured memory_bytes: 22720
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <deque>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <locale>
#include <iomanip>

#define nl '\n';

using namespace std;

double n;

int main(){

    cin >> n;

    if(n < 3){
        cout << 0;
        return 0;
    }

    cout << floor(n/3);






}

//g++ -std=c++14 comp.cpp -o b; ./b.exe
//g++ -std=c++14 comp.cpp && ./a.out

// char** arr = new char*[r];
// for(long long i = 0; i < r; i++) arr[i] = new char[c];

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define INF 100000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
const int MOD = 1000000007;

int main(){
    int N,K;cin>>N>>K;
    vector<ll> x(N,0);
    REP(i,N) cin>>x[i];
    ll res = 1LL<<60;
    for(int i = 0; i + K -1 <N ; i++)
    {
        ll left = x[i];
        ll right = x[i+K-1];
        res = min(res,min(abs(left),abs(right))+right - left);
        /* code */
    }
    cout<<res<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using loop = int;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(loop (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(loop (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(loop (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(loop (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause") //comment out this on AOJ.
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    ll x, y; cin >> x >> y;
    ll ans = LLINF;
    if (x <= y)chmin(ans, y - x);
    if (-x <= y)chmin(ans, y + x + 1);
    if (x <= -y)chmin(ans, -y - x + 1);
    if (-x <= -y)chmin(ans, -y + x + 2);
    cout << ans << "\n";
}

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

int main() {
    int n, m, c;
    cin>>n>>m>>c;
    int b[m];
    int a[n][m];
    for(int i=0;i<m;i++) cin>>b[i];
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) cin>>a[i][j];
    }
    int ans=0;
    for(int i=0;i<n;i++) {
        int tmp=0;
        for(int j=0;j<m;j++) {
            tmp+=a[i][j]*b[j];
        }
        if(tmp+c>0) ans++;
    }
    cout<<ans<<endl;
}

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

int main()
{
	int r, d, x0, x;
	cin >> r;
	cin >> d;
	cin >> x0;
	x = x0;
	for (int i=0; i<10; i++) {
		x = r * x - d;
		cout << x << endl;
	}
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("5");
            WillReturn.Add("10");
            WillReturn.Add("15");
            //25
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("10");
            WillReturn.Add("10");
            WillReturn.Add("15");
            //35
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("10");
            WillReturn.Add("20");
            WillReturn.Add("30");
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList.Skip(1).Select(X => int.Parse(X)).ToArray();

        //可能な和のSet
        var SumSet = new HashSet<int>();
        SumSet.Add(0);

        foreach (int EachInt in AArr) {
            foreach (int EachSum in SumSet.ToArray()) {
                int NewSum = EachSum + EachInt;
                SumSet.Add(NewSum);
            }
        }

        int Answer = 0;
        foreach (int EachSum in SumSet) {
            if (EachSum % 10 == 0) continue;

            if (Answer < EachSum) {
                Answer = EachSum;
            }
        }
        Console.WriteLine(Answer);
    }
}


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

long long pow(long long x, long long n, long long p)
{
    long long r = 1;
    while (n > 0)
    {
        if (n & 1)
            r = r * x % p;
        x = x * x % p;
        n >>= 1;
    }
    return r;
}

int main()
{
    long long P = 1000000007;
    long long m, n;

    cin >> m >> n;
    cout << pow(m, n, P) << endl;
}



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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int a, b, c;
    cin >> a >> b >> c;
    swap(a, b);
    swap(a, c);
    cout << a << " " << b << " " << c << endl;

}



Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<string>
#include<iomanip>
#include<algorithm>
#include<vector> 
#include <functional>
#define fx(x) fixed<<setprecision(x)
#define ll long long
using namespace std;
void fast() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
int main() {
	fast();
	int n;
	cin >> n;
	if (n % 1000==0)
		cout << 0;
	else
		cout << 1000-(n % 1000);
	return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define sec second
#define pii pair<int, int>
int n, m, k, x, y, sum, ans;
char s[110005];
int main () {
	scanf("%s", s);
	n=strlen(s);
	for (int i=0; i<n; i++) {
		if (s[i]=='d'&&s[i+1]=='r'&&s[i+2]=='e'&&s[i+3]=='a'&&s[i+4]=='m'){
			if (s[i+5]=='e'&&s[i+6]=='r'&&s[i+7]!='a') i+=6;
			else i+=4;
		} else if (s[i]=='e'&&s[i+1]=='r'&&s[i+2]=='a'&&s[i+3]=='s'&&s[i+4]=='e') {
			if (s[i+5]=='r') i+=5;
			else i+=4;
		} else {
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
	return 0;
}

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

void solve(){
    int h;
    int a;
    cin >> h >> a;
    int temp = h%a;
    if(temp ==0) {
        cout << h/a;
    }
    else {
        cout << h/a + 1;
    }
}

int main() {
    ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
    cout.setf(ios::fixed), cout.precision(0);
    // freopen("a.txt","r",stdin);
    solve();
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll MOD = (1e+9) + 7;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
typedef pair<P, int> PP;
int out[250000]; int used[250000] = {};
int main() {
	int n;
	cin >> n;
	int le = 0;
	int ri = n * n - 1;
	P x[500];
	rep(i, n) {
		cin >> x[i].first; x[i].second = i + 1; x[i].first--;
	}
	sort(x, x + n);
	rep(i, n) {
		used[x[i].first] = 1;
		out[x[i].first] = x[i].second;
	}
	bool f = true;
	rep(i, n) {
		int cnt = 0;
		while (cnt < x[i].second - 1&&le<n*n) {
			if (used[le]) {
				le++; continue;
			}
			out[le] = x[i].second; used[le] = 1; le++; cnt++;
		}
		if (le > x[i].first) {
			f = false; break;
		}
	}
	per(i, n) {
		int cnt = 0;
		while (cnt < n - x[i].second&&ri >= 0) {
			if (used[ri]) {
				ri--; continue;
			}
			out[ri] = x[i].second; used[ri] = 1; ri--; cnt++;
		}
		if (ri < x[i].first) {
			f = false; break;
		}
	}
	if (!f)cout << "No" << endl;
	else {
		cout << "Yes" << endl;
		rep(i, n*n) {
			if (i > 0)cout << " ";
			cout << out[i];
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3072
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;

using namespace std;

int main(void){
    int N;
    cin>>N;
    bool isKuKu = false;
    rep(i, 9) rep(j, 9) if((i+1)*(j+1) == N) isKuKu=true;
    if(isKuKu==true) cout<<"Yes"<<endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>
#include <sys/time.h>
#include <fstream>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define REP(i,n)  FOR(i,0,n)
#define each(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define EACH(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
#define sz(s) (int)((s).size())


#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
#define MP(x,y) make_pair((x),(y))

double pi=3.14159265358979323846;

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
	os << "[ ";
	REP(i,z.size())os << z[i] << ", " ;
	return ( os << "]" << endl);
}

template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
	os << "set( ";
	EACH(p,z)os << (*p) << ", " ;
	return ( os << ")" << endl);
}

template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
	os << "{ ";
	EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;
	return ( os << "}" << endl);
}

template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
	return ( os << "(" << z.first << ", " << z.second << ",)" );
}

double get_time(){
	struct timeval tv;
	gettimeofday(&tv, NULL);
	return tv.tv_sec + tv.tv_usec*1e-6;
}

typedef unsigned int uint32_t;
struct RND{
	uint32_t x;
	uint32_t y;
	uint32_t z;
	uint32_t w;
	RND(){
		x=123456789;
		y=362436069;
		z=521288629;
		w=88675123;
	}
	void init(int seed){
		x=123456789;
		y=362436069;
		z=521288629;
		w=seed+100;
		REP(i,10)get();
	}
	uint32_t get(){
		uint32_t t;
		t=x^(x<<11);
		x=y;y=z;z=w;
		w=(w^(w>>19))^(t^(t>>8));
		return w;
	}
};
RND rnd;

bool good(ll n){
	return n%2==0 || n%3==0 || n%5==0;
}

void _main(istream &inp){
	ll n;
	inp >> n;
	ll su = 0;
	for(int j=29998; j>=0; j--){
		if(j%2==0 || j%3==0 || j%5==0){
			su += j;
			n--;
			cout << j << " ";
			if(n==2){
				for(ll a=1; a<=100; a++){
					for(ll b=1; b<a; b++){
						if(a%3==0 && b%5==0 && (su+a+b)%30==0  ){
							cout << a << " " << b << endl;
							return;
						}
					}
				}
			}
		}
	}


}

int main(){
	if(0){
		ifstream ifs("test.txt");
		_main(ifs);
	}
	else{
		_main(cin);
	}
	return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

int n, m, a, b;
vector<int> edge[108000];
vector<P> ans;
int dep[108000];
bool come[108000];

int dfs(int x, int last = -1){
    int cnt = 0;
    int deg = 0;
    come[x] = true;
    vector<P> tmp;
    for(auto to:edge[x]){
        if(to == last)continue;
        if(come[to]){
            if(dep[to] < dep[x]){
                ans.push_back(P(x, to));
                deg++;
            }
        }
        else{
            dep[to] = dep[x] + 1;
            int tocnt = dfs(to, x);
            if(tocnt % 2 == 1)ans.push_back(P(to, x));
            else ans.push_back(P(x, to));
            cnt += tocnt;
            deg++;
        }
    }
//    cout << x << " " << cnt + (deg % 2) << endl;
    return cnt + (deg % 2);
}

int main(){
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        cin >> a >> b;
        a--,b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    if(dfs(0) % 2 == 1){
        cout << -1 << endl;
        return 0;
    }

    for(auto p:ans)cout << p.first+1 << " " << p.second+1 << endl;
    
    return 0;
}

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

#define int long long
#define rep(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define eb emplace_back
#define dump(x) cout << #x << " = " << (x) << endl
#define chk() cout << "now" << endl;
#define ALL(x) (x).begin(), (x).end()
#define SORT(c) sort((c).begin(), (c).end())
#define SORTG(c) sort(ALL(c), greater<int>());
#define fi first
#define se second
int INF = 1e9 + 7;

typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vector<int>> mat;

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

void solve() {
  int K;
  string S;
  cin >> K >> S;

  int l = S.length();
  if (l <= K) {
    cout << S;
  } else {
    rep(i, 0, K) { cout << S[i]; }
    cout << "...";
  }
  cout << endl;
}

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

  // cout << fixed << setprecision(10);

  solve();

  return 0;
}


Measured memory_bytes: 3668
# AC: msec(Python3)
from math import factorial
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

def cmb(n, r):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    r = min(n-r, r)
    res = 1
    for i in range(r):
        res *= n - i

    return res // factorial(r)


def prime_factorization(n):
    d = []
    i, e = 2, 0  # factor, exponent
    while i * i <= n:
        while n % i == 0:
            n //= i
            e += 1
        if e > 0:
            d.append((i, e))
        i += 1
        e = 0
    if n > 1:
        d.append((n, 1))
    return d


def main():
    N,M = map(int, readline().split())

    d = prime_factorization(M)

    ans = 1
    for i, e in d:
        ans *= cmb(N-1+e, e)
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
// #include <atcoder/all>
#define ll long long int
#define ld long double
#define yorn(f) std::cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) std::cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) std::cout << x << endl;
#define println(x) std::cout << x << endl;
using namespace std;
// using namespace atcoder;

void Main()
{
    ll n, m;
    cin >> n >> m;

    vector<ll> a(m), b(m), c(m);
    rep(i, m) cin >> a[i] >> b[i] >> c[i];

    // Warshall–Floyd 
    ll INF = 1e18;
    vector<vector<ll> > d(n, vector<ll>(n, INF));
    rep(i, m) {
        d[a[i] - 1][b[i] - 1] = c[i];
        d[b[i] - 1][a[i] - 1] = c[i];
    }
    rep (i, n) {
        rep (j, n) {
            if (i == j) d[i][j] = 0;
        }
    }
    rep(k, n) {
        rep (i, n) {
            rep (j, n) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }        
    }
    
    ll res = 0;
    rep(i, m) {
        bool ok = false;
        rep(s, n) {
            if (d[s][a[i]-1] + c[i] == d[s][b[i]-1]) {
                ok = true;
                break;
            }
        }
        if (!ok) {
            res++;
        }
    }

    put(res);
}
signed main(){ Main();return 0;}

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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
int a[100005];
int b[100005];

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

	cin >> n;

	for (int i = 0;i < n;i++){
		cin >> a[i];
	}
	for (int i = 0;i < n;i++){
		cin >> b[i];
	}

	int d[100005];

	for (int i = 0;i < n;i++){
		d[i] = a[i]-b[i];
	}

	sort(d,d+n);

	int ni = n;
	d[n] = 0;
	int ans = 0;
	for (int i = 0;i < n;i++){
		if(d[i] >= 0) break;
		while(d[ni]+d[i] < 0){
			d[i] += d[ni];
			ni--;
			ans++;
			if(ni == i){
				cout << -1 << endl;
				return 0;
			}
		}
		d[ni] += d[i];
		ans++;
	}

	cout << ans << endl;

	return 0;

}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define OUT(x) std::cout << (x) << std::endl
typedef long long ll;

int main() {
    int h, w;
    cin >> h >> w;
    int c[10][10];
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> c[i][j];
        }
    }

    for (int k = 0; k < 10; k++) {
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            int a;
            cin >> a;
            if (a == -1 || a == 1)
                continue;
            ans += c[a][1];
        }
    }
    OUT(ans);
}

Measured memory_bytes: 256
n = int(input())
a = list( map(int,input().split()) )
dp = [ 0 for i in range(n) ]
dp[0] = 0
if n==1:
    print(dp[0])
else:
    dp[1] = abs( a[1]-a[0])
    for i in range(2,n):
        dp[i] = min( dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]) )
    print(dp[n-1])


Measured memory_bytes: 13928
N = int(input())
D, X = map(int,input().split())
d = {}
for i in range(1,N+1):
  d[i] = int(input())

pieces = 0
for day in range(1,D+1):
  for person in range(1,N+1):
    if (day - 1) % d[person] == 0:
      pieces += 1
 
pieces += X
print(pieces)

Measured memory_bytes: 9120
"use strict";

function main(input) {
  input = input.trim().split(" ");
  const a = BigInt(input[0]);
  const b = BigInt(input[1]);
  const c = BigInt(input[2]);
  const d = BigInt(input[3]);

  let ans;
  ans = a * c;
  if (ans < a * d) {
    ans = a * d;
  }
  if (ans < b * c) {
    ans = b * c;
  }
  if (ans < b * d) {
    ans = b * d;
  }
  ans = String(ans).split("").join("");
  console.log(ans);
}

function numberSort(array) {
  array.sort(f);
  return array;
}

var f = function (a, b) {
  return a - b;
};

main(require("fs").readFileSync("/dev/stdin", "utf-8"));


Measured memory_bytes: 29676
/*
    問題をよく読もう！
    論理的に考えよう！
    サンプルを確認しよう!
    絶対に諦めるな！
    工夫をしろ！

    Twitterは終わるまでログアウト！
    （間違えて解法をツイートしてはいけないから）

*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cctype>
using namespace std;
#define rep(i, n) for(int i=0; i<n; ++i)
typedef long long ll;
//必要な宣言
#define MAX_N 1000

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  int time_A[100] = {};
  int time_B[100] = {};
  int cnt = 0;

  for(int i=A; i<B; ++i) {
    time_A[i] = 1;
  }

  for(int i=C; i<D; ++i) {
    time_B[i] = 1;
  }

  for(int i=0; i<100; ++i) {
    if(time_A[i] == 1 && time_B[i] == 1)
      ++cnt;
  }

  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 256
def solve():
    ans = 1
    N = int(input())
    s = input()
    ans = 0
    for i in range(1000):
    	t = str(i).zfill(3)
    	t_index = 0 
    	for s_element in s:
    		if s_element == t[t_index]:
    			t_index += 1
    			if t_index == 3:
    				break
    	if t_index == 3:
    		ans += 1
    print(ans)
solve()

Measured memory_bytes: 42396
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int x = scan.nextInt();
		int y = scan.nextInt();
		int z = scan.nextInt();
		
		System.out.println(z+" "+x+" "+y);
		
	}	
}


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

int main(){
  int a,b,c,d,e,k;
  cin >> a >> b >> c >> d >> e >> k;
  
  bool trans = true;
  if(abs(a-b) > k || abs( b-c)>k || abs(c-d)>k || abs(d-e)>k) trans = false;
  else if(abs(a-c) > k ||  abs(b-d)>k || abs(c-e)>k) trans = false;
  else if(abs(a-d) > k ||  abs(b-e)>k) trans = false;
  else if(abs(a-e)>k) trans = false;
  if(trans) cout<<"Yay!"<<endl;
  if(!trans) cout<<":("<<endl;
  return 0;
}


Measured memory_bytes: 256
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = I()
dp = FILL2(0,N+1,3)
H = LI2(N)
for i in range(N):
    for j in range(3):
        for k in range(3):
            if j!=k:
                dp[i+1][j] = max(dp[i+1][j],dp[i][k] + H[i][j])

print(max(dp[N]))


Measured memory_bytes: 90968
#include<stdio.h>
int main()
{
    int a,b,c;
    float u=a,x=b,k,n;
    scanf("%f%f",&u,&x);
    k=(u+x)/2;
    n=k+.5;
    c=n;
  printf("%d\n",c);
    return 0;
}

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

using namespace std;
	
const int maxn = 1e2 + 20;
int ar[maxn];

int main()
{
	int a,b;
	long long ans=0;
	cin >> a >> b;
	int c,a0=0,a1=0;
	for(int i=0;i<a;i++)
	{
		cin >> c;
		if(c%2 == 0)
			a0++;
		else 
			a1++;
	}
	if(a0 == 0 && b == 0)
		ans=pow(2,(a1-1));
	else if(a1 == 0 && b == 1)
		ans=0;
	else if(a1 == 0 && b == 0)	
		ans=pow(2,a0);
	else if(b == 0)
		ans=pow(2,(a1-1))*pow(2,a0);
	else if(b == 1)
		ans=pow(2,(a1-1))*pow(2,a0);
	cout << ans;
}		

 



Measured memory_bytes: 256
n = int(input())
hs = list(map(int,input().split()))
ans = 0
List = []
h = hs[0]
for i in range(n-1):
	hb = h
	h = hs[i+1]
	if(hb>=h):
		ans += 1
	else:
		List.append(ans)
		ans = 0
List.append(ans)
print(max(List))

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

int main(){
    ll n;
    cin >> n;
    ll ans = 1e18;
    for(int i = 1; i < 1000010; i++){
        ll can = 0;
        if(n%i == 0){
            can += i-1+(n/i)-1;
            if(ans > can) ans = can;
        }
    } 
    cout << ans << endl;
    return 0;   
}

Measured memory_bytes: 256