Problem D
Svampar
Languages
en
sv
För att kunna driva din nya AI-startup behöver du kunna utföra parallella beräkningar på stor skala. En stark kandidat för detta visar sig vara svampar! För att beräkna saker har du ett kluster bestående av $N$ stycken svampar numrerade från $1$ till $N$. Du vill nu ladda in vikterna för ett neuralt nätverk i svamparna. Varje svamp förvarar ett tal, som till början är $0$.
För att ändra på svamparnas tal kan du utföra en runda. För att utföra en runda anger du en instruktion till varje svamp. Alla dessa instruktioner utförs sedan samtidigt. Låt $P[i]$ beteckna värdet på svamp $i$ innan rundan och $A[i]$ värdet på svamp $i$ efter rundan. De tillgängliga operationerna för svamp $i$ är då:
|
Instruktion |
Operation |
Beskrivning |
|
p |
$A[i] = P[i]$ |
behåll värdet från innan |
|
< j |
$A[i] = P[j]$ << $1$ |
där << betecknar bitvis vänsterskift |
|
> j |
$A[i] = P[j]$ >> $1$ |
där >> betecknar bitvis högerskift |
|
+ j |
$A[i] = P[j] + 1$ |
där + betecknar addition |
|
^ j |
$A[i] = P[i]$ ^ $P[j]$ |
där ^ betecknar bitvis XOR |
|
& j |
$A[i] = P[i]$ & $P[j]$ |
där & betecknar bitvis AND |
|
| j |
$A[i] = P[i]$ | $P[j]$ |
där | betecknar bitvis OR |
Se till att läsa beskrivningen av operationerna noggrant. Du kan hitta en definition av alla bitvisa operationer här 1. Svamparna kan förvara godtyckligt stora tal. Detta innebär att bitvis vänsterskift och addition alltid leder till att talet blir större.
Du får nu $N$ vikter $w_1, w_2, \dots , w_N$ och behöver hitta en sekvens rundor som får $A[i]=w_i$ för alla $i$.
Ju färre rundor du använder, desto mer poäng får du. I testdatan är $N$ alltid $512$.
Indata
Den första raden av indatan innehåller heltalet $N$ ($N=512$), antalet svampar. Anledningen att detta är en del av indatan är för att underlätta testning av din lösning på mindre $N$.
Den andra raden innehåller heltalen $w_1, w_2, \dots , w_N$ ($0 \leq w_i \leq 255$), vikterna i det neurala nätverket.
Utdata
Skriv först ut heltalet $r$, antalet rundor din lösning använder.
Skriv därefter ut $r$ rader, där varje rad beskriver en runda. För varje runda, skriv ut $N$ mellanslagsseparerade operationer. Den första operationen är den som svamp $1$ ska utföra, den andra som svamp $2$ ska utföra och så vidare. Varje operation ska skrivas ut på samma format som tabellen ovan, där $j$ ($1 \leq j \leq N$) är indexet på en svamp. Två exempel på hur enstaka giltiga operationer kan se ut är ”p” och ”< 10”.
Poängsättning
Din lösning kommer testas på ett antal testfall. Om den någonsin skriver ut en sekvens rundor som är ogiltig eller som inte producerar rätt vikter får du noll poäng.
Annars, låt $R_{max}$ beteckna det största antalet rundor du använder över alla testfall. Då får du poäng enligt följande styckvis linjär funktion.
![\includegraphics[width=0.7\textwidth ]{scoring-se.pdf}](/problems/svampar/file/statement/sv/img-0002.png)
Notera att x-axeln inte är linjär.
Om $R_{max} \leq 9$ så får du 100 poäng. Poängvärdet för $9 \leq R_{max} \leq 20$ anges även i nedanstående tabell.
|
$R_{\text{max}}$ |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
Poäng |
100 |
70 |
60 |
50 |
48 |
47 |
46 |
45 |
44 |
43 |
42 |
41 |
Exempeldomare
För att underlätta testning av ditt program tillhandahålls en exempeldomare vid attachments längst ner. Detta är inte samma domarkod som körs i Kattis. En beskrivning av hur man kör koden ges i kommentaren i början av koden.
Förklaring av exempelfall
Not: din inskickning kommer inte köras mot följande exempelfall eftersom $N \neq 512$. Det finns endast för att demonstrera in- och utdataformatet, all indata som din lösning testas på har $N = 512$.
Till en början har alla svampar talet $0$. Nedan beskrivs svamparnas tal innan och efter varje operation i exempel-utdatan applicerats.
|
0 0 0 0 |
|
0 1 0 1 |
|
0 1 2 2 |
| Exempel på indata 1 | Exempel på utdata 1 |
|---|---|
4 0 1 2 2 |
2 p + 2 p + 4 p p < 2 + 4 |
