Universal Cup Judging System

Universal Cup

时间限制: 1.0 s 内存限制: 512 MB 总分: 100
统计

Andrianalla oli kaunis $n$ kokonaisluvusta koostuva syklinen taulukko $a = (a_0, a_1, \dots, a_{n-1})$, missä $0 \le a_i < 2^b$ kaikilla $0 \le i < n$, mutta valitettavasti hän hukkasi sen! Meille tämä on kuitenkin melko onnekasta, sillä ilman tällaisia hajamielisiä päähenkilöitä maailmassa olisi paljon vähemmän rekonstruktiotehtäviä.

Sillä välin Andrianan ystävällä Bobilla on hyödyllistä tietoa: hän piti muistikirjaa, johon hän kirjasi Andrianan taulukon peräkkäisten osavälien bittikohtaisia AND-arvoja. Eräänä päivänä Bob oli melkoisen tylsistynyt, joten hän kirjoitti muistiin jokaiselle kohdalle $i$ ja jollekin kiinteälle pituudelle $k$ ($k \le n$) arvon $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (missä indeksit otetaan modulo $n$, koska taulukko on syklinen). Ei ole tiedossa, hankkiko Bob nämä AND-arvot laillisin keinoin.

Andriana haluaa tietää, mikä on suurin sellainen luvun $k$ arvo, että Bobin muistikirja sisältää tarpeeksi tietoa hänen rakkaan alkuperäisen taulukkonsa yksikäsitteiseen rekonstruoimiseen?

Syöte

Syötteen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $b$, missä $n$ on Andrianan kadonneen taulukon pituus ja $b$ on rajoituksen $0 \le a_i < 2^b$ määrittävä parametri. Toinen rivi sisältää $n$ kokonaislukua $a_i$ — syklisen taulukon alkiot.

Tuloste

Tulosta yksi kokonaisluku — suurin luvun $k$ arvo siten, että taulukko $a$ voidaan yksikäsitteisesti rekonstruoida osavälien AND-arvojen taulukosta $x$.

Rajoitukset

$3 \le n \le 2 \cdot 10^5$, $1 \le b \le 30$, $0 \le a_i < 2^b$.

Esimerkit

Syöte 1

6 3
7 3 7 7 3 7

Tuloste 1

2

Huomautus

Esimerkkitapauksessa $n = 6, b = 3$. Taulukon $a = [7, 3, 7, 7, 3, 7]$ binääriesitys on $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$, kun jokaiselle alkiolle käytetään kolmea bittiä.

Kun $k = 2$, taulukko $x$ olisi $[3, 3, 7, 3, 3, 7]$ (missä $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$). Taulukosta $x$ ja luvun $b$ arvosta voimme rekonstruoida taulukon $a$ yksikäsitteisesti.

Kun $k = 3$, taulukko $x$ olisi $[3, 3, 3, 3, 3, 3]$, mikä ei määritä taulukkoa $a$ yksikäsitteisesti (esimerkiksi $[3, 3, 7, 3, 7, 7]$ tuottaisi saman taulukon $x$).

Näin ollen tässä esimerkissä vastaus on $k = 2$.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.