Koło olimpijskie

Zajęcia organizacyjne

Celem zajęć na kole olimpijskim jest przygotowanie uczniów do olimpiady informatycznej oraz do wszelkich innych konkursów, w których jest wymagana dobra umiejętność programowania komputerów w języku C++. Zajęcia będą obejmowały zakres materiału, który nie jest nauczany na lekcjach informatyki w szkole średniej. Wymaga zatem od uczestników dużo większej wiedzy od przeciętnego ucznia informatyki.

Zajęcia będą się odbywały w poniedziałki po 7-mej lekcji w sali komputerowej.

Podstawowym środowiskiem programowania będzie pakiet Code::Blocks, który jest ogólnie dostępny i darmowy w Internecie. Co więcej, pakiet ten daje się bez problemów zainstalować w środowisku Linux (takie jest w pracowni) oraz Windows (takie posiadają najczęściej uczniowie w swoich domach).

Przykładowe zadanie:

Opis

Załóżmy, że na stawie unosi się n kaczek tworzących koło. W stawie mieszka również aligator, który uwielbia jeść kaczki. Rozpoczynając od określonej pozycji (kaczka nr 1) aligator liczy w koło i zjada każdą m-tą kaczkę (koło się zamyka w miarę zjadania kaczek). Na przykład, gdy n = 8, a m = 4, to poniższy schemat pokazuje numery kaczek na zewnątrz węzła oraz kolejność ich zjadania wewnątrz węzła:

Pierwsza kaczka zostanie pożarta jako piąta z kolei, drugą kaczkę aligator zje jako czwartą z kolei, itd. Ciąg 5 4 6 1 3 8 7 2 kolejności zjadania kaczek całkowicie określa jadłospis aligatora. Napisz program, który określi ten ciąg dla danych n i m.

Specyfikacja wejścia

Wejście składa się z ciągu wierszy. W każdym wierszu są dwie liczby rozdzielone spacją. Liczby te określają kolejno n - liczbę kaczek (n > 0, n < 100), m - odstęp (m > 0, m < 100). Ostatni wiersz posiada obie liczby n i m równe 0.

Specyfikacja wyjścia

Dla każdego wiersza danych program powinien wypisać wiersz z ciągiem liczb, które określają numery kolejno zjadanych kaczek. Każda liczba na wydruku ma zajmować 3 znaki z cyframi dosuniętymi do prawej krawędzi pola.

Przykładowe dane wejściowe

Przykładowe dane wyjściowe

  5  4  6  1  3  8  7  2

  6  4  1 10  8  2  5  7  3  9

Rozwiązanie dla tablic

Tworzymy tablicę K o maksymalnym rozmiarze. Odczytujemy z wejścia liczbę kaczek n oraz odstęp m. Następnie zerujemy wszystkie komórki tablicy.

Teraz ustawiamy licznik zjedzonych kaczek lk = 0 oraz numer kaczki do zjedzenia nk = n - 1 (jest to ostatnia pozycja w kręgu – chodzi o to, aby odliczanie kaczek rozpoczęło się od następnej, czyli pierwszej w kręgu).

W pętli dopóki lk < n wykonujemy cyklicznie operacje:

Wyznaczamy numer kaczki do zjedzenia. Operacja ta wykonywana jest następująco:
m razy powtarzamy w pętli:
Zwiększamy nk o 1. Jeśli nk = n, to nk = 0. Jeśli K[nk] > 0, to operację powtarzamy (kaczka zjedzona, więc jej pozycję należy pominąć).
W ten sposób nk wskaże kaczkę do zjedzenia.
Zwiększamy lk o 1 (bo aligator zjada wyznaczoną przez nk kaczkę) i w komórce K[nk] umieszczamy lk (w ten sposób określimy, jako która z kolei będzie zjedzona kaczka na tej pozycji).

Dla n = 8 i m = 4:

lk = 0
nk = 7

komórka	0	0	0	1	0	0	0	0
indeks	0	1	2	3	4	5	6	7
				nk

lk = 1
nk = 3

komórka	0	0	0	1	0	0	0	2
indeks	0	1	2	3	4	5	6	7
								nk

lk = 2
nk = 7

komórka	0	0	0	1	3	0	0	2
indeks	0	1	2	3	4	5	6	7
					nk

lk = 3
nk = 4

komórka	0	4	0	1	3	0	0	2
indeks	0	1	2	3	4	5	6	7
		nk

lk = 4
nk = 1

komórka	5	4	0	1	3	0	0	2
indeks	0	1	2	3	4	5	6	7
	nk

lk = 5
nk = 0

komórka	5	4	6	1	3	0	0	2
indeks	0	1	2	3	4	5	6	7
			nk

lk = 6
nk = 2

komórka	5	4	6	1	3	0	7	2
indeks	0	1	2	3	4	5	6	7
							nk

lk = 7
nk = 2

komórka	5	4	6	1	3	8	7	2
indeks	0	1	2	3	4	5	6	7
						nk

lk = 8 - koniec, tablica jest wypełniona.

// Koło Informatyczne I LO w Tarnowie
// (C)2014 mgr Jerzy Wałaszek
// ACM - Jadłospis Aligatora
//-----------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  int K[99],n,m,lk,nk,i;

  while(true)
  {
    cin >> n >> m;    // Odczytujemy liczbę kaczek i krok

    if(!n || !m) break;

    // Zerujemy tablicę

    for(i = 0; i < n; i++) K[i] = 0;

    // Inicjujemy dane

    lk = 0; nk = n - 1;

    // W pętli wyznaczamy kolejno jedzone kaczki

    while(lk < n)
    {
      for(i = 0; i < m; i++)
        do
        {
          nk++;
          if(nk == n) nk = 0;
        } while(K[nk]);

      K[nk] = ++lk;
    }

    // Wyświetlamy zawartość tablicy

    for(i = 0; i < n; i++) cout << setw(3) << K[i];

    cout << endl;
  }
  return 0;
}