[Algorytmy] Bankiet - zadanie z OIG I

spammer
Użytkownik
Użytkownik
Posty: 174
Rejestracja: 15 sty 2009, o 17:28
Płeć: Mężczyzna
Podziękował: 40 razy
Pomógł: 12 razy

[Algorytmy] Bankiet - zadanie z OIG I

Post autor: spammer »

Witam wszystkich matematyków

Od jakiegoś czasu siedzę sobie nad takim jednym zadankiem z 2 etapu I Olimpiady Informatycznej Gimnazjalistów. Oczywiście Olimpiada ta zakończyła się już kilka lat temu także nie usuwajcie tego tematu

Zadanie znajduje się tu :p

I właśnie taka sprawa jest, że nie wiem jak wyliczyć ilość tych stolików. Moglibyście mnie jakoś nakierować?

Z góry dziękuję
Ostatnio zmieniony 10 gru 2013, o 23:15 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
flashion
Użytkownik
Użytkownik
Posty: 113
Rejestracja: 20 sty 2009, o 01:27
Płeć: Mężczyzna
Podziękował: 6 razy
Pomógł: 7 razy

[Algorytmy] Bankiet - zadanie z OIG I

Post autor: flashion »

let's do it.

weźmy podany przykład.
kartka do ręki i piszemy podane ustawienie:

Kod: Zaznacz cały

1. po prawej 4. (gość nr 1 po prawej stronie gościa nr 4 - zapisujemy odwrotnie, bo chcemy, żeby liczby 1, 2, 3... były po lewej, dla lepszej widoczności).
2. po prawej 10
3. po prawej 7
4. po prawej 3
5. po prawej 2
6. po prawej 6
7. po prawej 1
8. po prawej 5
9. po prawej 11
10. po prawej 8
11. po prawej 12
12. po prawej 9
najlepiej powyższe dane zapisać w postaci tabl. wielowymiarowej (czy gosc zostal juz usadzony, nr siedzacego po prawej) albo innego kontenera.

pod lupę bierzemy pierwszego gościa. jego nr zapisujemy w jakiejś zmiennej, np. firstguest.
siedzi on po prawej stronie gościa 4, zatem obecne ust. w stoliku wygląda tak:

Kod: Zaznacz cały

4  |  1
gość 4 po prawej gościa 3:

Kod: Zaznacz cały

3  |  4  |  1
gość 3 po prawej gościa 7:

Kod: Zaznacz cały

7  |  3  |  4  |  1
gość 7 po prawej gościa 1. jak widać, cały czas musimy porównywać gości z firstguest, jeśli numery są równe, to mamy cały stolik.

i tak z każdym kolejnym gościem. należy tylko sprawdzić wcześniej, czy nie został już usadzony.

powodzenia w kodowaniu

poprawny kod w c++:
Ukryta treść:    
Ostatnio zmieniony 20 lut 2009, o 18:26 przez flashion, łącznie zmieniany 1 raz.
spammer
Użytkownik
Użytkownik
Posty: 174
Rejestracja: 15 sty 2009, o 17:28
Płeć: Mężczyzna
Podziękował: 40 razy
Pomógł: 12 razy

[Algorytmy] Bankiet - zadanie z OIG I

Post autor: spammer »

Siemka.

Dzięki za wytłumaczenie teraz widzę, że nie było to takie trudne tylko chyba od złej strony na to patrzyłem
Za kod też dziękuję nie przydał się, ale dzięki
Valiors
Użytkownik
Użytkownik
Posty: 162
Rejestracja: 3 paź 2012, o 17:20
Płeć: Mężczyzna
Podziękował: 68 razy
Pomógł: 3 razy

[Algorytmy] Bankiet - zadanie z OIG I

Post autor: Valiors »

Tutaj można wykorzystać strukturę zbiorów rozłącznych, tzw. find and union. Główna idea polega na tym, aby elementy należące do tego samego zbioru były reprezentowane przez pewną liczbę, tzw. reprezentanta. Po szczegóły udaj się do internetu, ponieważ tam jest wiele artykułów dokładnie to opisujących.
ODPOWIEDZ