[PJWSTK] ASD – jesień 2015 – Zadanie 1 – Rozwiązanie

PRINTRO0 podciąg monotoniczny i spójny

ZADANIE NA 15.11.2015, WIĘC JESZCZE MACIE PONAD 2 TYGODNIE NA PRZEROBIENIE GO NA TYSIĄC SPOSOBÓW, ŻEBY NIE ZOSTAĆ WYKRYTYM PRZEZ ANTY-PLAGIATORA!

EDIT:

Dokładny (łopatologiczny) opis jak działa wczytywanie liczb z wejścia:
http://pastebin.com/YRNwr8rX

/*
48 - znak ASCII (wczytany jako liczba od 0 do 255) odpowiadający 0 ( https://pl.wikipedia.org/wiki/ASCII )
57 - znak ASCII odpowiadający 9
*/


//#define gc getchar_unlocked
#define gc getchar
 
int liczbaNaWejsciu;
 
/*
użycie 'inline' >daje szanse< na szybsze wykonanie programu ( https://pl.wikibooks.org/wiki/C%2B%2B/Funkcje_inline )
wywołanie funkcji to operacje na stosie [chyba], lepiej ich oszczędzić i wkleić kod funkcji w miejsce wywołania,
ale dla czytelności lepiej trzymać fragmenty kodu w funkcjach
 
'daje szanse' dlatego, że kompilatory same zazwyczaj decydują które funkcje skopiować i wkleić [inline],
a które zostawić oddzielnie i odwoływać się do ich przez adres w pamięci
*/

/*
ta funkcja zapisuje do zmiennej (zdefiniowanej wyżej) 'liczbaNaWejsciu' wartość kolejnej liczby z wejścia
na wejściu jest np. '12 43 32', ta funkcja z wejścia wczyta '12' (i zamieni z 'liter' na 'int') do zmiennej 'liczbaNaWejsciu',
a na wejściu zostanie do wczytania '43 32'
*/
inline void pobierzNastepnaLiczbeZWejscia()
{
    /*
    'register' daje do zrozumienia kompilatorowi, że potrzebujemy szybkiego dostępu do tej zmiennej,
    ale nie będziemy potrzebowali jej adresu [w RAM], dlatego zamiast trzymać zmienną w RAMie wystarczy nam
    dostęp do niej w 'rejestrze procesora' (setki tysięcy razy szybszy od RAM)
    */
	/*
	gc() - getchar() - wczytuje 1 znak z wejścia (tak wcześniej zdefiniowałem - parę linijek wyżej) do zmiennej typu 'int'
		wczytana wartość to liczba od 0 do 255 LUB 'znak EOF' ['end of file' - koniec pliku/wejścia] który zazwyczaj wynosi -1
		
		'getchar' działa na każdym systemie i w każdym kompilatorze,
		więc jest dobre do testów w domu (Visual Studio może się coś czepiać o 'bezpieczeństwo', ale to kwestia konfiguracji),
		na spox.spoj.pl [i linux] można tą funkcję [definicję] podmienić z 'getchar_unlocked' co skróci wczytywanie danych około 4 razy
	*/
    register int znakZWejscia = gc();

	/*
	resetujemy liczbę na wejściu
	*/
    liczbaNaWejsciu = 0;
 
	/*
	ta pętla 'zjada' znaki które nie są cyframi (inne niż znaki ASCII 48-57 [czyli cyfry 0-9])
	nie ważne czy liczby na wejściu są oddzielone spacjami, nowymi liniami czy czym kolwiek innym
	*/
    for( ; ((znakZWejscia < 48 || znakZWejscia > 57)); znakZWejscia = gc() );

	/*
	ta pętla wczytuje liczby do czasu, aż dojdzie do końca wejścia (EOF) lub innego znaku niż cyfra, więc po wczytaniu jednej liczby 'spacja' przerywa wczytywanie
	WYTŁUMACZENIE ALGORYTMU:
	na wejściu mamy '321', algorytm wczyta to jako 3 cyfry '3', '2' i '1'
	jednak w chwili wczytania '3' nie wiemy ile cyfr zostało i, że te '3' w rzeczywistości będzie '300'

	-----
	Obrót pętli 1:
	na początku:
		liczbaNaWejsciu = 0
		znakZWejscia = 51 ('3' ASCII)
	działanie:
		(na wejściu jest 'znakZWejscia = 51' który odpowiada w ASCII '3' wpisanej z klawiatury)
		mnożymy aktualną wartość 'liczbaNaWejsciu' przez 10,
		bo wczytanie każdej kolejnej cyfry znaczy,
		że wszystkie wcześniej wczytane są 10 razy większe - dlatego po wczytaniu 3 cyfr '321' dojdzie do tego, ze '3' wczytane na początku będzie wynosić 300!
		liczbaNaWejsciu = 0 * 2 + 0 * 8 + 51 - 48
	po zakończeniu:
		liczbaNaWejsciu = 3
		znakZWejscia = 51
	-----
	Obrót pętli 2:
	na początku:
		liczbaNaWejsciu = 3
		znakZWejscia = 50 ('2' ASCII)
	działanie:
		liczbaNaWejsciu = 3 * 2 + 3 * 8 + 50 - 48
	po zakończeniu:
		liczbaNaWejsciu = 32
		znakZWejscia = 50
	-----
	Obrót pętli 3:
	na początku:
		liczbaNaWejsciu = 32
		znakZWejscia = 49 ('1' ASCII)
	działanie:
		liczbaNaWejsciu = 32 * 2 + 32 * 8 + 49 - 48
	po zakończeniu:
		liczbaNaWejsciu = 321
		znakZWejscia = 49
	-----
	KONIEC WCZYTYWANIA
	*/
    for( ;znakZWejscia >= 48 && znakZWejscia <= 57; znakZWejscia = gc() )
    {
        /*
		mnożymy aktualną liczbę przez 10 (dzięki 2 operacją bitowym):
		------
		<< 1 to przesunięcie bitowe o 1 w lewo = mnożenie przez 2
		<< 3 to przesunięcie bitowe o 3 w lewo = mnożenie przez 8
		więc mnożymy przez 2 i 8, a potem sumujemy wyniki tych mnożeń
		(rozdzielność mnożenia względem dodawania czy coś takiego)
		------
		potem dodajemy znak z wejścia i odejmujemy 48
		*/
        liczbaNaWejsciu = (liczbaNaWejsciu << 1) + (liczbaNaWejsciu << 3) + znakZWejscia - 48;
    }
}

