Problemi 052

Kërkesa

Jepen disa shkopinj me gjatësi të përcaktuara. Gjeni sipërfaqen e drejtkëndëshit më të madh që mund të formohet me këta shkopinj, ose printoni -1 nëse asnjë drejtkëndësh nuk mund të formohet.

Referenca: https://www.codechef.com/problems/STICKS

Shembull

$ cat input.txt
2
5
1 2 3 1 2
4
1 2 2 3

$ python3 prog.py < input.txt
2
-1

Në rastin e parë mund të formohet një drejtkëndësh me brinjë 1 dhe 2. Në rastin e dytë asnjë drejtkëndësh nuk mund të formohet.

Zgjidhja

Sqarime

Duam të gjejmë 4 brinjë 2 e nga dy të barabarta, me gjatësi maksimale. Për ta lehtësuar këtë i rendisim shkopinjtë në rendin zbritës dhe fillojmë kontrollin. Kur gjejmë çiftin e parë të barabartë e ruajmë gjatësinë e tyre te ndryshorja a. Kur gjejmë çiftin tjetër printojmë direkt sipërfaqen dhe e mbyllim ciklin e kërkimit (me break). Normalisht kjo duhet të ndodhë para se të arrijmë në fund të kërkimit, por nqs arrijmë deri në fund të kërkimit dhe nuk kemi gjetur gjë akoma, atere printojmë -1.

Detyra

Shefi ka gjetur një libër me receta gatimesh, ku çdo gatim ka 4 përbërës. Ai do zgjedh 2 receta për ti gatuar për drekë, por dëshiron që këto dy gatime të mos jenë të ngjashme. Dy gatime quhen të ngjashme nëse kanë 2 ose më shumë përbërës të njëjtë.

Bëni një program që merr përbërësit e dy gatimeve dhe gjen nëse janë të ngjashme ose jo.

Referenca: https://www.codechef.com/problems/SIMDISH

Shembull

$ cat input.txt
5
eggs sugar flour salt
sugar eggs milk flour
aa ab ac ad
ac ad ae af
cookies sugar grass lemon
lemon meat chili wood
one two three four
one two three four
gibberish jibberish lalalalala popopopopo
jibberisz gibberisz popopopopu lalalalalu

$ python3 prog.py < input.txt
similar
similar
dissimilar
similar
dissimilar