TlačiťStránka sa načítava, prosím čakajte…
© 2005 – 2024 Roman Horváth, všetky práva vyhradené. Dnes je 28. 4. 2024.
Dátum: 29. 8. 2021, pred tromi rokmi
Toto je úloha z 30. ročníka krajského kola Olympiády v informatike (2014/2015) kategórie B. Text je jemne upravený. Úloha bola pôvodne riešená na hodinách tohto predmetu v zimnom semestri v akademickom roku 2017/2018. Ide o úlohy spojené s úvahami o počítačovej simulácii zaoberajúcej sa padaním zrniek piesku. Úloha na olympiáde nevyžadovala implementovanie, ale my sme ho na hodinách vykonali, aby sme prakticky videli výsledok takejto simulácie.
Každé zrnko piesku má mať určitú veľmi malú veľkosť, predpokladajme, že jeden pixel (bod obrazovky; neskôr to môžeme prispôsobiť, aby sme zlepšili viditeľnosť simulácie). Simulácia prebieha v taktoch. V každom takte najskôr všetky zrnká piesku vyhodnotia, kam sa majú pohnúť a podľa toho sa pohnú. Zrnko sa pred vykonaním pohybu rozhoduje takto: Najskôr sa pozrie pod seba. Ak je pixel pod ním prázdny, spadne tam. Ak nie je, pozrie sa šikmo doľava dole, či nemôže spadnúť tam (ak áno, spadne tam). Ak nemôže spadnúť ani tam, tak sa pozrie doprava dole (ak je tam voľno, spadne tam). Ak aj toto zlyhá, tak zrnko zostáva tam kde je.
Na nasledujúcich obrázkoch je jeden príklad cyklu simulácie. Vľavo je situácia obsahujúca viacero zrniek piesku. V strede je rozkreslené, ktoré zrnká sa chcú kam pohnúť. Vpravo je nakreslená situácia o takt neskôr – teda po tom, ako sa uskutočnili pohyby zrniek piesku znázornené v strede.
V ďalšom takte by potom jediné zrnko, ktoré je ešte vo vzduchu (v siedmom stĺpci) spadlo o políčko nižšie, čím by vzniklo stabilné rozloženie.
Podúloha A (3 body)
Vo vzduchu sa z ničoho nič zjavil blok tvorený 3 × 5 zrnkami piesku. Celá situácia je znázornená na nasledujúcom obrázku. Tento piesok teraz začne padať podľa vyššie opísaných pravidiel. Vašou úlohou je simulovať prvé dva takty a nakresliť situáciu po každom z nich.
Podúloha B (3 body)
Vyššie uvedené pravidlá simulácie nie sú dokonalé, pretože sa občas môžu dve zrnká piesku zraziť. Preto treba pridať nasledujúce dve pravidlá:
- Ak sa chce v nejakom takte viacero zrniek piesku pohnúť na to isté voľné miesto, tak má prednosť to zrnko, ktoré by padalo priamo dole. Ostatné zrnká, ktoré chceli ísť na toto miesto sa v tomto takte nebudú hýbať vôbec.
- Ak aj po použití prvého pravidla stále jestvujú situácie, v ktorých by chcelo ísť viacero zrniek na to isté miesto, tak sa pohne to z nich, ktoré je momentálne najviac vľavo.
Vašou úlohou je ukázať, že druhé pravidlo naozaj potrebujeme. Nájdite také rozmiestnenie zrniek piesku, pri ktorom je potrebné použiť druhé pravidlo na to, aby sme zistili, kam sa ktoré zrnko pohne v najbližšom takte.
Podúloha C (4 body)
Poďme sypať piesok zhora na dosku. Doska je naklonená. Na obrázku vľavo je situácia po 0 taktoch: je tam jediné zrnko piesku, ktoré sa nachádza vo vzduchu nad doskou. Na tomto mieste sa po každých piatich taktoch zjaví nové zrnko piesku. Obrázok v strede predstavuje situáciu po 11 taktoch. Obrázok vpravo predstavuje situáciu po 30 taktoch od začiatku.
Nakreslite, ako bude celá situácia vyzerať po 136 taktoch od začiatku.
Pravidlá z podúlohy B používať netreba, žiadne dve zrnká piesku sa počas tejto simulácie nezrazia. Potrebujeme však pridať jedno nové pravidlo: Zrnká piesku nemôžu opustiť obrazovku (ako keby bola všade okolo obrazovky stena).
Riešenia
Riešenia všetkých troch podúloh uvedieme postupne v rovnakom poradí, ako boli uvedené v zadaní.
Podúloha A (3 body)
V tejto podúlohe stačí dôsledne aplikovať pravidlá pohybu zrniek. Na rozloženie zo zadania sa zrnká chcú pohnúť takto:
Po prvom takte dostaneme nasledujúce rozloženie:
Z neho po druhom takte vznikne táto nesymetrická hrôza:
(Vyšla vám symetrická? Asi ste prehliadli, že zrnko piesku, ktoré bolo po prvom takte v stĺpci najviac vpravo najvyššie, nespadne v druhom takte doprava nadol, ale doľava nadol.)
Pre zaujímavosť, hoci piesok robí počas pádu takéto „roztodivné“ veci, o ďalšie tri takty sa dostane do stabilnej konfigurácie a tá bude opäť krásne symetrická.
Podúloha B (3 body)
Druhé pravidlo treba použiť vtedy, keď na to isté miesto chcú ísť práve dve zrnká – jedno šikmo zľava zhora a druhé šikmo sprava zhora. Volajme ich ľavé a pravé zrnko.
Pravé zrnko vyrobíme ľahko – stačí postaviť dve zrnká na seba, to horné bude chcieť spadnúť doľava dole. Ľavé zrnko vyrobíme takmer rovnako, budeme však potrebovať až tri zrnká: samotné ľavé zrnko, zrnko pod ním (aby nemohlo spadnúť priamo dole) a zrnko vľavo dole od neho (aby nemohlo spadnúť ani šikmo doľava dole). Výsledné rozloženie piesku teda vyzerá takto:
Je zároveň jasné, že menej zrniek piesku nestačí: musíme mať aspoň dve, ktoré naozaj chcú spadnúť na to isté políčko, a pod nimi aspoň tri ďalšie, aby tie dve spadali tými správnymi smermi.
Podúloha C (4 body)
Keby sme piesok sypali na rovnú dosku, tak by postupne začal vyrábať „pyramídu.“ Ľahko sa presvedčíme, že presne rovnako to bude aj v tomto prípade: pri pohľade zhora bude kopa piesku pyramídového tvaru. Len jej podstava nebude vodorovná, preto bude ľavá hrana pyramídy dlhšia od pravej.
Na ľavom obrázku nižšie sú znázornené záverečné polohy prvých desiatich zrniek.
Všimnite si, že každá nová „vrstva“ pyramídy vzniká tak, že najskôr niekoľko zrniek odíde doľava, potom toľko isto odíde doprava a na záver zostane nasledujúce zrnko sedieť presne v strede, čím vytvorí nový hrot pyramídy. Najbližších päť zrniek (čísla 11 až 15) teda pôjde doľava, ďalšie dve (16 a 17) doprava a potom zrnko číslo 18 utvorí nový hrot pyramídy vyššej o jeden riadok („poschodie“).
Pozorovanie, ktoré sme práve urobili, môžeme využiť na to, aby sme bez simulácie priamo zostrojili stav po 136 taktoch. Prvá vec, ktorú ľahko odhadneme je, že máme presne 28 zrniek: zrnko číslo 28 sa zjavilo po 135 taktoch. Toto posledné zrnko teda stihlo spadnúť len o jedno políčko nižšie (je ešte vo vzduchu). Poloha zrnka číslo 27 je zatiaľ neznáma, ale zrnko číslo 26 už bolo na svete 11 taktov, preto už určite leží na svojom záverečnom mieste. Aby sme zistili, kde sa nachádza zrnko 27 potrebujeme zistiť, ako vyzerá pyramída tvorená prvými 26 zrnkami.
Zatiaľ vieme, že po zrnku 18 sme mali peknú kompletnú pyramídu. Zrnká 19 až 23 potom po náraze na jej vrchol pôjdu doľava (pričom zrnko 19 sa zastaví o okraj obrazovky), zrnká 24 a 25 pôjdu doprava a zrnko 26 bude novým hrotom pyramídy vyššej o jedno poschodie.
Teraz už ľahko nájdeme aktuálnu polohu zrnka 27 a tým sme hotoví. Výsledná konfigurácia je na obrázku vpravo:
Nasledujúce riešenie je upravené tak, aby pracovalo na omnoho väčšej ploche s náhodne vygenerovanými prekážkami a zrnkami piesku.
Ukážka simulácie po spustení.
~
import knižnica.GRobot;
import static java.lang.Math.*;
import static knižnica.Svet.*;
public class PiesokLial extends GRobot
{
// Pole slúžiace na prepočítavanie zrniek piesku:
private char[][][] a = new char[][][] {
// Pole má dve vrstvy, ktoré neustále vymieňajú svoju funkciu.
// Jedna obsahuje aktuálny stav a do druhej sa prepočítava nový
// stav. To sa cyklicky opakuje (donekonečna).
{{' ', 'O', ' ', 'O', 'O', ' ', 'O', 'O'},
{' ', ' ', 'O', 'O', 'O', ' ', ' ', ' '},
{' ', ' ', ' ', ' ', ' ', 'X', ' ', ' '},
{' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
{'#', '#', '#', '#', '#', '#', '#', '#'}},
{{' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
{' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
{' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
{' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
{' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}}
};
// Veľkosť (grafická) jedného „pixela“ – bunky:
private final static double v = 3.0;
// Veľkosť grafiky (zrnka alebo iného obsahu) v rámci buniek:
private final static double o = 2.5;
// Indexy vrstiev:
// i – aktuálny stav (ktorý sa zároveň kreslí);
// j – budúci stav (do vrstvy s týmto indexom sa prepočíta
// najbližší nový stav):
private int i = 0, j = 1; // (Povolené sú len hodnoty 0 a 1.)
// Konštruktor:
private PiesokLial()
{
super(650, 650); // (Rozmer plátna.)
skry();
// Pôvodné pole prepíšeme omnoho väčším:
a = new char[2][100][100];
generuj();
prekresliť();
aktivuj(false); // (Prepočítavanie sa bude diať v aktivite.)
}
// Vygenerovanie nového náhodného rozloženia.
private void generuj()
{
for (int k = 0; k < a[i].length; ++k)
for (int l = 0; l < a[i][k].length; ++l)
{
double d = náhodnéReálneČíslo();
if (d < 0.20) a[i][k][l] = '#';
else if (d < 0.40) a[i][k][l] = 'O';
else a[i][k][l] = ' ';
}
}
// Prekreslenie grafiky.
private void prekresliť()
{
vymažGrafiku();
skoč((a[i].length - 1) * v);
for (char[] r : a[i])
{
preskočVľavo((r.length - 1) * v);
for (char s : r)
{
// Všetky bunky budú mať ako podklad šedý štvorček:
farba(svetlošedá);
štvorec(o);
// Znak 'O' znamená zrnko:
if ('O' == s)
{
farba(žltá);
kruh(o);
}
// Všetky ostatné neprázdne znaky sú prekážky:
else if (' ' != s)
{
farba(tmavozelená);
vyplňŠtvorec(o);
}
preskočVpravo(2 * v);
}
odskoč(2 * v);
preskočVľavo((r.length + 1) * v);
}
skoč((a[i].length + 1) * v);
prekresli();
}
// (Reakcia klávesnice.)
@Override public void stlačenieKlávesu()
{
// (Medzerník pregeneruje scénu.)
if (knižnica.ÚdajeUdalostí.kláves(knižnica.Kláves.MEDZERA)) generuj();
}
// (Reakcia aktivity.)
@Override public void aktivita()
{
// Vyčistenie prepočítavacej vrstvy:
for (int k = 0; k < a[j].length; ++k)
for (int l = 0; l < a[j][k].length; ++l)
a[j][k][l] = ' ';
// Prepočítavanie podľa pravidiel:
for (int k = 0; k < a[i].length; ++k)
for (int l = 0; l < a[i][k].length; ++l)
try
{
switch (a[i][k][l])
{
case ' ': break; // (Prázdne bunky sú preskočené.)
case 'O':
// Každé zrnko sa posúva okamžite, ak je cieľová
// bunka prázdna. Kontrolujeme zároveň starý aj
// nový stav. Postupne prepočítavame a obsadzujeme
// bunky zrnkami zľava zhora. Tým, že prepočet
// vykonávame do novej vrstvy, zároveň zabraňujeme
// kolíziám. (Ale zjednodušili sme si to. Nie je
// to celkom v súlade s dvomi dodatočnými
// pravidlami v zadaní. Nezabezpečujeme to, že
// prednosť majú zrnká, ktoré padajú priamo dole.
// Na to by sme museli algoritmus „rozštiepiť“ do
// dvoch samostatných cyklov alebo pridať novú
// komplikovanú podmienku, ktorá by to
// zabezpečila.)
// Najskôr overíme, či toto nie je najspodnejšia
// vrstva:
if (k < a[i].length - 1)
{
// Pre každý smer padania sú zároveň
// kontrolované podmienky pravej a ľavej
// hranice, čím dodržíme podmienku, aby zrnká
// nevypadávali mimo hraníc plochy simulácie.
// Priame (zvislé) padanie:
if (l < a[i][k].length &&
' ' == a[i][k + 1][l] &&
' ' == a[j][k + 1][l])
a[j][k + 1][l] = 'O';
// Padanie dole a doľava:
else if (l < a[i][k].length && l > 0 &&
' ' == a[i][k + 1][l - 1] &&
' ' == a[j][k + 1][l - 1])
a[j][k + 1][l - 1] = 'O';
// Padanie dole a doprava (toto zrnko má
// šancu sa „predbehnúť“ pred nasledujúcim
// dole padajúcim zrnkom, ktoré by malo mať
// prednosť):
else if (l < a[i][k].length - 1 &&
' ' == a[i][k + 1][l + 1] &&
' ' == a[j][k + 1][l + 1])
a[j][k + 1][l + 1] = 'O';
// Uchovanie zrnka, ktoré sa nepohlo (nová
// vrstva je prázdna, takže musíme skopírovať
// aj nepohyblivé zrnká):
else
a[j][k][l] = 'O';
}
else
// (Uchovanie zrniek ležiacich „na zemi.“)
a[j][k][l] = 'O';
break;
// (Prekážky sú skopírované.)
default: a[j][k][l] = a[i][k][l]; break;
}
}
catch (Exception e)
{
// (Toto by nastalo len ak by bolo pole zle
// inicializované.)
vypíšRiadok("Chyba na pozícii [", l, ", ", k, "].");
}
// Vymeníme indexy vrstiev:
int k = i; i = j; j = k;
prekresliť();
}
// (Hlavná metóda.)
public static void main(String[] args)
{
použiKonfiguráciu("PiesokLial.cfg");
nekresli();
new PiesokLial();
spustiČasovač(0.050);
}
}
Keby sme chceli vidieť spomalenú zväčšenú simuláciu pôvodného (preddefinovaného) rozloženia piesku (negenerovaného náhodne), upravili by sme kód takto:
- Zmenili (zväčšili) by sme hodnoty konštánt
vao(napríklad na 20 a 19,5). - Dali by sme do komentára dva riadky nasledujúce za komentárom „Pôvodné pole prepíšeme omnoho väčším“ v konštruktore (a nestláčali by sme medzerník po spustení simulácie).
- Zvýšili by sme interval časovača v hlavnej metóde (napríklad na 0,5 s).
Takto by vyzeral počiatočný a koncový stav tejto simulácie:
 |
 |
Keby sme si to chceli spestriť, mohli by sme zabezpečiť odlišné kreslenie viacerých rôznych prekážok v metóde prekresliť. Všimnite si, že v poli sú vložené dva druhy prekážok: 'X' a '#'. Stačilo by zmeniť napríklad farbu iného druhu prekážky:
Fragmenty upraveného kódu:
~
…
// Veľkosť (grafická) jedného „pixela“ – bunky:
private final static double v = 20.0;
// Veľkosť grafiky (zrnka alebo iného obsahu) v rámci buniek:
private final static double o = 19.5;
…
// Pôvodné pole prepíšeme omnoho väčším:
// a = new char[2][100][100];
// generuj();
…
// Znak 'O' znamená zrnko:
if ('O' == s)
{
farba(žltá);
kruh(o);
}
// Znak 'X' znamená modrú prekážku:
else if ('X' == s)
{
farba(svetlomodrá);
vyplňŠtvorec(o);
}
// Všetky ostatné neprázdne znaky sú štandardné prekážky:
else if (' ' != s)
{
farba(tmavozelená);
vyplňŠtvorec(o);
}
…
spustiČasovač(0.5);
…