Rozważmy losowy ciąg liczb naturalnych C. Podaj długość oraz sumę elementów najdłuższego możliwego monotonicznego i spójnego zarazem podciągu ciągu C. W przypadku niejednoznaczności odpowiedzi wskaż pierwszy taki ciąg począwszy od lewej strony.

 

WEJŚCIE
Wiersz opisujący elementy ciągu C oddzielone znakiem odstępu (kod ASCII 32) zakończony znakiem końca pliku (EOF).

WYJŚCIE
Wiersz zawierający dwie liczby będące rozwiązaniem postawionego problemu oddzielone znakiem odstępu.

OGRANICZENIA
Długość ciągu C dodatnia i ograniczona przez 10^7, elementy rozważanego ciągu zawarte w przedziale wartości[0,10^9].

LIMITY
Oczekiwana złożoność czasowa rzędu O(n). Oczekiwana złożoność pamięciowa rzędu O(1).

PRZYKŁAD 1

wejście:
8 4 2 3 2

wyjście:
3 14

/* KOMENTARZ DO ROZWIĄZANIA
Poszukiwany podciąg monotonicznie malejący to: 8 4 2.
Długość i suma elementów wskazanego ciągu są równe odpowiednio 3 oraz 14. */

PRZYKŁAD 2

wejście:
1 1 7 3 2 0 0 4 5 5 6 2 1

wyjście:
6 20

PRZYKŁAD 3

wejście:
65 87 47 5 12 74 25 32 78 44 40 77 85 4 29 57 55 79 31 63 84 66 62 41 52 36 82 86 6 98 63 65 14 57 75 14 74 15 41 88 27 75 6 78 98 78 22 77 68 74 92 47 30 44 40 52 70 66 17 60 47 97 34 37 23 69 56 57 3 45 7 76 18 35 24 73 47 77 1 84 92 54 18 98 84 36 66 71 92 13 77 28 75 24 46 67 4 63 82 1

