[PJWSTK] ASD – Kolokwium 2 – Rozwiązanie

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;
}