zadanie studenciaka

/*
   Trochę kodu w C/C++
   poziom abstrakcji jest dosyć wysoki.. chodzi o samą ideę rozwiązania
*/
// input: n
// input: tab [a1][b1]
// input: tab [a2][b2]
// input: tab [an][bn]

//////////////////////////////////////////////////////////////////////
// definicja nowego typu danych "pole" zawierającego dwa rekordy typu int
//////////////////////////////////////////////////////////////////////
typedef struct _pole {
   int numer_pola;
   int liczba_pionkow;
} pole;

// lista dwukierunkowa w C++ jest zaimplementowana już w bibliotece STL
// (jeśli mnie pamięć nie myli).. a jeśli nie można z niej korzystać, to trzeba
// zrobić własną implementacje.. gdzieś mogę wygrzebać prawdopodobnie
// implementację listy dwukierunkowej w C, którą kiedyś robiłem i działała

// potrzebna będzie lista dwukierunkowa, której elementy będą typu pole

// do listy dodajemy elementy, które zostają wczytane
// z pliku z danymi wejściowymi

//////////////////////////////////////////////////////////////////////
// Funkcja wykonuje przekształcenia zgodnie z ruchem w lewo
// zdefiniowanym w treści zadania
//////////////////////////////////////////////////////////////////////
void ruch_lewo(*wsk_aktualny_element) {
   if (wsk_aktualny_element.poprzedniElement == NULL) {
       // jeśli nie istnieje poprzednik aktualnie badanego elementu,
       // to trzeba go stworzyć
       pole *nowy_element = new pole;
       // nowemu elementowi przypisujemy numer pola mniejszy o jeden
       // względem badanego elementu
       nowy_element.numer_pola = wsk_aktualny_element.numer_pola - 1;
       nowy_element.liczba_pionkow = 1;
       // ustawiamy elementy w odpowiedniej relacji wzlgędem siebie
       wsk_aktualny_element.poprzedniElement = &nowy_element;
       nowy_element.nastepnyElement = &wsk_aktualny_element;
       // jeśli użyta będzie lista z biblioteki to nie trzeba będzie
       // tego wszystkiego robić ręcznie
       // --
       // w tym momencie wiemy też, że nie istnieje element poprzedzający
       // do dopiero co stworzonego nowego elementu, więc możemy
       // od razu dodać jeszcze jeden, zgodnie z ruchem w lewo
       wsk_aktualny_element = &nowy_element;
       pole *nowy_element = new pole;
       nowy_element.numer_pola = wsk_aktualny_element.numer_pola - 1;
       nowy_element.liczba_pionkow = 1;
       wsk_aktualny_element.poprzedniElement = &nowy_element;
       nowy_element.nastepnyElement = &wsk_aktualny_element;
   }
   else {
       // jeśli element poprzedzający badany element istnieje...
       // ... to sprawdzamy czy ma swojego poprzednika
       if (wsk_aktualny_element.poprzedniElement.poprzedniElement != NULL) {
           // jeśli posiada poprzednika
           // to dodajemy do jego liczby pionków wartość 1
           poprzedniElement = &wsk_aktualny_element.poprzedniElement.poprzedniElement;
           poprzedniElement.liczba_pionkow += 1;
       }
       else { // jeśli nie posiada poprzednika
           // to trzeba go stworzyć...
           pole *nowy_element = new pole;
           nowy_element.numer_pola = wsk_aktualny_element.poprzedniElement.numer_pola - 1;
           nowy_element.liczba_pionkow = 1;
           nowy_element.nastepnyElement = &wsk_aktualny_element.poprzedniElement;
           wsk_aktualny_element.poprzedniElement.poprzedniElement = &nowy_element;
       }
   }
   // zmniejszamy wartość liczby pionków aktualnie badanego elementu
   // o jeden
   wsk_aktualny_element.liczba_pionkow -= 1;
}

//////////////////////////////////////////////////////////////////////
// Funkcja wykonuje przekształcenia zgodnie z ruchem w prawo
// zdefiniowanym w treści zadania
//////////////////////////////////////////////////////////////////////
void ruch_prawo(*wsk_aktualny_element) {
   // jeżeli nie istnieje poprzednik dla aktualnie badanego elementu
   // to trzeba go stworzyć
   if (wsk_aktualny_element.poprzedniElement == NULL) {
       pole *nowy_element = new pole;
       nowy_element.numer_pola = wsk_aktualny_element.numer_pola - 1;
       nowy_element.liczba_pionkow = -1 ;
       wsk_aktualny_element.poprzedniElement = &nowy_element;
       nowy_element.nastepnyElement = &wsk_aktualny_element;
   }
   else { // jeżeli istnieje poprzednik...
       wsk_aktualny_element.poprzedniElement.liczba_pionkow -= 1;
   }

   // jeżeli nie istnieje element następujący po aktualnie badanym elemencie
   // to trzeba go stworzyć
   if (wsk_aktualny_element.nastepnyElement == NULL) {
       pole *nowy_element = new pole;
       nowy_element.numer_pola = wsk_aktualny_element.numer_pola + 1;
       nowy_element.liczba_pionkow = 1;
       wsk_aktualny_element.nastepnyElement = &nowy_element;
       nowy_element.poprzedniElement = &wsk_aktualny_element;
   }
   else { // jeśli istnieje następujący element...
       wsk_aktualny_element.nastepnyElement.liczba_pionkow += 1;
   }
   // zmniejszamy wartość liczby pionków aktualnie badanego elementu
   // o jeden
   wsk_aktualny_element.liczba_pionkow -= 1;
}

