Problema cu lingouri de aur

Salut.

Am de rezolvat o problema, dar cred ca nu are sens exemplu de date de intrare si iesire.
Problema:


Ideea e ca nu prea inteleg cum poate sa dea 8, luand inca in calcul ca asta e suma ariilor, al doilea lingou cum intra ? are o aria de 15 ( neconsiderand si lungimea, ca nu prea conteaza. Conteaza sa-i incapa latimea si inaltimea ). Eu cred ca daca am fi sa obitem cea mai mica arie a orificiului, asta ar fi a celui mai mare lingou, intrucat prin el trec toate, dar prin celelalte nu trec toate, iar sa faca doua orificii nu ar avea sens intrucat cel mai mare lingou oricum nu poate iesi, si deja suma nu e minima. Sunt putin confuz, sau poate nu am inteles conditia bine... Daca cineva ar putea sa ma lumineze, sau sa-mi confirme ca exemplul e prost... Multumesc

 index.jpg   409.28K   75 downloads

Edited by MarianG, 06 June 2018 - 13:45.
replaced link w/ attachment

Enuntul zice clar: "Evident, lingoul poate fi rotit in orice fel".
Tinand cont de asta, solutia e simpla si evidenta .

Sunt sigur ca asa s-a dezvoltat America =)) Cu astfel de probleme, total rupte de realitate.Asa probleme asa rezultate.
Initiator cum se numeste cartea de unde ai luat astfel de probleme ?  o are si pe aia cu broscuta melancolica care sare in progresie gemetrica ca nebuna ?

Edited by WinstonMontana, 06 June 2018 - 12:53.

 WinstonMontana, on 06 iunie 2018 - 12:51, said:

Habar nu am cartea, problema e pe o foaie a4

 LuvRaluK, on 06 iunie 2018 - 12:41, said:

 WinstonMontana, on 06 iunie 2018 - 12:51, said:

Pentru ce c*c*t v-ati chinuit sa raspundeti asa ?!
Mie mi se pare destul de clar ca solutia inseamna, de fapt, descoperirea algoritmului de optimizare a unei suprafete minime, fiind date alte suprafete.
Plus ca trebuie sa intre pe gaurile date toate suprafetele.
Din ce-mi aduc eu aminte de geometrie.... cam asta e ideea.
Pana mea, aia cu lingourile si r*h*t... e apa de ploaie.

 trollerul_de_serviciu, on 06 iunie 2018 - 13:04, said:

Dar nu e doar o suprafata minima, trebuie de aflat suma minima a ariilor suprafetelor. Deci pot fi mai multe suprafete.
EDIT: Analizand acum, vad ca 8 e aria unei suprafete de 2 pe 4, prin care trec toate. Cred ca suma e scris pentru a te duci in eroare, caci daca mai faci un orificiu mereu vei fi in plus, nu in minus.

Edited by AlexMatei2000, 06 June 2018 - 13:18.

Am zis optimizare.
Si am explicat babeste, cu cunostintele mele limitate de geometrie/calcul.

 AlexMatei2000, on 06 iunie 2018 - 13:09, said:

analiza ta e gresita.
uite, sa zicem ca avem 2 lingouri, unul de 3x4 si altul de 1x7. daca vrei un singur orificiu, atunci trebuie sa gauresti 3x7, deci suprafata totala e de 21. alternativa e un orificiu de 3x4 si unul de 1x7, suma lor fiind 19 (<21).

 _Smiley_, on 06 iunie 2018 - 13:28, said:

Ai intr-adevar si tu dreptate. Dar mai exista si a treia dimensiune, lungimea lingoului, pe care poti sa il intorci si sa intre, poate, pe un singur orificiu, si mai mic. Trebuie luat si el in considerare, desi in exemplul tau solutia cea mai buna e 19.

Edited by AlexMatei2000, 06 June 2018 - 13:35.

lumgimea este cea mai mare marime, o poti ignora.

de fapt marimea cea mai mare ar cam trebui sa o ignori, pentru ca ti se cere aria minima (deci vei putea scoate lingoul folosind celelalte 2 dimensiuni)

Ce inseamna Cp1 1 4 4 g m din datele de intrare?

 dani.user, on 06 iunie 2018 - 18:39, said:

cp1 si g m nu stiu ce insemna, folosim doar cifrele 1 4 4, ca lature.

 _Smiley_, on 06 iunie 2018 - 17:03, said:

Da, asta si am facut. Defapt am facut un algoritm functionabil, dar nu pentru toate cazurile.
de exeemplu.
Se dau 3 lingouri , cu marimile: 2 4 3 , 1 5 7 , 3 4 2. Le aranjez crescator, astfel ca laturea cea mai mare sa fie ultima, ca sa scap de ea cum ai spus si tu. Acum raman primele doua,
adica: 2 4
          1 5
          3 4
ideea este ca, gasesc cea mai mare valoarea din primul rand, si respectiv din al doilea. Cea ce formeaza o suprafata de 3*5. Prin aceasta arie vor putea patrunde toate, si e cea mai mica ( dupa testele mele ).
Problema este ca, in cazul in care ar exista o arie mai mica, formata din doua orificii in perete, nu le-ar afisa, ci o va afisa pe cea din urma, care nu e corecta pentru acel caz.
E un algoritm destul de complicat pentru a afla suma minima a ariilor orificiilor din perete. Daca am introduce 100 de lingouri cu marimi distincte, sigur ar exista minim 10 gauri, ca astfel sa fie suma ariilor minime. Dar din nou, e complicat, o gaura ar putea contine 20 lingouri, alta doar 5 din ele, alta chiar doar un lingou... e mai greu de determinat. Sunt atat de multe cazuri posibile, nu stiu cum sa le iau, trebuie verificat fiecare lingou in fiecare orificiu, sau nu...sau...

Ca-i interesanta problema, am generat niste date de intrare aleatoare pentru a putea compara rezultate.

Sunt 3 fisiere, cu 10 intrari, 100 si 1 milion.

 inputs.zip   4.67MB   3 downloads

(mici corectii la fisier fata de prima versiune)

Edited by dani.user, 06 June 2018 - 21:10.

 dani.user, on 06 iunie 2018 - 19:23, said:

De-as sti care e si rezultatul fiecareia

Le scriem aici si le comparam, "care da mai putin". E usor de verificat daca o solutie e valida chiar daca nu e minima.

Rezultele mele pentru cele 3 fisiere: 99, 320, 3355

 dani.user, on 06 iunie 2018 - 21:14, said:

Cum ai facut sa-ti incapa in array 1000000 de elemente ?
BTW, primele doua imi dau exact la fel, a treia nu (ca imi da stock overflow =)) ).
Ce algoritm ai folosit ?

Edited by AlexMatei2000, 06 June 2018 - 22:48.