Da li je ovo problem sa projecteuler.net ili sličnog sajta?

Sada mi je malo suviše kasno da rešavam, a s obzirom da je tebi trebao ceo dan, čisto sumnjam da mogu noćas da ga rešim, ali evo kako bih ja rešio (odnosno pokušao da rešim).

Ono što je očigledno je da je broj rasporeda manji od 20! a veći od 10!
20! je broj permutacija 20 vojnika, ali nisu sve permutacije dozvoljene. Sada ću da objasnim zašto je veće od 10!

Postoji raspored (parova) vojnika takav da je prvi element para manji od drugog elementa para (a rešenje je (1,2), (3,4), ... (19,20) gde manji broj pretstavlja nižeg vojnika) pa je i svaki raspored parova koji je njihova permutacija rešenje problema, tako da postoji bar 10! rešenja.

Dakle, nađemo sva takva rešenja gde je prvi element prvog para manji od prvog elementa drugog para i tako do poslednjeg para.
Drugo ograničenje, pošto nečemo da tražimo sve permutacije uvek će skup parova biti sortiran po prvom elementu para.
Ovo je nešto što već može da se reši brute force metodom.

Iz skupa brojeva 1..20 uzeti minimalni element (1), i probati da li postoji rešenje za (1,2)...(1..20)
svaki put kada napravimo par, obrisati iz skupa brojeve koji smo uzeli i rešiti problem za k-2 elemenata.
Na kraju pomnožiti sa 10!

Možda može i bez programiranja.

Posmatrajmo niz od dvadeset različitih brojeva sortiran od najmanjeg do najvećeg.

Prvi par mora da ima minimalni element iz skupa kao prvi, a drugi može da bude bilo koji od preostalih brojeva, dakle 19 kombinacija.

rešenje je 10!*19*(broj rešenja za preostalih 18 brojeva)

U skupu od 18 brojeva, prvi par ima kao prvi element minimalni element, i bilo koji drugi od preostalih 17, znači ukupno 17 parcijalnih rešenja).

Na kraju ispada da je rešenje 10!*19*17*15*13*11*9*7*5*3*1=2375880867360000
(wolfram alpha mi je to izmnožio).

Ovako na brzinu, ako se izuzmu situacije da dva ili više vojnika mogu biti iste visine, onda postoji samo jedan redosled: svi vojnici se poredjaju u jednu vrstu po visini a onda svaki drugi predje u drugu vrstu.

Podeli ih u 10 parova na proizvoljan način. Niži ide ispred, a viši iza.

Prvi par možeš izabrati na 20*19/2 načina. Oni će biti najlevlji.

Drugi par možeš izabrati na 18*17/2 načina.

I tako dalje.

Na kraju dobijaš 20!/2^10=2375880867360000.

To je isto što je i prethodnik napisao.

Elegantno, Nedeljko, nema šta!
Vidi se šta je matematičar. Ja sam problemu pristupio kao da je to nešto što treba da se isprogramira, pa sam razišljao o strukturama podataka i rekurzivnom algoritmu, a ti si ga pogodio pravo u centar

Da ali to je pod pretpostavkom da ne postoje dva vojnika iste visine. A sta ako su svi potpuno iste visine? Onda postoji 0 nacina :)

Pogledaj drugu rečenicu postavke zadatka:

djoka_l

Pa, sad, poklapa se sa tvojim.

To sam odgovorio Informeru na ovu primedbu:

Hvala puno.

Razumeo sam.


Zadatak je sa kolokvijuma.

Bivši Mašinski fakultet u Kragujevcu.
Sada Fakultet inžinjerskih nauka.
Novi smer.
Softversko inžinjerstvo.

Četvrti zadatak u prilogu.


_{[Ovu poruku je menjao miki069 dana 13.02.2017. u 06:52 GMT+1]}

