[PJWSTK] ASD – Kolokwium 2 – Rozwiązanie

Opublikowano 30 października 2012, autor: Jerzy Skalski

Drugie zadanie z ASD:

Rozważmy dowolny indeksowany ciąg liczb naturlanych C, dla którego definiujemy pojęcie wskaźnika aktualnej pozycji POS. Dalej wprowadzamy dwie operacje na elementach tego ciągu:

R() – usunięcie elementu c ciągu o indeksie POS+1, następnie przesunięcie wskaźnika POS o c elementów w prawo,
X() – wstawienie tuż po (pozycja POS+1) elemencie c ciągu o indeksie POS elementu o wartości c-1, następnie przesunięcie wskaźnika POS o c elementów w prawo.
Wyznacz postać ciagu wejściowego C po t-krotnym wykonaniu schematu operacji R() i X():

jeżeli elementu ciągu o indeksie POS jest liczbą:
parzystą, to wykonaj operację R(),
nieparzystą, to wykonaj operację X(),
przyjmując, że:

początkowo wskaźnik POS wskazuje na pierwszy element ciągu wejściowego (jeżeli taki istnieje),
jeżeli zachodzi taka konieczność przesuwanie wskaźnika POS w prawo odbywaja się w sposób cykliczny względem elementów ciągu C.
Wejście

Wierszy zawiera kolejno:

liczbę definiująca krotność t powtórzeń schematu operacji R() i X() zakończoną znakiem odstępu/spacji (ASCII kod 32),
elementy ciągu oddzielone znakiem odstępu/spacji i zakończone znakiem końca pliku (EOF).
Długość początkowa ciągu C zawarta w przedziale [0,10^6]. Liczba t powtórzeń schamatu operacji R() i X() ograniczona przez 10^6. Zakres przesunięcia wskaźnika POS w prawo określony przedziałem [0,10^9].

Wyjście

Wiersz zakończony znakiem nowego wiersza/linii (ASCII kod 10) zawierajacy ciąg liczb naturalnych będący rozwiązaniem postawionego problemu wypisany cyklicznie, jeżeli zachodzi taka konieczność, począwszy od elementu ciągu wynikowego znajdującego się na pozycji wskazywanej przez wskaźnik POS w kierunku w prawo. Elementy ciągu wynikowego oddzielone znakiem odstępu/spacji (ASCII kod 32).

Złożoności i limity

Złożoność czasowa O(tn), złożoność pamięciowa O(n), gdzie n jest długością początkową ciągu C, t krotnością powtórzeń schamatu operacji R() i X(). Fizyczny limit pamięci zależny od rozmiaru danych wejściowych i ograniczony przez 12(n+t) B + 1 KB.

Przykład 1

Wejście:
3 1 2 3
Wyjście:
0 0 3 1

Przykład 2

Wejście:
8 5 1 2 3
Wyjście:
2 2

A tutaj kodzik w C++:

#include <stdio.h>
#include <iostream>

struct C
{
  unsigned int c;
  C* next;
  C(unsigned int value)
  {
    c = value;
    next = NULL;
  }
};

int main()
{
  unsigned int rounds;
  fscanf(stdin, "%u", &rounds);
  if(!feof(stdin))
  {
    unsigned int elements = 0;
    unsigned int tmp;
    fscanf(stdin, "%u", &tmp);
    C* first = new C(tmp);
    elements++;
    C* current = first;
    while(std::cin >> tmp)
    {
      current->next = new C(tmp);
      current = current->next;
      elements++;
    }
    current->next = first;
    current = first;
    for(int i = 0; i < rounds; i++)
    {
      if(elements == 0)
        break;
      unsigned int value;
      if(current->c & 1)
      {
        value = current->c;
        C* newC = new C(value-1);
        newC->next = current->next;
        current->next = newC;
        elements++;
      }
      else
      {
        value = current->next->c;
        C* toDelete = current->next;
        current->next = toDelete->next;
        delete toDelete;
        elements--;
      }
      if(elements > 0)
      {
        value = value % elements;
        for(int ii = 0; ii < value; ii++)
        {
          current = current->next;
        }
      }
    }
    if(elements > 0)
    {
      first = current;
      fprintf(stdout, "%u", current->c);
      current = current->next;
      while(first != current)
      {
        fprintf(stdout, " %u", current->c);
        current = current->next;
      }
    }
  }
  fprintf(stdout, "\n");
  return 0;
}

 

