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.
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.
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.
Witam, czy udziela Pan korepetycji z ASD? Proszę o kontakt mailowy. Z góry dziękuję.
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 🙂