wyjście:
4 253

Rozwiązanie z komentarzami opisującymi dlaczego, co i gdzie:

#include <stdio.h>

//#define gc getchar_unlocked
#define gc getchar

int liczbaNaWejsciu;

/*
użycie 'inline' >daje szanse< na szybsze wykonanie programu ( https://pl.wikibooks.org/wiki/C%2B%2B/Funkcje_inline )
wywołanie funkcji to operacje na stosie [chyba], lepiej ich oszczędzić i wkleić kod funkcji w miejsce wywołania,
ale dla czytelności lepiej trzymać fragmenty kodu w funkcjach

'daje szanse' dlatego, że kompilatory same zazwyczaj decydują które funkcje skopiować i wkleić [inline],
a które zostawić oddzielnie i odwoływać się do ich przez adres w pamięci
*/
inline void pobierzNastepnaLiczbeZWejscia()
{
	/*
	'register' daje do zrozumienia kompilatorowi, że potrzebujemy szybkiego dostępu do tej zmiennej,
	ale nie będziemy potrzebowali jej adresu [w RAM], dlatego zamiast trzymać zmienną w RAMie wystarczy nam
	dostęp do niej w 'rejestrze procesora' (setki tysięcy razy szybszy od RAM)
	*/
    register int znakZWejscia = gc();
    liczbaNaWejsciu = 0;

    for( ; ((znakZWejscia < 48 || znakZWejscia > 57)); znakZWejscia = gc() );
 
    for( ;znakZWejscia > 47 && znakZWejscia < 58; znakZWejscia = gc() )
	{
		// mnozymy aktualna liczba przez 10 (dzięki 2 operacją bitowym) i
		// dodajemy cyfrę z wejścia (znaki ASCII 0-9 zaczynają się od 48 znaku)
        liczbaNaWejsciu = (liczbaNaWejsciu << 1) + (liczbaNaWejsciu << 3) + znakZWejscia - 48;
    }
}

// użycie 'inline' daje szanse na szybsze wykonanie programu ( https://pl.wikibooks.org/wiki/C%2B%2B/Funkcje_inline )
inline bool czyJestNastepnaLiczbaNaWejsciu()
{
    return !feof(stdin);
}

