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

 

Problem I/S. 17. (April 2017)

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

(10 pont)

Deadline expired on 10 May 2017.


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

A feladat megoldásához egy könnyen implementálható modellt kell találnunk a kocka tárolására, illetve a gördítés műveletek megvalósítására.

Sok jó választás lehet, a minta megoldás két 4-elemű tömböt használ; az egyik a felső-bal-alsó-jobb, a másik pedig a felső-első-alsó-hátsó oldalakat tárolja. Ekkor a gördítés az egyik tömb ciklikus forgatását (vagyis az 1-5-6-2 tömb 2-1-5-6 lesz a forgatás után), illetve a másik tömb 0. és 2. elemeinek frissítését foglalja magában.

Ezzel megoldható volt a részfeladat:

5 pontos minta megoldás (c++)

A teljes megoldáshoz azt kellett még észrevenni, hogy a kockának csak 24 (vagyis véges számú) pozíciója van, ezért egy idő után amikor egy sor elején jobbra indulunk, ugyanazokon a pozíciókon fogunk végigmenni, mint az indulásnál. Ez azt is jelenti, hogy ha egy \(\displaystyle x\) sor hosszú minta ismétlődik, ahol minden iterációval az összeg \(\displaystyle y\)-nal nő, akkor az első \(\displaystyle S - (S \mod x)\) sorban összesen \(\displaystyle S \div x\) alkalommal adunk \(\displaystyle y\)-t az összeghez, vagyis a teljes összeg \(\displaystyle (S \div x) \cdot y + M\) lesz, ahol \(\displaystyle M\) az utolsó \(\displaystyle S \mod x\) sorban elért összeg. Mivel 24 féle pozíciót vehet fel a kocka, ezért ez konstans számú sort jelent, így ez a megoldás a sorok számában konstans \(\displaystyle O(O)\).

Teljes minta megoldás (c++)

Megjegyzés: amennyiben az összeget tudjuk tárolni, a minta egy-egy soron belül is ismétlődik, így a feladat \(\displaystyle O(1)\) időben is megoldható, bár ez nem volt szükséges a 10 pont megszerzéséhez.


Statistics:

12 students sent a solution.
10 points:Busa 423 Máté, Gáspár Attila, Janzer Orsolya Lili, Kiss Gergely, Molnár Bálint, Nagy Nándor, Németh 123 Balázs, Noszály Áron, Szakály Marcell.
7 points:1 student.
6 points:1 student.
5 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