KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem I/S. 16. (March 2017)

I/S. 16. Subscribers can reach the complete after signing in. The text will be public from 28 March 2017.

(10 pont)

Deadline expired on 10 April 2017.


Sorry, the solution is available only in Hungarian. Google translation

Ha \(\displaystyle K\) sort tudunk törölni a mátrix tetejéről úgy, hogy ne maradjon két egyforma oszlop, akkor \(\displaystyle K-1\) sor törlésével is teljesül ez a feltétel. Emiatt a tulajdonság miatt a maximális \(\displaystyle K\) bináris kereséssel található meg.

Hatékony eljárást kell találni, amivel megállapíthatjuk adott \(\displaystyle K\)-ra, hogy az első \(\displaystyle K\) sor elhagyásával ne maradjon két egyforma oszlop. Ha az oszlopokat alulról felfele \(\displaystyle STRING\)-ként kezeljük, akkor könnyen ábécé szerint növekvő sorba tudjuk őket rendezni. Így bármely két, egyformán kezdődő oszlop egymás mellé kerül, emiatt csak a szomszédos elemeket kell \(\displaystyle K\) hosszúságig ellenőrizni.

Az eljárás hatékonysága \(\displaystyle O(N*log(N))\), ahol \(\displaystyle N=max(R,~C)\).

Másik lehetőség az összehasonlításra valamilyen hash-elő eljárás, amivel két szöveg összehasonlítása egészek összehasonlítására vezethető vissza.

Mintamegoldás: main.cpp


Statistics:

12 students sent a solution.
10 points:Busa 423 Máté, Gáspár Attila, Janzer Orsolya Lili, Kiss Gergely, Nagy Nándor, Németh 123 Balázs, Noszály Áron, Stomfai Gergely, Szakály Marcell, Vári-Kakas Andor.
9 points:Molnár Bálint.
4 points:1 student.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley