[acnoi2022] guess numbers

subject

Background
“ Ah, here ,” $\mathsf{O}\mathsf{U}\mathsf{Y}\mathsf{E}$ Suddenly said ,“ Let's be brothers ！ That's it. , As an extension of the condition . Because a weak person like me , It's very suspicious not to report to the group for warmth ……”

$\mathsf{D}\mathsf{D}(\mathsf{X}\mathsf{Y}\mathsf{X})$ Quite surprised . He didn't expect things to go so smoothly .

“ Good. , On the way home, drop in and say goodbye ！”

“ As long as the inner volume is more than .” $\mathsf{O}\mathsf{U}\mathsf{Y}\mathsf{E}$ Want to .

“ As long as the red stone is not finished .” $\mathsf{D}\mathsf{D}(\mathsf{X}\mathsf{Y}\mathsf{X})$ Want to .

—— “ Will never be separated ！” The two said in unison .

Title Description
Interactive questions . There is one $x\in [10,2^{64}-10)$ Unknown , You guess. . Several intervals can be given each time ：

• if $x$ In the union of these intervals , Then the interactive library has $p=0.8$ Probability return of $1$, Yes $(1-p)$ Probability return $0$ .
• otherwise , The interactive library must return $0$ .

Please use the least expected number of times to determine $x$ .

Data range and tips
Conduct $T=3000$ After the first test , Your average number of inquiries should not exceed $107$ .

Ideas

I hope you have too $\mathsf{O}\mathsf{U}\mathsf{Y}\mathsf{E}$ The same insight , Enough to see that the key message is The probability that each number will become the answer .

We use it $\mathrm{E}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{o}\mathrm{p}\mathrm{y}$ Measure it , The symbol is $H$ .—— You don't know information entropy ？ Then you certainly haven't seen $3\mathrm{b}1\mathrm{b}$ Teach you to play $\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{l}\mathrm{e}$

---

Suddenly found that I can't information entropy , I'm a clown .

Definition
$$H=-\sum _{x\in \mathbb{U}}\mathrm{Pr}(x){\log }_2\mathrm{Pr}(x)$$

among $\mathbb{U}$ It's the sample space . The following is a brief description $\omega (x)=-x{\log }_{2}x$ .

This definition is very consistent with our intuition ： be aware $\omega (ab)=b\omega (a)+a\omega (b)$, So there is
$$\begin{array}{rl}H& =\sum _{x\in \mathbb{U}}\omega (\mathrm{Pr}[x|A]\mathrm{Pr}(A))+\sum _{x\in \mathbb{U}}\omega (\mathrm{Pr}[x|\neg A]\mathrm{Pr}(\neg A))\\ & =\mathrm{Pr}(A)H[A]+\mathrm{Pr}(\neg A)H[\neg A]+\omega (\mathrm{Pr}(A))+\omega (\mathrm{Pr}(\neg A))\end{array}$$
among $H[A]$ by $A$ Entropy under conditions , namely ${\sum }_{x\in \mathbb{U}}\omega (\mathrm{Pr}[x|A])$ .

in other words , use $\mathrm{Pr}(A)$ Corresponding entropy （ The amount of information ） know $A$ Is it true , Then recurse down .

---

Consider asking a set $T$ Satisfy $\mathrm{Pr}[x\in T]=q,H[x\in T]=h_1,H[x\notin T]=h_0$ . After asking ：

• Yes $pq$ The probability of $1$, then $\mathrm{Pr}[x\in T]=1$, New entropy $H=h_1$ .
• Yes $(1-pq)$ The probability of $0$, By Bayesian formula $\mathrm{Pr}[x\in T|0]=\frac{\mathrm{Pr}[0|x\in T]\mathrm{Pr}[x\in T]}{\mathrm{Pr}[0]}=\frac{q-pq}{1-pq}$, New entropy $H=\frac{q-pq}{1-pq}{h}_1+\frac{1-q}{1-pq}{h}_2+\omega (\frac{q-pq}{1-pq})+\omega (\frac{1-q}{1-pq})$ .

The original entropy is $q{h}_1+(1-q)h_2+\omega (q)+\omega (1-q)$ . therefore , The expected amount of information is
$$\begin{array}{rl}\Delta H& =q{h}_1+(1-q)h_2+\omega (q)+\omega (1-q)-pq{h}_1\\ & -(1-pq)\left[\frac{q-pq}{1-pq}{h}_1+\frac{1-q}{1-pq}{h}_2+\omega \left(\frac{q-pq}{1-pq}\right)+\omega \left(\frac{1-q}{1-pq}\right)\right]\\ & =\omega (q)+\omega (1-q)-(1-pq)\left[\omega \left(\frac{q-pq}{1-pq}\right)+\omega \left(\frac{1-q}{1-pq}\right)\right]\end{array}$$
This is also in line with our intuitive feelings —— Internal elements are not distinguished , Therefore, the internal entropy does not interfere with the amount of information .

Use online math tools （ In the examination room, it is suggested to type the table and take the best value ） We know the best
$$q=\frac{5\left(5\sqrt{4000+3381\sqrt{5}}-100\sqrt{5}-64\right)}{2869}$$
It's about equal to
$$q\approx 0.4356636377796835808889$$
take $q=0.435$ Calculation , expect $\Delta H\approx 0.618$ . What a beautiful number . So I hope to pass $\frac{64}{\Delta H}\approx 103.56$ After times of inquiry, it can be solved .

Code

• Because it is the expected number of inquiries , Cannot exhaust $107$ Just ask once , But the solution is $\mathtt{r}\mathtt{e}\mathtt{t}\mathtt{u}\mathtt{r}\mathtt{n}$ .
• As many as $2^{64}$ individual , The real answer in the process $\mathrm{Pr}$ It may be very low , Please don't give it up ！
• The time complexity is not easy to calculate . But what you can think of is ： The number of intervals is relatively small , about $64$ individual .

#include "guess.h"
#include <cstdio>
#include <algorithm> // Almighty XJX yyds!!!
#include <cstring> // oracle: ZXY yydBUS!!!
#include <cctype> // Huge Egg Dog eats me!!!
#include <vector>
#include <utility>
#include <cmath>
using llong = long long;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
inline int readint(){
    
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar()) if(c == '-') f = -f;
	for(; isdigit(c); c=getchar()) a = a*10+(c^48);
	return a*f;
}

using ullong = unsigned long long;
using PUU = std::pair<ullong,ullong>;
extern bool Query(std::vector<PUU> v);
bool query(std::vector<PUU> v){
    
	for(PUU &rg : v) -- rg.second;
	return Query(v); // close range
}

using ldb = long double;
using NODE = std::pair<PUU,ldb>;
bool cmp(const NODE &a, const NODE &b){
    
	return a.second/(a.first.second-a.first.first)
		> b.second/(b.first.second-b.first.first);
}
ullong Guess(){
    
	static const ullong MAXX = 18446744073709551606ull;
	std::vector<NODE> v; v.resize(1);
	v[0] = NODE{
    PUU{
    10,MAXX},1};
	const long double q = 0.435, p = 0.8, notp = 0.2;
	while(true){
    
		if(v[0].first.second == v[0].first.first+1
		  && int(v.size()) == 1) return v[0].first.first;
		std::vector<PUU> ask; ask.clear();
		long double nowq = 0;
		for(const NODE &rg : v){
    
			if(nowq >= q) break; // enough
			if(nowq+rg.second <= q){
    
				nowq += rg.second; // good
				ask.push_back(rg.first); continue;
			}
			ullong len = rg.first.second-rg.first.first;
			ullong cnt = ullong(floor((q-nowq)*len/rg.second));
			if(nowq == 0 && cnt == 0) cnt = 1;
			if(!cnt) continue; // length = 0
			nowq += cnt*rg.second/len; ask.push_back(
				PUU{
    rg.first.first,rg.first.first+cnt});
		}
		if(query(ask)){
    
			const int lenask = int(ask.size());
			for(int i=0,j=0,k=0; true; ++i){
    
				if(j == lenask){
     v.resize(k); break; }
				if(ask[j] == v[i].first) // covered
					v[k] = v[i], v[k++].second /= nowq, ++ j;
				else if(ask[j].first == v[i].first.first){
    
					ullong nxt = ask[j].second-ask[j].first;
					ullong now = v[i].first.second-v[i].first.first;
					v[k++] = NODE{
    ask[j++],v[i].second/nowq*nxt/now};
				}
			}
		}
		else{
    
			long double wxk = 1-p*nowq;
			const int lenask = int(ask.size()), lenv = int(v.size());
			for(int i=0,j=0; i!=lenv; ++i){
    
				v[i].second /= wxk;
				if(j == lenask) continue;
				if(ask[j] == v[i].first)
					v[i].second *= notp, ++ j;
				else if(ask[j].first == v[i].first.first){
    
					ullong nxt = ask[j].second-ask[j].first;
					ullong now = v[i].first.second-v[i].first.first;
					v.push_back(NODE{
    ask[j],v[i].second*notp*nxt/now});
					v[i].first.first = ask[j++].second; // outside
					v[i].second = v[i].second*(now-nxt)/now;
				}
			}
		}
		if(true){
     // will this be slow?
			std::sort(v.begin(),v.end(),cmp);
			long double tot = 0;
			for(const NODE &rg : v) tot += rg.second;
			for(NODE &rg : v) rg.second /= tot;
		}
	}
}