Ĺadny brzuch
Witam :)
tyle tych konkursow ostatnio, ze i ja sie dorzuce ze swoim zadaniem :]
of coz zadanie prosciutkie, mysle ze po potyczkach algorytmicznych zrobicie od strzalu :]
tu opowiesc sie zaczyna ;]
Pan Jan [tak, tak ;) ten sam od palindromów i słów Jana] tym razem zainteresował się liczbami, bo dłubanie cały czas w wyrazach i kolejnościach liter już go zmęczyło wielce ;). Pewnego razu wstukując mozolnie pin swojej karty bankomatowej naszło go z nienacka pytanie: ile takich kombinacji pinów może być? Oczywiście szybko rozwiązał ten prosty problem matematyczny, jednakże zaintrygowany światem liczb, a zwłaszcza pinów, wkrótce zaczął obliczać ilości pinów o specyficznym układzie liczb na kolejnych pozycjach. Jeden z takich właśnie specyficznych rodzajów pinów wydał się Janowi szczególnie interesujący i postanowił nazwać je "Pinami Jana" :)
Do tworzenia "Pinów Jana" brane jest m różnych liczb naturalnych i z nich tworzone są piny składające się z 4 liczb, ale liczby występujące w pinie muszą być w tej samej kolejności w jakiej zostały podawane.
Czyli jeżeli zostały podane 3 następujące liczby do tworzenia pinów: 3 5 23 to "Pinami Jana" będą:
3 3 5 23
23 23 23 23
5 5 23 23
natomiast następujące piny, nie są "Pinami Jana":
23 23 23 5
3 5 3 5
5 3 23 23
ponieważ liczby na kolejnych pozycjach nie są w takiej kolejności, jak występowały przy podawaniu liczb do tworzenia pinów.
Niestety biedny Jan ma strasznie dużo pracy i nie ma czasu rozpisywać wszystkich możliwych "Pinów Jana", dlatego poprosił Ciebie, abyś napisał program, który dla podanej ilości m różnych liczb wyświetli ilość "Pinów Jana", które można z tych liczb wygenerować :] Oczywiście twoj program musi być na tyle szybki, żeby Jan nie musiał czekać zbyt długo na odpowiedź :]
Zadanie:
Napisz program, który:
- wczyta ilość m liczb do tworzenia "Pinów Jana",
- wyznaczy ilość "Pinów Jana", które można utworzyć z m liczb,
- wypisze wynik.
Wejście:
W pierwszym i jedynym wierszu wejścia znajduje się jedyna liczba m (1 <= m <= 100000) określająca ilość róznych liczb naturalnych, z których generowane są 4 liczbowe piny.
Wyjście:
W pierwszym i jedynym wierszu wyjścia powinna znajdować się liczba naturalna będąca rozwiązaniem zadania.
Limity:
pamięć: 32 MB
czas: 1s :]
Przykład1:
Dla danych wejściowych:
3
poprawny wynik:
15
Przykład2:
Dla danych wejściowych:
11
poprawny wynik:
1001
Przykład3:
Dla danych wejściowych:
20
poprawny wynik:
8855
Organizator [czyli ja] rozwiazalem zadanko i jestem prawie na 100% pewien, ze dziala dobrze. Ewentualne niescislowsci mozna zawsze zalatwic bruteforcem, aczkolwiek od razu mowie, ze nie miesci sie on w limicie czasu ;)
Niestety organizator nie przewiduje zadnych nagrod :( of coz poza satysfakcja i uznaniem geniuszu programisty plynacych z poprawnego rozwiazania zadania :)
Co do czasu na rozwiazanie zadania mysle, ze mozemy to jakos wspolnie ustalic [ jesli w ogole beda chetni do podjecia wyzwania ;) ]
ja ze swojej strony proponuje takie cus: mamy czas na zadanie do 31 marca do polnocy, jezeli ktos zrobi zadanie to w tym watku wrzuca 10 swoich przykladow [rozniacych sie od innych zgloszen] gdzie m >= 10000. W taki sposob bedzie mozna sprawdzic, czy ktos zrobil dobrze zadanie i czy w ogole zrobil ;), a po zakonczeniu konkursu wkleimy [jesli ktos bedzie sie chcial podzielic] kodziki...
co wy na to? podejmie ktos wyzwanie, czy wymiekacie??? :P
Przeciez duzo jest roznych contestów w internecie
niektóre mają nawet sprawdzacza on-line :D
Po co jeszcze jeden na forum ?? :>
a jaką technologię sobie pepsi życzysz ??? java? paszczak?
Do tworzenia "Pinów Jana" brane jest m różnych liczb naturalnych i z nich tworzone są piny składające się z 4 liczb, ale liczby występujące w pinie muszą być w tej samej kolejności w jakiej zostały podawane.
Czyli jeżeli zostały podane 3 następujące liczby do tworzenia pinów: 3 5 23 to "Pinami Jana" będą:
3 3 5 23
23 23 23 23
5 5 23 23
natomiast następujące piny, nie są "Pinami Jana":
23 23 23 5
3 5 3 5
5 3 23 23
ponieważ liczby na kolejnych pozycjach nie są w takiej kolejności, jak występowały przy podawaniu liczb do tworzenia pinów.
no przecież jest podane że nie ma ograniczenia. jedynym ograniczeniem jest to że liczba ma być naturalna.
a po za tym w znaczeniu nei ma znaczenia jaka jest wartość liczby. najważniejsze jest to ile możliwych kombinacji możesz uzyskać jeżeli masz m liczb.
kombinatoryka się kłania i algorytmy kombinatoryczne :D
jak z tego skorzystasz to będzie śmigało aż miło i na pewno nie będzie brute force :D
Użytkownik j-mail edytował ten post 17 marzec 2005, 15:51
Pin składa się z 4 liczb, a nie cyfr?! jeśli tak, to jaka jest największa wartość tej "liczby"?
to sa takie specjalne piny ;) ktore sobie umyslil Jan :]
"najwiekszy" pin Jana spelniajacy warunki zadania jest taki:
100000 100000 100000 100000
[ nie jest to taki pin jak wstukujesz w polskich bankomatach ;) aczkolwiek bylby na pewno bezpieczniejszy :P ]
j-mail: kazdy jezyk programowania jest dozwolony, byleby progs w nim napisany wczytywal z wejscia liczbe i wyrzucal na wyjscie dobry wynik...
Pinochet wiem ze konkursow jest sporo, to nie jest konkurs, tylko zadanko typu proof your mastahacka programing skills :)
jezeli jednak rozwiazesz to zadanko to bedziesz jednym z nielicznych na tym forum, ktorzy potrafia cos skladnie pomyslec i pozniej to oprogramowac :) czym bylby swiat bez wyzwan :)
anyway ciekawe jak dlugo pozostane jedynym szczesliwym posiadaczem pomyslu na rozwiazanie ;) wierze w was, ze dacie rade ;) hiehiehiehie :P
jezeli jednak rozwiazesz to zadanko to bedziesz jednym z nielicznych na tym forum, ktorzy potrafia cos skladnie pomyslec i pozniej to oprogramowac :) czym bylby swiat bez wyzwan :)
anyway ciekawe jak dlugo pozostane jedynym szczesliwym posiadaczem pomyslu na rozwiazanie ;) wierze w was, ze dacie rade ;) hiehiehiehie :P
Fajna zadanko, chociaż bardziej matematyczne niż informatyczne :) Jeżeli odkryło się prawidłowy wzór, to złożoność programu jest O(1) i jedynym malutkim problemem przy implementacji jest dopilnowanie, żeby w trakcie liczenia nie przekroczyć zakresu int64 (w Pasccalu)
hehe. nie zostało powiedziane czy jeżeli przy czterocyfrowym pinie ta sama liczba zostaje wybrana po raz drugi to czy jest ona traktowana jako element ten sam czy jako nowy. na przykład
a= 11
b=3
c=5
d=11
to d traktujemy jako a czy jako osobny element ?
zakładamy że jako a czyli tak jakbyśmy wylosowali 3 a nie cztery liczby.
ale co do 11 = 1001 w żadnym wypadku się nie zgodzę.
z prostej przyczyny z 11 liczb możemy wylosować 4 niepowtarzające się na 330 sposobów. z każdego zestawu możemy ułożyć x (ty już pepsi wiesz dobrze ile zestawów można utworzyć nie chcę za bardzo ułątwiać nikomu) układów. wszystkie te układy zawierają w sobie wszelkie możliwe uklady gdzie liczby się powtarzają. kwestia ile możemy ułożyć jest prosta
x * 330 potencjalnych zestawów liczb. jak doszedłęm do tych 330? tobie pepsi mogę przesłać pw ale innym nie pomogę. ja już rozwiązanie mam :)
//edit
jescze źle policzyłem bo tych zestawów możemy wylosować więcej. zapomniałem przecież o tym że kolejność wylosowania liczb ma znaczenie. :/
zaraz ile to będzie. :)
7920 kombinacj z 11 liczb gdzie kolejność ma znaczenie :/ rośnie nam lawinowo to rozwiązanie ale pepsi nie da się ukryć że rozwiązanie będzie bardzo wielkie. teraz trzeba pokombinować w ilu wypadkach na przykład a zostanie wylosowane na pierwszym miejscu dalej w ilu wypadkach a i b wylosowane zostaną razem abc zostaną wylosowane razem no i abd wylosowane razem w tej samej kolejności i tak dalej.
pepsi chyba coś niedomyślałeś tego zadania
//edit2
znalazłem prawidłowe rozwiązanie dla 11
jest 11231 prawidłowych pinów :D
dobrze? na pewno. skontrolowałem. pepsi stuknij do mnie na gadu albo na pw to ci napiszę dlaczego musi tak wyjść. :D zadanie robi się nieobliczalne przy liczbach powyżej 30 bo komp tego nie uciąga :P
Użytkownik j-mail edytował ten post 17 marzec 2005, 21:18
ale co do 11 = 1001 w żadnym wypadku się nie zgodzę.
(...)
pepsi chyba coś niedomyślałeś tego zadania
Zadanie jest jak najbardziej w porządku, a Ty już jesteś naprawdę blisko poprawnego rozwiązania ;)
znalazłem prawidłowe rozwiązanie dla 11
jest 11231 prawidłowych pinów
dobrze? na pewno. skontrolowałem.
Na pewno źle. Moim zdaniem rozwiązania podane przez pepsi są poprawne. Dla 100000 otrzymany wynik mieści się w zakrecie int64.
Użytkownik Favex edytował ten post 17 marzec 2005, 21:28
pisze drugiego posta bo skończyłem.
macie linkę do działającego progsa :)
http://atos.wmid.amu...18061/pepsi.exe
pozdrawiam.
pepsi -->> twoje rozwiązanie pod tytułem 11 nie uwzględniło baaaardzo dużo rzeczy :) no ale co ja na to ci poradzę? na gadu stuknij do mnie w sobotę na ten przykład 1531972
pozdrawiam wszystkich
favex -->> w żadnym wypadku dla 11 nie będzie 1001 z prostego powodu
pierwsze
możemy wylosować 11 pojedynczych liczb i z tego stworzyć 11 pinów skłądających się z czterech takich samych cyfr
dalej na 110 sposobów możemy wylosować 2 cyfry kktóre ustawimy na 3 sposoby w zestawienia czterocyfrowe z zachowaniem kolejności losowania oczywiście nie liczę tu ustawiania z dwóch wylosowanych liczb w kombinację aaaa bo to już było przy jednej cyfrze
dalej na 990 sposobów możemy wylosować trzy różne cyfry które ustawimy na 3 sposoby tak żeby wykluczyć ustawienia z dwoma cyframi
i na 7920 sposobów możemy polosować cztery cyfry wykluczając nadal ustawienia z mnhiejszą ilością cyfr czy liczb nie ważne
posumuj
11 + 330 + 2970 + 7920 = 11231 możliwych pinów. ktoś chyba pisząc to zadanie zapomniał o kombinatoryce? co pepsi??? ;)
Użytkownik j-mail edytował ten post 17 marzec 2005, 21:41
hehe. nie zostało powiedziane czy jeżeli przy czterocyfrowym pinie ta sama liczba zostaje wybrana po raz drugi to czy jest ona traktowana jako element ten sam czy jako nowy. na przykład
a= 11
b=3
c=5
d=11
to d traktujemy jako a czy jako osobny element ? nie bardzo rozumiem ;) mialem dzis bad day ;)
jezeli pytasz czy do wyboru pinow mozesz wziasc zbior liczb 11, 3, 5, 11 to zgodnie z trescia zadania nie, poniewaz liczby brane do generowania pinow sa rozne...
jezeli mamy zbior liczb 11, 3, 5 to nie mozesz wygenerowac z niego pinu 11 3 5 11 bo ostatnia jedenastka wystepuje w zlej kolejnosci :)
favex -->> w żadnym wypadku dla 11 nie będzie 1001 z prostego powodu
pierwsze
możemy wylosować 11 pojedynczych liczb i z tego stworzyć 11 pinów skłądających się z czterech takich samych cyfr ql :]
dalej na 110 sposobów możemy wylosować 2 cyfry kktóre ustawimy na 3 sposoby w zestawienia czterocyfrowe z zachowaniem kolejności losowania oczywiście nie liczę tu ustawiania z dwóch wylosowanych liczb w kombinację aaaa bo to już było przy jednej cyfrze not ql :]
mozesz wylosowac 2 cyfry tylko na 55 sposobow, moge ci nawet napisac jakich ;)
jezeli zbior liczb do generowania pinow mamy taki: 1,2,3,4,5,6,7,8,9,10,11, to mozesz wzisc dwojki liczb do generowania pinow tylko takie:
1-2, 1-3, 1-4, 1-5, 1-6, 1-7, 1-8, 1-9, 1-10, 1-11
2-3, 2-4, 2-5, 2-6, 2-7, 2-8, 2-9, 2-10, 2-11
3-4, 3-5, 3-6, 3-7, 3-8, 3-9, 3-10, 3-11
...
10-11
razem 55 na oko ;)
reszta twoich obliczen tez jest bledna, na tej samej zasadzie :)
aaaaa a to nie było uwzględnione że mogą być brane tylko w kolejności rosnącej. przecież równie dobrze jan mógłby podać takie liczby z zestawu 11 : 6 i 5 i co wtedy? nie wygeneruje żadnego pinu bo uklad 6 5 jest niemożliwy?
trzeba było powiedzieć że tylko w kolejności rosnącej można podawać liczby wtedy to będzie zupełnie inna rozmowa bo sobie walnę inny algorytm
ale przy tak sformułowanej treści zadania nie możesz mieć pretensji że tak znacząco podniosłą się ilość możliwych pinów
z twojego rozumowania wynika że niemożliwe jest stworzenie pinu z róznych trzech cyfr jeżeli pierwszą z nich jest 10 (nadal rozmawiamy o tym przypadku z 11)
jest podane tylko że jest branych m różnych liczb. więc gdzie tutaj info o tym że nie mogą być piny w kolejności malejącej czy pomieszanej. ma być tylko zachowana kolejność z wejscia.
Użytkownik j-mail edytował ten post 17 marzec 2005, 22:16
przeczytaj jeszcze raz tresc :] najpierw wyjasnione jest co to sa piny jana, z warunkow zadania mozna wywnioskowac dlaczego na wejsciu pojawia sie tylko ilosc liczb do tworzenia pinow a nie same liczby... jesli by ktos przeoczyl to daje przyklady :]
gdy liczby do tworzenia pinow bylyby takie: 200 50 100
to mozna wygenerowac piny:
200 50 100 100
200 200 50 100
50 100 100 100
a nie mozna wygenerowac pinow:
50 200 200 200
50 100 200 200
50 200 100 50
poniewaz liczby do tworzenia pinow sa w innej kolejnosci niz w pinie:
i.e. w 50 200 200 200 liczba piecdziesiat jest przed dwiescie a mialy byc w kolejnosci zadanej 200 50 100...
czyli w przypadku m=11 i zakladajac ze mamy do tworzenia pinow takie liczby 1,2,3,4,5,6,7,8,9,10,11
jezeli wezmiesz do pinu liczbe 5 to na kolejnych pozycjach moze byc tylko liczba 5 albo nastepne 6,7,8,... ale nie sa istotne ich wartosci, tylko miejsce.
gdyby liczby byly tak ulozone: 11,10,9,8,7,6,5,4,3,2,1 to biorac do pinu liczbe 7 na kolejnych pozycjach pinu moglaby znalezc sie liczba 7,6,5,4,... ale nie 11 bo zostalo ono podane przed 7.
z tresci zadania to wynika :]
ok. ale to nadal trzeba by pomnożyć przez ilośc permutacji na jakie możęmy te liczby podzielić bo nie jest powiedziane w jakiej kolejności one są wstawiane więc nadal musimy rozważyć przypadek gdzie liczby są podawane 1 2 3 jak również 2 1 3 jak również 3 2 1 i dalej 1 3 2, 3 1 2, 3 2 1
co ty na to?
no chyba nie możesz zaprzeczyć???
chociaż jak znam życie to pewnie zaprzeczysz.
mówię o kombinatoryce
powiedziałeś że podaję ile liczb zostało wpisanych. gdybym podawał jakie liczby po kolei to się z tobą zgodzę. bo wtedy rzeczywiście jest tak jak mówisz. ale w zadaniu jest tylko ilość liczb więc muszę rozważyć wszelkie możliwe ich początkowe ustawienia. nie mam racji?
w calym tym zamieszaniu zapomnialem pogratulowac oficjalnie Favex'owi :]
w pm'ie z 17.03.2005 21:16 przedstawil poprawne rozwiazanie o zlozonosci O(1) :D u mnie jest marna O(n) :] ale w dozwolonym czasie sie miesci :)
takze wielkie wyrazy uznania i gratulacje :)
ok. ale to nadal trzeba by pomnożyć przez ilośc permutacji na jakie możęmy te liczby podzielić bo nie jest powiedziane w jakiej kolejności one są wstawiane więc nadal musimy rozważyć przypadek gdzie liczby są podawane 1 2 3 jak również 2 1 3 jak również 3 2 1 i dalej 1 3 2, 3 1 2, 3 2 1
co ty na to?
no chyba nie możesz zaprzeczyć???
chociaż jak znam życie to pewnie zaprzeczysz.
mówię o kombinatoryce
powiedziałeś że podaję ile liczb zostało wpisanych. gdybym podawał jakie liczby po kolei to się z tobą zgodzę. bo wtedy rzeczywiście jest tak jak mówisz. ale w zadaniu jest tylko ilość liczb więc muszę rozważyć wszelkie możliwe ich początkowe ustawienia. nie mam racji?
nie masz ;) z prostej przyczyny: kolejnosc liczb jest z gory ustalona przez Jana i nie wplywa na ilosc "Pinow Jana" jaka mozna z nich wygenerowac. dlatego aby uproscic wejscie podawana jest tylko moc zbioru liczb do generowania a nie same liczby.
w przykladzie ktorym podajesz niezaleznie czy liczby do generowania pinow Jana beda 1 2 3, czy tez 2 1 3, czy 3 2 1 czy tez 1000 2000 3000 to ilosc Pinow Jana z kazdego takiego zestawu wynosi 15.
nie moge przyznac sie do bledu w zadaniu, bo go nie ma ;)
sa tacy co zrozumieli zadanie i tacy co musza dopiero zrozumiec :] ja dostalem zadanko, rozwiazalem, ubarwilem troszke ;) i poslalem dalej, cobyscie tez mogli sie poglowic troszke ;)
taaaak ustalana przez Jana. doskonałe. a skąd masz pewnosc w jakiej je poda??
nieważne. spadam stąd. podziwiam. szczerze podziwiam.
wyszło że lame jestem. no cóż. zdarza się.
masz rację pepsi. nie dałem rady rozwiązać bo jestem na to za głupi.
Nie wiem jak zrobiliście, aby taki program wykonywał się w 1s :blink: . Zastosowałem metodę brute-force, więc chyba nikt się nie obrazi jak zapodam kod:
... pins+=m; for(int i=0; i<m-1; ++i) for(int j=i+1; j<m; ++j) pins+=3; for(int i=0; i<m-2; ++i) for(int j=i+1; j<m-1; ++j) for(int k=j+1; k<m; ++k) pins+=3; for(int i=0; i<m-3; ++i) for(int j=i+1; j<m-2; ++j) for(int k=j+1; k<m-1; ++k) for(int l=k+1; l<m; ++l) ++pins; ...
No więc nie działa to zbyt szybko... Jeszcze jedno-jak w czystym c++ oznacza się liczbę 64-bitową(na maszynach 32-bit oczywiście)? Ja na kompliatorze borlanda skorzystałem z __int64. pepsi, mam nadziję że szybciej rzucisz dobry kod, bo po 1. nie mogę się doczekać, a po drugie nie widać żeby wiele osób to rozwiązywało.
No więc nie działa to zbyt szybko... Jeszcze jedno-jak w czystym c++ oznacza się liczbę 64-bitową(na maszynach 32-bit oczywiście)? Ja na kompliatorze borlanda skorzystałem z __int64. niektore kompilatory wspieraja __int64, na innych stosujesz long long
pepsi, mam nadziję że szybciej rzucisz dobry kod, bo po 1. nie mogę się doczekać, a po drugie nie widać żeby wiele osób to rozwiązywało. spoko :) powiedzmy po weekendzie wkleje swoje rozwiazanie, mam nadzieje ze FaveX tez sie podzieli :P
w calym tym zamieszaniu zapomnialem pogratulowac oficjalnie Favex'owi :]
w pm'ie z 17.03.2005 21:16 przedstawil poprawne rozwiazanie o zlozonosci O(1) :D u mnie jest marna O(n) :] ale w dozwolonym czasie sie miesci :)
takze wielkie wyrazy uznania i gratulacje :)
nu widze, ze Kodie dolacza do klubu :) wyniki takie same jak u mnie, a ze raczej nie liczyles na kartce ;) to twoje rozwiazanie jest dobre :)
gratulacje !!! :D
ja swoj kodzik wkleje po weekendzie, wiec mozesz sie wtedy tez dorzucic :)
widze, ze tylko ekipa z pa tylko podejmuje wyzwania programistyczne :)
moze ktos jeszcze przez weekend sprobuje??? :)
Wyniki: 18000: 4375458148504500 18001: 4376430472537501 18002: 4377402958615505 18003: 4378375606756515 18004: 4379348416978535 18005: 4380321389299570 18006: 4381294523737626 18007: 4382267820310710 18008: 4383241279036830 18009: 4384214899933995
Powinny być dobre, bo dla 17000 - 17009 otrzymałem to samo, co Kodie :-).
Co do limitów to program wymaga 8 bajtów pamięci i wykonuje 4 mnożenia i sześć dodawań (O(1)), więc powinien się zmieścić :-). Jeżeli ktoś chce, to mogę wysłać kod na PW (11 linii :-)).
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
tyle tych konkursow ostatnio, ze i ja sie dorzuce ze swoim zadaniem :]
of coz zadanie prosciutkie, mysle ze po potyczkach algorytmicznych zrobicie od strzalu :]
tu opowiesc sie zaczyna ;]
Pan Jan [tak, tak ;) ten sam od palindromów i słów Jana] tym razem zainteresował się liczbami, bo dłubanie cały czas w wyrazach i kolejnościach liter już go zmęczyło wielce ;). Pewnego razu wstukując mozolnie pin swojej karty bankomatowej naszło go z nienacka pytanie: ile takich kombinacji pinów może być? Oczywiście szybko rozwiązał ten prosty problem matematyczny, jednakże zaintrygowany światem liczb, a zwłaszcza pinów, wkrótce zaczął obliczać ilości pinów o specyficznym układzie liczb na kolejnych pozycjach. Jeden z takich właśnie specyficznych rodzajów pinów wydał się Janowi szczególnie interesujący i postanowił nazwać je "Pinami Jana" :)
Do tworzenia "Pinów Jana" brane jest m różnych liczb naturalnych i z nich tworzone są piny składające się z 4 liczb, ale liczby występujące w pinie muszą być w tej samej kolejności w jakiej zostały podawane.
Czyli jeżeli zostały podane 3 następujące liczby do tworzenia pinów: 3 5 23 to "Pinami Jana" będą:
3 3 5 23
23 23 23 23
5 5 23 23
natomiast następujące piny, nie są "Pinami Jana":
23 23 23 5
3 5 3 5
5 3 23 23
ponieważ liczby na kolejnych pozycjach nie są w takiej kolejności, jak występowały przy podawaniu liczb do tworzenia pinów.
Niestety biedny Jan ma strasznie dużo pracy i nie ma czasu rozpisywać wszystkich możliwych "Pinów Jana", dlatego poprosił Ciebie, abyś napisał program, który dla podanej ilości m różnych liczb wyświetli ilość "Pinów Jana", które można z tych liczb wygenerować :] Oczywiście twoj program musi być na tyle szybki, żeby Jan nie musiał czekać zbyt długo na odpowiedź :]
Zadanie:
Napisz program, który:
- wczyta ilość m liczb do tworzenia "Pinów Jana",
- wyznaczy ilość "Pinów Jana", które można utworzyć z m liczb,
- wypisze wynik.
Wejście:
W pierwszym i jedynym wierszu wejścia znajduje się jedyna liczba m (1 <= m <= 100000) określająca ilość róznych liczb naturalnych, z których generowane są 4 liczbowe piny.
Wyjście:
W pierwszym i jedynym wierszu wyjścia powinna znajdować się liczba naturalna będąca rozwiązaniem zadania.
Limity:
pamięć: 32 MB
czas: 1s :]
Przykład1:
Dla danych wejściowych:
3
poprawny wynik:
15
Przykład2:
Dla danych wejściowych:
11
poprawny wynik:
1001
Przykład3:
Dla danych wejściowych:
20
poprawny wynik:
8855
Organizator [czyli ja] rozwiazalem zadanko i jestem prawie na 100% pewien, ze dziala dobrze. Ewentualne niescislowsci mozna zawsze zalatwic bruteforcem, aczkolwiek od razu mowie, ze nie miesci sie on w limicie czasu ;)
Niestety organizator nie przewiduje zadnych nagrod :( of coz poza satysfakcja i uznaniem geniuszu programisty plynacych z poprawnego rozwiazania zadania :)
Co do czasu na rozwiazanie zadania mysle, ze mozemy to jakos wspolnie ustalic [ jesli w ogole beda chetni do podjecia wyzwania ;) ]
ja ze swojej strony proponuje takie cus: mamy czas na zadanie do 31 marca do polnocy, jezeli ktos zrobi zadanie to w tym watku wrzuca 10 swoich przykladow [rozniacych sie od innych zgloszen] gdzie m >= 10000. W taki sposob bedzie mozna sprawdzic, czy ktos zrobil dobrze zadanie i czy w ogole zrobil ;), a po zakonczeniu konkursu wkleimy [jesli ktos bedzie sie chcial podzielic] kodziki...
co wy na to? podejmie ktos wyzwanie, czy wymiekacie??? :P
Przeciez duzo jest roznych contestów w internecie
niektóre mają nawet sprawdzacza on-line :D
Po co jeszcze jeden na forum ?? :>
a jaką technologię sobie pepsi życzysz ??? java? paszczak?
Do tworzenia "Pinów Jana" brane jest m różnych liczb naturalnych i z nich tworzone są piny składające się z 4 liczb, ale liczby występujące w pinie muszą być w tej samej kolejności w jakiej zostały podawane.
Czyli jeżeli zostały podane 3 następujące liczby do tworzenia pinów: 3 5 23 to "Pinami Jana" będą:
3 3 5 23
23 23 23 23
5 5 23 23
natomiast następujące piny, nie są "Pinami Jana":
23 23 23 5
3 5 3 5
5 3 23 23
ponieważ liczby na kolejnych pozycjach nie są w takiej kolejności, jak występowały przy podawaniu liczb do tworzenia pinów.
no przecież jest podane że nie ma ograniczenia. jedynym ograniczeniem jest to że liczba ma być naturalna.
a po za tym w znaczeniu nei ma znaczenia jaka jest wartość liczby. najważniejsze jest to ile możliwych kombinacji możesz uzyskać jeżeli masz m liczb.
kombinatoryka się kłania i algorytmy kombinatoryczne :D
jak z tego skorzystasz to będzie śmigało aż miło i na pewno nie będzie brute force :D
Użytkownik j-mail edytował ten post 17 marzec 2005, 15:51
Pin składa się z 4 liczb, a nie cyfr?! jeśli tak, to jaka jest największa wartość tej "liczby"?
to sa takie specjalne piny ;) ktore sobie umyslil Jan :]
"najwiekszy" pin Jana spelniajacy warunki zadania jest taki:
100000 100000 100000 100000
[ nie jest to taki pin jak wstukujesz w polskich bankomatach ;) aczkolwiek bylby na pewno bezpieczniejszy :P ]
j-mail: kazdy jezyk programowania jest dozwolony, byleby progs w nim napisany wczytywal z wejscia liczbe i wyrzucal na wyjscie dobry wynik...
Pinochet wiem ze konkursow jest sporo, to nie jest konkurs, tylko zadanko typu proof your mastahacka programing skills :)
jezeli jednak rozwiazesz to zadanko to bedziesz jednym z nielicznych na tym forum, ktorzy potrafia cos skladnie pomyslec i pozniej to oprogramowac :) czym bylby swiat bez wyzwan :)
anyway ciekawe jak dlugo pozostane jedynym szczesliwym posiadaczem pomyslu na rozwiazanie ;) wierze w was, ze dacie rade ;) hiehiehiehie :P
jezeli jednak rozwiazesz to zadanko to bedziesz jednym z nielicznych na tym forum, ktorzy potrafia cos skladnie pomyslec i pozniej to oprogramowac :) czym bylby swiat bez wyzwan :)
anyway ciekawe jak dlugo pozostane jedynym szczesliwym posiadaczem pomyslu na rozwiazanie ;) wierze w was, ze dacie rade ;) hiehiehiehie :P
Fajna zadanko, chociaż bardziej matematyczne niż informatyczne :) Jeżeli odkryło się prawidłowy wzór, to złożoność programu jest O(1) i jedynym malutkim problemem przy implementacji jest dopilnowanie, żeby w trakcie liczenia nie przekroczyć zakresu int64 (w Pasccalu)
hehe. nie zostało powiedziane czy jeżeli przy czterocyfrowym pinie ta sama liczba zostaje wybrana po raz drugi to czy jest ona traktowana jako element ten sam czy jako nowy. na przykład
a= 11
b=3
c=5
d=11
to d traktujemy jako a czy jako osobny element ?
zakładamy że jako a czyli tak jakbyśmy wylosowali 3 a nie cztery liczby.
ale co do 11 = 1001 w żadnym wypadku się nie zgodzę.
z prostej przyczyny z 11 liczb możemy wylosować 4 niepowtarzające się na 330 sposobów. z każdego zestawu możemy ułożyć x (ty już pepsi wiesz dobrze ile zestawów można utworzyć nie chcę za bardzo ułątwiać nikomu) układów. wszystkie te układy zawierają w sobie wszelkie możliwe uklady gdzie liczby się powtarzają. kwestia ile możemy ułożyć jest prosta
x * 330 potencjalnych zestawów liczb. jak doszedłęm do tych 330? tobie pepsi mogę przesłać pw ale innym nie pomogę. ja już rozwiązanie mam :)
//edit
jescze źle policzyłem bo tych zestawów możemy wylosować więcej. zapomniałem przecież o tym że kolejność wylosowania liczb ma znaczenie. :/
zaraz ile to będzie. :)
7920 kombinacj z 11 liczb gdzie kolejność ma znaczenie :/ rośnie nam lawinowo to rozwiązanie ale pepsi nie da się ukryć że rozwiązanie będzie bardzo wielkie. teraz trzeba pokombinować w ilu wypadkach na przykład a zostanie wylosowane na pierwszym miejscu dalej w ilu wypadkach a i b wylosowane zostaną razem abc zostaną wylosowane razem no i abd wylosowane razem w tej samej kolejności i tak dalej.
pepsi chyba coś niedomyślałeś tego zadania
//edit2
znalazłem prawidłowe rozwiązanie dla 11
jest 11231 prawidłowych pinów :D
dobrze? na pewno. skontrolowałem. pepsi stuknij do mnie na gadu albo na pw to ci napiszę dlaczego musi tak wyjść. :D zadanie robi się nieobliczalne przy liczbach powyżej 30 bo komp tego nie uciąga :P
Użytkownik j-mail edytował ten post 17 marzec 2005, 21:18
ale co do 11 = 1001 w żadnym wypadku się nie zgodzę.
(...)
pepsi chyba coś niedomyślałeś tego zadania
Zadanie jest jak najbardziej w porządku, a Ty już jesteś naprawdę blisko poprawnego rozwiązania ;)
znalazłem prawidłowe rozwiązanie dla 11
jest 11231 prawidłowych pinów
dobrze? na pewno. skontrolowałem.
Na pewno źle. Moim zdaniem rozwiązania podane przez pepsi są poprawne. Dla 100000 otrzymany wynik mieści się w zakrecie int64.
Użytkownik Favex edytował ten post 17 marzec 2005, 21:28
pisze drugiego posta bo skończyłem.
macie linkę do działającego progsa :)
http://atos.wmid.amu...18061/pepsi.exe
pozdrawiam.
pepsi -->> twoje rozwiązanie pod tytułem 11 nie uwzględniło baaaardzo dużo rzeczy :) no ale co ja na to ci poradzę? na gadu stuknij do mnie w sobotę na ten przykład 1531972
pozdrawiam wszystkich
favex -->> w żadnym wypadku dla 11 nie będzie 1001 z prostego powodu
pierwsze
możemy wylosować 11 pojedynczych liczb i z tego stworzyć 11 pinów skłądających się z czterech takich samych cyfr
dalej na 110 sposobów możemy wylosować 2 cyfry kktóre ustawimy na 3 sposoby w zestawienia czterocyfrowe z zachowaniem kolejności losowania oczywiście nie liczę tu ustawiania z dwóch wylosowanych liczb w kombinację aaaa bo to już było przy jednej cyfrze
dalej na 990 sposobów możemy wylosować trzy różne cyfry które ustawimy na 3 sposoby tak żeby wykluczyć ustawienia z dwoma cyframi
i na 7920 sposobów możemy polosować cztery cyfry wykluczając nadal ustawienia z mnhiejszą ilością cyfr czy liczb nie ważne
posumuj
11 + 330 + 2970 + 7920 = 11231 możliwych pinów. ktoś chyba pisząc to zadanie zapomniał o kombinatoryce? co pepsi??? ;)
Użytkownik j-mail edytował ten post 17 marzec 2005, 21:41
hehe. nie zostało powiedziane czy jeżeli przy czterocyfrowym pinie ta sama liczba zostaje wybrana po raz drugi to czy jest ona traktowana jako element ten sam czy jako nowy. na przykład
a= 11
b=3
c=5
d=11
to d traktujemy jako a czy jako osobny element ? nie bardzo rozumiem ;) mialem dzis bad day ;)
jezeli pytasz czy do wyboru pinow mozesz wziasc zbior liczb 11, 3, 5, 11 to zgodnie z trescia zadania nie, poniewaz liczby brane do generowania pinow sa rozne...
jezeli mamy zbior liczb 11, 3, 5 to nie mozesz wygenerowac z niego pinu 11 3 5 11 bo ostatnia jedenastka wystepuje w zlej kolejnosci :)
favex -->> w żadnym wypadku dla 11 nie będzie 1001 z prostego powodu
pierwsze
możemy wylosować 11 pojedynczych liczb i z tego stworzyć 11 pinów skłądających się z czterech takich samych cyfr ql :]
dalej na 110 sposobów możemy wylosować 2 cyfry kktóre ustawimy na 3 sposoby w zestawienia czterocyfrowe z zachowaniem kolejności losowania oczywiście nie liczę tu ustawiania z dwóch wylosowanych liczb w kombinację aaaa bo to już było przy jednej cyfrze not ql :]
mozesz wylosowac 2 cyfry tylko na 55 sposobow, moge ci nawet napisac jakich ;)
jezeli zbior liczb do generowania pinow mamy taki: 1,2,3,4,5,6,7,8,9,10,11, to mozesz wzisc dwojki liczb do generowania pinow tylko takie:
1-2, 1-3, 1-4, 1-5, 1-6, 1-7, 1-8, 1-9, 1-10, 1-11
2-3, 2-4, 2-5, 2-6, 2-7, 2-8, 2-9, 2-10, 2-11
3-4, 3-5, 3-6, 3-7, 3-8, 3-9, 3-10, 3-11
...
10-11
razem 55 na oko ;)
reszta twoich obliczen tez jest bledna, na tej samej zasadzie :)
aaaaa a to nie było uwzględnione że mogą być brane tylko w kolejności rosnącej. przecież równie dobrze jan mógłby podać takie liczby z zestawu 11 : 6 i 5 i co wtedy? nie wygeneruje żadnego pinu bo uklad 6 5 jest niemożliwy?
trzeba było powiedzieć że tylko w kolejności rosnącej można podawać liczby wtedy to będzie zupełnie inna rozmowa bo sobie walnę inny algorytm
ale przy tak sformułowanej treści zadania nie możesz mieć pretensji że tak znacząco podniosłą się ilość możliwych pinów
z twojego rozumowania wynika że niemożliwe jest stworzenie pinu z róznych trzech cyfr jeżeli pierwszą z nich jest 10 (nadal rozmawiamy o tym przypadku z 11)
jest podane tylko że jest branych m różnych liczb. więc gdzie tutaj info o tym że nie mogą być piny w kolejności malejącej czy pomieszanej. ma być tylko zachowana kolejność z wejscia.
Użytkownik j-mail edytował ten post 17 marzec 2005, 22:16
przeczytaj jeszcze raz tresc :] najpierw wyjasnione jest co to sa piny jana, z warunkow zadania mozna wywnioskowac dlaczego na wejsciu pojawia sie tylko ilosc liczb do tworzenia pinow a nie same liczby... jesli by ktos przeoczyl to daje przyklady :]
gdy liczby do tworzenia pinow bylyby takie: 200 50 100
to mozna wygenerowac piny:
200 50 100 100
200 200 50 100
50 100 100 100
a nie mozna wygenerowac pinow:
50 200 200 200
50 100 200 200
50 200 100 50
poniewaz liczby do tworzenia pinow sa w innej kolejnosci niz w pinie:
i.e. w 50 200 200 200 liczba piecdziesiat jest przed dwiescie a mialy byc w kolejnosci zadanej 200 50 100...
czyli w przypadku m=11 i zakladajac ze mamy do tworzenia pinow takie liczby 1,2,3,4,5,6,7,8,9,10,11
jezeli wezmiesz do pinu liczbe 5 to na kolejnych pozycjach moze byc tylko liczba 5 albo nastepne 6,7,8,... ale nie sa istotne ich wartosci, tylko miejsce.
gdyby liczby byly tak ulozone: 11,10,9,8,7,6,5,4,3,2,1 to biorac do pinu liczbe 7 na kolejnych pozycjach pinu moglaby znalezc sie liczba 7,6,5,4,... ale nie 11 bo zostalo ono podane przed 7.
z tresci zadania to wynika :]
ok. ale to nadal trzeba by pomnożyć przez ilośc permutacji na jakie możęmy te liczby podzielić bo nie jest powiedziane w jakiej kolejności one są wstawiane więc nadal musimy rozważyć przypadek gdzie liczby są podawane 1 2 3 jak również 2 1 3 jak również 3 2 1 i dalej 1 3 2, 3 1 2, 3 2 1
co ty na to?
no chyba nie możesz zaprzeczyć???
chociaż jak znam życie to pewnie zaprzeczysz.
mówię o kombinatoryce
powiedziałeś że podaję ile liczb zostało wpisanych. gdybym podawał jakie liczby po kolei to się z tobą zgodzę. bo wtedy rzeczywiście jest tak jak mówisz. ale w zadaniu jest tylko ilość liczb więc muszę rozważyć wszelkie możliwe ich początkowe ustawienia. nie mam racji?
w calym tym zamieszaniu zapomnialem pogratulowac oficjalnie Favex'owi :]
w pm'ie z 17.03.2005 21:16 przedstawil poprawne rozwiazanie o zlozonosci O(1) :D u mnie jest marna O(n) :] ale w dozwolonym czasie sie miesci :)
takze wielkie wyrazy uznania i gratulacje :)
ok. ale to nadal trzeba by pomnożyć przez ilośc permutacji na jakie możęmy te liczby podzielić bo nie jest powiedziane w jakiej kolejności one są wstawiane więc nadal musimy rozważyć przypadek gdzie liczby są podawane 1 2 3 jak również 2 1 3 jak również 3 2 1 i dalej 1 3 2, 3 1 2, 3 2 1
co ty na to?
no chyba nie możesz zaprzeczyć???
chociaż jak znam życie to pewnie zaprzeczysz.
mówię o kombinatoryce
powiedziałeś że podaję ile liczb zostało wpisanych. gdybym podawał jakie liczby po kolei to się z tobą zgodzę. bo wtedy rzeczywiście jest tak jak mówisz. ale w zadaniu jest tylko ilość liczb więc muszę rozważyć wszelkie możliwe ich początkowe ustawienia. nie mam racji?
nie masz ;) z prostej przyczyny: kolejnosc liczb jest z gory ustalona przez Jana i nie wplywa na ilosc "Pinow Jana" jaka mozna z nich wygenerowac. dlatego aby uproscic wejscie podawana jest tylko moc zbioru liczb do generowania a nie same liczby.
w przykladzie ktorym podajesz niezaleznie czy liczby do generowania pinow Jana beda 1 2 3, czy tez 2 1 3, czy 3 2 1 czy tez 1000 2000 3000 to ilosc Pinow Jana z kazdego takiego zestawu wynosi 15.
nie moge przyznac sie do bledu w zadaniu, bo go nie ma ;)
sa tacy co zrozumieli zadanie i tacy co musza dopiero zrozumiec :] ja dostalem zadanko, rozwiazalem, ubarwilem troszke ;) i poslalem dalej, cobyscie tez mogli sie poglowic troszke ;)
taaaak ustalana przez Jana. doskonałe. a skąd masz pewnosc w jakiej je poda??
nieważne. spadam stąd. podziwiam. szczerze podziwiam.
wyszło że lame jestem. no cóż. zdarza się.
masz rację pepsi. nie dałem rady rozwiązać bo jestem na to za głupi.
Nie wiem jak zrobiliście, aby taki program wykonywał się w 1s :blink: . Zastosowałem metodę brute-force, więc chyba nikt się nie obrazi jak zapodam kod:
... pins+=m; for(int i=0; i<m-1; ++i) for(int j=i+1; j<m; ++j) pins+=3; for(int i=0; i<m-2; ++i) for(int j=i+1; j<m-1; ++j) for(int k=j+1; k<m; ++k) pins+=3; for(int i=0; i<m-3; ++i) for(int j=i+1; j<m-2; ++j) for(int k=j+1; k<m-1; ++k) for(int l=k+1; l<m; ++l) ++pins; ...
No więc nie działa to zbyt szybko... Jeszcze jedno-jak w czystym c++ oznacza się liczbę 64-bitową(na maszynach 32-bit oczywiście)? Ja na kompliatorze borlanda skorzystałem z __int64. pepsi, mam nadziję że szybciej rzucisz dobry kod, bo po 1. nie mogę się doczekać, a po drugie nie widać żeby wiele osób to rozwiązywało.
No więc nie działa to zbyt szybko... Jeszcze jedno-jak w czystym c++ oznacza się liczbę 64-bitową(na maszynach 32-bit oczywiście)? Ja na kompliatorze borlanda skorzystałem z __int64. niektore kompilatory wspieraja __int64, na innych stosujesz long long
pepsi, mam nadziję że szybciej rzucisz dobry kod, bo po 1. nie mogę się doczekać, a po drugie nie widać żeby wiele osób to rozwiązywało. spoko :) powiedzmy po weekendzie wkleje swoje rozwiazanie, mam nadzieje ze FaveX tez sie podzieli :P
w calym tym zamieszaniu zapomnialem pogratulowac oficjalnie Favex'owi :]
w pm'ie z 17.03.2005 21:16 przedstawil poprawne rozwiazanie o zlozonosci O(1) :D u mnie jest marna O(n) :] ale w dozwolonym czasie sie miesci :)
takze wielkie wyrazy uznania i gratulacje :)
nu widze, ze Kodie dolacza do klubu :) wyniki takie same jak u mnie, a ze raczej nie liczyles na kartce ;) to twoje rozwiazanie jest dobre :)
gratulacje !!! :D
ja swoj kodzik wkleje po weekendzie, wiec mozesz sie wtedy tez dorzucic :)
widze, ze tylko ekipa z pa tylko podejmuje wyzwania programistyczne :)
moze ktos jeszcze przez weekend sprobuje??? :)
Wyniki: 18000: 4375458148504500 18001: 4376430472537501 18002: 4377402958615505 18003: 4378375606756515 18004: 4379348416978535 18005: 4380321389299570 18006: 4381294523737626 18007: 4382267820310710 18008: 4383241279036830 18009: 4384214899933995
Powinny być dobre, bo dla 17000 - 17009 otrzymałem to samo, co Kodie :-).
Co do limitów to program wymaga 8 bajtów pamięci i wykonuje 4 mnożenia i sześć dodawań (O(1)), więc powinien się zmieścić :-). Jeżeli ktoś chce, to mogę wysłać kod na PW (11 linii :-)).