Green Byte Hackathon 2024 | Bozo Hash

ATENȚIE: Aceasta problemă valorează $150$ de puncte. La "submissions" scorul maxim este rescalat la $100$ de puncte, dar adevaratul scor va fi vizibil pe leaderboard.

Sistemul digital de gestionare a pesticidelor din Chert And se folosește foarte mult de următoarea funcție hash pentru gestionarea traficului datelor:

long long hashFunction(long long x) {
  long long Hash = x;
  Hash += (Hash << 10);
  Hash ^= (Hash >> 6);
  Hash += (Hash << 3);
  Hash ^= (Hash >> 11);
  Hash += (Hash << 15);

  return Hash & ((1ll << 42) - 1);
}

Functia este scrisa in c++ si se folosesc operatiile pe biti xor si shiftari de biti dreapta/stanga.

Găsiți cât mai multe valori $y$ (cu condiția $y \le 2 \ 000 \ 000$) care sunt hash-ul a mai mult de două valori $x$ din intervalul $1...36987 \cdot 10^7$. Formal, găsiți cât mai multe valori $y$ astfel încât mulțimea $\{x | hashFunction(x) = y, 0 \le y \le 2 \ 000 \ 000, 1 \le x \le 36987 \cdot 10^7\}$ are cardinalul cel puțin $2$.

Output

Aceasta problema este output only.

Pe prima linie, submisia voastră trebuie să conțină numărul $k$ de numere pe care le raportați.

Pe următoarea linie submisia voastră trebuie să conțină $k$ valori distince, care să respecte condiția din enunț.

Mai jos aveti un exemplu de submisie:

3
1590155 872696 560605

Punctaj

Definim: $\text{accuracy} = \frac{\text{reported}}{\text{total}}$, unde $reported$ este numărul de numere distincte raportate de voi, iar $total$ este numărul total de $y$ care respectă condiția.

Atunci, scorul pe care îl veți primi la problemă va fi: $accuracy \cdot 150$. În plus:

• $\text{p} \ge 0.2$, veți primi un batch de coordonate pentru META-TASK.
• $\text{p} \ge 0.5$, veți primi două batch-uri de coordonate pentru META-TASK.
• $\text{p} \ge 0.95$, veți primi trei batch-uri de coordonate pentru META-TASK.

ATENȚIE: Batch-urile se primesc sub formă de link la atașament în verdictul testului de evaluare.
ATENȚIE: Dacă raportați un $y$ care nu respectă condiția, punctajul vostru va fi nul.