Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | inno.in, inno.out | Sursă | OSEPI 2021 baraj gimnaziu |
|---|---|---|---|
| Autor | Dan Pracsiu | Adăugată de |
Mircea Rebengiuc
•
mircea_007
|
| Timp de execuție pe test | 0.3 sec | Limită de memorie | 65536 KB |
| Scorul tău | N/A | Dificultate |
  2.75
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Inno (baraj gimnaziu)
Se dau numerele naturale N și K, precum și un șir a1, a2, . . . , aN de numere naturale nenule. Din șir se poate elimina o singură secvență (eventual vidă) ai, ai + 1, ..., aj astfel că în șir rămân elementele a1, a2, . . . , ai − 1, aj + 1, . . . , aN. De exemplu, din șirul a = [1, 2, 3, 4, 5, 7] se poate elimina secvența 3, 4, 5 și rămâne 1, 2, 7; sau se poate elimina secvența vidă și rămâne șirul inițial 1, 2, 3, 4, 5, 7; sau se poate elimina 1, 2, 3, 4 și rămâne șirul 5, 7. După eliminarea secvenței, elementele rămase formează un șir inno dacă aplicându-se operația & pe biți asupra lor, rezultatul este un număr care are cel puțin K biți de 1 în baza 2. De exemplu, dacă a = (1, 2, 3, 4, 5, 7) și K = 2, atunci prin eliminarea secvenței 1, 2, 3, 4 rămân elementele 5, 7, iar 5&7 = 5, care are 2 biți de 1 în baza 2. Dar dacă se elimină secvența 3, 4, 5 atunci rămân elementele 1, 2, 7, iar 1&2&7 = 0, deci nu este șir inno.
Cerință
Să se determine în câte moduri se poate elimina o secvență astfel încât elementele rămase să formeze șir inno.
Date de intrare
Fișierul de intrare inno.in conține pe prima linie numerele naturale N și K. Pe linia a doua se află N numere naturale reprezentând elementele șirului, separate prin câte un spațiu.
Date de ieșire
Fișierul de ieșire inno.out va conține pe prima linie un singur număr natural reprezentând numărul de moduri de a elimina o secvență astfel încât șirul rămas să fie inno.
Restricții și precizări
- 3 ≤ N ≤ 200 000
- 1 ≤ K ≤ 29
- 0 ≤ ai ≤ 231 − 1
- & este operatorul de conjuncție pe biți. Dacă x și y sunt valori binare, atunci expresia x & y este egală cu 1 dacă și numai dacă x = 1 și y = 1. Deci 1&1 = 1, 0&1 = 0, 1&0 = 0, 0&0 = 0. Dacă a și b sunt numere naturale, atunci expresia a&b se efectuează la nivelul reprezentării în baza 2. De exemplu, dacă a = 12 și b = 20, atunci: a&b = 12&20 = 01100(2) & 10100(2) = 00100(2) = 4(10)$
- Pentru teste în valoare de 12 puncte: 1 ≤ K ≤ 2 și 3 ≤ N ≤ 25
- Pentru alte teste în valoare de 23 de puncte: 500 ≤ N ≤ 8 000
- Pentru alte teste în valoare de 65 de puncte: Nu există restricții suplimentare.
Exemplu
| inno.in | inno.out |
|---|---|
| 4 2 10 7 5 15 |
5 |
| 5 4 7 7 6 1 62 |
1 |
Explicație
Pentru primul exemplu modalitățile sunt:
- se elimină 10 și rămâne șirul 7, 5, 15, iar 7&5&15 = 5, care are 2 biți de 1
- se elimină 10, 7 și rămâne șirul 5, 15, iar 5&15 = 5, care are 2 biți de 1
- se elimină 10, 7, 5 și rămâne șirul 15, iar 15 are 4 biți de 1
- se elimină 7, 5 și rămâne șirul 10, 15, iar 10&15 = 10 are 2 biți de 1
- se elimină 7, 5, 15 și rămâne șirul 10, iar 10 are 2 biți de 1
Pentru cel de-al doilea exemplu singura posibilitate este eliminarea secvenței 7 7 6 1. Rămâne doar numărul 62, care are 5 biți de 1.