Post Views: 11 672
Ten wpis został opublikowany w kategorii PJWSTK, PJWSTK - ASD. Dodaj zakładkę do bezpośredniego odnośnika.

15 odpowiedzi na [PJWSTK] ASD – Kolokwium 2 – Rozwiązanie

  1. Maciej pisze:
    27 listopada 2013 o 22:46

    chyba coś trefny kod masz przy tym zadaniu ponieważ nie działa nawet dla danych testowych. ja się zastanawiam nad złożonością mojego kodu bo musze ją zmniejszyć.

    Odpowiedz
    • Jerzy Skalski pisze:
      30 listopada 2013 o 02:55

      Musisz zamienić:
      while(!feof(stdin))
      {
      fscanf(stdin, "%u", &tmp);
      current->next = new C(tmp);
      current = current->next;
      elements++;
      }
      na:
      while(std::cin >> tmp)
      {
      current->next = new C(tmp);
      current = current->next;
      elements++;
      }

      I na górze dodać:
      #include <iostream>

      TADAM! 🙂

      Odpowiedz
  2. Jerzy Skalski pisze:
    30 listopada 2013 o 02:04

    Kod działa na 100%. Sprawdzałem z tegorocznymi danymi testowymi (w domu, sam na Spoxa nie wrzucam) i wszystkie wyniki były poprawne.

    Natrafiłem prawdopodobnie na ten sam problem co Ty. Na linux (konkretnie na Ubuntu 12.04 Desktop testowałem) wyniki wychodziły nie poprawne, ale na starym dobrym DevCpp w windows wszystko działa jak należy.

    Jeśli test Ci na Spox’ie nie przechodzi to tam kiedyś (i pewnie teraz) były do wyboru różne wersje kompilatora C++. Może z jakąś starsza zadziała.

    Odpowiedz
  3. Ciekawski pisze:
    23 marca 2014 o 17:38

    Z ciekawości sprawdziłem i niestety w tym roku nie przechodzi żadnego testu na SPOX 🙁
    Coś jest nie tak….

    Odpowiedz
  4. Nie dziala pisze:
    23 marca 2014 o 22:42

    Niestety nie dziala. Żadnego testu nie przechodzi. Starsze wersje kompilatorów też nie pomagają.

    Odpowiedz
    • Jerzy Skalski pisze:
      24 marca 2014 o 18:05

      Wklej treść tegoroczną i dane testowe (możesz do jakiegoś serwisu pastebin.com wysłać i dać linki tylko) to zobaczę czy nie ma różnic, bo rembel wrzuca małe zmiany w treści co semestr, żeby ktoś kto nie ogarnia algorytmu nie zauważył.

      Odpowiedz
  5. Jeremy Clarkson pisze:
    23 marca 2014 o 23:29

    Dziwna sprawa bo jak testuje u siebie lokalnie np w Visual Studio, to dostaje dobre wyniki. Ale jak wrzuce na SPOX to testy 0-3 pokazują błędna odpowiedź. Dla pozostałych 2 przekroczono limit czasu ale to inna bajka. Czy wygląda na to, że dane wejściowe się zmieniły a algorytm ma jakiś błąd ?

    Odpowiedz
  6. What the fuck ? pisze:
    23 marca 2014 o 23:30

    Dlaczego wszystkie komentarze świadczące o tym, że kod nie działa są usuwane ?! Niezła polewka z tej stronki…

    Odpowiedz
    • Jerzy Skalski pisze:
      24 marca 2014 o 17:59

      Może dlatego, że musza być zaakceptowane zanim zostaną wyświetlone na stronie, a ja nie siedzę na kompie cały czas.

      Odpowiedz
  7. kelu pisze:
    30 marca 2014 o 12:34

    Hej,
    A nie masz pomysłu może na zareprezentowanie tego problemu przy pomocy drzewa? Podobno drzewo tutaj przyspiesza do 100 punktów.

    Co do Twojego rozwiązania to masz jakiś błąd, nie chciało mi się wczytywać, ale nawet dla prostych danych testowych 2 9 4 0 przykładowo już daje zły wynik. (powinno dać 9 8 0 a daje 0 9 8)

    Co do reszty leszczy którzy chcą ściągnąć na pałe rozwiązanie to żeby Wam przechodziło na spoxie to musicie przynajmniej wywalić tego entera z końca algorytmu… nie sprawdzałem ale przypuszczam że pare testów przejdzie ten algorytm jeśli się tego entera pozbędzie.

    Pozdrawiam

    Odpowiedz
    • Jerzy Skalski pisze:
      30 marca 2014 o 23:31

      Nie wiem skąd wziąłeś dane '2 9 4 0′ -> '9 8 0′, bo przy zmianie algorytmu, aby takie dane zwracał nie zgadza się żaden przykład z tych podanych tu:
      'Jerzy, tegoroczna treść i przykłady:’
      http://pastebin.com/raw.php?i=5MPTEufw
      [dokładnie zmieniłem operacje 'R’ w linijce 'value = current->next->c;’ na 'value = current->c;’ ]
      W poleceniu jest wszystko jasne:
      – R, usunięcie elementu c ciągu o indeksie POS+1, następnie przesunięcie wskaźnika POS o c elementów w prawo,
      – X, wstawienie tuż po (pozycja POS+1) elemencie c ciągu o indeksie POS elementu o wartości c-1, następnie przesunięcie wskaźnika POS o c elementów w prawo.

      Jeśli parzysta (R) to usuń następny element który nazwiemy sobie 'c’, a potem przesuń od aktualnego elementu o tyle pozycji ile wynosiła wartość 'c’.
      Jeśli nie parzysta (X) to dodaj element, ale przesuń o tyle ile wynosiła wartość elementu aktualnego, a nie tego tworzonego.

      Na wykorzystanie drzewa nie mam pomysłu, ale można coś kombinować z tym fragmentem zadania:
      'Fizyczny limit pamięci zależny od rozmiaru danych wejściowych i ograniczony przez 12(n+t) B + 1 KB’
      Jeśli z 12(n+t)B chodziło o bity to mamy na razie użyte 8b [4b int z wartością i 4b wskaźnik], więc można by jeszcze dodać wskaźnik na element 'poprzedni’. W przypadku wrednych danych (a takie mogą być na spoxie) może być tak, że po liście miliona elementów algorytm leci 999.999 'next’ elementów zamiast sprawdzić, że 'taniej’ było by się cofnąć o jeden element (porównując to z ilością elementów na liście). Przy takich danych wykonujemy jedną operacje wstaw/usuń na milion operacji 'next’, więc większy 'koszt’ operacji wstawiania/usuwania (z dbaniem o odnośnik do 'poprzedni’) nie był by problemem.

      Odpowiedz
      • kelu pisze:
        31 marca 2014 o 23:01

        Hej,
        Musiałem być zaspany, faktycznie z dupy ten przykład dałem 😀 Ja oczywiście samemu to rozwiązałem i robiłem małe „ulepszenia” i akurat porównałem testowe wyniki z Twoimi w złym rozwiązaniu.

        Co do Twojej propozycji to takie rozwiązanie też zaimplementowałem i w zasadzie od razu mi to przyszło do głowy (to ze wskaźnikiem w lewo). Prawdę mówiąc niewiele to daje, jak statystyka mówi powinno to dwukrotnie przyspieszyć i tak właśnie jest (miałem przy prostym algorytmie 0.49 wynik, a przy sprawdzaniu czy przesunąć w lewo czy w prawo mam wynik 0.23).

        Co do rozwiązania na drzewie to Rembelski mówił, że właśnie na drzewie da się to rozwiązać (nie na cyklicznej liście) na 100 punktów tylko, więc dlatego pytam. No cóż, pewnie zostanę z tym co mam chyba że będę miał olśnienie jakieś to się podzielę spostrzeżeniami 😉

        Odpowiedz

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *