#include "bits/stdc++.h"
using namespace std;
// ================================== Macros ======================================================
#define int long long int
#define double long double
#define uint unsigned long long
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vvi vector<vector<int>>
#define vvb vector<vector<bool>
#define vp vector<pair<int,int>>
#define pb push_back
#define el(a,v) for(auto& a : v)
#define fr(i,n) for(int i=0;i<n;i++)
#define rf(i,n) for(int i = (n)-1;i>=0;i++)
#define rep(i,a,n) for(int i=0;i<=(a);i++)
#define sz(v) = (int) v.size()
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define srt(v) sort(v.begin(),v.end())
#define rev(v) sort(v.rbegin(),v.rend())
#define dbg(var) cout<<#var<<" = "<<var<<nl;
#define unq(v) v.resize(distance(v.begin(), unique(v.begin(), v.end())))
#define nl "\n"
#define ws " "
const int MOD=1e9+7;
const int INF = INT64_MAX-4;
void solve() {
int n;cin>>n;
vector<int> v(n);
int ops = 0;
cin>>v;
reverse(v.begin(),v.end());
while(v.back()==1)v.pop_back();
el(a,v){
if(a==1){
cout<<-1<<nl;
return;
}
}
reverse(v.begin(),v.end());
// dbg(v);
n=v.size();
vector<double> b(n);
fr(i,n){
b[i] =log2(log2(v[i]));
}
// dbg(b);
for(int i =1;i<n;i++){
int tmp = max((double)0.0,ceil(b[i-1]-b[i]));
b[i]+=tmp*log2(2);
ops+=tmp;
}
cout<<ops<<nl;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
Using direct floating point arithmetic is a gamble if you don't understand what you are doing.
Then what is the solution, how to avoid such errors.
I am really curious about how the second approach avoids floating point errors.
I don't trust FP in this problem either. I'd rather do a full integer-based solution.
For this one, the
epsused in AC solution helped a little bit in circumventing. TL;DR there might be cases where the "equal" comparison for FP numbers aren't accurate, somehow making two identical number having slight errors (turning $$$0$$$ into $$$10^{-15}$$$ or something that similarly low, pushingceilto $$$1$$$).epssets a threshold for ignored error.