Az S. 162. feladat (2022. május)

S. 162. Jónásnak van egy \(\displaystyle N\) csúcsú teljes bináris fája. A fa gyökere az 1-es sorszámú csúcs. Ha az \(\displaystyle i\)-edik csúcs nem levél, akkor a két gyereke a \(\displaystyle 2i\) és \(\displaystyle 2i+1\) sorszámú csúcs. Minden csúcshoz hozzárendeltünk egy pozitív egész számot, ez a csúcs súlya. A súlyok között nincs két egyforma.

Jónás megpróbálta a fát maximum-kupaccá alakítani. Azt szeretné, hogy minden csúcs súlya nagyobb legyen, mint a két gyerekének a súlya. Ehhez a következő műveletet hajtotta végre \(\displaystyle Q\)-szor: kiválasztott egy csúcsot, majd megkereste, melyik a legnagyobb súly az összes alatta lévő csúcsban. Ezután a kiválasztott csúcs súlyát kicserélte a legnagyobb súllyal. Számítsuk ki, mennyire sikerült Jónás terve, azaz hány olyan szülő-gyerek pár van, amire teljesül a kupac feltétel.

Bemenet: az első sor tartalmazza a csúcsok \(\displaystyle N\) számát. A következő sorban a csúcsok súlya szerepel sorszám szerint növekvő sorrendben. A harmadik sorban a cserék \(\displaystyle Q\) száma szerepel. A negyedik sorban \(\displaystyle Q\) szám szerepel: a kiválasztott csúcsok sorszámai a kiválasztás sorrendjében.

Kimenet: a kimenet első és egyetlen sorába azon szülő-gyerek párok számát kell írni, melyben a szülő súlya nagyobb, mint a gyerek súlya.

Minta:

Magyarázat: a 3-as csúcs súlya 6, ezt a 7-essel cseréljük meg. A 2-es csúcs súlya 4, ezt a 9-essel cseréljük meg. Az 1-es csúcs súlya 1, ezt a 9-essel cseréljük. A csúcsok súlya ezután: 9, 1, 7, 4, 2, 3, 6.

Korlátok: \(\displaystyle 3 \le N = 2^k-1 < 10^5\). A csúcsok súlya legfeljebb \(\displaystyle 10^9\). Időlimit: 1 mp.

Értékelés: a pontok 50%-a kapható arra a programra, amely helyes kimenetet ad, ha \(\displaystyle N\cdot Q\le 10^6\).

Beküldendő egy s162.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2022. június 15-én LEJÁRT.

Statisztika:

3 dolgozat érkezett.
10 pontot kapott:	Tóth 057 Bálint, Veres Benedek Zoltán.
9 pontot kapott:	Sándor Péter.

A KöMaL 2022. májusi informatika feladatai