g875 - Error
題目描述
題目要求透過互動式判斷，找出一個滿足特定條件的數字。程式需要向伺服器發送數字，伺服器會回傳一個布林值，表示該數字是否滿足條件。目標是找到最小的滿足條件的數字。由於 ZeroJudge 伺服器目前回傳 500 錯誤，無法正常運作，因此只能根據提供的程式碼推測題目意圖。
解題思路
程式碼使用二分搜尋法來尋找滿足條件的數字。request 函數向伺服器發送一個數字，並根據伺服器的回應決定搜尋範圍。upload_answer 函數將答案提交給伺服器。cpp_start 函數負責讀取輸入，並初始化二分搜尋的範圍。由於伺服器無法正常運作，程式碼的實際行為無法驗證，但可以推斷題目要求找到一個最小的數字 m，使得 request(m) 回傳 true。
複雜度分析
- 時間複雜度: O(log N)，其中 N 是搜尋範圍的大小。二分搜尋每次將搜尋範圍減半，因此時間複雜度為對數級別。
- 空間複雜度: O(1)。程式碼只使用了常數級別的額外空間。
程式碼
#include <iostream>
using namespace std;
long long st_ans1=0,st_ans2=0,st_com=0,st_cnt=0;template<typename stst>stst request(stst a){st_cnt++;if(st_com==1)std::cout << "request=qwertyuiopasdfghjklzxcvbnm;check=ok;waiting_for_the_answer;next_line=check;reading=false;check_point=false\n";if(a>=st_ans2-st_ans1) return 1ll;else return 0ll;}template<typename stst>void upload_answer(stst a){if(st_com==1){std::cout<<"request=mnbvcxzlkjhgfdsapoiuytrewq;check=ok;waiting_for_the_answer;next_line=answer;reading=true;check_point=true\n";std::cout <<1000000007+5*(4*a+3) << '\n';}if(a==st_ans2-st_ans1){std::cout << "AC\n";std::cout << "request: "<<st_cnt<<" times.";}else{std::cout << "WA\n";std::cout << "Your answer is: "<<a<<".\n";std::cout << "request: "<<st_cnt<<" times.";}}void cpp_start(){long long st_cc;std::cin>>st_cc;if(st_cc==-87) st_com=1;if(st_com==1){long long Do_not_change_it_plz,ststone,st_zerojudge,st_IDK,st_hard,st_mouse,st_check;std::cin>>Do_not_change_it_plz>>ststone>>st_zerojudge>>st_IDK>>st_hard>>st_mouse>>st_check;st_ans1=Do_not_change_it_plz+ststone-st_zerojudge-st_IDK+st_hard-st_mouse;st_ans2=st_ans1*st_check;}else st_ans2 = st_cc;}
int main(){
cpp_start();
long long l=0,r=1e7;
while(l<=r){
long long m=(l+r)/2;
if(request(m)){
r=m-1;
}
else{
l=m+1;
}
}
upload_answer(l);
}