Pagini recente » Problema satisfiabilităţii formulelor logice de ordinul doi | Problema satisfiabilităţii formulelor logice de ordinul doi | Cod sursa (job #238220) | Problema satisfiabilității formulelor logice de ordinul doi | Cod sursa (job #2521738)
#include <bits/stdc++.h>
std::ifstream fin("secv3.in");
std::ofstream fout("secv3.out");
int n, l, u, cnt;
double left, right, mid, sum;
std::pair<double, double> list[30005];
double numbers[30005];
std::queue<double> q;
bool check(double val);
int main()
{
fin>>n>>l>>u;
for(int i=1; i<=n; ++i) fin>>list[i].first;
for(int i=1; i<=n; ++i) fin>>list[i].second;
left=0.0, right=1000.0;
for(int k=1; k<=500; ++k){
mid=(left+right)/2;
if(check(mid)) left=mid;
else right=mid;
}
fout<<std::fixed<<std::setprecision(2)<<left;
return 0;
}
bool check(double val){
sum=0.0; cnt=0; bool done=false;
for(int i=1; i<=n; ++i) numbers[i]=list[i].first-list[i].second*val;
for(int i=1; i<l; ++i) {
q.push(numbers[i]);
sum+=numbers[i];
++cnt;
}
for(int i=l; i<=n; ++i){
q.push(numbers[i]);
sum+=numbers[i];
++cnt;
if(cnt>u){
--cnt;
sum-=q.front();
q.pop();
}
while(cnt>l && sum<0 && q.front()<0){
--cnt;
sum-=q.front();
q.pop();
}
if(sum>=0) {done=true; break;}
}
while(!q.empty()) q.pop();
return done;
}