[PJWSTK] ASD – Kolokwium 4 – Rozwiązanie

Czwarte zadanie z ASD:

Rozważmy uporządkowany ciąg C różnych liczb naturalnych długości n>0 oraz wybrany element c tego ciągu. Dalej przyjmujemy, że algorytm wyszukiwania binarnego jest zgodny z poniższym (zakładamy indeksowanie elementów ciągu od wartości początkowej 0):

l:=0, r:=n-1, m:=(l+r)/2;

while (C[m]!=c) {
  if (C[m]<c)
    l:=m+1;
  else
    r:=m-1;
  m:=(l+r)/2;
}

Wprowadzamy teraz modyfikacje algorytmu wyszukiwania binarnego polegającą na tym, że w miejsce instrukcji zawartych w wierszach 4-8 w pewnej iteracji rozważanego algorytmu wykonujemy sekwencyjne przeszukanie pozostałego fragmentu ciągu począwszy od pozycji l aż do skutku, tj.

while (C[l]!=c)
  l:=l+1;

m:=l;

Załóżmy, że koszt wykonania algorytmu wszykiwania binarnego (zarówno bez i z w/w modyfikacją) oznaczamy jako COST i definiujemy zależnością:

COST=sqrt(a)div+cmp*

gdzie a jest pewną dodatnią stałą naturalną, sqrt(a) jest funkcją, której rezultatem jest część naturalna z pierwiastka z liczby a oraz div i cmp to odpowiednio liczba operacji dzielenia przez 2 (wiersze 1 i 8) oraz liczba operacji prówniania z elementami ciągu C występujacych w rozważanym algorytmie (wiersze 3 i 4).

Wyznacz najmniejszą możliwą wartość stałej a, dla której wykonanie algorytmu wyszukiwania binarnego z modyfikacją sekwencyjną niezależnie od wybranej iteracji zastosowania tej modyfikacji, prowadzi w każdym przypadku do rozwiązania o koszcie mniejszym niż standardowe wyszukiwanie binarne (tj. algorytm bez modyfikacji sekwencyjnej).

Wejście

Wiersz zawierający ciąg liczb naturlanych oddzielonych znakiem odstępu/spacji (ASCII kod 32) i zakończony znakiem końca pliku (EOF), gdzie:

• pierwszy element ciągu definiuje długość n ciągu C tak, że n zawarte jest w przedziale wartości [1,10^6],
• kolejne elementy ciągu reprezentują elementy właściwe ciagu C i zawarte są w przedziale wartości [0,10^9],
• ostatni element ciągu wejściowego reprezentuje wybrane element c ciągu C.

Wyjście

Wiersz zawierajacy pojedynczą liczbę naturalną nie większą niż 10^9 będącą rozwiązaniem postawionego problemu (wiersz pusty w przypadku braku rozwiązania).

Złożoności i limity

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

Przykład 1

Wejście:

3 1 2 3 3

Wyjście:

9

Przykład 2

Wejście:

10 0 1 2 3 4 5 6 7 8 9 0

Wyjście:

1

Rozwiązanie w C++:

#include <stdio.h>

int main()
{
    int n;
    fscanf(stdin, "%i", &n);
	int* C = new int[n];
	for(int i = 0; i < n; i++)
	{
		fscanf(stdin, "%i", &C[i]);
	}
	int c;
	fscanf(stdin, "%i", &c);
	n--;
	int l = 0;
	int r = n;
	int m = (l + r) / 2;
	int binarneDzielenie = 1;
	int binarnePorownania = 1;
	while(C[m] != c)
	{
		binarnePorownania++;
		if(C[m] < c)
			l = m + 1;
		else
			r = m - 1;
		binarnePorownania++;
		m = (l + r) / 2;
		binarneDzielenie++;
	}
	int indeksWyniku = m;
	l = 0;
	r = n;
	m = (l + r) / 2;
	int minimalneA = 0;
	int sekwencyjneDzielenie = 1;
	int sekwencyjnePorownania = 1;
	while(C[m] != c)
	{	
		sekwencyjnePorownania++;
		int iloscPorownan = sekwencyjnePorownania + indeksWyniku - l + 1;
		int a = ((iloscPorownan - binarnePorownania) / (binarneDzielenie - sekwencyjneDzielenie)) + 1;
		if(a > minimalneA)
			minimalneA = a;
		if(C[m] < c)
			l = m + 1;
		else
			r = m - 1;
		sekwencyjnePorownania++;
		m = (l + r) / 2;
		sekwencyjneDzielenie++;
	}
	fprintf(stdout, "%i", minimalneA * minimalneA);
	return 0;
}