Plan Zajęć PJATK z wyszukiwarką

Ucząc się obsługi Selenium napisałem crawler do strony z planem zajęć PJATK ( https://planzajec.pjwstk.edu.pl/PlanOgolny.aspx ). Oryginalna strona działa wolno, a wyszukiwanie wykładowców jest niewygodne. Crawler działa na moim VPS i odświeża dane codziennie o 2 w nocy.

Plan zajęć z wyszukiwarką (np. wykładowców) jest dostępny pod adresem:

http://plan.skalski.pro/

Link do strony dodałem pod logo.

Kod aplikacji w Pythonie i PHP jest dostępny pod adresem:
https://github.com/JSkalskiSBG/PJATK-schedule-crawler

Opublikowano PJWSTK | Skomentuj

[GIZ] Silnie Spójne Składowe – algorytm bez rekurencji

Algorytm Kosaraju do znajdowania silnie spójnych składowych w grafie ( http://www.algorytm.org/algorytmy-grafowe/silnie-spojne-skladowe.html – tu są 2 implementacje rekurencyjne i DOKŁADNY OPIS) zaimplementowałem w wersji bez rekurencji.

Dalej nie wygląda to za przejrzyście, ale jeśli ktoś ma problem ze rozumieniem rekurencji to może pomóc.

/*
"Program znajdujący silnie spójne składowe w grafie skierowanym - bez funkcji rekurencyjnych"
Jerzy Skalski (phoowned@wp.pl)
2017-05-15

Wymagania programu:
C++11 (opcja kompilatora) - można przepisać pętle po vectorach i listach tak, żeby nie był wymagany

Opis wejścia:
W pierwszej linii wejścia znajduje się jedna liczba dodatnia n - liczba wierzchołków grafu.
Dalej następuje n linii; i-ta spośród tych linii ma postać
k a1 a2 ... ak
gdzie a1, a2, ..., ak to numery wierzchołków, do których prowadzą krawędzie z i-tego, zaś k jest liczbą tych wierzchołków.

Przykładowe dane:
5
1 1
3 2 3 4
1 0
0
0

Rysunek grafu skierowanego:
  /<---< 2 <---<\
 /               \
0 >-------------> 1 >--> 3
                   \
                    \>-> 4

Wynik:
SSS ID: 0
1 2 0
SSS ID: 1
3
SSS ID: 2
4

*/
#include <iostream>
#include <map>
#include <vector>
#include <stack>
#include <list>

using namespace std;

int main()
{
    int iloscWezlow, iloscKrawedziWezla, wezel, wezelSasiedni, wezelStartowy, idSilnieSkladowej, i;
    vector<int>* listaSasiadowGraf;
    vector<int>* listaSasiadowGrafTransponowany;
    list<int> kolejnoscOdwiedzaniaDFSem;
	stack<int> wezlyDoOdwiedzenia;
    unsigned int* odwiedzoneWezly;

    cin >> iloscWezlow;

    // inicjujemy tablice
    listaSasiadowGraf = new vector<int>[iloscWezlow];
    listaSasiadowGrafTransponowany = new vector<int>[iloscWezlow];
	odwiedzoneWezly = new unsigned int[iloscWezlow];

    // ladujemy krawedzie do grafu i grafu transponowanego
    for (wezel = 0; wezel < iloscWezlow; ++wezel) {
        cin >> iloscKrawedziWezla;
        for (i = 0; i < iloscKrawedziWezla; ++i) {
            cin >> wezelSasiedni;
            listaSasiadowGraf[wezel].push_back(wezelSasiedni);
            listaSasiadowGrafTransponowany[wezelSasiedni].push_back(wezel);
        }
    }

    for (wezel = 0; wezel < iloscWezlow; ++wezel)
		odwiedzoneWezly[wezel] = 0;

    // przegladamy wezly grafu DFSem
    // zapisujemy czas przetworzenia (kolejnosc odwiedzania post order - dodajemy do listy jak sie 'cofamy')
	for(wezelStartowy = 0; wezelStartowy < iloscWezlow; ++wezelStartowy)
	{
		if(odwiedzoneWezly[wezelStartowy])
			continue;

		wezlyDoOdwiedzenia.push(wezelStartowy);
		while(!wezlyDoOdwiedzenia.empty()) {
			wezel = wezlyDoOdwiedzenia.top();
			wezlyDoOdwiedzenia.pop();

			if(odwiedzoneWezly[wezel]) {
				if(odwiedzoneWezly[wezel] == 1) {
					// push_front - powstanie lista od najwiekszego czasu przetworzenia
					kolejnoscOdwiedzaniaDFSem.push_front(wezel);
					odwiedzoneWezly[wezel] = 2;
				}
				continue;
			}
			odwiedzoneWezly[wezel] = 1;
			wezlyDoOdwiedzenia.push(wezel);
			for(int wezelSasiedni : listaSasiadowGraf[wezel]) {
				if(!odwiedzoneWezly[wezelSasiedni])
					wezlyDoOdwiedzenia.push(wezelSasiedni);
			}
		}
	}

    for (wezel = 0; wezel < iloscWezlow; ++wezel)
		odwiedzoneWezly[wezel] = 0;

    // przegladamy wezly grafu transponowanego DFSem od najwiekszego czasu przetworzenia DFSem
    // wszystkie przejrzane w ten sposob wezly naleza do jednej silnie spójnej składowej

	idSilnieSkladowej = 0;
	for(int wezelStartowy : kolejnoscOdwiedzaniaDFSem) {
		if(odwiedzoneWezly[wezelStartowy])
			continue;

		wezlyDoOdwiedzenia.push(wezelStartowy);
		cout << "SSS ID: " << idSilnieSkladowej << endl;
		// TUTAJ ZACZYNA SIE NOWA SSS
		while(!wezlyDoOdwiedzenia.empty()) {
			wezel = wezlyDoOdwiedzenia.top();
			wezlyDoOdwiedzenia.pop();

			if(odwiedzoneWezly[wezel]) {
				if(odwiedzoneWezly[wezel] == 1) {
					// przy ponownym wejsciu do wezla (cofajac sie DFS - post order) ustawiamy na 2
					odwiedzoneWezly[wezel] = 2;
					cout << wezel << " ";
					// TUTAJ NALEZY WYKONAC OPERACJE NA ELEMENCIE DANEJ SSS
				}
				continue;
			}
			// przy pierwszym wejsciu do wezla ustawiamy na 1
			odwiedzoneWezly[wezel] = 1;
			// dodajemy ten sam wezel ponownie na stos, zeby odwiedzic go podczas cofania
			wezlyDoOdwiedzenia.push(wezel);
			for(int wezelSasiedni : listaSasiadowGrafTransponowany[wezel]) {
				if(!odwiedzoneWezly[wezelSasiedni])
					wezlyDoOdwiedzenia.push(wezelSasiedni);
			}
		}
		cout << endl;
		// TUTAJ KONCZY SIE SSS
		idSilnieSkladowej++;
	}

    return 0;
}

Dla studentów którzy mają zadanie ‚od babki’:

Jeśli chodzi o zadanie ‚od babki’ to trzeba jeszcze dodać jednego ‚for’ (może być z DFSem jak w drugim ‚forze’ lub można w drugim ‚forze’ wygenerować sobie ‚mapę’ ze spisem wszystkich węzłów w każdej SSS) do policzenia ile każda silnie składowa spójna ma sąsiednich SSS, a potem jeszcze jeden ‚for’ do wyświetlenia węzłów należących do tej SSS.

Algorytm który udostępniłem zakłada numerowanie węzłów od 0, a nie 1 jak w danych przykładowych od babki, więc należy przy wczytywaniu połączeń między węzłami zawsze zmieniać ‚-1’ każde połączenie!

Opublikowano Bez kategorii | Skomentuj

[NBD] Ćwiczenia 1

EDIT: Rozwiązanie zadania 7 zmienione na wersję używającą ‚case class’ – zgodnie z wykładem.

Rozwiązanie, zawiera komentarze, więc nie oddawać bez czytania i zrozumienia, bo jak się o coś zapyta to z kodu nie ma szans zrozumieć jak to działa:

import scala.collection.mutable.ListBuffer

object Lab1 {
  def main(args: Array[String]): Unit =
  {
    val days = List("Poniedzialek", "Wtorek", "Sroda", "Czwartek", "Piatek", "Sobota", "Niedziela")

    // 1 A
    var ret = ""
    for (day <- days) {
      ret += day + "\n"
    }
    println("1 A")
    println(ret)

    // 1 B
    ret = ""
    for (day <- days) {
      if (day.startsWith("P")) {
        ret += day + "\n"
      }
    }
    println("1 B")
    println(ret)

    // 1 C
    ret = ""
    days.foreach { day => ret += day + "\n" }
    println("1 C")
    println(ret)

    // 1 D
    ret = ""
    var i = 0
    while (i < days.length) {
      ret += days(i) + "\n"
      i += 1
    }
    println("1 D")
    println(ret)

    // 1 E
    println("1 E")
    println(generateList(days, ""))

    // 1 F
    println("1 F")
    println(generateListReverse(days, ""))

    // 1 G
    println("1 G left")
    println(days.foldLeft("")(_ + "\n" + _ ))
    println("1 G right")
    println(days.foldRight("")(_ + "\n" + _))

    // 1 H
    println("1 H")
    println(days.foldRight("\n") { (element, input) => if (element.startsWith("P")) input + element+ "\n" else input })

    // 2
    val priceMap = Map("Jablko" -> 100, "Pomidor" -> 200)

    println("2")
    println(priceMap.map({case(a,b) => a -> b * 0.9}))

    // 3
    println
    println("3")
    val tuple3 : (String, Int, Double) = ("Al", 42, 200.0)
    printTuple3(tuple3)

    // 4
    println
    println("4")
    val cenaPomidora : Option[Int] = priceMap.get("Pomidor")
    if (cenaPomidora.isDefined) {
      println("Cena pomidora: " + cenaPomidora.get)
    } else {
      println("Nie ma ceny Pomidora w cenniku.")
    }

    // 5
    println
    println("5")
    var element = "Sobota"
    println(element, dayDescription(element))
    element = "Poniedzialek"
    println(element, dayDescription(element))
    element = "Test"
    println(element, dayDescription(element))

    // 6
    println
    println("6")
    val konto1 = new KontoBankowe()
    val konto2 = new KontoBankowe(300)
    println(konto1.stanKonta, konto2.stanKonta)

    konto1.wplata(111)
    konto2.wplata(222)
    println(konto1.stanKonta, konto2.stanKonta)

    konto1.wyplata(11)
    konto2.wyplata(22)
    println(konto1.stanKonta, konto2.stanKonta)

    // blad przy ustalaniu wartosci, 'readonly'
    // konto1.stanKonta = 3
    // konto1._stanKonta = 3

    // 7
    println
    println("7")
    val osoba1 = Osoba("Jan", "Kowalski")
    val osoba2 = Osoba("Piotr", "Nowak")
    val osoba3 = Osoba("Michal", "Nieznajomy")
    println(getHelloMessage(osoba1))
    println(getHelloMessage(osoba2))
    println(getHelloMessage(osoba3))

    // 8
    println
    println("8")
    println(filterZeros(List(0, 0, 0, 1, 4, 6, 0, 4, 9, 0, 4, 5, 0, 0, 0)))

    // 9
    println
    println("9")
    println(increaseByOne(List(1, 3, 6, 2)))

    // 10
    println
    println("10")
    println(magicFilter(List(-15, -5, 0, 5, 15, -13, 13, 12)))
  }

  // 1 E
  def generateList(days: List[String], ret: String): String =
  {
    if (days.nonEmpty) {
      return generateList(days.tail, ret + days.head + "\n")
    }
    ret
  }

  // 1 F
  def generateListReverse(days: List[String], ret: String): String =
  {
    if (days.nonEmpty) {
      return generateListReverse(days.tail, days.head + "\n" + ret)
    }
    ret
  }

  // 3
  def printTuple3(tuple3: (String, Int, Double)): Unit =
  {
    println("String: " + tuple3._1, "Int: " + tuple3._2, "Double: " + tuple3._3)
  }

  // 5
  def dayDescription(dayName: String): String = dayName match {
    case "Poniedzialek" => "Praca"
    case "Wtorek" => "Praca"
    case "Sroda" => "Praca"
    case "Czwartek" => "Praca"
    case "Piatek" => "Praca"
    case "Sobota" => "Weekend"
    case "Niedziela" => "Weekend"
    case _ => "Nie ma takiego dnia"
  }

  // 6
  class KontoBankowe(poczatkowyStanKonta: Int) {
    def this() = this(0)
    private var _stanKonta: Int = poczatkowyStanKonta

    def wplata(kwota : Int): KontoBankowe = {
      this._stanKonta += kwota
      this
    }

    def wyplata(kwota : Int): KontoBankowe = {
      this._stanKonta -= kwota
      this
    }

    def stanKonta : Int = this._stanKonta
  }

  // 7
  case class Osoba(imie: String, nazwisko: String) {
    def nazwa : String = imie + " " + nazwisko
  }
  def getHelloMessage(osoba: Osoba): String = osoba match {
    case Osoba("Jan", "Kowalski") => "Witaj Jan!"
    case Osoba("Piotr", "Nowak") => "Czesc Piotr!"
    case _ => "Witaj nieznajomy"
  }

  // 8
  def filterZeros(list: List[Int]): List[Int] = {
    var newList = new ListBuffer[Int]()
    list.foreach { element => if (element != 0) newList += element }
    newList.toList

    // krotka wersja:
    // return list.filter(v => v != 0)
  }

  // 9
  def increaseByOne(numbers : List[Int]) : List[Int] = {
    numbers.map((d) => d+1)
  }

  // 10
  def magicFilter(list: List[Int]): List[Int] = {
    var newList = new ListBuffer[Int]()
    list.foreach { element => if (-5 <= element && element <= 12) newList += scala.math.abs(element) }
    newList.toList
  }
}

							
Opublikowano Bez kategorii | Skomentuj

[PUZ][2016] Nauczanie łamigłówkowe – zadania z wykładu – wykład nr 1

WYKŁAD 2, ZADANIE 2 B:

TRATWA BĘDZIE PŁYNĄĆ 6 GODZIN. Mam na to dowód na kartce nabazgrany, ale na pewno każdy inżynier sam sobie dowód obliczy. Mamy 2 elementy składające się na prędkość łodzi motorowej. Silnik daje 2 razy więcej prędkości, niż prąd rzeki. Proporcje, wpływ prędkości na czas podróży, ‚s = v * t’ itp.

Rozwiązanie zadań z wykładu pierwszego.
1 A:

1 B:

 

Opublikowano Bez kategorii | Skomentuj

[ASD][2015]Treści zadań (3, 4, 5, 6) i dodatkowe dane do testowania

STUDENCIE 2 ROKU! PAMIĘTAJ, ŻE KAŻDE ZADANIE JEST PUNKTOWANE TAK SAMO, A DO ZALICZENIA POTRZEBA TYLKO TRZECH.

ZAZWYCZAJ 2 PIERWSZE ZADANIA SĄ NAJŁATWIEJSZE, WIĘC NIE ZAŚPIJ NA POCZĄTKU SEMESTRU!

Treści zadań które miałem z tamtego semestru:
http://skalski.at/files/?dir=files/PJWSTK/ASD/zadania_tresci_i_dane/2015_pazdziernik-2016_luty

Do niektórych zadań są dodatkowe dane do testów – duże zbiory jak na spox’ie, a nie te przykładowe co są w treści zadania. Pliki mają nazwy ‚in’ (to dajemy programowi na wejście) i ‚out’ (to powinien zwrócić program) oraz numer testu ze spoxa.

Zadania co roku zmieniają się numerami i pojawia się 1-2 nowe, więc warto sprawdzić wszystkie.

Opublikowano PJWSTK, PJWSTK - ASD | Skomentuj

[PJATK] ASD – wiosna 2016 – Zadanie 5 – Prawie rozwiązanie

Problemy z algorytmem podobne jak w ‚problem liszaja’ [ https://www.youtube.com/watch?v=4pdBHJYf3Hw ] – setki rozwiązań w internecie. Tylko, że na ASD zamiast tablicy 2-wymiarowej mamy graf.
Chodzi o to, że mamy jakieś wierzchołki grafu ‚zarażone’ [założone sztaby wyborcze] i one zarażają te z którymi mają kontakt [miasta sąsiedzkie]. Jednak, żeby nie było za łatwo, wszystko trzeba podzielić na tury. Wierzchołki zarażone w danej turze zaczynają zarażać dopiero w następnej. Jak już się zrozumie o co chodzi to napisanie programu jest bardzo proste.

Jeśli uda mi się na jutro dokończyć artykuł o list/vector/map w C++ to wrzucę, żeby trochę rozjaśnić temat dlaczego korzystam z tylu ‚map’ i jakie cudowne właściwości one mają.

 
Jednak dla osób które mają problem udostępniam pseudokod/trochę jak C++. Do niedzieli, do północy, jest jeszcze czas na przerobienie tego na działający program.

Jeśli kod poniżej jest kiepsko wyświetlany, to można też go obejrzeć na pełnej szerokości okna z kolorowaniem składni [głównie komentarzy]:

http://hastebin.com/kodekiwita.php

 

klasa Kandydat
{
	- id
	- koszt kampanii metoda A
	- koszt kampanii metoda B
};

klasa Miasto
{
	- id
	- zwyciezca metoda A
	- zwyciezca metoda B
	- lista sasiadow
};

funckja wczytajLiczbe()
{
	// wczytuje liczbe z wejscia do zmiennej
}

int main()
{
	// 1. tworzymy liste/tablice zawierajaca wszystkie miasta
	var iloscMiast;
	wczytajLiczbe >> iloscMiast;

	// musi byc mozliwosc latwego zaladowania miasta o numerze X
	var listaMiast = (lista miast o wielkosci 'iloscMiast');
	for(i < iloscMiast, i++)
	{
		// dodajemy do listy miasta, zapamietujac w miastach ich ID
		listaMiast[i] = new Miasto(i);
	}
	
	// 2. wczytujemy sasiadow miast
	var sasiad_1;
	var sasiad_2;
	wczytajLiczbe >> sasiad_1;
	wczytajLiczbe >> sasiad_2;

	// do czasu az wystapi koniec listy sasiadow
	while(sasiad_1 != -1)
	{
		// oba miasta sasiedzkie musza miec dodane siebie nawzajem do list sasiadow
		listaMiast[sasiad_1]->lista_sasiadow->dodaj(sasiad_2);
		listaMiast[sasiad_2]->lista_sasiadow->dodaj(sasiad_1);
		
		wczytajLiczbe >> sasiad_1;
		wczytajLiczbe >> sasiad_2;
	}

	// 3. tworzymy liste/tablice kandydatow od razu wczytujac ich startowe miasto
	var iloscKandydatow;
	wczytajLiczbe >> iloscKandydatow;
	
	// musi byc mozliwosc latwego zaladowania kandydata o numerze X
	var listaKandydatow = (lista kandydatow o wielkosci 'iloscKandydatow');

	map<Miasto*, char> listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda; // bez powtorzen = 'map', klucz musi byc unikalny, a wartosc moze byc dowolna

	for(i < iloscKandydatow, i++)
	{
		var miastoStartoweKandydata;
		wczytajLiczbe >> miastoStartoweKandydata;

		for(sasiad in listaMiast[miastoStartoweKandydata])
		{
			// przeprowadz wybory u kazdego sasiada startowego miasta
			listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda[miastoStartoweKandydata] = ' ';
		}

		// dodajemy do listy kandydatow, zapamietujac w kandydatach ich ID
		listaKandydatow[i] = new Kandydat(i);

		// w miescie startowym zapamietujemy kto jest zwyciezca
		listaMiast[miastoStartoweKandydata]->zwyciezcaKampaniiMetodaA = listaKandydatow[i];
		listaMiast[miastoStartoweKandydata]->zwyciezcaKampaniiMetodaB = listaKandydatow[i];

		// w kandydacie zapisujemy zmiane kosztu kampanii, zalozenie sztabu w startowym miescie
		listaKandydatow[i]->kosztKampaniiMetodaA++;
		listaKandydatow[i]->kosztKampaniiMetodaB++;
	}

	// 4. tworzymy 'mapy' do przechowywania wielu danych
	
	// tak samo jak 'listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda', lista bez powtorzen miast do przeprowadzenia wyborow
	map<Miasto*, char> listaMiastDoPrzeprowadzeniaWyborow_aktualnaRunda;
	
	// dla kazdego miasta bedziemy potrzebowac tymczasowa liste kandydatow na zwyciezce i ilosc glosow na nich oddanych [przez sasiednie miasta]
	map<Kandydat*, short int> glosyNaKandydataMetodaA;
	map<Kandydat*, short int> glosyNaKandydataMetodaB;
	
	// zwyciezcow wyborow mozemy zapisac dopiero po przeprowadzeniu wszystkich glosowan w 'danej rundzie'
	// inaczej glosowania z danej rundy mogly by wplywac na wyniki glosowan w tej samej rundzie
	map<Miasto*, Kandydat*> zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaA;
	map<Miasto*, Kandydat*> zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaB;
	
	// 5. mielimy dane (przegladamy graf)
	while(nie pusta 'listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda')
	{
		// przepisujemy miasta z 'nastepnej rundy' do 'aktualnej rundy'
		wyczysc 'listaMiastDoPrzeprowadzeniaWyborow_aktualnaRunda';
		listaMiastDoPrzeprowadzeniaWyborow_aktualnaRunda = listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda;
		wyczysc 'listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda';

		// przeprowadzamy wybory w kazdym
		for(miasto in listaMiastDoPrzeprowadzeniaWyborow_aktualnaRunda)
		{
			// sprawdzamy czy w miescie nie ma jeszcze zwyciezcy
			// po poczatkowym dodawaniu kandydatow do miast startowych na liscie moga byc miasta w ktorych juz sa zwyciezcy
			if(czy nie ma zwyciezcy w 'miasto')
			{
				// czyscimy glosy oddane przy poprzednim liczeniu
				wyczysc 'glosyNaKandydataMetodaA';
				wyczysc 'glosyNaKandydataMetodaB';

				// dla kazdego miasta w sasiedztwie
				for(miastoSasiedzkie in miasto->lista_sasiadow)
				{
					if(czy jest zwyciezca w 'miastoSasiedzkie')
					{
						// jesli jest zwyciezca to oddaje on glosy metoda A i B
						
						// korzystamy z 'magicznej' wlasciwosci 'map',
						// operator ++: dla elementu ktory nie istnieje w mapie ustawia jego wartosc na 1 (startowa wartosc int to 0)
						// a dla elementu ktory juz jest w mapie zwieksza wartosc powiazanego 'inta'
						// nie musimy sie martwic o to czy cos jest w mapie itp., wszystko dziala tak jak bysmy chcieli
						
						// glos metoda A oddaje zwyciezca metoda A
						glosyNaKandydataMetodaA[miastoSasiedzkie->zwyciezcaKampaniiMetodaA]++;
						// glos metoda B oddaje zwyciezca metoda B
						glosyNaKandydataMetodaB[miastoSasiedzkie->zwyciezcaKampaniiMetodaB]++;
					}
					else
					{
						// jesli w miescie nie ma zwyciezcy to znaczy, ze w nastepnej rundzie nalezy w tym miescie przeprowadzic wybory
						listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda[miastoSasiedzkie] = ' ';
					}
				}

				// glosy przez wszystkich sasiadow zostaly oddane, teraz trzeba ustalic ktory kandydat wygral metoda A i B
				
				
				// Metoda A: kandydat ma miec najmniej glosow, a dla tych o takiej samej ilosci glosow wybieramy tego z wyzszym ID
				int minimalnaIloscGlosow = 100000; // ustawiamy jakas wartosc wieksza, niz maksymalna ilosc glosow [ilosc miast]
				Kandydat* zwyciezajacyKandydatMetodaA;
				for(map<Kandydat*, short int>::iterator it in glosyNaKandydataMetodaA)
				{
					if(it->second < minimalnaIloscGlosow || 
						(it->second == minimalnaIloscGlosow && it->first->id > zwyciezajacyKandydatMetodaA->id))
					{
						zwyciezajacyKandydatMetodaA = it->first;
						minimalnaIloscGlosow = it->second;
					}
				}
				// zapamietujemy kto wygral, ale nie zapisujemy w miescie, to zrobimy po zakonczeniu wyborow we wszystkich miastach w tej rundzie
				zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaA[miasto] = zwyciezajacyKandydatMetodaA;
				// zwiekszamy koszt kampanii metoda A
				zwyciezajacyKandydatMetodaA->kosztKampaniiMetodaA++;
				
				
				// Metoda B: kandydat ma miec najwiecej glosow, a dla tych o takiej samej ilosci glosow wybieramy tego z nizszym ID
				int maksymalnaIloscGlosow = 0;
				Kandydat* zwyciezajacyKandydatMetodaB;
				for(map<Kandydat*, short int>::iterator it in glosyNaKandydataMetodaB)
				{
					if(it->second > maksymalnaIloscGlosow || 
						(it->second == maksymalnaIloscGlosow && it->first->id < zwyciezajacyKandydatMetodaB->id))
					{
						zwyciezajacyKandydatMetodaB = it->first;
						maksymalnaIloscGlosow = it->second;
					}
				}
				// zapamietujemy kto wygral, ale nie zapisujemy w miescie, to zrobimy po zakonczeniu wyborow we wszystkich miastach w tej rundzie
				zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaB[miasto] = zwyciezajacyKandydatMetodaB;
				// zwiekszamy koszt kampanii metoda B
				zwyciezajacyKandydatMetodaB->kosztKampaniiMetodaB++;
			}
		}
		// skonczyly sie wybory tej rundy, pora przypisac zwyciezcow do miast
		for(map<Miasto*, Kandydat*>::iterator it in zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaA)
		{
			// metoda A
			it->first->zwyciezcaKampaniiMetodaA = it->second;
		}
		for(map<Miasto*, Kandydat*>::iterator it in zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaB)
		{
			// metoda B
			it->first->zwyciezcaKampaniiMetodaB = it->second;
		}
		
		wyczysc 'zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaA';
		wyczysc 'zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaB';
		
		// mozna zaczac kolejna ture wyborow
	}
	// wszystkie wybory sie skonczyly, pora wypisac koszty kampanii
	for(i < iloscKandydatow, i++)
	{
		wyswietl << listaKandydatow[i]->kosztKampaniiMetodaA;
		wyswietl << "spacja";
		wyswietl << listaKandydatow[i]->kosztKampaniiMetodaB;
		wyswietl << "znak nowej linii 🙂 ";
	}
}
Opublikowano PJWSTK, PJWSTK - ASD | Skomentuj

[PJATK][SKJ 2016] Serwer Proxy z ograniczaniem dostępu

Zadanie na 17.01.2016 z SKJ.

Niestety nie mam gotowego rozwiązania, ale mam serwer proxy z filtrem po IP (z maską sieci) i domenie, więc zostało dopisać protokół do ustawiania różnych ograniczeń zgodnie z treścią zadania.

Aby z niego skorzystać należy zainstalować ‚Maven’ w Eclipse. W moim ‚Eclipse for Java’ był już dołączony, a w necie jest dużo kursów jak to zrobić. Aby sprawdzić czy jest zainstalowany wejdź w ‚Window -> Preferences’, po lewej stronie powinien być ‚Maven’ na liście . Po instalacji Mavena trzeba załadować listę bibliotek:

Kliknij na górze Eclipse: ‚Window -> Show View -> Other..’, a w otwartym oknie w ‚Maven -> Maven Repositories’. Na dole Eclipse otworzy się nowe okno. Rozwinąć opcję ‚Global’ i nacisnij prawym myszki na ‚centel’. W menu kliknij ‚Rebuild Index’. Może to zająć kilka-kilkanaście minut.

Kolejne kroki konfiguracji to dużo pisania. Mam nadzieję, że projekt Maven który eksportowałem jako archiwum z Eclipse wam zadziała:
http://skalski.at/files/files/PJWSTK/SKJ_proxy_filters/LittleProxyWithIpAndDomainFilters.zip

Program składa się z LittleProxy-1.1.0-beta1 (to coś powinien wam zainstalować Maven automatycznie jak wgracie mój projekt, bo jest w nim plik ‚pom.xml’ w którym jest takie ‚dependency’) oraz tylko 2 plików:

MyProxyApp.java (z mainem):

package prx2.prx2;

import org.littleshoot.proxy.HttpFiltersAdapter;
import org.littleshoot.proxy.HttpFiltersSourceAdapter;
import org.littleshoot.proxy.impl.DefaultHttpProxyServer;

import io.netty.channel.ChannelHandlerContext;
import io.netty.handler.codec.http.HttpRequest;

public class MyProxyApp 
{
    public static void main( String[] args )
    {
        System.out.println( "Proxy started!" );
        
	    DefaultHttpProxyServer.bootstrap()
	        .withPort(8088)
	        .withFiltersSource(new HttpFiltersSourceAdapter()
    	        {
    	            public HttpFiltersAdapter filterRequest(HttpRequest originalRequest, ChannelHandlerContext ctx)
    	            {
    	               return new MyHttpFilter(originalRequest, ctx);
    	            }
    	        })
	        .start();
	    
        System.out.println( "Proxy is working!" );
        
        /*
         * TUTAJ KOD ODPOWIEDZIALNY ZA KOMUNIKACJE Z KLIENTEM KONTROLUJACYM LISTY DOSTEPU
         * postawienie jakiegos serwera, na jakims porcie, nasluchiwanie polaczen, obsluga ich w nowych watkach itd.
         */
    }
}

 

oraz pliku MyHttpFilter.java odpowiedzialnego za filtrowanie połączeń:

package prx2.prx2;

import java.net.Inet4Address;
import java.net.InetAddress;
import java.net.UnknownHostException;

import org.littleshoot.proxy.HttpFiltersAdapter;

import io.netty.buffer.Unpooled;
import io.netty.channel.ChannelHandlerContext;
import io.netty.handler.codec.http.DefaultFullHttpResponse;
import io.netty.handler.codec.http.HttpObject;
import io.netty.handler.codec.http.HttpRequest;
import io.netty.handler.codec.http.HttpResponse;
import io.netty.handler.codec.http.HttpResponseStatus;

public class MyHttpFilter extends HttpFiltersAdapter
{
	ChannelHandlerContext ctx;

	public MyHttpFilter(HttpRequest originalRequest, ChannelHandlerContext ctx)
	{
		super(originalRequest, ctx);
		this.ctx = ctx;
	}

	public HttpResponse clientToProxyRequest(HttpObject httpObject)
	{

		if(httpObject instanceof HttpRequest)
		{
			HttpRequest httpRequest = (HttpRequest) httpObject;

			try
			{
				// cos jak: http://www.onet.pl/podstrona/index.html
				// LUB w przypadku HTTPS: www.onet.pl:443
				String uri = httpRequest.getUri();
	
				// nalezy z 'uri' wyciagnac 'www.onet.pl'
				String[] domainData = uri.split("/", 4);
				String domain = null;
				if(domainData.length == 1)
				{
					domain = domainData[0].split(":")[0];
				}
				else if(domainData.length >= 3)
				{
					domain = domainData[2].split(":")[0];
				}
				else
				{
					throw new Exception("INVALID HOST FORMAT");
				}
				
	
				// IP otwierajacego strone www w formacie: 127.0.0.1
				String clientIP = ctx.channel().remoteAddress().toString().split(":")[0].split("/")[1];
			
				// IP w formacie ulatwiajacym porownywanie przy uzyciu maski
				int clientIPint = MyHttpFilter.ipStringToInt(clientIP);

				boolean blockWebsite = false;

				
				// KOD REGULUJACY DOSTEP DO DANEJ STRONY

	
				// PRZYKLADOWE BLOKADY
				if(domain.contains("google")) // dostepne: contains, equals [nie porownywac uzywajac '==', to nie C++!], startsWith, endsWith
					blockWebsite = true;
				
				if(domain.equals("www.wp.pl") || domain.equals("wp.pl")) // mozna zamiast tego 'endsWith'
					blockWebsite = true;

				if(isIpInNetwork(clientIPint, MyHttpFilter.ipStringToInt("127.0.2.2"), 24)) // czy klient w sieci: 127.0.2.2/24 (znaczy 127.0.2.*)
					blockWebsite = true;
	
				
				// JESLI ZABLOKOWANY, TO NIE WYSYLAJ ZAPYTANIA DO WSKAZANEGO SERWERA, TYLKO OD RAZU ZWROC KLIENTOWI KOD 403
				if(blockWebsite)
				{
					System.out.println("ACCESS DENIED  FOR CLIENT IP: " + clientIP + " (" + clientIPint  + "), DOMAIN: " + domain);
					
					return new DefaultFullHttpResponse(httpRequest.getProtocolVersion(), HttpResponseStatus.FORBIDDEN, Unpooled.copiedBuffer("403 PROXY: ACCESS DENIED".getBytes()));
				}
				
				System.out.println("ACCESS GRANTED FOR CLIENT IP: " + clientIP + " (" + clientIPint  + "), DOMAIN: " + domain);
			}
			catch (Exception e)
			{
				// jesli wystapil blad przy zamianie IP (stringa np. "127.0.0.0") na ciag bajtow, to zwroc blad 500
				return new DefaultFullHttpResponse(httpRequest.getProtocolVersion(), HttpResponseStatus.INTERNAL_SERVER_ERROR, Unpooled.copiedBuffer(("500 PROXY: " + e.getMessage()).getBytes()));
			}
		}

		return null;
	}

    public static int ipStringToInt(String ipString) throws Exception
    {
    	Inet4Address ipv4;
		try
		{
			ipv4 = (Inet4Address) InetAddress.getByName(ipString);
		}
		catch (UnknownHostException e)
		{
			throw new Exception("CANNOT RESOLVE ADDRESS " + ipString);
		}
    	byte[]       ipAsByteArray = ipv4.getAddress();
    	int          ipAsInt = ((ipAsByteArray[0] & 0xFF) << 24) |
    	                 ((ipAsByteArray[1] & 0xFF) << 16) |
    	                 ((ipAsByteArray[2] & 0xFF) << 8)  |
    	                 ((ipAsByteArray[3] & 0xFF) << 0);
    	return ipAsInt;
    }

    public static boolean isIpInNetwork(int testIp, int networkIp, int networkMask) throws Exception
    {
    	// magia na bitach (operacja AND na bitach IP i bitach maski)
    	int maskInt = ~((1 << (32 - networkMask)) - 1);
    	return ((testIp & maskInt) == (networkIp & maskInt));
    }
}

Jako przykład dodałem do filtra 3 reguły:

// dostepne: contains, equals [nie porownywac uzywajac '==', to nie C++!], startsWith, endsWith
if(domain.contains("google"))
	blockWebsite = true;

// mozna zamiast tego 'endsWith'
if(domain.equals("www.wp.pl") || domain.equals("wp.pl"))
	blockWebsite = true;

// czy klient w sieci: 127.0.2.2/24 (znaczy 127.0.2.*)
if(isIpInNetwork(clientIPint, MyHttpFilter.ipStringToInt("127.0.2.2"), 24))
	blockWebsite = true;

Wasze zadanie to zrobić protokół komunikacji na jakimś innym porcie, przez który użytkownik będzie mógł dodawać listy IP i listy domen, a potem wiązać je dodając zasadę ‚allow’ czy ‚deny’.

Następnie trzeba tylko dopisać, żeby te listy były uwzględniane przez proxy i opisać wszystko dokładnie w dokumentacji.

Zgodnie z poleceniem, serwer proxy można ściągnąć z sieci i nie trzeba wiedzieć jak on działa.

Opublikowano PJWSTK - SKJ | Skomentuj

[PJWSTK] ASD – jesień 2015 – Zadanie 4 – Porady

Sam algorytm jest banalny do napisania, ale nie mam zgody twórcy na publikację kodu (rok temu dostał 100%).

Najpierw wytłumaczę o co chodzi w poleceniu:
„Wyznacz liczbę klas abstrakcji zbioru R ustalonych względem relacji binarnej r takiej, że m(i) r m(j) wtedy i tylko wtedy, gdy suma elementów podmacierzy m(i) jest równa sumie elementów podmacierzy m(j), dla 0<=i,j<k. Dodatkowo ustal liczbę klas abstrakcji o maksymalnym rozmiarze oraz średnią wartość sum elementów podmacierzy stanowiących zbiór R zredukowaną do jej części całkowitoliczbowej.”

Tłumacząc to na ‚nasze’:
1. mamy macierz kwadratową X (którą trzymamy jako tablice 2 wymiarową)
2. potem dostajemy dużo linijek, a w każdej 4 liczby które wyznaczają ‚lewy górny’ i ‚prawy dolny’ róg ‚podmacierzy’ (czyli prostokąta)
3. dla każdej podmacierzy musimy wyliczyć sumę elementów

Na wyjściu musimy wyświetlić 3 liczby:
(liczba klas abstrakcji, liczba klas abstrakcji o maksymalnym rozmiarze, średnia wartość sum elementów podmacierzy należących do zbioru R)

Najpierw 2 definicje:
klasa abstrakcji – suma elementow podmacierzy
rozmiar klasy abstrakcji – ilosc podmacierzy o konkretnej sumie elementow podmiacierzy

Teraz co wyświetlić:
1. ilość podmacierzy o różnych sumach elementów (czyli jak dwie lub więcej podmacierzy ma taka samą sumę elementów to do tego licznika dodajemy ją jako jedną podmacierz)

2. (najdziwniejszy punkt):
mozemy miec klasy abstakcji ktore zapiszemy w ‚map’ w C++ (przykład: mielismy 14 podmacierzy, ale suma ich elementow dawala tylko 4 rozne wyniki):
suma elementow podmacierzy -> ilosc wystapien
390 – 3
293 – 5
43 – 5
178 – 1
a na wyjsciu ma byc: 2, bo maksimum to 5, a ilosc wystapien maksimum to wlasnie 2

3. banał, sumować wszystkie ‚sumy podmacierzy’ i podzielić przez ich ilość (czyli ‚k’), operowac na int (long long int) to sie samo zaokragli w dół zgodnie z poleceniem
Teraz cały problem z algorytmem:
Obliczanie sum podmacierzy to masa dodawania która zajmie ‚za dużo czasu’. Zamiast tego można uzyskać sumę elementów jedną linijką obliczeń:

sumaElementowPodmacierzy = 
  macierz[wierszDolny+1][kolumnaPrawa+1] + 
  macierz[wierszGorny][kolumnaLewa] - 
  macierz[wierszGorny][kolumnaPrawa+1] - 
  macierz[wierszDolny+1][kolumnaLewa];

Tylko najpierw przy wczytaniu macierzy trzeba zapisac w kazdej komorce macierzy ‚sume elementow w gore i lewo od tej komorki z jej wartoscia włącznie’ zamiast ‚jej wartosci’ – co mozna tez obliczac jedna linijka.
Dla ulatwienia obliczen mozna utworzyc macierz kwadratową o rozmiarze ‚n+1’ zamiast ‚n’ i w pierwsza linijke/pierwsza kolumne wpisac same zera.

Rysunek pomocniczy:


Ważne, żeby pamiętać o używaniu w większości miejsc ‚long long int’.

Gotowy program ma mniej, niż 100 linijek i składa się z paru pętli ‚for’ oraz jednej ‚pętli po mapie’. Rozwiązanie rok temu dostało 100%, ale nie mogę go publikować.

 

— DLA GOOGLE —

ZADANIE NUMER 4

Rozważmy macierz kwadratową M rozmiaru n, której elementy są liczbami całkowitymi. Dalej R={m(0),m(1),…,m(k-1)}jest zbiorem k różnych podmacierzy macierzy M (przez podmacierz rozumiemy spójny fragment macierzy właściwej o zadanych indeksach elementów krańcowych).
Wyznacz liczbę klas abstrakcji zbioru R ustalonych względem relacji binarnej r takiej, że m(i) r m(j) wtedy i tylko wtedy, gdy suma elementów podmacierzy m(i) jest równa sumie elementów podmacierzy m(j), dla 0<=i,j<k. Dodatkowo ustal liczbę klas abstrakcji o maksymalnym rozmiarze oraz średnią wartość sum elementów podmacierzy stanowiących zbiórR zredukowaną do jej części całkowitoliczbowej.

WEJŚCIE

Wiersz zawierający liczby n oraz k oddzielone znakiem odstępu (kod ASCII 32) i zakończony znakiem nowej linii (kod ASCII 10). Następnie n wierszy reprezentujących kolejne wiersze macierzy M, w których elementy rozdzielone są znakiem odstępu, a każdy wiersz zakończony jest znakiem nowej linii. Dalej k wierszy, z których każdy reprezentuje podmacierz m(i), dla i=0,1,…,k-1, postaci:
– liczba określająca indeks wiersza lewego górnego „rogu” podmacierzy m(i), znak odstępu,
– liczba określająca indeks kolumny lewego górnego „rogu” podmacierzy m(i), znak odstępu,
– liczba określająca indeks wiersza prawego dolnego „rogu” podmacierzy m(i), znak odstępu,
– liczba określająca indeks kolumny prawego dolnego „rogu” podmacierzy m(i), znak nowej linii.
Zakładamy indeksowanie wierszowe i kolumnowe elementów macierzy M od 0 do n-1 włącznie.

WYJŚCIE

Wiersz zawierający trzy liczby całkowite oddzielone znakiem odstępu (liczba klas abstrakcji, liczba klas abstrakcji o maksymalnym rozmiarze, średnia wartość sum elementów podmacierzy należących do zbioru R) stanowiące rozwiązanie problemu.

OGRANICZENIA

Liczby n i k ograniczone kolejno od dołu przez 1, od góry odpowiednio przez 10^4 oraz 10^8. Elementy macierzy Mograniczone przedziałem [-10^3,10^3].

LIMITY

Oczekiwana złożoność czasowa rzędu O(n^2+klgk). Oczekiwana złożoność pamięciowa rzędu O(n^2+k).

PRZYKŁAD 1

wejście:
4 8
-2 -2 -3 1
3 0 1 3
1 3 -3 3
2 0 0 -2
0 0 2 1
2 2 2 3
1 2 1 3
3 2 3 3
3 0 3 3
0 1 2 1
3 3 3 3
1 3 1 3

wyjście:
5 3 0

/* KOMENTARZ DO ROZWIĄZANIA
Oznaczmy przez SM0, SM1, …, SM7 sumy elementów kolejnych podmacierzy podanych na wejściu, wtedy:
SM0=(-2)+(-2)+3+0+1+3=3
SM1=(-3)+3=0
SM2=1+3=4
SM3=0+(-2)=(-2)
SM4=2+0+0+(-2)=0
SM5=(-2)+0+3=1
SM6=(-2)
SM7=3
Stąd liczba klas abstrakcji względem rozważanej relacji jest równa 5 (różne wartości w/w sum to kolejno (-2), 1, 0, 3 oraz 4). Dalej, liczba klas abstrakcji o maksymalnym rozmiarze równa jest 3, są to klasy abstrakcji elementów (-2), 0 oraz 3. Ostatecznie średnia wartość sumy elementów rozważanych podmacierzy zredukowana do części całkowitoliczbowej to:
(3+0+4+(-2)+0+1+(-2)+3)/8=7/8=0
Zatem odpowiedź stanowi trójka liczb 5, 3 oraz 0. */

PRZYKŁAD 2

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

wyjście:
8 8 -4

PRZYKŁAD 3

wejście:
16 24
1 -9 7 1 8 -5 0 -7 -2 5 7 -1 -5 -1 0 8
-6 2 0 5 -5 -3 0 3 6 9 2 9 7 9 7 1
4 -6 -1 -6 2 -4 -7 -3 1 0 8 8 2 6 1 6
5 0 0 6 -5 -5 -8 -9 -3 -5 2 -1 -1 9 4 -8
9 -5 -6 -2 0 -5 7 1 7 0 -9 -3 -9 -6 0 -9
6 9 2 5 -6 -2 -6 0 0 4 3 -5 7 -4 -4 9
-4 -8 6 -6 3 5 -3 -8 5 -5 9 -8 -2 3 7 6
2 -1 -1 8 7 -5 -8 1 1 0 7 0 4 6 9 -4
-9 -9 0 4 -2 8 -1 6 8 5 -3 -9 1 -7 0 8
-8 7 8 8 -1 3 0 -6 -4 -2 1 -9 2 -5 -4 -8
-3 -1 9 8 8 1 -6 8 -4 -8 0 -7 -7 -9 -4 6
0 -2 7 -1 6 7 1 2 9 -7 -6 8 -2 7 -2 9
-9 1 -8 -3 7 4 4 -1 9 -8 8 5 8 9 8 -2
-8 -5 5 -8 5 8 4 -4 1 5 9 -5 -8 5 -6 -8
1 6 0 -7 9 9 7 -1 0 0 4 5 9 5 -8 -1
-5 -5 2 6 7 9 6 -6 -8 -9 -3 9 -9 -8 9 5
2 11 15 15
12 12 12 12
15 7 15 15
10 1 13 14
0 14 8 15
8 13 9 13
11 2 12 7
0 2 15 15
12 13 15 13
1 10 14 11
13 7 13 15
14 14 14 14
15 6 15 6
8 9 8 15
11 5 15 9
15 6 15 10
10 12 14 15
7 12 14 13
14 4 14 13
9 13 15 15
4 4 7 12
12 6 14 12
11 7 11 15
10 2 11 4

wyjście:
21 3 20

Opublikowano PJWSTK, PJWSTK - ASD | 2 komentarze

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

Drzewo binarne – najstarsze słowo – rozwiązanie nr 2 (łatwiejsze)

ZADANIE NA 29.11.2015, WIĘC JESZCZE MACIE PONAD 2 TYGODNIE NA PRZEROBIENIE GO NA TYSIĄC SPOSOBÓW 🙂

Rozwiązanie nigdy nie wrzucane na spox, więc nie wiem ile punktów dostanie.

Jest to rozwiązanie ŁATWIEJSZE (w rekurencji jest najprostsza możliwa pętla).

Rozwiązanie TRUDNIEJSZE (około 30% szybsze):

http://skalski.at/2015/11/14/pjwstk-asd-jesien-2015-zadanie-2-rozwiazanie-nr-1/

Rozwiązanie oszczędzające 1/3 pamięci, ale dające tylko 85% punktów w tym roku (z przed 2 lat):

http://skalski.at/2012/11/17/pjwstk-asd-kolokwium-3-rozwiazanie/

Inne możliwe rozwiązania:

  • można utworzyć listę elementów (oprócz drzewa) i na niej znaleźć ‚liście’ bez męczenia się z rekurencją (po prostu puścić ‚while’ po wszystkich elementach w ‚main’)
  • można oszczędzić 1/3 pamięci nie zapisując ‚rodzica’ w elementach, zamiast tego wystarczy dodatkowa tablica ‚char wyraz[65]’ z wyrazem ‚od korzenia do liścia’ (czyli odwrotną do tej jakiej potrzebujemy) oraz zmienna ‚int aktualnaGlebokoscRekurencji’ zwiększana na początku każdego wywołania rekurencji (zanim przejdzie do lewego/prawego) i zmniejszana przed końcem

 

ZADANIE
Rozważmy niepuste drzewo binarne T etykietowane literami alfabetu angielskiego (tylko małe litery) i zapisane wierzchołkowo tak, że pozycję dowolnego wierzchołka x w drzewie T określa ciąg skierowań krawędzi (L – lewa krawędź, R – prawa krawędź) jakie pokonamy przechodząc w tym drzewie ścieżkę od korzenia do wierzchołka x.
Wyznacz najstarsze leksykograficznie słowo, jakie można zbudować z etykiet wierzchołków rozważanego drzewa występujących na dowolnej ścieżce wierzchołek zewnętrzny (liść) drzewa T – korzeń drzewa T.
WEJŚCIE
Ciąg wierszy zakończony symbolem znaku końca pliku (EOF) reprezentujący poprawnie (zgodnie z powyższym opisem) pewne drzewo binarne T. Każdy pojedynczy wiersz zakończony znakiem nowej linii (kod ASCII 10) opisujący pozycję wierzchołka w drzewie T i zawierający:
– małą literę alfabetu angielskiego (kod ASCII od 97 do 122) – etykieta wierzchołka,
– znak odstępu (kod ASCII 32),
– ciąg znaków L (kod ASCII 76) oraz R (kod ASCII 82) – ciąg skierowań krawędzi na ścieżce od korzenia drzewa do rozważanego wierzchołka.
WYJŚCIE
Wiersz zawierajacy ciąg znaków będący rozwiązaniem postawionego problemu.
OGRANICZENIA
Liczba wierzchołków drzewa T nie większa niż 10^7. Wysokość drzewa T ograniczona przez 2^6.

 

LIMITY
Złożoność czasowa O(n), złożoność pamięciowa O(n), gdzie n jest liczbą wierzchołków drzewa T.
PRZYKŁAD 1

wejście:
a LL
d
a R
s L

wyjście:
asd

ROZWIĄZANIE:

Pamiętajcie, żeby przed wrzuceniem na spoxa zmienić getchar na getchar_unlocked (w 2 miejscach):

#include <stdio.h>
#include <string.h>
class Element;

Element* aktualnyElement;

char najstarszyWyraz[65];
char aktualnyWyraz[65];

class Element
{
	public:
		char wartosc;
		Element* prawy;
		Element* lewy;
		Element* rodzic;
		Element()
		{
			wartosc = 0;
			prawy = NULL;
			lewy = NULL;
			rodzic = NULL;
		}

		void rekurencja()
		{
			// jesli ma lewy
			if(this->lewy)
			{
				this->lewy->rekurencja();
			}
			// jesli ma prawy
			if(this->prawy)
			{
				this->prawy->rekurencja();
			}
			// jesli nie ma lewego, ani prawego = JEST LISCIEM
			else if(!this->lewy)
			{
				// jest lisciem, sprawdzamy czy wyraz utworzony z liter od liscia do korzenia
				// jest starszy od aktualnego rekordzisty, jak tak to zapisujemy jako nowego rekordziste
				
				// zapisujemy aktualny wyraz (z liter od liscia do korzenia) do zmiennej
				aktualnyElement = this;
				register int i = 0;
				while(aktualnyElement->rodzic)
				{
					aktualnyWyraz[i] = aktualnyElement->wartosc;
					aktualnyElement = aktualnyElement->rodzic;
					++i;
				}
				// po zakonczeniu petli zostaje jedna litera ktora musimy dodac
				aktualnyWyraz[i] = aktualnyElement->wartosc;
				// dodanie NULL na koncu wyrazu
				aktualnyWyraz[i+1] = 0;
				
				// jesli aktualny wyraz jest starszy leksykograficznie
				if(strcmp(najstarszyWyraz, aktualnyWyraz) < 0)
				{
					strncpy(najstarszyWyraz, aktualnyWyraz, 65);
				}
			}
			// pod spodem kod do wypisywania na konsole aktualnie przegladanej litery i aktualnego rekordzisty
			//fprintf(stdout, "litera '%c' wyraz: '%s'\n", this->wartosc, najstarszyWyraz);
		}
};

int main()
{
	// czyscimy tablice z naj
	for(int i = 0; i < 65; ++i)
	{
		najstarszyWyraz[i] = 0;
	}
	register char znakNaWejsciu;
	register char wartosc = getchar();

	Element* korzen = new Element();
	aktualnyElement = korzen;

	while(!feof(stdin))
	{
		znakNaWejsciu = getchar();
		// litera 'a-z'
		if(znakNaWejsciu > 96 && znakNaWejsciu < 123)
		{
			// zapisz ostatnio zapamietana litere na elemencie na ktorym zatrzymal sie wskaznik
			aktualnyElement->wartosc = wartosc;
			// cofnij wskaznik na poczatek drzewa
			aktualnyElement = korzen;
			// zapamietaj nowa litere
			wartosc = znakNaWejsciu;
		}
		// R
		else if(znakNaWejsciu == 82)
		{
			// jesli element po prawej nie istnieje to go utworz
			if(!aktualnyElement->prawy)
			{
				aktualnyElement->prawy = new Element();
				aktualnyElement->prawy->rodzic = aktualnyElement;
			}
			// przejdz w prawo
			aktualnyElement = aktualnyElement->prawy;
		}
		// L
		else if(znakNaWejsciu == 76)
		{
			// jesli element po lewej nie istnieje to go utworz
			if(!aktualnyElement->lewy)
			{
				aktualnyElement->lewy = new Element();
				aktualnyElement->lewy->rodzic = aktualnyElement;
			}
			// przejdz w lewo
			aktualnyElement = aktualnyElement->lewy;
		}
	}

	// koniec wczytywania, wskaznik doszedl do jakiegos elementu
	// trzeba w tym elemencie zapisac ostatnio zapamietana wartosc
	aktualnyElement->wartosc = wartosc;

	// rekurencja przemieli drzewo i zapisze nam najstarszy wyraz do zmiennej
	korzen->rekurencja();
	fprintf(stdout, "%s", najstarszyWyraz);
	return 0;
}
Opublikowano Bez kategorii, PJWSTK - ASD | Skomentuj

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

Drzewo binarne – najstarsze słowo – rozwiązanie nr 1 (trudniejsze)

ZADANIE NA 29.11.2015, WIĘC JESZCZE MACIE PONAD 2 TYGODNIE NA PRZEROBIENIE GO NA TYSIĄC SPOSOBÓW 🙂

Rozwiązanie nigdy nie wrzucane na spox, więc nie wiem ile punktów dostanie.

Jest to rozwiązanie TRUDNIEJSZE (w rekurencji jest złożona pętla która pozwala zaoszczędzić parę bajtów i sporo obliczeń). Za chwilę dodam wpis z rozwiązaniem łatwiejszym do zrozumienia, ale wolniejszym o jakieś 30%.

 

ZADANIE
Rozważmy niepuste drzewo binarne T etykietowane literami alfabetu angielskiego (tylko małe litery) i zapisane wierzchołkowo tak, że pozycję dowolnego wierzchołka x w drzewie T określa ciąg skierowań krawędzi (L – lewa krawędź, R – prawa krawędź) jakie pokonamy przechodząc w tym drzewie ścieżkę od korzenia do wierzchołka x.
Wyznacz najstarsze leksykograficznie słowo, jakie można zbudować z etykiet wierzchołków rozważanego drzewa występujących na dowolnej ścieżce wierzchołek zewnętrzny (liść) drzewa T – korzeń drzewa T.
WEJŚCIE
Ciąg wierszy zakończony symbolem znaku końca pliku (EOF) reprezentujący poprawnie (zgodnie z powyższym opisem) pewne drzewo binarne T. Każdy pojedynczy wiersz zakończony znakiem nowej linii (kod ASCII 10) opisujący pozycję wierzchołka w drzewie T i zawierający:
– małą literę alfabetu angielskiego (kod ASCII od 97 do 122) – etykieta wierzchołka,
– znak odstępu (kod ASCII 32),
– ciąg znaków L (kod ASCII 76) oraz R (kod ASCII 82) – ciąg skierowań krawędzi na ścieżce od korzenia drzewa do rozważanego wierzchołka.
WYJŚCIE
Wiersz zawierajacy ciąg znaków będący rozwiązaniem postawionego problemu.
OGRANICZENIA
Liczba wierzchołków drzewa T nie większa niż 10^7. Wysokość drzewa T ograniczona przez 2^6.

 

LIMITY
Złożoność czasowa O(n), złożoność pamięciowa O(n), gdzie n jest liczbą wierzchołków drzewa T.
PRZYKŁAD 1

wejście:
a LL
d
a R
s L

wyjście:
asd

ROZWIĄZANIE:

Pamiętajcie, żeby przed wrzuceniem na spoxa zmienić getchar na getchar_unlocked (w 2 miejscach):

#include <stdio.h>

class Element;

Element* aktualnyElement;

char najstarszyWyraz[65];

class Element
{
	public:
		char wartosc;
		Element* prawy;
		Element* lewy;
		Element* rodzic;
		Element()
		{
			wartosc = 0;
			prawy = NULL;
			lewy = NULL;
			rodzic = NULL;
		}

		void rekurencja()
		{
			// jesli ma lewy
			if(this->lewy)
			{
				this->lewy->rekurencja();
			}
			// jesli ma prawy
			if(this->prawy)
			{
				this->prawy->rekurencja();
			}
			// jesli nie ma lewego, ani prawego = JEST LISCIEM
			else if(!this->lewy)
			{
				aktualnyElement = this;
				register int i = 0;
				while(aktualnyElement->rodzic)
				{
					// aktualny 'najstarszyWyraz' jest krotszy od aktualnego wyrazu
					if(najstarszyWyraz[i] == NULL)
					{
						while(aktualnyElement->rodzic)
						{
							najstarszyWyraz[i] = aktualnyElement->wartosc;
							aktualnyElement = aktualnyElement->rodzic;
							++i;
						}
						najstarszyWyraz[i] = aktualnyElement->wartosc;
						// dodanie NULL na koncu wyrazu
						najstarszyWyraz[i+1] = 0;
						break;
					}
					// aktualna litera 'najstarszyWyraz' jest rowna literze aktualnego wyrazu
					// moze to byc nowy rekordzista, trzeba sprawdzac dalej
					else if(najstarszyWyraz[i] == aktualnyElement->wartosc)
					{
						aktualnyElement = aktualnyElement->rodzic;
						++i;
					}
					// aktualna litera 'najstrszyWyraz' jest nizsza, niz litera aktualnego wyrazy
					// aktualny wyraz jest rekordzista, trzeba go przepisac do konca
					else if(najstarszyWyraz[i] < aktualnyElement->wartosc)
					{
						while(aktualnyElement->rodzic)
						{
							najstarszyWyraz[i] = aktualnyElement->wartosc;
							aktualnyElement = aktualnyElement->rodzic;
							++i;
						}
						najstarszyWyraz[i] = aktualnyElement->wartosc;
						// dodanie NULL na koncu wyrazu
						najstarszyWyraz[i+1] = 0;
						break;
					}
					// aktualna litera 'najstarszyWyraz' jest wyzsza, niz aktualnego wyrazu
					// na pewno nie bedzie to nowy rekordzista
					else
					{
						break;
					}
				}
				// dodanie ostatniego elementu ktory zostal po wykonaniu petli
				// o ile nowy wyraz jest rekordzista
				if(najstarszyWyraz[i] <= aktualnyElement->wartosc)
				{
					najstarszyWyraz[i] = aktualnyElement->wartosc;
					// dodanie NULL na koncu wyrazu
					// nowy wyraz moze byc KROTSZY, niz poprzedni rekordzista
					najstarszyWyraz[i+1] = 0;
				}
			}
			// pod spodem kod do wypisywania na konsole aktualnie przegladanej litery i aktualnego rekordzisty
			//fprintf(stdout, "litera '%c' wyraz: '%s'\n", this->wartosc, najstarszyWyraz);
		}
};

int main()
{
	// czyscimy tablice z naj
	for(int i = 0; i < 65; ++i)
	{
		najstarszyWyraz[i] = 0;
	}
	register char znakNaWejsciu;
	register char wartosc = getchar();

	Element* korzen = new Element();
	aktualnyElement = korzen;

	while(!feof(stdin))
	{
		znakNaWejsciu = getchar();
		// litera 'a-z'
		if(znakNaWejsciu > 96 && znakNaWejsciu < 123)
		{
			// zapisz ostatnio zapamietana litere na elemencie na ktorym zatrzymal sie wskaznik
			aktualnyElement->wartosc = wartosc;
			// cofnij wskaznik na poczatek drzewa
			aktualnyElement = korzen;
			// zapamietaj nowa litere
			wartosc = znakNaWejsciu;
		}
		// R
		else if(znakNaWejsciu == 82)
		{
			// jesli element po prawej nie istnieje to go utworz
			if(!aktualnyElement->prawy)
			{
				aktualnyElement->prawy = new Element();
				aktualnyElement->prawy->rodzic = aktualnyElement;
			}
			// przejdz w prawo
			aktualnyElement = aktualnyElement->prawy;
		}
		// L
		else if(znakNaWejsciu == 76)
		{
			// jesli element po lewej nie istnieje to go utworz
			if(!aktualnyElement->lewy)
			{
				aktualnyElement->lewy = new Element();
				aktualnyElement->lewy->rodzic = aktualnyElement;
			}
			// przejdz w lewo
			aktualnyElement = aktualnyElement->lewy;
		}
	}

	// koniec wczytywania, wskaznik doszedl do jakiegos elementu
	// trzeba w tym elemencie zapisac ostatnio zapamietana wartosc
	aktualnyElement->wartosc = wartosc;

	// rekurencja przemieli drzewo i zapisze nam najstarszy wyraz do zmiennej
	korzen->rekurencja();
	fprintf(stdout, "%s", najstarszyWyraz);
	return 0;
}
Opublikowano Bez kategorii, PJWSTK - ASD | 4 komentarze