Zdravím, dostal jsem na přijímačky na FIT ČVUT pár úloh. Jednu z nich
ale nedokážu vymyslet.
V úloze jde vlastně o toto: Máme n-dimenzionální prostor a v něm dva
body, které mají pomyslné senzory mířící do všech stran os. Chceme
zjistit počet možností, kdy se dva body navzájem vidí (ohrožují), čili
jinak řečeno jsou na stejné ose.
Formálně zapsáno:
Nechť A na souřadnicích (a1, a2, ..., an) a B na souřadnicích (b1, b2, ...,
bn)
jsou dva body v n-dimenzionálním prostoru a existuje i ∈ 1, 2, ..., n
takové, že ai = bi,
potom se hlídatka A a B vzájemně ohrožují.
Nyní budeme pracovat se dvěma body. Zjisti kolik existuje všech možných
pozic dvou
bodů, ve kterých se body ohrožují.
Toto n-dimenzionální pole může být velké až 107. Zatím
jsem neřešil, že případně tak velký výsledke bz ani nešel v C# zapsat,
ale jako první potřebuju vymyslet algoritmus, který mi počet všech
kombinací vyplivne.
Příklad: Vstup
Každý vstup zabírá dva řádky. Jeden řádek obsahuje číslo N (1 ≤ N
≤ 107) znázorňující
dimenzi omezeného prostoru. Druhý řádek obsahuje N čísel d1, d2, ..., dn
reprezentujících
rozměry omezeného prostoru di (1 ≤ di ≤ 106). Výstup
Na samostatném řádku vypiš číslo udávající počet všech rozmístění
dvou hlídátek, při kterých
se vzájemně ohrožují.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.
