/*
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);
Comments