Detta är en interaktiv uppgift.
Kvällen före dessertfestivalens öppnande arbetar chefskocken omsorgsfullt med konditoriets berömda signaturdessert, ”千层幻彩慕斯”. Denna dessert består av $n$ bitar mousse med olika smaker, numrerade $0,1,\dots,n-1$.
Men i all brådska har assistenten råkat blanda ihop ordningen på moussebitarna. Nu står de på en rad från vänster till höger och bildar en okänd permutation av placeringarna $p=(p_0,p_1,\dots,p_{n-1})$, där $p_i$ är numret på moussebiten på position $i$.
För att ta reda på varje moussebits exakta position kan du använda en desserttestare. Varje gång du väljer tre sinsemellan olika positioner $x,y,z$ ger testaren summan av det minsta och det största numret bland dessa tre moussebitar:
$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$
Snart ljuder klockan som markerar öppnandet. Kan du med ett begränsat antal tester återskapa varje moussebits verkliga position exakt?
Det finns en permutation $p$ av längd $n$, vars element är exakt $0,1,\ldots,n-1$. Du känner inte till innehållet i $p$.
Du kan välja tre sinsemellan olika index $x,y,z$, och det interaktiva biblioteket returnerar
$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$
Din uppgift är att återskapa hela permutationen. Gränsen för antalet frågor och hur poängen beräknas utifrån antalet frågor beskrivs nedan.
Implementationsdetaljer
Du behöver inte, och ska inte, implementera funktionen main. Den inlämnade källkodsfilen ska innehålla:
#include "mousse.h"Du ska implementera följande två funktioner:
void init(int c);
std::vector<int> mousse(int c, int n);- $c$ är deluppgiftens nummer; $c=0$ betecknar exemplet. Varje testfall innehåller exakt en instans. Det interaktiva biblioteket anropar
init(c)en gång för testfallet och sedanmousse(c,n)en gång. mousseska returnera en array av längd $n$, där elementet med index $i$ är $p_i$ och indexeringen börjar med $0$.
Du kan anropa följande funktion för att ställa en fråga:
int query(int x, int y, int z);Det måste gälla att $0\le x,y,z < n$, och $x,y,z$ måste vara parvis olika. Funktionen returnerar $\min(p_x,p_y,p_z)+\max(p_x,p_y,p_z)$.
Testning av programmet
Bilagorna innehåller mousse.h, det lokala interaktiva biblioteket grader.cpp och exempelprogrammet template_mousse.cpp. Spara ditt eget program som mousse.cpp och kör följande i uppgiftens katalog:
g++ grader.cpp mousse.cpp -o mousse -O2 -std=c++14
./mousse < mousse1.inDet lokala interaktiva biblioteket läser den dolda permutationen från standardindata. Ditt program får inte läsa dessa data på egen hand. Indataformatet är följande:
- Den första raden innehåller två heltal $c,n$.
- Den andra raden innehåller $p_0,p_1,\ldots,p_{n-1}$.
Om svaret är korrekt skriver det interaktiva biblioteket ut Correct! och Max queries used: Q, där $Q$ är antalet frågor i testfallet. Om svaret är felaktigt skriver det ut Wrong answer.. Om en ogiltig fråga ställs eller gränsen för antalet frågor överskrids skriver programmet ett felmeddelande till standardfelströmmen och avslutas. Du kan lägga till argumentet -v för att se antalet frågor i testfallet.
Exempel
Indata 1
0 10
0 2 9 1 5 8 3 7 6 4Utdata 1
Correct!
Max queries used: 15Förklaring
Om till exempel query(0,1,2) anropas är de tre motsvarande värdena $0,2,9$, och returvärdet är $0+9=9$. Referensprogrammet använder $15$ frågor för dessa data. Om du använder en annan strategi kan antalet vara annorlunda.
Begränsningar
För alla testdata gäller $n\in\{10,100,10^5\}$, och $p$ är en permutation av $0\sim n-1$. Varje testfall innehåller exakt en instans.
| Deluppgiftens nummer | Poäng | $n =$ | $Q_{\max} = $ | Särskilda egenskaper |
|---|---|---|---|---|
| $1$ | $5$ | $10$ | $1000$ | Inga |
| $2$ | $5$ | $100$ | $10000$ | Inga |
| $3$ | $30$ | $10^5$ | $2\times10^6$ | $p_0=0$ |
| $4$ | $60$ | $10^5$ | $2\times10^6$ | Inga |
För exemplet gäller $c=0$ och $n=10$, och gränsen för antalet frågor är $1000$.
Poängsättning
Observera:
- Det interaktiva biblioteket är inte adaptivt. Permutationen i varje testfall bestäms innan ditt program anropas och ändras inte beroende på frågorna.
- Du får inte ta reda på den dolda permutationen genom att läsa standardindata eller på något annat otillåtet sätt. Det interaktiva bibliotek som används vid den slutliga bedömningen kan ha en annan implementation än det lokala interaktiva biblioteket.
Om mousse returnerar ett felaktigt svar i ett testfall, parametrarna till query är ogiltiga eller antalet frågor överskrider deluppgiftens $Q_{\max}$, blir poängmultiplikatorn för detta testfall $0$.
I deluppgifterna $1,2$ måste alla testfall lösas korrekt för att du ska få deluppgiftens fulla poäng.
För deluppgifterna $3,4$ gäller att om något testfall har poängmultiplikatorn $0$, får hela deluppgiften $0$ poäng. Annars låter vi $Q$ vara det största antalet frågor bland alla testfall i deluppgiften. Poängmultiplikatorn $f(Q)$ bestäms av följande tabell:
| Antal frågor $Q_i$ | Poängmultiplikator $f_i$ |
|---|---|
| $99970$ | $100\%$ |
| $99975$ | $98\%$ |
| $99981$ | $95\%$ |
| $99988$ | $90\%$ |
| $99996$ | $84\%$ |
| $100000$ | $80\%$ |
| $100010$ | $74\%$ |
| $100026$ | $66\%$ |
| $100051$ | $58\%$ |
| $100093$ | $52\%$ |
| $150000$ | $32\%$ |
| $200000$ | $20\%$ |
| $1660964$ | $8\%$ |
| $2000000$ | $5\%$ |
Om $Q\le 99970$, är $f(Q)=100\%$. Om $Q$ ligger mellan två intilliggande rader $(Q_i,f_i)$ och $(Q_{i+1},f_{i+1})$ i tabellen, gäller:
$$ f(Q)=f_i+\frac{Q-Q_i}{Q_{i+1}-Q_i}(f_{i+1}-f_i). $$
Poängen för deluppgift $3$ är $30f(Q)$, och poängen för deluppgift $4$ är $60f(Q)$. Den slutliga poängen avrundas till $3$ decimaler.
Tidsgräns: $10\ \mathrm{s}$.
Minnesgräns: $512\ \mathrm{MiB}$.