ACM RTK - 2. skupina

Imamo n telefonskih številk, s₁, ..., s_n (vse so k-mestne in v njih nastopajo števke od 0 do 9), ki jih pogosto kličemo. Katerikoli dve od njih se razlikujeta v vsaj štirih istoležnih števkah. Pri klicanju se pogosto zmotimo v eni števki (in torej pokličemo napačno številko), nikoli pa v več kot eni. Zdaj smo dobili seznam številk, ki smo jih dejansko poklicali, recimo t₁, ..., t_m (tudi to so k-mestne številke, niso pa nujno vse različne), pri čemer je m precej večji od n. Originalnih s₁, ..., s_n nimamo več, vemo pa, da se vsaka od njih pojavi vsaj enkrat nespremenjena v zaporedju t₁, ..., t_m. Iz zaporedja t₁, ..., t_m torej ne moremo nujno ugotoviti, katere so originalne številke s₁, ..., s_n, lahko pa ugotovimo, katere skupine t-jev se nanašajo na isto originalno številko; opiši postopek, ki ugotovi velikost največje take skupine.

Primer: če imamo naslednje zaporedje 15 štirimestnih številk t₁, ..., t_m (torej je k = 4 in m = 15):

1234, 2234, 4322, 3234, 2121, 1334, 4352, 1214, 5545,
2123, 4312, 4512, 5445, 4445, 5444, 5145, 5345

se dá ugotoviti, da so bile originalne številke štiri (torej n = 4) in da se na posamezne originalne številke nanašajo naslednje klicane številke:

• 1234, 2234, 3234, 1334, 1214 so vse nastale iz iste originalne številke;
• 4322, 4352, 4312, 4512 so vse nastale iz iste originalne številke;
• 5445, 5545, 5145, 5345, 4445, 5444 so vse nastale iz iste originalne številke;
• 2121, 2123 sta obe nastali iz iste originalne številke.

Za prve tri od teh štirih skupin lahko celo ugotovimo, kakšne so bile originalne številke s_i: to so bile 1234, 4322 in 5445; pri četrti skupini pa ne moremo ugotoviti, ali je bila originalna številka 2121 ali 2123. Kakorkoli že, vidimo lahko, da ima največja od teh skupin šest številk, tako da bi moral tvoj postopek pri tem primeru kot rezultat vrniti število 6.

<PDF>