//////////////////////////////////////////////////////////////////////
// Funkcja wypisująca wynik końcowy po przekształceniach
//////////////////////////////////////////////////////////////////////
void wypisz_wynik(lista) {
   // funkcja wypisze całą zawartość listy w postaci
   // a1 b1
   // a2 b2
   // .. ..
   // aN bN
   pole *wsk_aktualny_element; // wsk_aktualny element podczas wywołania
                               // funkcji musi wskazywać na pierwszy
                               // element listy
   for(wsk_aktualny_element = &lista; \     // wsk_aktualny_element podczas
                           // inicjalizacji pętli powinien wskazywać
                           // na pierwszy element listy
       wsk_aktualny_element.nastepnyElement != NULL; \// pętla zatrzyma się w momencie,
                           // w którym element, który jest wskazywany przez
                           // wsk_aktualny_element.nextElement będzie pusty
                           // (nie będzie kolejnego elementu w liście)
       wsk_aktualny_element = wsk_aktualny_element.nastepnyElement) {

       printf("%d %d", wsk_aktualny_element.numer_pola, \
              wsk_aktualny_element.liczba_pionkow);
   }
}

//////////////////////////////////////////////////////////////////////
// Inicjalizacja listy danymi wejściowymi
//////////////////////////////////////////////////////////////////////
FILE *f;                        // wskaźnik na deskryptor pliku
f.open('input.txt', 'r');       // otwieramy plik do odczytu
pole *lista = inicjalizuj_liste(); // tutaj trzeba użyć własnej implementacji
                               // lub gotowców z bibliotek
for (i=0; i<n; i++) {
   int input_liczba_pierwsza, input_liczba_druga;  // deklaracja zmiennych
                           // pomocniczych do odczytania danych wejściowych

   fscanf(f, "%d %d", &input_liczba_pierwsza, \    // zczytanie
          &input_liczba_pierwsza);     // pary liczb z pliku wejściowego
   pole *element = new pole;     // tworzenie nowego elementu typu "struct _pole"
   element.numer_pola      = input_liczba_pierwsza;
   element.liczba_pionkow  = input_liczba_druga;
   lista.dodaj_element(&nowy_element); // metoda/funkcja dodawania nowego
                                   // elementu na koniec istniejącej listy
}


// w tym momencie mamy już w pamięci wszystkie dane, których potrzebujemy
// zaczynamy iterację

bool _koniec=false;      // zmienna sterująca pętlą while()

// aczkolwiek spokojnie można by tutaj zrobić pętlę nieskończoną
// ponieważ wiemy w którym momencie powinniśmy skończyć
while (_koniec==false) {

   pole *max_element = &lista; // zakładamy, że pierwszy element listy
                               // ma największą wartość..
   // iterujemy sie po całej liście w poszukiwaniu maximum
   for(wsk_aktualny_element=&lista; wsk_aktualny_element.nastepnyElement != NULL \
       wsk_aktualny_element=wsk_aktualny_element.nastepnyElement;) {

       // jeśli natkniemy się na wartość mniejszą niż zero, to musimy
       // wykonać ruch w lewo dla następnego elementu
       if (wsk_aktualny_element.liczba_pionkow < 0) {
           max_element = wsk_aktualny_element.nastepnyElement;
           break; // opuszczamy pętlę for i wykonujemy ruch w lewo
       }
       // jeśli następny element ma większą liczbe pionków
       // to wyznaczamy nasz max_element i lecimy dalej
       if (wsk_aktualny_element.liczba_pionkow > max_element.liczba_pionkow) {
           max_element = wsk_aktualny_element;
       }
   }
   // jeśli znalezionym maximum jest liczba pionków = 1
   // oznacza to, że skończyliśmy algorytm i możemy wyjśc z pętli while
   if (max_element.liczba_pionkow == 1) {
       _koniec = true;
       break; // wychodzimy z pętli
   }
   // w tym momencie mamy wyznaczone nasze maximum w tej iteracji
   // (tylko jeśli nie nastąpił _koniec)
   if ( _koniec == false) {
       // sprawdzamy, czy poprzedzający element istnieje..
       if (max_element.poprzedniElement != NULL) {
           // jeśli istnieje, to sprawdzamy, czy jego liczba pionków
           // jest mniejsza od zera
           if (max_element.poprzedniElement.liczba_pionkow < 0) {
               // jesli tak, to robimy ruch w lewo
               ruch_lewo(&max_element);
           }
           else { // jeśli liczba pionków poprzedzającego elementu jest większa,
               // lub równa zero, to lecimy z ruchem w prawo

           }
       }
       else { // jeśli poprzedzający element nie istnieje, to robimy ruch w prawo
           ruch_prawo(&max_element);
       }
   }
}

// w tym miejscu możemy już wyświetlić wynik końcowy
wypisz_wynik(&lista);