A može i ovako (pretpostavka): 20 vojnika se na 20 pozicija može rasporediti na 20! načina, bez obzira kako su te pozicije rasporedjene, razbacane, u jednoj liniji ili u dve vrste kao što se zahteva u zadatku, kako će vojnici biti rasporedjeni u dve vrste to možemo uočiti 10 parova od kojih se zahteva da uvek vojnik iz prve vrste u paru bude niži od vojnika iz druge vrste u paru, pošto baratamo sa 10 parova, i za sad imamo svih 20! načina rasporeda možemo one parove vojnika koji su se dobro rasporedili (niži u prvoj vrsti a viši u drugoj) da označimo sa 0 one parove koji su se rasporedili loše (viši u prvoj, niži u drugoj) sa 1, kada sad pogledamo dve vrste, tj, deset parova jasno je da se oni mogu rasporediti uzimajući u obzir orijentaciju parova kao i njihov položaj u samom stroju na 1024 različita načina jer 2^ 10= 1024 ( na primer ako su od deset parova 7 dobro okrenuti a samo neka tri kako ne treba to bi se vizuelno moglo predstaviti ovako: 0010001100 – dakle treći, sedmi I osmi par nam ne odgovara kako su stali) od kojih nama samo jedan način rasporeda odgovara a to je onaj kad su svih deset parova označeni sa 0 tj u svakom je niži vojnik u prvoj vrsti a viši u drugoj, I zbog toga pošto nam samo jedna kombinacija od mogućih 1024 odgovra: 20!/1024 = 2375880867360000 što se poklapa sa prethodna 2 rešenja.

Edit: ekhm, ovaaaaaj…ja nešto uopšte nisam siguran da je ovo tačno rešenje iako sam dobio isti rezultat, i iako ima pridruženu neku kao logiku, ovo je više bilo kako obrazložiti dobijeni rezultat nego rešavanje jer: … rezultat je veći od 10! * 10! – kao kad bi podelili vojnike na dve grupe 10 nižih I deset viših i onda permutovali sve u svojim vrstama, dobro ovaj rezultat se uklapa I u ovaj uslov, ali sad kad počnem da prebacujem neke vojnike koji su prvobitno bili u drugoj vrsti u prvu max može 5 vojnika da bude I to ne uvek bilo kojih ako su na primer 16, 17 i 19 u prvoj vrsti to je nemoguća situacija jer 18 i 20 nije dovoljno da sva tri iz prve vrste budu pokrivena, a to nigde nemam u računici…
Na primer gde grešim ako ovako pokušam da rešim šaljući vojnike jedan po jedan u stroj a popunjavajući pozicije prvi u prvoj vrsti, pa prvi u drugoj vrsti, pa drugi u prvoj vrsti itd…:
Na prvu poziciju može da dodje bilo koji od 19 vojnika (samo ne može najvišlji on nikad ne može da bude u prvoj vrsti), na prvo mesto u drugoj opet 19 (sad može najvišlji, ali ne može više onaj što je već rasporedjen uprvu vrstu), preostaje 18 od kojih 17 može na tu poziciju i istom logikom 17 na drugu sve u svemu 19*19*17*17*15*15… itd … = 428670161650355625 što je veći rezultat nego do sada, ali i dalje manje od 20!

I na kraju ali ne najmanje važno: ja kao raspisivao nešto, deluje mi da postupak radi za 4 vojnika i za 6, a već za 8 ne radi, po ovoj dosadašnjoj računici trebalo bi da mogu da se rasporede na 2520 različitih načina a ja sam „prebrojao“ da mogu na 1728 načina koji zadovoljavaju uslov zadatka...? Dobro nisam baš brojao ali baš da fali oko 1000 kombinacija...?

I uopšte sav mi je ovaj zadatak nešto smutljiv ne mogu da se razaberem šta je tačno rešenje.

Zadatak je kristalno jasan.

To što smo se ja i ti smutili pokušavajući da kombinujemo ko ide u prvu vrstu, pa da ih permutujemo, je naš problem.
Na taj način je zadatak nerešiv, jer se ne mogu permutovati u svim kombinacijama.
Mogu samo u nekim, a u nekima ne. Tako prebrojavanje je nemoguća misija.

