[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.

Opublikowano PJWSTK - ASD | 4 komentarze

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

UTP 1 – przykładowe rozwiązanie, wymaga przerobienia przed oddaniem!

POBIERZ WSZYSTKIE PLIKI W .ZIP

Nie mam treści zadania.
Jedynie je widziałem przez parę minut i napisałem potem z pamięci rozwiązanie które jest podobne do wymaganego rozwiązania.
Na pewno znajdziesz tutaj rozwiązanie wszystkich problemów z ‚generics’ (jak użyć w metodzie statycznej, jak i gdzie podawać te wszystkie cholerne T i S).

Wolał bym tego nie pisać po jednym roku nauki Javy 😉

Jerzy Skalski (phoowned@wp.pl)

PODGLĄD PLIKÓW NA WWW:
GENERATOR WIDOKU PLIKÓW – PJWSTK – UTP – ZADANIE 1

Opublikowano PJWSTK - UTP | Skomentuj

[PJWSTK] ASD – wiosna 2015 – Zadanie 5 – Rozwiązanie

TO JEST KOMENTARZ DO ZADANIA ‚PROJEKT 1’ (teraz zwanego Zadanie 5) – http://skalski.at/2013/01/27/pjwstk-asd-projekt-1-rozwiazanie/

W tym kodzie zmieniłem nazwy zmiennych na ‚opisowe’ i dodałem dużo komentarzy przy if’ach i pętlach. Samo działanie/algorytm bez zmian.

Do zrozumienia algorytmu trzeba wiedzieć co to są grafy (tutaj zaimplementowane jako tablice i listy).

Co do dużej ilości klas:

ListElementTown, ListTowns, ListElementThief, ListThiefs – to moje własne implementacje ‚list’, równie dobrze do testów możecie użyć normalnej C++’owej listy http://www.cplusplus.com/reference/vector/vector/ (ma ona więcej funkcjonalości i jest znacznie wolniejsza, więc walcząc o sekundy i tak warto pomyśleć o własnym ‚list’ i ‚map’ [dla ‚optymalizacja hardcore’owa])

Opis ogólny założeń programu:
kandydat – obiekt ktory liczy koszt kampani A/B i zajmuje miasta [tworzy sztaby wyborcze]
miasto – wierzcholek grafu, zawierajacego informacje o sasiedztwie z innymi miastami
sztab wyborczy – przypisanie danego miasta do kandydata, przypisanego miasta nie moze przejac inny kandydat
prawybory – jezeli w miescie nie ma jeszcze ‚sztabu wyborczego’, a w ktoryms z miast sasiadujacych jest, to w danym miescie nalezy przeprowadzic prawybory zgodnie z podanym algorytmem (wygrywa ten kandydat ktorego sztaby sa w najwiekszej ilosci miast sasiednich)
tura – jeden obrot petli w ktorym kazde miasto w ktorym jest sztab proboje zalozyc sztab (doprowadza do prawyborow wpisujac swojego kandydata na liste) w sasiednich miastach

KANDYDACI JAKO WIRUSY:
Program mozna latwiej zrozumiec, patrzac na problem jak na komorki organizmu (miasta) i wirusy (kandydatow):
Wirusy znalazly sie w kilku komorkach, kazda komorka zarazona w danej ‚turze’ zaraza wszystkie z ktorymi ma kontakt [miasta sasiedzkie] w nastepnej turze
Tak wiec mozna podzielic komorki na 3 grupy:
– nie zarazone
– zarażone
– zarażające
1. Kazda komorka w chwili zarazenia staje sie zarazajaca [w nastepnej turze!]
2. Kazda komorka po turze w ktorej zarazala staje sie ‚zarazona’ [sama juz wiecej nie zaraza, nie ma po co, bo wszystkich sasiadow juz zarazila, a sasiadow nie przybywa]

Dana nie zarazona komorka, moze byc w danej turze zarazana przez wiecej, niz jedna sasiednia komorke, wygrywa ten wirus ktory ma najwiecej sasiadujacyh zarazonych komorek [przy remisie porownujemy ID wirusa wedlug polecenia w wersji A i B].
W zalozeniu kazda komorka ma jakiegos sasiada, wiec algorytm mieli dane do czasu, az ilosc zarazonych komorek jest rowna liczbie wszystkich komorek.

UWAGA! Opisany powyżej algorytm to teoretycznie najwydajniejsza wersja kodu, a nie ta jaka jest przedstawiona w C++ [zarażone ciągle zarażają.., dużo rzeczy jest zapisywane do tymczasowych list mimo, że mogło by działać bez nich itd.].

Kod C++ był pisany na ostatnią chwilę, a przed publikacją przeszedł jeszcze obróbkę po której zgodność z oryginałem według ‚plagiatora’ wynosiła poniżej 5% [poprzez dodanie mniej wydajnych pętli, ‚get’ w listach, deklaracje zmiennych w złych miejscach itd.]

ROZWIĄZANIE KTÓRE OPUBLIKOWAŁEM W C++ JEST DALEKIE OD TEORETYCZNIE NAJSZYBSZEGO. W DODATKU NIE JEST WYDAJNE (CO ZMIENIĆ OPISZĘ NA KOŃCU POSTA). Nie można wprost powiedzieć jakie rozwiązanie będzie najlepsze, bo na każdy algorytm duży wpływ ma ilość miast, kandydatów i połączeń między miastami, a jakie są ilości w danych testowych to nie wiem 🙁

#include<stdio.h>
 
class Miasto;
class Kandydat;
 
class ListElementTown
{
    public:
        Miasto* miasto;
        ListElementTown* nastepnyElementListy;
 
        ListElementTown(Miasto* m)
        {
            this->miasto = m;
            this->nastepnyElementListy = NULL;
        }
 
        ListElementTown(Miasto* m, ListElementTown* nastepnyElementListy)
        {
            this->miasto = m;
            this->nastepnyElementListy = nastepnyElementListy;
        }
};
 
class ListTowns
{
    public:
        ListElementTown* pierwszyElementListy;
        int iloscElementow;
 
        ListTowns()
        {
            pierwszyElementListy = NULL;
            iloscElementow = 0;
        }
 
        Miasto* get(int elementIterator)
        {
            ListElementTown* tmp = pierwszyElementListy;
            for(int i = 0; i < elementIterator; i++)
                tmp = tmp->nastepnyElementListy;
 
            return tmp->miasto;
        }
 
        void add(Miasto* m)
        {
            if(this->pierwszyElementListy == NULL)
                this->pierwszyElementListy = new ListElementTown(m);
            else
                pierwszyElementListy = new ListElementTown(m, pierwszyElementListy);
 
            iloscElementow++;
        }
 
        bool contains(Miasto* m)
        {
            ListElementTown* tmp = pierwszyElementListy;
            while(tmp)
            {
                if(m == tmp->miasto)
                    return true;
 
                tmp = tmp->nastepnyElementListy;
            }
            return false;
        }
 
        void clear()
        {
            pierwszyElementListy = NULL;
            iloscElementow = 0;
        }
};
 
class ListElementThief
{
    public:
        Kandydat* kandydat;
        ListElementThief* nastepnyElementListy;
 
        ListElementThief(Kandydat* t)
        {
            this->kandydat = t;
            this->nastepnyElementListy = NULL;
        }
 
        ListElementThief(Kandydat* t, ListElementThief* nastepnyElementListy)
        {
            this->kandydat = t;
            this->nastepnyElementListy = nastepnyElementListy;
        }
};
 
class ListThiefs
{
    public:
        ListElementThief* pierwszyElementListy;
        int iloscElementow;
 
        ListThiefs()
        {
            pierwszyElementListy = NULL;
            iloscElementow = 0;
        }
 
        Kandydat* get(int elementIterator)
        {
            ListElementThief* tmp = pierwszyElementListy;
            for(int i = 0; i < elementIterator; i++)
                tmp = tmp->nastepnyElementListy;
 
            return tmp->kandydat;
        }
 
        void add(Kandydat* t)
        {
            if(this->pierwszyElementListy == NULL)
                this->pierwszyElementListy = new ListElementThief(t);
            else
            {
                pierwszyElementListy = new ListElementThief(t, pierwszyElementListy);
            }
            iloscElementow++;
        }
 
        bool contains(Kandydat* t)
        {
            ListElementThief* tmp = pierwszyElementListy;
            while(tmp)
            {
                if(t == tmp->kandydat)
                    return true;
 
                tmp = tmp->nastepnyElementListy;
            }
            return false;
        }
 
        void clear()
        {
            pierwszyElementListy = NULL;
            iloscElementow = 0;
        }
};
class Miasto
{
    public:
        int id;
        Kandydat* kandydatKtoryZalozylSztabWyborczyA;
        Kandydat* kandydatKtoryZalozylSztabWyborczyB;
        Kandydat* zwyciezcaA;
        Kandydat* zwyciezcaB;
        ListThiefs* kandydaciA;
        ListThiefs* kandydaciB;
        ListTowns* miastaSasiedzkie;
 
        Miasto(int i)
        {
            id = i;
            kandydatKtoryZalozylSztabWyborczyA = NULL;
            kandydatKtoryZalozylSztabWyborczyB = NULL;
            zwyciezcaA = NULL;
            zwyciezcaB = NULL;
            kandydaciA = new ListThiefs();
            kandydaciB = new ListThiefs();
            miastaSasiedzkie = new ListTowns();
        }
};
 
class Kandydat
{
    public:
        int id;
        int tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA;
        int tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB;
        int kosztKampaniA;
        int kosztKampaniB;
 
        Kandydat(int indeks)
        {
            this->id = indeks;
            this->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA = 0;
            this->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB = 0;
            this->kosztKampaniA = 0;
            this->kosztKampaniB = 0;
        }
};

int main()
{ 
    int iloscDzialajacychSztabowWyborczychA = 0;
    int iloscDzialajacychSztabowWyborczychB = 0;
    int iloscMiast = 0;
    int iloscKandydatow = 0;
	// wczytujemy ilosc miast
    fscanf(stdin, "%d", &iloscMiast);
	// tworzymy tablice z miastami
    Miasto* miasta[iloscMiast];
    for(int i = 0; i < iloscMiast; i++)
    {
		// uzupelniamy ja pustymi miastami 
        miasta[i] = new Miasto(i);
    }
    int miasto_1;
    int miasto_2;
	// wczytujemy po kolei po 2 id miast ktore sa sasiadami
    fscanf(stdin, "%d", &miasto_1);
    fscanf(stdin, "%d", &miasto_2);
	// lista tych miast konczy sie dwoma id miast -1
    while(miasto_1 != -1 && miasto_2 != -1)
    {
		// graf ma byc nie skierowany, czyli jak sasiad X wie o sasiedzie Y to Y tez musi wiedziec o X
		// dlatego dodajemy informacje o sasiedze do obu miast
        miasta[miasto_1]->miastaSasiedzkie->add(miasta[miasto_2]);
        miasta[miasto_2]->miastaSasiedzkie->add(miasta[miasto_1]);
        fscanf(stdin, "%d", &miasto_1);
        fscanf(stdin, "%d", &miasto_2);
    }
	// wczytujemy ilosc kandydatow
    fscanf(stdin, "%d", &iloscKandydatow);
	// tworzymy tablice z kandydatkami
    Kandydat* kandydaci[iloscKandydatow];
    for(int i = 0; i < iloscKandydatow; i++)
    {
		// uzupelniamy ja kandydatami ktorzy znaja swoje id
        kandydaci[i] = new Kandydat(i);
    }
	// wczytujemy sztaby poczatkowe kandydatow
    int idSztabuStartowegoKandydata;
    for(int i = 0; i < iloscKandydatow; i++)
    {
		// zalozenie jest takie, ze kazdy kandydat ma wlasne miasto,
		// wiec nie trzeba sprawdzac czy aby 2 nie jest naraz w tym samym miescie startowym
        fscanf(stdin, "%d", &idSztabuStartowegoKandydata);
		// dla algorytmu z zasada A i zasada B przypisujemy, ze ten kandydat juz wygral w tym miescie wybory
        miasta[idSztabuStartowegoKandydata]->kandydatKtoryZalozylSztabWyborczyA = kandydaci[i];
		// naliczany koszt kampani wyborczej
        kandydaci[i]->kosztKampaniA++;
		// dodajemy +1 do ilosci dzialajacych sztabow wyborczych
        iloscDzialajacychSztabowWyborczychA++;
		
		// tutaj to samo co wyzej tylko dla algorytmu 'B'
        miasta[idSztabuStartowegoKandydata]->kandydatKtoryZalozylSztabWyborczyB = kandydaci[i];
        kandydaci[i]->kosztKampaniB++;
        iloscDzialajacychSztabowWyborczychB++;
    }
	/*
	teraz dochodzimy do samego mielenia danych:
	w celu szybszych obliczen zrobimy sobie liste pomocnicza 'miastaWktorychTrzebaPrzeprowadzicPrawybory'
	zalozenia:
	mamy milion wierzcholkow grafu [miast]
	kazdy wierzcholek ma polaczenie z tysiacami innych wierzcholkow [innymi miastami]
	mamy kilkuset kandydatow ktorzy maja ustalone miasta startowe
	*/
    ListTowns* miastaWktorychTrzebaPrzeprowadzicPrawybory = new ListTowns();
	// [PĘTLA GŁÓWNA] do poki nie we wszystkich miastach sa sztaby wyborcze
    while(iloscDzialajacychSztabowWyborczychA != iloscMiast && iloscDzialajacychSztabowWyborczychB != iloscMiast)
    {
		// co obrot petli (ture) czyscimy liste pomocnicza
        miastaWktorychTrzebaPrzeprowadzicPrawybory->clear();
		// [PĘTLA 1]
        for(int i = 0; i < iloscMiast; i++)
        {
			// dla kazdego miasta ..
            if(miasta[i]->kandydatKtoryZalozylSztabWyborczyA != NULL && miasta[i]->kandydatKtoryZalozylSztabWyborczyB != NULL)
            {
				// .. w ktorym jest sztab wyborczy [X kandydata]
				// [PĘTLA 1.1]
                for(int i2 = 0; i2 < miasta[i]->miastaSasiedzkie->iloscElementow; i2++)
                {
					// dla kazdego miasta sasiedniego ..
                    if(miasta[i]->miastaSasiedzkie->get(i2)->kandydatKtoryZalozylSztabWyborczyA == NULL && miasta[i]->miastaSasiedzkie->get(i2)->kandydatKtoryZalozylSztabWyborczyB == NULL)
                    {
						// .. w ktorym nie ma sztabu wyborczego
						
						// wszystko jest w 'ifach', bo wiele innych miast moze byc sasiadem w ktorym jest juz sztab wyborczy,
						// a lista kandydatow i miast w ktorych maja byc wybor ma byc bez powtorzen
                        if(!(miasta[i]->miastaSasiedzkie->get(i2)->kandydaciA->contains(miasta[i]->kandydatKtoryZalozylSztabWyborczyA)))
                        {
							// dodaj do listy kandydatow A o ile jeszcze na niej nie jest
                            miasta[i]->miastaSasiedzkie->get(i2)->kandydaciA->add(miasta[i]->kandydatKtoryZalozylSztabWyborczyA);
                        }
                        if(!(miasta[i]->miastaSasiedzkie->get(i2)->kandydaciB->contains(miasta[i]->kandydatKtoryZalozylSztabWyborczyB)))
                        {
							// dodaj do listy kandydatow B o ile jeszcze na niej nie jest
                            miasta[i]->miastaSasiedzkie->get(i2)->kandydaciB->add(miasta[i]->kandydatKtoryZalozylSztabWyborczyB);
                        }
                        if(!(miastaWktorychTrzebaPrzeprowadzicPrawybory->contains(miasta[i]->miastaSasiedzkie->get(i2))))
                        {
							// dodaj miasto sasiedzkie do listy miast w ktorych trzeba przeprowadzic prawybory w tej turze
                            miastaWktorychTrzebaPrzeprowadzicPrawybory->add(miasta[i]->miastaSasiedzkie->get(i2));
                        }
                    }
                }
            }
        }
		// koniec 'for' ktory generowal liste miast w ktorych trzeba przeprowadzic prawybory i dodawal w tych miastach kandydatow
        ListElementTown* elementPoczatkowy = miastaWktorychTrzebaPrzeprowadzicPrawybory->pierwszyElementListy;
        int loopsCounter = miastaWktorychTrzebaPrzeprowadzicPrawybory->iloscElementow;
		// teraz trzeba przeprowadzic prawybory i ustalic ktory kandydat wygral w danym miescie
		// przy czym jego wygrana nie moze wplywac na obliczenia innych wygranych (na to moze wplywac dopiero w nastepnej 'turze' algorytmu)
		// dlatego wynik prawyborow zapisujemy do zmiennych 'zwyciezcaA' i 'zwyciezcaB'
		// [PĘTLA 2]
        for(int i = 0; i < loopsCounter; i++)
        {
            Miasto* aktualneMiasto = elementPoczatkowy->miasto;
            Kandydat* tmpKandydat = NULL;
			// z dziwnych powodow trzymamy ilosc 'sztabow wyborczych w miastach sasiednich' w kandydatach,
			// wiec trzeba to co obrot petli czyscic w kazdym kandydacie
            for(int x = 0; x < iloscKandydatow; x++)
            {
                kandydaci[x]->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA = 0;
                kandydaci[x]->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB = 0;
            }
            int loopsCounter_2 = aktualneMiasto->miastaSasiedzkie->iloscElementow;
            ListElementTown* petlaPoSasiadach = aktualneMiasto->miastaSasiedzkie->pierwszyElementListy;
			// teraz dodajemy w tych kandydatach liczbe przechowujaca w ilu miastach sasiedzkich [dla 'aktualneMiasto'] jest sztab danego kandydata
            for(int ii = 0; ii < loopsCounter_2; ii++)
            {
                Miasto* tmpMiasto = petlaPoSasiadach->miasto;
                if(tmpMiasto->kandydatKtoryZalozylSztabWyborczyA != NULL)
                {
                    tmpMiasto->kandydatKtoryZalozylSztabWyborczyA->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA++;
                    tmpMiasto->kandydatKtoryZalozylSztabWyborczyB->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB++;
                }
                petlaPoSasiadach = petlaPoSasiadach->nastepnyElementListy;
            }
			// teraz sprawdzamy ktory kandydat ma najwiecej sztabow wyborczych w sasiadujacych miastach
            Kandydat* zwyciezcaA = aktualneMiasto->kandydaciA->get(0);
            Kandydat* zwyciezcaB = aktualneMiasto->kandydaciB->get(0);
 
			// dla A
            loopsCounter_2 = aktualneMiasto->kandydaciA->iloscElementow;
            for(int i2 = 1; i2 < loopsCounter_2; i2++)
            {
                tmpKandydat = aktualneMiasto->kandydaciA->get(i2);
                if((zwyciezcaA->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA > tmpKandydat->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA) || (zwyciezcaA->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA == tmpKandydat->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA && zwyciezcaA->id < tmpKandydat->id))
                    zwyciezcaA = tmpKandydat;
            }
            aktualneMiasto->zwyciezcaA = zwyciezcaA;
            aktualneMiasto->kandydaciA->clear();
			// dla B
            loopsCounter_2 = aktualneMiasto->kandydaciB->iloscElementow;
            for(int i2 = 1; i2 < loopsCounter_2; i2++)
            {
                tmpKandydat = aktualneMiasto->kandydaciB->get(i2);
                if((zwyciezcaB->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB < tmpKandydat->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB) || (zwyciezcaB->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB == tmpKandydat->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB && zwyciezcaB->id > tmpKandydat->id))
                    zwyciezcaB = tmpKandydat;
            }
            aktualneMiasto->zwyciezcaB = zwyciezcaB;
            aktualneMiasto->kandydaciB->clear();
            elementPoczatkowy = elementPoczatkowy->nastepnyElementListy;
        }
        elementPoczatkowy = miastaWktorychTrzebaPrzeprowadzicPrawybory->pierwszyElementListy;
        loopsCounter = miastaWktorychTrzebaPrzeprowadzicPrawybory->iloscElementow;
		// znamy juz zwyciezcow, teraz trzeba ich zwycieztwa w prawyborach przepisac na zalozone sztaby, aby w kolejnej 'turze' mogli zakladac kolejne sztaby
		// [PĘTLA 3]
        for(int i = 0; i < loopsCounter; i++)
        {
            Miasto* tmpMiasto = elementPoczatkowy->miasto;
            tmpMiasto->kandydatKtoryZalozylSztabWyborczyA = tmpMiasto->zwyciezcaA;
            tmpMiasto->kandydatKtoryZalozylSztabWyborczyB = tmpMiasto->zwyciezcaB;
            tmpMiasto->kandydatKtoryZalozylSztabWyborczyA->kosztKampaniA++;
            tmpMiasto->kandydatKtoryZalozylSztabWyborczyB->kosztKampaniB++;
            iloscDzialajacychSztabowWyborczychA++;
            iloscDzialajacychSztabowWyborczychB++;
            elementPoczatkowy = elementPoczatkowy->nastepnyElementListy;
        }
    }
    for(int i = 0; i < iloscKandydatow; i++)
    {
        fprintf(stdout, "%d %d\n",kandydaci[i]->kosztKampaniA, kandydaci[i]->kosztKampaniB);
    }
    return 0;
}

Optymalizacja:

– zmiana wczytywania danych na szybkie wczytywanie ( http://skalski.at/2014/11/04/asd-spox-spoj-szybkie-wczytywanie-intow-w-c/ )

– przepisanie kodu tak, żeby nigdy nie korzystał z funkcji ‚get’ [super nie wydajna!!] w listach (ZAWSZE algorytm iteruje po elementach listy w pętli od elementu zero do końca, więc zamiast ‚for’ trzeba dać ‚while’ który się zatrzyma jak ‚next’ będzie NULLem)

– jeśli już nie przepisywać kodu na ‚while’ to dodać w listach ‚currentElement’ i ‚currentIndex’, tak, aby po prośbie o element o ‚id’ wyższym o jeden nie jechać pętlą od elementu zerowego do tego o ‚id’ podanych tylko przejść do ‚next’

– w pętlach wiele razy występują np. ‚miasta[i]’ czy jeszcze gorsze ‚miasta[i]->miastaSasiedzkie->get(i2)’, należało by przypisać wartość zmiennej do jakiejś zmiennej tymczasowej Miasto* tmpMiasto i z niej korzystać zamiast w jednej pętli po 8 razy odwoływać się do 2-3 skoków po pamięci RAM

– WSZYSTKIE zmienne tymczasowe powinny być zadeklarowane na początku ‚main’, a nie w jakimkolwiek ‚for’ czy ‚while’, może to zaoszczędzić miliony wrzuceń i usunięć zmiennych z stosu co może dać te brakujące milisekundy do zaliczenia

– w listach funkcja ‚clear’ nie czyści listy, więc jest tutaj duży wyciek pamięci, bo ‚pierwszyElement’ ustawia na NULL, ale ten element mógł wskazywać na listę miliona elementów które już z RAM nie są wywalane, jaki to ma wpływ na wydajność nie wiem [może mieć pozytywny! warto sprawdzić czy aktualna wersja bez czyszczenia nie jest szybsza]

Optymalizacja hardcore’owa:

– kod oznaczony jako PĘTLA 1 i PĘTLA 2 uprościć poprzez nie używanie listy ‚kandydaciA’ (na podstawie której PĘTLA 2 oblicza kto wygrał), tylko użycie mapy ( http://www.cplusplus.com/reference/map/map/)  która by przechowywala danych kandydatow bez powtorzen i ile razy wystapili w miastach sasiedzkich [ pseudokod(!):  std::map<Kandydat* kandydat, int iloscWystapien> kandydaciA ]

Opublikowano PJWSTK - ASD | 3 komentarze

[BSI] Kodowanie, hashowanie, szyfrowanie: Szyfrowanie

Część trzecia z czterech:

  1. Kodowanie.
  2. Hashowanie.
  3. Szyfrowanie.
  4. Przykłady zastosowań. Analiza istniejących rozwiązań.

3. Szyfrowanie – czyli ‚zamiana tekstu jawnego w szyfrogram’, a w praktyce (nie wspominając o ZŁYCH praktykach) polega to na wykorzystaniu jakiejś funkcji matematycznej do przetworzenia ‚czystego tekstu’ w ‚bezsensowny bełkot’ z pomocą KLUCZA (hasła). W przeciwieństwie do ‚hashowania’ ważne jest, aby ten proces dało się odwrócić (zamienic bełkot w początkowy tekst).
Głównym podziałem ze względu na zastosowanie jest podział na typ klucza/kluczy. Do wyboru mamy:
Algorytmy symetryczne (klucza prywatnego) – wykorzystują jeden klucz (hasło) do szyfrowania i odszyfrowywania
Algorytmy asymetryczne (klucza publicznego) – wykorzystują dwa klucze (między którymi istnieje pewna matematyczna zależność): publiczny do szyfrowania wiadomości i prywatny do odszyfrowywania, ważną cechą jest to, że z klucza szyfrującego (publicznego) nie da się utworzyć klucza deszyfrującego (prywatnego), więc jeśli da się komuś klucz szyfrujący (publiczny) i on nim zaszyfruje wiadomość to nikt po drodze nie będzie w stanie jej odczytać, bo tylko osoba która wygeneruje klucze ma klucz prywatny

Skąd nazwy symetryczne i asymetryczne? Zależą one od wykorzystanych w algorytmach funkcji:
Symetryczne to takie gdzie wykonuje się operacje odwrotną np. szyfrując `dodaje` się tyle do bajta ile wynosi wartość litery w KLUCZU (haśle), a odszyfrowując `odejmuje` się tą wartość (algorytmy: Rijndael [w wersji z ‚blokami danych’ długości 128 bit zwany też ‚AES’], DES [stary]).
Asymetryczne to takie gdzie do szyfrowania i odszyfrowywania wykonuje się inne operacje (i inne klucze, bo jest publiczny i prywatny) których działanie udowodnił jakiś matematyczny geniusz (algorytmy: RSA [wykorzystywany do szyfrowania połączeń do stron www, banków, między komputerami, w sieciach WiFi, … WSZĘDZIE], więc innych nie będę omawiał).

Co to jest szyfr blokowy (‚bloki danych’)?
Szyfrowanie zazwyczaj polega na przestawianiu miejscami i zwiększaniu/zmniejszaniu wartości poszczególnych bajtów w przekazanym ciągu znaków. Większość algorytmów to szyfry blokowe – wymagają danych o określonej długości. np. AES przyjmuje dane w ‚blokach danych’ o długości 128 bitów (16 bajtów), jeśli przekaże się mu dłuższy ciąg to podzieli go na 128 bitowe kawałki i każdy oddzielnie zaszyfruje, jeśli przekaże mu się ciąg krótszy to zależnie od implementacji danej funkcji/klasy AES w danym języku (często jest kilka do różnych zastosowań):
na końcu ciągu doda zera (NULL) – stosowane gdy niskie opóźnienie jest ważniejsze od ilości przesłanych danych = chcemy uzyskać zaszyfrowany ciąg natychmiast po przekazaniu danych (wada: przesłanie 1 znaku wykorzysta 16 znaków (128bit), marnując resztę na zera), stosowane np. w grach online (mało gier korzysta z szyfrowania ze względu na opóźnienia)
[nie zawsze na końcu są dodawane zera, czasem inne ustalone wcześniej wartości ‚dopełniania bloku danych’, więcej na ten temat: http://en.wikipedia.org/wiki/Padding_%28cryptography%29 ]
nie zrobi nic – będzie czekał, aż przekażemy kolejne znaki i będzie ich w sumie 128 bit – wymagane przy szyfrowaniu pliku, kiedy odczytujemy plik ‚czysty’ i zapisujemy używając AES, ilość danych zapisanych powinna być jak najmniejsza, więc lepiej poczekać, aż się plik skończy (program wywoła na pliku funkcje np. ‚plik.close()’) i wtedy zapisać ostatni ‚blok’ z zerami na końcu (NULLami), niż co chwilę na dysk zrzucać kolejne bloki kończąc je zerami (zakładając typowy algorytm kopiowania ‚odczytaj 100 bajt -> zapisz 100 bajt -> sprawdź czy koniec pliku odczytywanego’)

Co to jest ‚CBC’, ‚Block cipher mode of operation’, ‚Tryb wiązania bloków zaszyfrowanych’?
Tryby wiązania bloków są różne, ale do praktycznych (bezpiecznych) zastosowań wykorzystuje się ‚CBC’ (Cipher-block chaining). Na pewno przemawia za tym fakt, że w wielu językach programowania oprócz trybu CBC nie ma innych, a czasem nie ma nawet możliwości wyboru trybu tylko gdzieś w dokumentacji jest notatka, że dana biblioteka korzysta z trybu CBC. Jak działa CBC?
CBC to tryb który nie pozwala na szyfrowanie wielowątkowe, ale można odszyfrowywać wielowątkowo (na kilku rdzeniach, a nawet wielu komputerach naraz). Nie da się szyfrować pliku w kilku wątkach naraz, bo aby zaszyfrować blok danych (te wspominane wcześniej 128 bitów) trzeba znać wynik zaszyfrowania poprzedniego bloku. Po co? Zanim zacznie działać algorytm mieszania tablicy bajtów w pamięci (szyfrowania bloku [dla AES – 16 bajtowej tablicy]) ta pamięć (RAM) musi mieć jakąś wartość. Jaką? Najprościej było by dać tam zawsze same NULLe i po sprawie nie? Jednak geniusze wymyślili, że lepiej będzie tam przypisać jakieś wartości pseudo-losowe, a skąd wziąć wartości pseudo-losowe które przy szyfrowaniu i odszyfrowywaniu będą takie same, a za razem inne dla każdego bloku? Z poprzedniego zaszyfrowanego bloku! W tym momencie dochodzimy do czegoś co nazywa się IV..
(Odszyfrowywanie w wielu wątkach jest możliwe, bo można do wątku nr X przekazać, że ma odszyfrowywać dane od 1500 bloku korzystając z wartości zaszyfrowanego bloku 1499 jako IV.)

Co to jest IV (Initialization vector)?
Jest to ciąg znaków o długości równej blokowi danych danego algorytmu (128 bit dla AES). Wykorzystuję się go w większości trybów szyfrowania (np. we wspomnianym wyżej CBC). Jest to wartość tablicy ‚mieszającej’ trzymanej w pamięci RAM. Za wartość tą bierze się ciąg znaków poprzedniego zaszyfrowanego bloku (w trybie CBC), ale co z pierwszym blokiem? Nie ma bloku ‚zero’ z którego można by wziąść wartości do ustawienia w tablicy mieszającej. Wtedy właśnie bierze się wartość IV! Blok IV nie zawiera w sobie żadnych informacji – dla tego można go dodać do danych zaszyfrowanych. Najpopularniejszą praktyką jest dodanie go przed danymi zaszyfrowanymi. Skoro ma 16 znaków (w AES) to wystarczy tylko pamiętać, że zawsze kiedy bierzemy jakieś dane do odszyfrowania musimy odczytać 16 znaków i przekazać je do ‚decryptora’ jako blok IV (funkcje typu ‚mojDekryptor.setIv(pierwsze16znakow);’, a reszte znaków (do 16 do końca) przekazać jako zaszyfrowane dane.
Bardzo ważne jest, aby blok IV zawsze był inny (pseudo-losowy)! Inaczej ułatwiamy atak mający na celu odszyfrowanie danych (szczególnie kiedy mamy miliony zaszyfrowanych danych, np. dla wszystkich plików na dysku używamy jednego IV).
Co jeszcze nam daje IV? Jeśli ten sam ciąg znaków np. ‚ala ma kota’ zaszyfrujemy używając innego IV to zaszyfrowany blok danych będzie inny. Dzięki temu hacker nie ma szans sprawdzić czy 2 pliki są identyczne na podstawie ich zaszyfrowanej wersji danych.
Blok IV można też traktować jako ‚drugą część hasła’ (i przekazywać ‚tajnie’, a nie dołączać do pliku), bo nie posiadając bloku IV nie można odszyfrować danych nawet znając hasło. Jednak nie znalazłem nigdzie informacji czy ‚odkrycie’ IV jest tak samo trudne jak hasła do zaszyfrowanych danych.

Omówienie 2 najpopularniejszych szyfrowań:
AES (Advanced Encryption Standard) – szyfr blokowy, symetryczny (klucz prywatny), o blokach danych długości 16 znaków i kluczach (hasłach) długości 16, 24 lub 32 znaków, do zaszyfrowania danych trzeba wylosować IV i hasło, jeśli hasło ma być ‚dla ludzi’ np. ‚ala ma kota’, to można wykorzystać jakąś funkcje hashująca która po wpisaniu przez użytkownika hasła wygeneruje ciąg pseudo-losowy [pseudo, bo zależy od tego co wpisze użytkownik] o odpowiedniej długości.
Zastosowania:
– szyfrowanie plików (dość szybkie szyfrowanie dużych ilości danych)
– szyfrowanie danych kiedy hasło ma być czytelne dla ludzi – można samemu ustalić hasło

RSA – szyfr blokowy, asymetryczny (klucz publiczny), o blokach danych zależnych od długości klucza (11 znaków krótszych od klucza), aktualnie używa się kluczy o długości od 1024 do 4096 bitów (128 znaków do 512 znaków z czego ‚dla Ciebie’ jest od 117 do 501 znaków), ze względu na dość wolne działanie wykorzystywany zazwyczaj jako algorytm do szyfrowania ‚kluczem publicznym’ hasła (klucza prywatnego [czasem także IV]) algorytmu AES. Wyjątkową cechą RSA jest to, że korzystając z tego algorytmu można nie tylko szyfrować/deszyfrować wiadomości, ale także ‚podpisywać’ i ‚sprawdzać podpis’ cyfrowy.
Najwięcej czasu w typowym zastosowaniu algorytmu zajmuje wygenerowanie klucza publicznego i prywatnego, składają się one z 3 liczb: ‚n’, ‚e’ i ‚d’.
Klucz publiczny (do szyfrowania, sprawdzania podpisu) składa się z ‚n’ i ‚e’.
Klucz prywatny (do odszyfrowywania, tworzenia podpisu) składa się z ‚n’ i ‚d’. Czasem razem z kluczem prywatnym zapisuje się też ‚e’ tak, aby móc w przyszłości przekazać komuś klucz publiczny. Jednak w normalnych zastosowaniach klucz publiczny należy przekazać ustalonej osobie/maszynie, a potem zapomnieć i przechowywać tylko klucz prywatny (‚n’ i ‚d’).
Ważną cechą algorytmu RSA jest to, że oprócz oczywistej w kryptografii klucza publicznego nie możliwości odtworzenia klucza prywatnego na podstawie publicznego, nie możliwe jest też odtworzenie klucza publicznego na podstawie prywatnego [zapisanego bez liczby ‚e’].
Zastosowania:
– szyfrowanie klucza algorytmu AES (kiedy jest potrzebna kryptografia ‚klucza publicznego’, a zarazem do przesłania jest dużo danych)
– podpis cyfrowy (e-maile, pliki, a także potwierdzanie ‚tożsamości’ przez strony www banków i firm – wszystko to się opiera na generowaniu i wymianie wielu kluczy publicznych przez komputery)
Wady:
– wolne działanie – mimo, że to algorytm blokowy, zazwyczaj wykorzystuje się tylko jeden blok (zaszyfrowany klucz [+IV?] do algorytmu AES – 16-48 znaków)
– stosunkowo dużo (do 8 procent!) dodatkowych danych zapisywanych w zaszyfrowanych blokach danych
– ‚hasła’ (klucze) są generowane losowo i składają się z ciągów setek cyfr – nie do zapamiętania/wpisania dla człowieka
Teraz pora na trochę przykładów z życia z Bob’em i Alice:

AES – Bob chce nagrać na pendrive plik dla Alice, ale w przypadku zgubienia pendrive znalazca nie może mieć dostępu do pliku:
1. Bob losuje hasło, szyfruje plik algorytmem symetrycznym AES i nagrywa na pendrive.
2. Bob daje Alice pendrive.
3. Bob wysyła do Alice SMS z hasłem do pliku.
4. Alice odszyfrowuje plik używając algorytmu AES i hasła jakie dostała od Boba.
Podsumowanie: aby przejąć plik ktoś musiał by mieć pendrive i telefon Alice (lub inną rzecz jeśli hasło zostało by przesłane inną drogą)

RSA – Bob chce wysłać tajną wiadomość do Alice którą nawet jak ktoś podejrzy to nie będzie mógł odczytać.
(Rozwiązanie przykładowe, nie nadaje się do implementacji ze względu na podatność na pewne ataki):
1. Bob prosi Alice o przysłanie e-mailem wylosowanego klucza publiczenego RSA.
2. Alice losuje klucz publiczny i prywatny RSA, a potem publiczny wysyła do Boba.
3. Bob szyfruje swoją wiadomość algorytmem RSA używając klucza publicznego Alice.
4. Bob wysyła zaszyfrowany bełkot do Alice.
5. Alice odszyfrowuje wiadomość używając klucza prywatnego.
… taka jest teoria …

PROBLEM 1:
W rzeczywistości ‚listonosz’ może wziąć klucz publiczny Alice który miał przekazać do Boba i zaszyfrować co chce używając tego klucza. Potem może wysłać taka wiadomość do Alice podpisując się ‚Bob’. W ten sposób Alice dostanie wiadomość zaszyfrowaną kluczem ‚który ma Bob’, a napisaną przez kogoś innego.

PROBLEM 2 (poważniejszy):
1. ‚listonosz’ zapisuje ‚klucz publiczny Alice’, samemu generuje nową parę kluczy RSA i przekazuje ‚swój’ klucz publiczny do Boba mówiąc, że to od Alice
2. Bob szyfruje swoją wiadomość kluczem ‚listonosza’ (nie Alice!) i oddaje mu, żeby ją przekazał Alice
3. ‚listonosz’ odszyfrowuje wiadomość, bo przecież to jego (listonosza!) klucz prywatny jest do tego potrzebny
4. ‚listonosz’ odczytuje wiadomość i szyfruje ją za pomocą klucza publiczego który dała mu Alice
5. ‚listonosz’ daje Alice wiadomość od Boba (lub inną którą sam napisze!)
Wynik: listonosz zna treść listu, listonosz może podmienić treść listu, Alice i Bob nie mają o niczym pojęcia, mimo mocnego szyfrowania osoba ‚po środku’ (odpowiedzialna za komunikację) może robić co chce z wiadomościami

Atak tego typu nazywa się ‚Man in the middle‚ ( http://pl.wikipedia.org/wiki/Atak_man_in_the_middle ), występuje we wszystkich protokołach ‚klucza publicznego’ i jest nie do uniknięcia. Jak OGRANICZYĆ możliwość takiego ataku opiszę w części czwartej (organizacje certyfikujące / wykorzystanie innych dróg komunikacji [e-mail, sms …] / tokenizery).

———————————–
Listonosz [nasz zły bohater z opowieści o Alice i Bobie] to ktoś kto wepnie się w łącze internetowe/przeglądarkę internetową/włamie do telefonu i będzie ‚filtrował’ ruch zmieniając przesyłane treści – przykłady: NSA/dostawca internetu/pracodawca/hacker/dzieciak rozsyłający trojany itp.

Opublikowano PJWSTK - BSI | Skomentuj

[BSI] Kodowanie, hashowanie, szyfrowanie: Hashowanie

Część druga z czterech:

  1. Kodowanie.
  2. Hashowanie.
  3. Szyfrowanie.
  4. Przykłady zastosowań. Analiza istniejących rozwiązań.

2. Hashowanie (zwane też ‚funkcja skrótu’) – jest to przekształcanie ciągu bajtów w inny ciąg bajtów który NIE ZAWIERA żadnych informacji o źródle. Ze względu na praktyczne zastosowanie takich przekształceń, celem algorytmów hashujących jest przekształcenie dowolnej długość ciągu bajtów w ciąg o określonej długość (nie ważne czy będzie to hasło ‚123’ czy plik o wielkości 20 GB, funkcja skrótu zawsze zwróci ciąg o takiej samej długości). Najważniejszymi cechami są:
– wygenerowany ciąg nie może zawierać informacji o ciągu źródłowym (wiąże się to z ‚jednokierunkowością’ takich funkcji)
– wygenerowany ciąg musi być maksymalnie losowy względem ciągu wejściowego (np. ‚1’ -> ‚c4ca4238a0b923820dcc509a6f75849b’, ‚2’ -> ‚c81e728d9d4c2f636f067f89cc14862c’ = mała zmiana na wejściu daje duże i nie przewidywalne zmiany na wyjściu)
– dla tych samych danych źródłowych zawsze musi generować taki sam ‚hash’

Wymyślaniem takich super algorytmów zajmują się różni geniusze, a cechą takich algorytmów jest to, że, aby ‚złamać’ (dowiedzieć się z jakiego ciągu znaków został wygenerowany) hash trzeba wpisywać po koleji (‚1’, ‚2’, ‚3’, … ,’asdasdsad’) ciągi znaków i generować ich hashe do czasu, aż się trafi taki sam hash jaki chcemy złamać. Dla starych i prostych algorytmów (32-40 znaków ‚hasha’) hashujących trwa to kilka dni na super komputerze. Dla nowoczesnych algorytmów generujących hashe (o długości 60-160 znaków) są to już lata lub tysiące lat generowania przy obecnych możliwościach komputerów.

Algorytmy hashujące stosowane w przeszłości:
– MD5 – długość hasha: 32 znaki w kodowaniu szesnastkowym – kiedyś bardzo popularny, ale aktualnie tak słaby, że można znaleźć/kupić w internecie bazę danych z wszystkimi możliwymi kombinacjami 32 znaków
– SHA1 – długość hasha: 40 znaków w kodowaniu szesnastkowym – zastąpił MD5, ale aktualnie jest również uznawany za słaby i w internecie są dostępne wielkie bazy wygenerowanych hashy
Używanie MD5 i SHA1 jest bezpiecznie jeśli używa się ich do weryfikacji zawartości plików lub przechowywania haseł wykorzystując ‚sól’, więcej o soli w hasłach w części czwartej artykułu ‚Zastosowania’. Nie należy ich używać do przechowywania haseł ‚wprost’ ze względu na możliwość odczytania haseł.

Algorytmy hashujące stosowane aktualnie:
– SHA-2 – obsługuje różne długości generowanych hashy, popularne to ‚SHA-256’ i ‚SHA-512’ które mają długość hasha w kodowaniu szesnastkowym odpowiednio 64 i 128 znaków – dostępny w większości języków programowania
– SHA-3 – rozwiązanie przyszłościowe (zatwierdzone w 2012), wymaga instalowania dodatkowych bibliotek

Możliwe zastosowania:
przechowywanie haseł w bazie danych w formie zahashowanej nie pozwala nikomu (włącznie z administratorem) przeglądać haseł, jak się logować kiedy hasło w bazie jest zahashowane opiszę w części czwartej
sprawdzanie czy plik nie został zmodyfikowany – do dużych plików udostępnianych w internecie często są dołączane pliki .md5 lub .sha1 które zawierają hash danego pliku, korzystając ze specjalnych programów można szybko sprawdzić czy hash danego algorytmu wygenerowany z naszego pobranego pliku i ten który ktoś chciał nam wysłać są identyczne, zapobiega to problemom z błędami pojedyńczych bitów podczas transmisji w internecie, a także potencjalnym próbą przesłania nam zmodyfikowanego pliku przez hackera

Więcej informacji: http://pl.wikipedia.org/wiki/Funkcja_skr%C3%B3tu

Przykład algorytmu hashującego:

Zamień każdą literę w ciągu na wartość jej kodu w kodowaniu ANSI, np. dla hasła ‚123’ (daje to odpowiednio kody 51, 52, 53), teraz pomnóż przez siebie te liczby, da to wynik 140556, tak właśnie powstał ‚hash’ hasła ‚123’. Z wyniku ‚140556’ nie da się jednoznacznie ustalić z jakiego ciągu powstał (wykorzystałem funkcję/algorytm jednokierunkową/y), ale jego rozkład losowy jest bardzo słaby (taki sam hash daje np. ‚132’, ‚321’, ‚231’ ..). Tworzenie takiego hashowania jest przykładem ‚złych praktyk’ w dziedzinie kryptografii – tworzenia własnych algorytmów zakładając, że skoro znam je tylko ja to ciężko będzie je złamać. Lepiej zostawić to ‚geniuszom’.

Opublikowano PJWSTK - BSI | Skomentuj

[BSI] Kodowanie, hashowanie, szyfrowanie: Kodowanie

Kodowanie, hashowanie, szyfrowanie – to seria artykułów o tematyce bezpieczeństwa i przetwarzania danych przez komputery. Dowiecie się z nich:
– jak o bezpieczeństwo klientów dbają strony banków, a jak proste logowanie do forum
– dlaczego tak działają – jakim atakom hackerów przeciwdziałają
– jak samodzielnie zaplanować bezpieczne logowanie, przesyłanie danych, przetrzymywanie danych
Pierwsze trzy artykuły to teoria którą trzeba choć częściowo rozumieć [coś czego powinniście się nauczyć na przedmiocie BSI], aby zrozumieć czwarty artykuł prezentujący istniejące rozwiązania.

Część pierwsza z czterech:

  1. Kodowanie.
  2. Hashowanie.
  3. Szyfrowanie.
  4. Przykłady zastosowań. Analiza istniejących rozwiązań.

1. Kodowanie – jest to format zapisu informacji na komputerze. Celem kodowania jest używanie wspólnego ‚języka’.
Przykładem z życia może być system dziesiętny. Jeśli zapisujący i odczytujący znają system dziesiętny to obliczenia zapisane przez jedną osobę są czytelne dla drugiej. Wspólne (i jakoś ustalone/oznaczone) kodowanie jest wymagane, aby 2 programy mogły się komunikować.

Kodowania z jakimi często się spotkasz w programowaniu:
ANSI i UTF-8 – 2 formaty zapisu liter wykorzysywane przy przesyłaniu tekstu.
Pierwszy (ANSI) używa jednego bajta na jedną literę, pozwala to używać znaków takich jak ą,ę,ć.. , ale trzeba najpierw przekazać/ustalić jakiego alfabetu mają używać zapisujący i czytający (np. polskiego).
Drugi (UTF-8) używa jednego lub 2 bajtów na jedną literę, pierwszy z nich oznacza z jakiego alfabetu jest dany znak, a drugi już sam znak w danym alfabecie, dzięki temu na jednej stronie/w jednym programie można używać wielu języków naraz. ANSI jest wypierany na rzecz UTF-8, np. wszystkie programy w Javie używają zapisu ‚string’ jako UTF-8, przez co zmienna typu ‚char’ ma 2 bajty w Javie (w innych jezykach ‚char’ [znak] jest równy rozmiarem ‚byte’ i ma jeden bajt).
Problemem (dla programistów, nie użytkowników) z zapisem UTF-8 jest to, że litery angielskie i cyfry zapisuje się jako jeden bajt, a znaki z konkretnych języków jako 2 bajty. Dlatego zapis ‚aą’ do pliku zajmuje 3 bajty i chcąc pobrać 3 znak ze stringa z pliku nie można odczytać po prostu 3-go bajtu z pliku, tylko trzeba odczytać wszystko od początku sprawdzając czy są to normalne znaki czy był znak ‚zmiana alfabetu następnego znaku’. Jednak robiąc wszystko w Javie (zapis/odczyt) nie ma się czym martwić, bo Java sama ogarnie UTF-8.

Kodowania z jakimi często się spotkasz w szyfrowaniu/hashowaniu:
Mają na celu ograniczenie używanych w nich znaków do tych dostępnych na klawiaturze (jak wpisać liczbę 240 jako jeden znak (bajt) z klawiatury? ..) lub tych które można przesyłać w danym formacie danych (JSON, HTML, ..):
zapis szesnastkowy (hexadycymalny, ‚hex’), zapisanie jednego bajtu (8 bit, wartości od 0 do 255 w systemie dziesiętnym) dokonuje się za pomocą 2 znaków z zakresu 0-9 i A-F, przykład (często wynik funkcji hashujących): 32 (system dziesiętny) -> 20 (system szesnastkowy), 9 -> 9, 10 -> A, 11 -> B
zapis ’64’ (Base64), wykorzystuje małe i duże litery angielskie, cyfry 0-9 oraz kilka znaków specjalnych (tak, aby były w sumie 64 różne znaki), często wykorzystywany do przesyłania danych zaszyfrowanych na strony WWW (ze względu na to, że znaki takie jak < i > są ‚specjalne’ w HTMLu) oraz w popularnym formacie do przesyłania danych ‚JSON’, gdzie też jest ograniczenie co do dopuszczalnych znaków.
Czasem jest też wykorzystywany do zapisywania danych/kluczy w bazie danych kiedy chce się je przechowywać w sposób czytelny w polu string, a nie jako ciąg bajtów (np. w kolumnie typu ‚blob’ lub inne do przechowywania danych binarnych).

Podsumowując, kodowanie jest stosowane, aby różne programy mogły się ze sobą komunikować używając takich samych znaków – aby komunikacja była możliwa.

Możliwe zastosowania:
zapis kluczy/danych do przesłania używając formatu który nie pozwala na przesyłanie ‚binarne’ (kiedy bajt może przyjąć dowolną wartość od 0 do 255 – dowolny znak)
zapis klucza/hasha tak, aby użytkownik mógł go wpisać z klawiatury (np. klucz logowania do sieci WiFi w routerach domowych)

Zastosowanie ‚dziwne’:
Zmiana kodowania na nietypowe. Przykład: przesyłanie zaszyfrowanych danych w systemie 62-owym zamiast popularnego 64-owego. Wystarczy napisać funkcje która zapisuje dane używając 62 różne znaki zamiast 64 i dorzucić losowo 2 pozostałe znaki z 64-owego kodowania, a przy odczycie ignorować te 2 znaki. Wtedy osoba (hacker) która ‚podsłuchuje’ wasze połączenie (ale nie ma dostępu do kodu programu, żeby sprawdzić kodowanie) próbując się włamać zmarnuje 5-15 minut zanim ogarnie które znaki są nie istotne i jakie kodowanie jest używane lub podda się i poszuka innego celu który łatwiej złamać. Takie rozwiązanie jest mało skutecznie w przypadku ataku konkretnie na wasz program, ale w przypadku kogoś kto chce ‚coś’ zhackować może go zniechęcić.

Opublikowano PJWSTK - BSI | Skomentuj

[PRO sieci] Kółko i krzyżyk z limitem czasu na ruch w języku Processing

Gra ‚kółko i krzyżyk’ (tic tac toe) napisana w języku Processing (wersja używa funkcji z Javy do pobierania czasu). Dla 2 graczy, limit czasu 5 sekund, kółka/krzyżyki gracza który powinien się ruszyć zmieniają kolor z zielonego do czerwonego (przez żółty) i ‚zanikają’ (zwiększa się przeźroczystość).

Plik gra.pde:

Field[][] fields;
// time to move for players in miliseconds
long timeToMove = 5000;
/* current/winner:
0 = none
1 = player one
2 = player two
*/
int currentPlayer = 0;
int gameWinner = 0;
/* game states:
0 = game not started
1 = game running
2 = game finished
*/
int gameState = 0;
// time of last time counter reset
long timeCounterStart = 0;

long getTime()
{
  // Java's function
  return System.currentTimeMillis() - timeCounterStart;
}

void resetTime()
{
  // Java's function
  timeCounterStart = System.currentTimeMillis();
}

// PROCESSING's function called at start of program
void setup()
{
  // window size
  size(600, 630);
  // draw anti-aliased lines/texts/shapes
  smooth(); 
  // initialize fields array
  fields = new Field[3][3];
  for(int i1 = 0; i1 < 3; i1++)
  {
    for(int i2 = 0; i2 < 3; i2++)
    {
      // create Fields with their 3 and position (position with 30 px offset from top)
      fields[i1][i2] = new Field(width / 3 * i1, 30 + 600 / 3 * i2, width / 3, 600 / 3);
    }
  }
}

// PROCESSING's function called every 'frame draw'
void draw()
{
  // set background color to rgb(0,0,0) [black]
  background(0);
  // game not started
  if(gameState == 0)
  {
    // set 'fill' [for text/shapes] color to rgb(255,255,255) [white]
    fill(255);
    // set text size to 20 px
    textSize(20);
    // draw text
    text("Press ANY KEY to Start", width / 2 - width / 4, height / 2);
  }
  // game is running
  else if(gameState == 1)
  {
    // check time left for move (switch player?)
    if(checkTimeForMove()) // true = time elapsed
    {
      switchPlayer();
    }
    // set 'fill' [for text/shapes] color to rgb(255,255,255) [white]
    fill(255);
    textSize(15);
    text("Player " + getPlayerName(currentPlayer) + " move", 150, 20);
    // draw time left for move
    setDrawColorByTimeLeft();
    textSize(20);
    double timeLeft = ((double)timeToMove - (double)getTime()) / 1000.0;
    text("" + timeLeft, 20, 20);
    // call draw function for each Field
    for(int i1 = 0; i1 < 3; i1++)
    {
      for(int i2 = 0; i2 < 3; i2++)
      {
        fields[i1][i2].draw();
      }
    }
  }
  // someone won game
  else
  {
    // set 'fill' [for text/shapes] color to rgb(255,255,255) [white]
    fill(255);
    // set text size to 20 px
    textSize(20);
    // draw text
    if(gameWinner > 0)
    {
      text("Player " + getPlayerName(gameWinner) + " won game!", width / 2 - width / 4, height / 2);
    }
    else
    {
      text("Game draw!", width / 2 - width / 4, height / 2);
    }
    text("Press ANY KEY", width / 2 - width / 4, (height / 2) + 30);
  }
}
 
//mouse & key functions
void mousePressed()
{
  if(gameState == 1)
  {
    for(int i1 = 0; i1 < 3; i1++)
    {
      for(int i2 = 0; i2 < 3; i2++)
      {
        fields[i1][i2].click(mouseX, mouseY);
      }
    }
  }
  else
  {
    keyPressed();
  }
}

void keyPressed()
{
  if(gameState == 0)
  {
    gameState = 1;
    switchPlayer();
  }
  else if(gameState == 2)
  {
    gameState = 0;
  }
}

String getPlayerName(int id)
{
  if(id == 1)
  {
    return "ONE";
  }
  else
  {
    return "TWO";
  }
}

void setDrawColorByTimeLeft()
{
  double alpha = (double) (timeToMove-getTime()) / (double) timeToMove;
  int g = 255;
  int r = 0;
  if(alpha > 0.5)
  {
    r = (int) ((1 - alpha) * 510);
  }
  else
  {
    r = 255;
    g -= (0.5 - alpha) * 510;
  }
  int alphaValue = (int) (alpha * 155.0) + 100;
  fill(r, g, 0, alphaValue);
  stroke(r, g, 0, alphaValue);
}

void switchPlayer()
{
  resetTime();
  if(currentPlayer == 2)
  {
    currentPlayer = 1;
  }
  else
  {
    currentPlayer = 2;
  }
}

boolean checkTimeForMove()
{
  return timeToMove < getTime();
}

int getWinner()
{
  // lines
  for(int i = 0; i < 3; i++)
  {
    if(fields[i][0].getOwner() != 0 && fields[i][0].getOwner() == fields[i][1].getOwner() && fields[i][1].getOwner() == fields[i][2].getOwner())
  {
    return fields[i][0].getOwner();
    }

    if(fields[0][i].getOwner() != 0 && fields[0][i].getOwner() == fields[1][i].getOwner() && fields[1][i].getOwner() == fields[2][i].getOwner())
  {
    return fields[0][i].getOwner();
    }
  }
  // diagonal 1
  if(fields[0][0].getOwner() != 0 && fields[0][0].getOwner() == fields[1][1].getOwner() && fields[1][1].getOwner() == fields[2][2].getOwner())
  {
    return fields[0][0].getOwner();
  }
  // diagonal 2
  if(fields[0][2].getOwner() != 0 && fields[0][2].getOwner() == fields[1][1].getOwner() && fields[1][1].getOwner() == fields[2][0].getOwner())
  {
    return fields[0][2].getOwner();
  }
  return 0;
}


// Field:
//
//
class Field
{
  int x;
  int y;
  int w;
  int h;
  int fieldOwner = 0;

  Field(int posX, int posY, int fieldWidth, int fieldHeight)
  {
    x = posX;
    y = posY;
    w = fieldWidth;
    h = fieldHeight;
  } 

  void clear()
  {
    fieldOwner = 0; 
  }

  int getOwner()
  {
    return fieldOwner;
  }

  void click(int mx, int my)
  {
    if(fieldOwner > 0)
    {
      return;
    }
    if(mx > x && mx < x+w && my > y && my < y+h)
    {
      fieldOwner = currentPlayer;
      gameWinner = getWinner();
      if(gameWinner == 0)
      {
        for(int i1 = 0; i1 < 3; i1++)
        {
          for(int i2 = 0; i2 < 3; i2++)
          {
            if(fields[i1][i2].getOwner() == 0)
            {
              // not all fields are full
        switchPlayer();
              return;
            }
          }
        }
      }
      for(int i1 = 0; i1 < 3; i1++)
      {
        for(int i2 = 0; i2 < 3; i2++)
        {
          fields[i1][i2].clear();
        }
      }
      gameState = 2;
    }
  }

  void draw()
  {
    noFill();
    stroke(255);
    strokeWeight(3);
    rect(x, y, w, h);
    stroke(150,0,150, 160);
    if(fieldOwner == currentPlayer)
    {
      strokeWeight(6);
      setDrawColorByTimeLeft();
    }
    noFill();
    if(fieldOwner == 1)
    {
      ellipseMode(CORNER);
      ellipse(x, y, w, h);
    }
    else if(fieldOwner == 2)
    {
      line(x, y, x+w, y+h);
      line(x+w, y, x, y+h);
    }
  }
}

Oczywiście każdy pisze sam, zero ściągania 🙂

Opublikowano PJWSTK | Skomentuj

[ASD] Spox, Spoj, szybkie wczytywanie int’ów w C

W tym semestrze zadania z spox’a wymagają jeszcze szybszego wczytywanie danych, niż rok temu, więc wielu osobą może przydać się informacja jak szybko wczytać inty z wejścia.

Jak wczytać z wejścia int’y najszybciej? Wczytując po znaku z wejścia cyfry i zamieniając na int’y kiedy ‚inny znak niż cyfra’.

Do wczytywania najlepiej użyć getchar_unlocked [do użycia tylko w aplikacjach jednowątkowych – czyli takich jak na spox, zwykłe getchar robi to samo tylko, że przy każdym wczytaniu znaku chce synchronizować wątki [jeden wątek?] i wykonuje się 4 razy dłużej!], funkcja ta istnieje na ‚spox.spoj.pl’, jeśli na kompie jej nie macie to do testów możecie podmienić tą linijkę:

#define gc getchar_unlocked

na:

#define gc getchar

A to cała funkcja (TYLKO DLA DODATNICH!):

#define gc getchar_unlocked
void scan_integer( int* o )
{
    register int c = gc();
    int x = 0;
    for( ; ((c<48 || c>57)); c = gc() );

    for( ;c>47 && c<58; c = gc() ) {
        x = (x << 1) + (x << 3) + c - 48;
    }
    *o = x;
}

Wersja dla wszystkich int (ujemnych i dodatnich):

#define gc getchar_unlocked
void scan_integer( int* o )
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for( ; ((c<48 || c>57) && c != '-'); c = gc() );
    if( c=='-' ) {
        neg=1;
        c=gc();
    }
    for( ;c>47 && c<58; c = gc() ) {
        x = (x << 1) + (x << 3) + c - 48;
    }
    if( neg )
        x=-x;
    *o = x;
}

Przykład wczytania i wyświetlenia wszystkich int’ów z wejścia dla czystego C z podstawową biblioteką ‚stdio.h’:

int main()
{
	int liczba;
	while(!feof(stdin))
	{
		scan_integer(&liczba);
		printf("%d ", liczba);
	}
	return 0;
}

Czas wykonania algorytmu na spox z wczytywaniem metoda:
cin >> x; = 0,7 sec
fscanf(stdin, „%d”, &x); = 0,27 sec
scan_integer(&x); // z ‚getchar’ = 0,11 sec!
scan_integer(&x); // z ‚getchar_unlocked’ = 0,03 sec!

 

Więcej informacje na temat: http://stackoverflow.com/a/25388170/4047081

Opublikowano PJWSTK - ASD | 8 komentarzy

[FIZYKA] Lab 3

KOD PONIŻEJ (midPoint) TO TEN SAM KOD CO W NECIE TYLKO TROCHĘ INACZEJ UŁOŻONY, ŻEBY BYŁ CZYTELNIEJSZY – NIE KOPIUJCIE JAK MACIE JUŻ Z NETA

// p - punkt, dt - czas od ostatnich obliczen ruchu [reguluje szybkosc symulacji]
void solveMidPoint(Punkt *p, float dt)
{
	// KOMENTARZ
	// wzory po przeksztalceniu na choc troche prostsza matematyke sa w 'LAB03 metody.pdf'
	// glownie trzeba sie wzorowac na kodzie z 'solveEuler'
	// i dorobic jego rozwiniecie w midPoint
	// i jeszcze dluzsze rozwiniecie w RK4
	// KOMENTARZ END


	// y = pozycja w przestrzeni [zwana w kodzie 'r']
	// t = predkosc i kierunek ruchu [zwana w kodzie 'v']

	// troche zmiennych do trzymania wynikow obliczen
	Wektor k1[2],k2[2];
	Wektor y_k[2];
	Wektor y_h[2];
	Wektor yout[2];
	
	// obliczanie k1 czyli: f(y , t)
	y_h[0] = p->r; // ustawiam 'y'
	y_h[1] = p->v; // ustawiam 't'
	derivatives(y_h, yout, p); // magicznie sie liczy
	k1[0] = yout[0]; // zapisuje wynik 'y' do kolejnych obliczen
	k1[1] = yout[1]; // zapisuje wynik 't' do kolejnych obliczen
	
	// obliczanie k2 czyli: f(y+(h/2)*k1 , t +  h/2)
	y_k[0] = y_h[0] + dt * 0.5 * k1[0]; // ustawiam 'y' uwzgledniajac wynik obliczen k1
	y_k[1] = y_h[1] + dt * 0.5 * k1[1]; // ustawiam 't' uwzgledniajac wynik obliczen k1
	derivatives(y_k, yout, p); // magicznie sie liczy
	k2[0] = yout[0]; // zapisuje wynik 'y' do kolejnych obliczen
	k2[1] = yout[1]; // zapisuje wynik 't' do kolejnych obliczen

	// obliczam nowa pozycje i predkosc 'punktu'
	// ze wzoru: y[n+1] = y[n] + k2 * h + O(h^3)
	// to ostatnie '+ O(h^3)' znacz tyle,
	// ze blad obliczen moze wyniesc maksymalnie 'h do 3' - dosc malo
	// ale tego nie ma jak uwzglednic w obliczeniach
	p->r = p->r + k2[0] * dt;
	p->v = p->v + k2[1] * dt;	
}

Kod RK4 jaki znalazłem w necie ma dość dużo błędów i naprawienie ich zajęło mi dużo czasu [o ile w ogóle poprawiłem je dobrze…], więc tym podzielę się dopiero jak oddam sam [możecie sami kombinować o co w tym chodzi lub oddać za tydzień za 50% pkt.].

 

Opublikowano PJWSTK - FIZ | Skomentuj

[FIZYKA] Praca domowa 01

`The best software.` – Yuri.

Wystarczy dodać ‚input’ i gotowe. Pokazuje wyniki obliczeń i wynik dawany przez jave.

Można też dopisać kilka poprawek, aby dokładniej (!) i szybciej liczyć o czym wspominał na ćwiczeniach (dla sin/cos zostawić jako X resztę z dzielenia przez 2PI, im wyższy stopień tym niższa precyzja obliczeń, a wyniki się powtarzają co 360 stopni).

Możliwe, że wykonuje złą ilość obrotów pętli (pierwszy ‚obrót’ – dla ‚n = 0’ jest wykonywany przed pętlą ‚for’), bo dla ‚k =8’ wykonywane jest obliczanie 8 elementów (n od 0 do 7). Jak ktoś wie, że ma ich być mniej liczone, to wystarczy w ‚for’ zmienić z ‚i < k’ na ‚i < k-1’.

public class Main
{
	public static void main(String[] args)
	{
		int k = 9;
		double x = 3; // moze byc np. 60 stopni: Math.PI / 3
		// pamietamy poczatkowe X do obliczania kwadratu
		double startX = x;
		// pierwszy wyraz szeregu dla sinus to X, wiec go nie liczymy
		double sin = x;
		// pierwszy wyraz szeregu dla cosinus to 1, wiec go nie liczymy
		double cos = 1;
		// pamietamy jaka silnie obliczylismy przed chwila, zeby moc wyliczyc nastepna: silniaWynik = silniaWynik * silnia
		double silnia = 1;
		double silniaWynik = 1;
		// do liczenia 'e do x' potrzebujemy innych silni i poteg
		double eDoX = 1 + x;
		double xEx = x;
		double silniaEx = 1;
		double silniaExWynik = 1;
		// liczymy od 'i=1', bo dla k = 8 chcemy policzyc tylko 7 (a moze 6?) obrotow petli
		for(int i = 1; i < k; i++)
		{
			// ponosimy potege X o jeden w gore
			xEx = xEx * startX;
			// zwiekszamy silnie o jeden w gore
			silniaExWynik *= ++silniaEx;
			// obliczamy kolejny element szeregu 'e do x'
			eDoX += xEx / silniaExWynik;
			// ponosimy potege X o jeden w gore
			x = x * startX;
			// zwiekszamy silnie o jeden w gore
			silniaWynik *= ++silnia;
			if(i % 2 == 0)
			{
				// dla parzystych dodajemy
				cos += (1 / silniaWynik) * x; 
			}
			else
			{
				// dla nie parzystych odejmujemy
				cos -= (1 / silniaWynik) * x; 
			}
			// ponosimy potege X o jeden w gore
			x = x * startX;
			// zwiekszamy silnie o jeden w gore
			silniaWynik *= ++silnia;
			if(i % 2 == 0)
			{
				sin += (1 / silniaWynik) * x; 
			}
			else
			{
				sin -= (1 / silniaWynik) * x; 
			}
		}
		System.out.println(sin + " | " + Math.sin(startX));
		System.out.println(cos + " | " + Math.cos(startX));
		System.out.println(eDoX + " | " + Math.pow(Math.E, startX));
	}

}

Pamiętajcie, żeby nie ściągać, a ten materiał jest tylko w celach nauki (sam oddaje inny).

Opublikowano PJWSTK - FIZ | Skomentuj