/*
"elementy rozważanego ciągu zawarte w przedziale wartości [0,10^9]" - wystarczą nam INT dla elementów,
ale do przechowywania sumy elementow potrzeba LONG [0,10^18] (w C 'long long int')
*/
int main()
{
	// "Długość ciągu C dodatnia i ograniczona przez 10^7" - na pewno bedzie 1 liczba do wczytania
	// wczytujemy pierwszą liczbę z wejścia
    pobierzNastepnaLiczbeZWejscia();

	/*
	ciągi monotoniczne dzielimy na ( https://pl.wikipedia.org/wiki/Funkcja_monotoniczna ):
	rosnące
	malejące
	stałe
	nierosnące - zawiera w sobie ciągi malejące i stałe
	niemalejące - zawiera w sobie ciągi rosnące i stałe

	ze względu na to, że chcemy znaleźć najdłuższe ciągi,
	możemy podzielić ciąg który otrzymamy na wejściu na 2 rodzaje:
	nierosnące
	niemalejące
	
	pamiętając jednak o tym,
	że ciąg 'stały' może być końcem ciągu nierosnącego i za razem początekim ciągu niemalejącego i na odwrót
	*/

	// czy aktualnie ciąg rośnie czy maleje, wartość początkowa bez znaczenia
	bool czyNiemalejacy = true;

	// ostatnio wczytana liczba, potrzebna do sprawdzenia czy ciąg rośnie/maleje/jest stały
	long long int poprzedniaLiczbaNaWejsciu = liczbaNaWejsciu;

	// długość ciągu 'stałęgo', po wczytaniu pierwszej liczby mamy ciąg stały od długości 1
	int dlugoscCiaguStalego = 1;

	// aktualna długość podciągu, po wczytaniu pierwszej liczby mamy ciąg stały od długości 1
	int dlugoscAktualnegoCiagu = 1;
	// suma elementów aktualnego podciągu, po wczytaniu pierwszej liczby jest równa jej wartości
	long long int sumaElementowAktualnegoCiagu = poprzedniaLiczbaNaWejsciu;

	// maksymalne wartości znalezionego podciągu
	int maksymalnaDlugoscPodciaguMonotonicznego = 1;
	long long int sumaElementowCiaguMaksymalnejDlugosci = poprzedniaLiczbaNaWejsciu;



    while(czyJestNastepnaLiczbaNaWejsciu())
    {
        pobierzNastepnaLiczbeZWejscia();

		// jeśli ciąg rośnie
        if(liczbaNaWejsciu > poprzedniaLiczbaNaWejsciu)
        {
        	// jeśli wcześniej też rósł
        	if(czyNiemalejacy)
        	{
				// dodajmy aktualną liczbę do sumy aktualnego ciągu
				sumaElementowAktualnegoCiagu += liczbaNaWejsciu;
				// zwiększmy długość aktualnego ciągu o 1
        		dlugoscAktualnegoCiagu++;
			}
			// jeśli wcześniej malał
			else
			{
        		// jeśli wcześniej malał, a teraz rośnie to trzeba sprawdzić czy ostatni podciąg nie jest najdłuższy
				if(dlugoscAktualnegoCiagu > maksymalnaDlugoscPodciaguMonotonicznego)
				{
					maksymalnaDlugoscPodciaguMonotonicznego = dlugoscAktualnegoCiagu;
					sumaElementowCiaguMaksymalnejDlugosci = sumaElementowAktualnegoCiagu;
				}
				// zapamiętujemy, że teraz rośnie
				czyNiemalejacy = !czyNiemalejacy;
				// dodajemy sumę elementów poprzedzającego ciągu stałego i aktualną wartość
				sumaElementowAktualnegoCiagu = dlugoscCiaguStalego * poprzedniaLiczbaNaWejsciu + liczbaNaWejsciu;
				// aktualna długość ciągu to długość poprzedzającego ciągu stałego plus 1
				dlugoscAktualnegoCiagu = dlugoscCiaguStalego + 1;
			}
        	dlugoscCiaguStalego = 1;
		}
		// jeśli ciąg maleje
        else if(liczbaNaWejsciu < poprzedniaLiczbaNaWejsciu)
        {
        	// jeśli wcześniej rósł
        	if(czyNiemalejacy)
        	{
        		// jeśli wcześniej rósł, a teraz maleje to trzeba sprawdzić czy ostatni podciąg nie jest najdłuższy
				if(dlugoscAktualnegoCiagu > maksymalnaDlugoscPodciaguMonotonicznego)
				{
					maksymalnaDlugoscPodciaguMonotonicznego = dlugoscAktualnegoCiagu;
					sumaElementowCiaguMaksymalnejDlugosci = sumaElementowAktualnegoCiagu;
				}
				// zapamiętujemy, że teraz maleje
				czyNiemalejacy = !czyNiemalejacy;
				// dodajemy sumę elementów poprzedzającego ciągu stałego i aktualną wartość
				sumaElementowAktualnegoCiagu = dlugoscCiaguStalego * poprzedniaLiczbaNaWejsciu + liczbaNaWejsciu;
				// aktualna długość ciągu to długość poprzedzającego ciągu stałego plus 1
				dlugoscAktualnegoCiagu = dlugoscCiaguStalego + 1;
			}
			// jeśli wcześniej malał
			else
			{
				// dodajmy aktualną liczbę do sumy aktualnego ciągu
				sumaElementowAktualnegoCiagu += liczbaNaWejsciu;
				// zwiększmy długość aktualnego ciągu o 1
        		dlugoscAktualnegoCiagu++;
			}
        	dlugoscCiaguStalego = 1;
		}
		// jeśli ciąg jest stały
		else
		{
			/*
			zwiększamy długość ciągu stałego
			(potrzebna do obliczenia ilości i sumy elementów poprzedzających,
			w przypadku zmiany z rosnącego na malejący lub odwrotnie)
			*/
			dlugoscCiaguStalego++;
			
			/*
			podciąg 'stały' może być elementem ciągu nierosnącego/niemalejącego
			'dlugoscCiaguStalego' trzymamy na wypadek gdyby ciąg zmienił kierunek
			'dlugoscAktualnegoCiagu' i 'sumaElementowAktualnegoCiagu' zwiększamy,
			żeby nie musieć tego dodatkowo obliczać w warunkach '>' i '<' oraz sprawdzać po 'while'
			*/

			// zwiększamy długość aktualnego ciągu
			dlugoscAktualnegoCiagu++;
			// zwiększamy sumę elementów aktualnego ciągu
			sumaElementowAktualnegoCiagu += liczbaNaWejsciu;
		}

		poprzedniaLiczbaNaWejsciu = liczbaNaWejsciu;

    }

	// sprawdzamy czy ciąg na którym zakończyły się dane nie jest najdłuższy
	if(dlugoscAktualnegoCiagu > maksymalnaDlugoscPodciaguMonotonicznego)
	{
		maksymalnaDlugoscPodciaguMonotonicznego = dlugoscAktualnegoCiagu;
		sumaElementowCiaguMaksymalnejDlugosci = sumaElementowAktualnegoCiagu;
	}

	// wyświetlamy wynik, %d = int, %lld = long long int
	// użycie '%d' dla 'long long int' wyświetliło by dziwną lub zmniejszoną wartość nie pokazując żadnego błedu
    printf("%d %lld", maksymalnaDlugoscPodciaguMonotonicznego, sumaElementowCiaguMaksymalnejDlugosci);
    return 0;
}