Pogledaj Nedeljkovo rešenje.
Sve je kristalno jasno.

I Đokino rešenje je OK, ali je malo komplikovanije i teže za razumeti.


Zadatak na kolokvijumu nije bio sa 2*10 vojnika, nego 2*n vojnika.
Ali se lako generalizuje koristeći data rešenja.

Tako je.
Nedeljkovo i moje rešenje je identično, osim što sam ga ja bespotrebno zakomplikovao sa permutacijama i sortiranjima.

Jasno je da je broj načina na koji PRVI par može da se izabere jednak broju kombinacija bez ponavaljanja 20 (2k) elemenata 2. klase. Drugi par je broj kombinacija bez ponavljanja 18 (2k-2) elemenata 2. klase. I tako dalje do poslednjeg para.

Kada se to lepo izmnoži, gore se lepo namesti 20! (odnosno (2k)!), a dole, u imeniocu 2^10 (odnosno 2^k).

Rešenje je, u opštem slučaju za 2k vojnika, (2k)!/2^k

Uzgred, rešenje može da bude i "generalnije":

Na koliko načina može da se rasporedi kn vojnika u k vrsta tako da su vojnici ispred niži (viši) od onih iza, a rešenje je (kn)!/(k!)^n

Verujem ja vama al verujte i vi meni, na primer u rešenju koje sam predložio nedostaje ako su svi kontra postavljeni ali obe vrste gledaju na suprotnu stranu na primer sad prema poligonu umesto kao malopre prema izlazu iz kasarne onda ispada da su ponovo dobro postrojeni. Za 8 vojnika posle onih 4!*4! što je 576 kombinacija imaju situacije kad recimo spustiš 5 u prvu vrstu iza tog vojnika mogu biti 6, 7 ili 8 to je još 3 puta po 360 kombinacija i kad spustiš 6 ili 7 i zajedno 5 i 6 ili 5 i 7 (6 i 7 oba ne mogu u prvi red jer 8 ne može da se nadje iza obojice) to je još 3 * 24 kombinacije sve ukupno 1728 nema šansi da namaknem na 2520 koliko rešenje kaže da bi trebalo da bude...? Evo ne znam a voleo bih još nekako da mogu da proverim.

Veruj mi, druže majore, kombinacije bez ponavljanja eliminšu problem sortiranja. Ako kažeš da je nešto kombinacija 20 elemenata 2. klase, to je kao da od skupa od dvadeset elemenata izabereš sve podskupove sa dva elementa. A skupovi {a, b} i {b, a} su isti jer redosled nije važan.

Pa nije važan kad biraš a vidiš da je ovde važan kad ih postrojiš, a ovi zadaci su mi klimavo postavljeni ili dozvoljavaju klimava rešenja jer ništa ne govore o orijentaciji odakle gledaš stroj i slično gde je isti okrenut itd... verovaću kad ispišeš 2520 kombinacija za 8 vojnika.

Gde je greška ovde? "Na primer gde grešim ako ovako pokušam da rešim šaljući vojnike jedan po jedan u stroj a popunjavajući pozicije prvi u prvoj vrsti, pa prvi u drugoj vrsti, pa drugi u prvoj vrsti itd…:
Na prvu poziciju može da dodje bilo koji od 19 vojnika (samo ne može najvišlji on nikad ne može da bude u prvoj vrsti), na prvo mesto u drugoj opet 19 (sad može najvišlji, ali ne može više onaj što je već rasporedjen uprvu vrstu), preostaje 18 od kojih 17 može na tu poziciju i istom logikom 17 na drugu sve u svemu 19*19*17*17*15*15… itd … = 428670161650355625 što je veći rezultat nego do sada, ali i dalje manje od 20!"?

Pa grešiš.

Ako si izabrao prvog vojnika u prvoj vrsti, tada u drugu vrstu ne možeš da izabereš BILO KOG od preostalih 19 nego samo one koji su viši od njega. Recimo izabereš vojnika 19, onda iza njega može samo vojnik 20. Pa onda nije 19*19 nego 19*1.

