POLSKI SPOJ

Jakiś czas temu na stronie WWW pewnego urzędu gminy pojawiło się następujące ogłoszenie:

„Urząd Gminy Szachownica ogłasza przetarg na zakup działek budowlanych i zaprasza wszystkich chętnych do zakupu niezwykle atrakcyjnych gruntów. Licytacji podlegać będą kwadratowe działki (tzw. działki elementarne) o wymiarach 20x20 metrów ułożone na gruntach gminnych w regularną siatkę na kwadratowym obszarze ziemi o boku n działek elementarnych. Dla ułatwienia życia gminnym urzędnikom wszystkie działki ponumerowano kolejnymi liczbami naturalnymi począwszy od 1, a skończywszy na n² i uczyniono to w taki sposób, że działka, która na mapie geodezyjnej położona jest w północno-zachodnim wierzchołku obszaru ma numer 1, w wierzchołku północno-wschodnim numer n, południowo-zachodnim (n-1) * n+1, a w południowo-wschodnim n².

Zainteresowani zakupem działki mogą w zgłosić chęć zakupu więcej niż jednej działki, ale tylko w taki sposób, aby w jednej ofercie licytować dowolnie duży prostokątny obszar złożony z sąsiadujących działek elementarnych. Można oczywiście zgłaszać dowolną liczbę ofert i nie jest przeszkodą to, że obszary kolejnych ofert zazębiają się z poprzednimi – na pewną działkę elementarną zawsze brana jest pod uwagę tylko oferta najwyższa.

Zainteresowani zakupem działki zgłaszają swoje oferty, wysyłając na standardowe wejście Gminnego Systemu Licytacji (GSL) wiersze tekstu zawierające kolejno:

• numer PESEL licytującego (13 cyfr)

• numer działki leżącej w północno-zachodnim wierzchołku licytowanego prostokąta złożonego z wybranych działek elementarnych

• numer działki leżącej w południowo-wschodnim wierzchołku tego samego prostokąta

• deklarowaną cenę zakupu za jedną działkę elementarną

Jeśli pewna oferta ma dotyczyć dotyczy tylko jednej działki, należy podać ten sam numer dla obu deklarowanych wierzchołków.

Każdy oferent może złożyć dowolną liczbę ofert na dowolną liczbę działek i dopuszcza się sytuację, w której licytujący przebija własną ofertę. Złożonych ofert nie wolno wycofywać, a licytację prowadzi się do chwili zarejestrowania przez GSL końca pliku na jego standardowym wejściu.

Jeżeli w odniesieniu do pewnej działki elementarnej złożono co najmniej jedną ofertę, to przypada ona temu oferentowi, który zadeklarował najwyższą cenę. W przypadku równych cen wygrywa oferta złożona wcześniej. Po zakończeniu licytacji GSL opublikuje na swoim standardowym wyjściu tekst obwieszczenia, którego każdy wiersz zawierać będzie następujące informacje:

• PESEL oferenta

• rozdzielone spacjami numery działek przez niego zakupionych, ułożone w kolejności rosnących numerów

• łączna kwota, jaką oferent musi wpłacić do urzędu gminy jako należność za zakupione działki

przy czym wiersze obwieszczenia opublikowane zostaną w kolejności narastania numerów PESEL oferentów.

Oferenci, którzy nie wygrali żadnej działki elementarnej, nie pojawią się na zestawieniu”.

Twoim zadaniem będzie napisanie systemu GSL dla Urzędu Gminy Szachownica.

Polecenie: napisz program, który przeprowadzi operację licytacji działek budowlanych w gminie Szachownica; program powinien odczytać ze standardowego wejścia najpierw liczbę n, oznaczającą liczbę działek elementarnych przypadających na bok obszaru sprzedawanego gruntu, a następnie dowolną, nieznaną z góry, liczbę ofert; po wyczerpaniu danych wejściowych program powinien wygenerować obwieszczenie o wynikach licytacji.

Dane wejściowe: kolejno:

• liczba całkowita n, oznaczająca liczbę działek elementarnych przypadających na bok kwadratu podlegającego sprzedaży
  (n: n >= 1 i n <=10000)

• dowolna liczba wierszy opisujących ofertę w sposób przedstawiony w obwieszczeniu urzędu gminy, czyli zawierających kolejno, rozdzielone spacjami, następujące dane:

  • numer PESEL (13 cyfr dziesiętnych)

  • numer (liczba całkowita) działki leżącej w wierzchołku północno-zachodnim
    (x_nw: x_nw >= 1 i x_nw <= n²)

  • numer (liczba całkowita) działki leżącej w wierzchołku południowo-wschodnim
    (x_se: x_se >= 1 i x_se <= n² i x_se >= x_nw)

  • deklarowana cena (liczba całkowita) za jedną działkę elementarną
    (w: w >=1 i w <= 10000)

     

Dane wyjściowe:

• pewna liczba wierszy opisujących wyniki licytacji w sposób podany w obwieszczeniu urzędu gminy, tzn. zawierajacych kolejno:

  • numer PESEL oferenta
  • numery działek, które wygrał w licytacji (rosnąco)
  • łączną kwotę należności za wylicytowane działki

Przykład:

Wejście:

4

1990050112345 6 11 1000

1980122454321 3 15 1500

1970060198765 11 12 3000

1960123100001 1 1 9000

Wyjście:

1960123100001 1 9000

1970060198765 11 12 6000

1980122454321 3 7 15 4500

1990050112345 6 10 2000

Objaśnienie przykładu

Mamy do czynienia z szesnastoma działkami elementarnymi, ułożonymi jak poniżej:

Oferent o numerze PESEL 1990050112345 (kolor czerwony) zalicytował 1000 zł za działki elementarne w prostokącie od działki 6 do działki 11 – po jego postąpieniu sytuacja przedstawia się następująco:

Oferent o numerze PESEL 1970060198765 (kolor zielony) zalicytował 1500 zł za działki elementarne w prostokącie od działki 3 do działki 15 – widać, że działki 7 i 11 przeszły do jego oferty:

Oferent o numerze PESEL 1970060198765 (kolor niebieski) zalicytował 3000 zł za działki elementarne w prostokącie od działki 11 do działki 12 – działka 11 przeszła do jego oferty:

Oferent o numerze PESEL 1960123100001 (kolor żółty) zalicytował 9000 zł za działkę elementarną nr 1:

Widać już ile działek przypadło każdemu z oferentów – znając kwoty ofert można dla każdego z nich wyliczyć całkowitą należność z wygrane działki.

UWAGA

Termin "numer PESEL" należy rozumieć tylko i wyłącznie jako ciąg dowolnych jedenastu cyfr - w żadnym teście nie wymaga się interpretacji znaczenia jakiegokolwiek podciągu tego numeru, a w szczególności nie bada się poprawności cyfry kontrolnej.