Zkouška 10. 6. 2019 [T. Holan]

Pokračování základního kursu programování pro studenty 1. ročníku bakalářského studia informatiky a učitelství informatiky. Výuka bezprostředně navazuje na předmět PRG030 Programování I výkladem dalších algoritmů a jejich programové realizace, postupů a technik užívaných při tvorbě programů. Posluchači se seznámi se základy objektového programování a práce v současných vývojových prostředích. Předpokládají se vstupní znalosti v rozsahu předmětu PRG030 Programování I.
Kwan
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 8. 6. 2019 09:25
Typ studia: Informatika Bc.

Zkouška 10. 6. 2019 [T. Holan]

Příspěvek od Kwan »

Zadání:
E-shop posílá zboží zákazníkům tak, že každý kus zboží zabalí do právě 1 krabice. Za tuto krabici se pak platí poštovné podle objemu krabice. Na vstupu dostaneme údaje o všech prodaných zboží za minulý rok a naším úkolem je navrhnout rozměry 2 druhů krabic tak, aby se v nich dalo posílat veškeré zboží a zároveň aby e-shop zaplatil co nejméně za poštovné.
Vstup:
D...počet druhů zboží
Pro každý druh zboží počet kusů, které se loni prodalo a trojice čísel xyz což jsou rozměry zboží.
Výstup:
(x1,y1,z1), N1
(x2,y2,z2), N2
kde xyz jsou rozměry krabice a N je číslo udávající kolik krabic tohoto druhu si má e-shop nechat vyrobit.
Upřesnění a omezení:
Rozměrem zboží se myslí nejmenší krabice, do které se vejde. Okraje krabice zanedbáváme. Např. pokud zboží má rozměry 2x3x6, tak se vejde do krabice 2x3x6 nebo větší.
Rozměry jsou v milimetrech v rozsahu 5 až 2000.
Zboží můžeme různě překlápět. (otáčet kolem různých os o 90 stupňů).
D <= 100 (max 100 různých druhů zboží)
Počet všech kusů zboží je nejvýše 10^9
Povolená paměť je 4GB
Místa na disku neomezeně, ale neplýtvat.
Čas běhu programu by měl být hodiny až několik dní.

Moje řešení:
Nejdřív jsem si řekl, že pokud potřebuju, aby se dalo poslat veškeré zboží, tak jedna krabice bude určitě muset mít 1 rozměr rovno maximu ze všech čísel x, y, z ze vstupu. Prostě pokud všechno zboží bude mít rozměry já nevím 3x4x4, ale 1 druh bude mít 2000x1x1, tak stejně potřebuju krabici, která má 1 z rozměrů 2000 mm.
Pokud bych měl za úkol najít jen 1 krabici, tak by to bylo triviální (popsáno níže). Řekl jsem si tedy, že si druhy zboží rozdělím do 2 skupin a pro každou tu skupinu už jednoduše najdu potřebné rozměry. Pak vyzkouším tolik možných rozdělení do skupin kolik dokážu a vypíšu nejlepší nalezené řešení. Tady je nejtěžší zjistit, jak rozdělit zboží, protože možných rozdělení je hodně. Rozhodl jsem se dělit zboží podle velikosti jejich největší hrany.

Udělám si nějaký struct, např.
struct Zbozi
{
int X;
int Y;
int Z;
int pocet;
}
Připravím si pole o max 100 prvcích typu Zbozi - pojmenuju si to pole třeba P. Načtu si vstup. Při načítání si rovnou spočítám parametr V, což je: (objem daného zboží * počet kusů) sečtené přes všechny druhy zboží. Toto číslo vlastně znát ani nepotřebuju, ale dává to jakousi míru a kontrolu, jak dobré je moje řešení a jestli je správné. Kdyby se mi náhodou povedlo najít řešení, které se rovná V, tak můžu rovnou skončit a vypsat rozměry. Kdybych našel řešení, které je menší než V, tak někde musí být chyba.
Projdu P a přeuspořádám si u každého zboží čísla tak, aby ten největší rozměr byl X. Př.: zboží d1 má rozměry 2x10x7. Tedy d1.X == 2, d1.Y == 10 a d1.Z == 7. Přeuspořádám takto: d1.X = 7; d1.Y = 2; a d1.Z = 7; (všechno zboží si pomyslně otočím nejdelší stranou na délku).
Pole P setřídím vzestupně podle X.
For i od 1 do velikosti P (tedy max 100) dělám:
Spočítám si rozměry krabice pro všechno zboží od P[1] do P[i-1] a pro zboží od P do P[100] (proměnná i dělí zboží na 2 skupiny).
Spočítám si S = (objem krabice 1 skupiny * počet kusů zboží v 1. skupině) + (objem krabice 2. skupiny * počet kusů zboží v 2. skupině).
Porovnám S s V, jestli jsem náhodou nenašel ideální řešení. Pokud ne, porovnám S s předchozím S. Pokud je menší, tak si zapamatuju současné S, rozměry krabic a proměnnou i a počet kusů v každé skupině (tj. N1 a N2 ze zadání).
Na konci pak vypíšu to, co jsem našel.
Jak jsem hledal rozměr krabice ve skupině:
Jeden ze tří rozměrů krabice určitě musí být největší X, protože jsem si to tak uložil do P. Zbylé rozměry zjistím snadno. Prostě najdu největší Y a největší Z u všech zboží ve skupině. Tedy pokud hledám rozměry v i-tém průchodu for cyklem v 1 skupině, tak:
krabice.X musí být P[i-1].X
krabice.Y bude maximum ze všech P[k].Y, kde k jde od 1 do i-1. Podobně krabice.Z bude maximum ze všech P[k].Z, kde k jde od 1 do i-1.
Čas a paměť si snadno spočítáte.

Pan Holan mi řekl, že můj program určitě nenajde nejlepší řešení, což je pravda, protože procházím velmi malou podmnožinu všech dělení do 2 skupin, ale líbilo se mu to na 1 až 2. Dal mi otázku na AVL stromy. Vložit několik prvků do stromu. Zkazil jsem dvojitou rotaci. Pak se zeptal, kolikrát nejvýše musím provést rotaci, když vkládám nebo odstraňuju. Řekl jsem, že když vkládám, tak log(n), protože to může jít až do kořene. To není pravda. Při vkládání pokud se mi pokazí výška, tak musím udělat jen buď jednoduchou rotaci nebo dvojitou. Při odstraňování musím dělat víc (potenciálně až do kořene). Ještě se mě zeptal na dolní odhad složitosti třídění porovnáváním. To jsem řekl správně, takže mi nakonec dal za 1.
vitSkalicky
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 20. 5. 2023 15:23
Typ studia: Informatika Bc.

Re: Zkouška 10. 6. 2019 [T. Holan]

Příspěvek od vitSkalicky »

2. 5. 2023 Holan a Pergel - Stejné zadání, ale jen 5 MB paměti a upřesnění, že data o objednávkách z minulého roku jsou ve formátu XML (a nevejdou se do paměti) na což stačí říct, že použijete vhodný XML parser, který to umí zpracovávat proudově jeden záznam po druhém.

Nejrychlejší algoritmus je asi O(d³), ale O(d⁶) se taky dá obhájit. (d je počet různých druhů zboží)
Odpovědět

Zpět na „PRG031 Programování II“