Link do kodu do pobrania:
http://paste.ots.me/562724

Rozwiązanie nie wysyłane nigdy przez nikogo na spoxa! Nie testowane na spox, więc nie mogę powiedzieć jakie czasy/ile punktów dostanie.

Teoretycznie w 100% zgodne poleceniem i bardzo wydajne.

Ten wpis został opublikowany w kategorii PJWSTK - ASD. Dodaj zakładkę do bezpośredniego odnośnika.

4 odpowiedzi na [PJWSTK] ASD – jesień 2015 – Zadanie 1 – Rozwiązanie

  1. Mr No pisze:

    Mam problem z wprowadzaniem danych z konsoli po skompilowanym programie – pętla nie chce się zakończyć i nie przez to nie wyświetla mi wyniku. na koniec kombinacja ctrl + d lub ctrl + z nie pomaga. Co zrobić, żeby ta pętla się kończyła? Może to wina, że kompiluję na Windows – program Code blocks.

    • Jerzy Skalski pisze:

      Problemów z testowaniem programów gdzie nie ma ustalonej liczby argumentów jest dużo [wiele zadań na spoxa ma w treści 'pierwszy podany int to ilość elementów do wczytania’ i wtedy nie ma problemu].

      Co do problemu tu opisanego to w przypadku, gdy program czeka na 'koniec pliku’ [EOF jak w tym zadaniu] należy mu przesłać dane z pliku. Czyli w katalogu w którym jest skompilowany plik [zadanie.exe] należy otworzyć konsole (prawy przycisk myszki na folderze trzymając SHIFT wyświetla opcje 'Otwórz okno poleceń tutaj’) i odpalić program przekazując mu zawartość pliku:

      zadanie.exe < nazwaPliku.txt Do pliku 'nazwaPliku.txt' należy wkleić to co jest na spoxie w testowych danych. Może wtedy wystąpić inny problem: często na końcu jest dodana spacja, a najczęściej problemem jest jakiś znak nowej linii na końcu [miałem już przypadki, że edytor tekstu dodawał znaki przy zapisie bez żadnej informacji na ten temat]. Należy się upewnić, że po ostatniej cyfrze nie ma już ani jednego znaku, inaczej program pomyśli, że jest jeszcze coś do wczytania i będzie czekał, aż pojawi się jakaś cyfra [będzie dostawał znak 'koniec pliku' - znak o specjalnym numerze -1] i zawiesi się na pętli w 26 linijce programu.

  2. Pat pisze:

    Witam, czy udziela Pan korepetycji z ASD? Proszę o kontakt mailowy. Z góry dziękuję.

    • Jerzy Skalski pisze:

      Myślałem nad tym, ale czy z korepetycji można się utrzymać? Jako bezrobotny informatyk żyje mi się całkiem wygodnie od kilku miesięcy 🙂

Dodaj komentarz

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