Biraš PAR (dva vojnika) i onda kažeš nižem da stane napred. A par se bira na jedan od načina.

Druže majore stroj može da se gleda "licem u lice" ili "licem u ledja" ili još dve kombinacije koje za majora nisu interesantne, jer ne vidi stroj u tim kombinacijama.
Vi kao major bi trebali da znate kako se gleda stroj.
Samo "licem u lice".
Tako da zadatak nije klimavo postavljen, što se tiče orjentacije.

To što ga vi klimavo rešavate (isto kako sam ga i ja rešavao ceo dan), je naš problem.

Daaaa, hvala, totalno sam se zaglupeo oko ovog zadatka...



Upravo si i sam rekao, to je kako biraš 2 od 20, ali kako kažeš nižem da stane napred?

S tim u vezi i Nedeljkovo rešenje je čini mi se odgovor na pitanje na koliko načina možeš odabrati 10 parova i postrojiti ih, ničim ne govori kako da se postroje tj da niži stoji ispred višeg, tj. i kod njega postoji slična rečenica "kažeš nižem da stane napred" ali je nigde nema u računici, nema matematički to izraženo, isto kod tebe ti permutuješ parove u kojim je jedan vojnik uvek niži (a uvek je jedan niži jedan viši jer su svi različite visine...) tu deluje da si odredio kako da se postroje, tj. odredio na koliko načina mogu da se postroje, a u stvari si samo birao par tako da jedan (prvi) član bude niži, tj tvoje rešenje je kao da si birao parove vojnika ali tako da si uvek od dva vojnika prvo birao nižeg ali im nikad nisi rekao kako da se postroje tj. da zadrže tej redosled kako si ih birao???

@Nedeljko Koji bi bio tvoj odgovor na pitanje na koliko načina možeš odabrati 10 parova vojnika i postrojiti ih da stoje parovi jedan pored drugog i na taj način čine 2 vrste po 10 vojnika? Isto 20!/2^10? Nigde se ne govori da je niži ispred višeg?



Da, šta se ja tu raspravljam sa vama kad sam Major valjda znam kako se postrojavaju vojnici, haha, nisam ni obratio pažnju koji mi je nick na es, meni ne moraš da persiraš...Dobro zeznuo sam i to sa orijentacijom, podrazumeva se da gledaju na jednu stranu, tj. da se postrojavaju u jednom pravcu.

Ali i dalje nikako ne mogu da prebrojim 2520 rasporeda za 8 vojnika? Vidi, rasporeda gde su 1234 u prvoj vrsti kao niži a 5678 u drugoj kao viši ima 4!*4! to je 576 različitih rasporeda, i sad kad spustiš vojnika br 5 u prvu vrstu gde su niži iza njega mogu biti samo vojnici br 6,7 ili 8, to su još tri situcije gde ima po 360 različitih rasporeda, i još imaš kad je 6 u prvoj vrsti iza njega može biti samo 7 ili 8, i kad je 7 u prvoj vrsti iza njega može biti samo 8, ali pošto su neke od ovih situacija već bile obradjene kad je 5 u prvoj vrsti ovih imaš 3 puta po 144 rasporeda i nijedan više! Sve zajedno 2088 različitih rasporeda fali još oko 500 do 2520 koliko kaže formula: 4!*7*5*3*1 = 8!/2^4 = 8!/16 = 2520 ???

Po meni i ovo je korektno rešenje.

Imamo tri ispravna rešenja, dobijena totalno drugačijem pristupu problema.

Ako gledamo kao matematičari, najbolje je Nedeljkovo rešenje, pa Majorovo, pa onda Đokino.

Ako gledamo kao informatičari, najbolje je Đokino rešenje, pa Majorovo, pa Nedeljkovo.
Mislim ako bi trebalo napisati program, koji generiše svih tih 2.375.880.867.360.000 različitih rasporeda.

Ma prebrojah konačno 2520 rasporeda za 8 vojnika, 576 i 3 * 360 i 3 * 288, bio sam uveren da mora da ih ima manje, sve je ok :)