[PJWSTK] ASD – Kolokwium 1 – Rozwiązanie

Rozwiązanie na 100%. Treść:

Rozważmy rodzinę C ciągów rekurencyjnych C{n}, gdzie n jest pewną liczbą naturalną, których elementy zawarte są w zbiorze liczb naturalnych. Dalej i-ty element ciągu C{n} zapisujemy jako C{n}(i) i definiujemy rekurencyjnie w następujący sposób:

• n, dla i=0,
• C{n}(i-1)/2, dla i>0 oraz C{n}(i-1) będącego liczbą parzystą,
• 3C{n}(i-1)+1, dla i>0 oraz C{n}(i-1) będącego liczbą nieparzystą.

Na przykład dla n=7 ciąg C{7} ma postać:

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, …

Sprawdź, czy podany na wejściu ciąg liczba naturalnych jest prefiksem pewnego ciągu z rodziny C. Jeżeli odpowiedź jest twierdząca wypisz na wyjściu OK, w przeciwnym przypadku wypisz sufiks ciagu wejściowego, którego pierwszy element jest zarazem pierwszym elementem tego ciągu, ze względu na który ten że ciąg przstał być prefiksem pewnego ciagu z rodziny C (przykłady poniżej).

Wejście

Wiersz zawierający ciąg liczb naturlanych dodatniej długości i zakończony znakiem końca pliku (EOF). Długość ciągu ograniczona przez 10^9. Elementy ciągu oddzielone znakiem odstępu/spacji (ASCII kod 32) i zawarte w przedziale wartości [0,10^9].

Wyjście

Wiersz zawierajacy słowo OK jeżeli wejście spełnia kryteria założone w zadaniu. W przeciwnym przypadku wiersz zawierający stosowny sufiks ciągu wejściowego. Elementy ciągu oddzielone znakiem odstępu/spacji (ASCII kod 32).

Złożoności i limity

Złożoność czasowa O(n), złożoność pamięciowa O(1), gdzie n jest długością ciągu podanego na wejściu. Fizyczny limit pamięci niezależny od rozmiaru danych wejściowych i ograniczony przez 1 KB.

Przykład 1

Wejście:
64 32 16 8 4 2 1 4 2 1 4
Wyjście:
OK

Przykład 2

Wejście:
7 22 11 34 17 52 26 13 30 20 10 5 17 8 4 1
Wyjście:
30 20 10 5 17 8 4 1

Rozwiązanie w C:

#include 
int main()
{
    int current;
	int next;

	int validInput = 1;
	fscanf(stdin, "%i", &current);
	while(!feof(stdin))
	{
		fscanf(stdin, "%i", &next);
		if(current & 1)
		{
			if(current != (next-1)/3)
			{
				validInput = 0;
				break;
			}
		}
		else if(current != next*2)
		{
			validInput = 0;
			break;
		}
		current = next;
	}

	if(validInput == 1)
	{
		fprintf(stdout, "OK");
	}
	else
	{
		fprintf(stdout, "%i", next);
		while(!feof(stdin))
		{
			fscanf(stdin, "%i", &next);
			fprintf(stdout, " %i", next);
		}
	}
	return 0;
}

Nie było takie trudne co nie? 🙂