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

Opublikowano 16 maja 2017, autor: Jerzy Skalski

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!

Zaszufladkowano do kategorii Bez kategorii | Dodaj komentarz

[NBD] Ćwiczenia 1

Opublikowano 12 marca 2017, autor: Jerzy Skalski

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
  }
}

							

	
			

									
						Zaszufladkowano do kategorii Bez kategorii					
					|
				
				
				Dodaj komentarz

							

		


		
	

	
			

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


			

				Opublikowano 13 września 2016, autor: Jerzy Skalski			


					

				
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.

							

	
			

									
						Zaszufladkowano do kategorii PJWSTK, PJWSTK - ASD					
					|
				
				
				Dodaj komentarz

							

		


		
	

	
			

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


			

				Opublikowano 4 czerwca 2016, autor: Jerzy Skalski			


					

				
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 :) ";
	}
}

							

	
			

									
						Zaszufladkowano do kategorii PJWSTK, PJWSTK - ASD					
					|
				
				
				Dodaj komentarz

							

		


		
	

	
			

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


			

				Opublikowano 8 stycznia 2016, autor: Jerzy Skalski			


					

				
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.

							

	
			

									
						Zaszufladkowano do kategorii PJWSTK - SKJ					
					|
				
				
				Dodaj komentarz

							

		


		
	

	
			

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


			

				Opublikowano 1 grudnia 2015, autor: Jerzy Skalski			


					

				
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

							

	
			

									
						Zaszufladkowano do kategorii PJWSTK, PJWSTK - ASD					
					|
				
				
				2 komentarze

							

		


		
	

	
			

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


			

				Opublikowano 14 listopada 2015, autor: Jerzy Skalski			


					

				
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;
}

							

	
			

									
						Zaszufladkowano do kategorii Bez kategorii, PJWSTK - ASD					
					|
				
				
				Dodaj komentarz

							

		


		
	

	
			

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


			

				Opublikowano 14 listopada 2015, autor: Jerzy Skalski			


					

				
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;
}

							

	
			

									
						Zaszufladkowano do kategorii Bez kategorii, PJWSTK - ASD					
					|
				
				
				4 komentarze

							

		


		
	

	
			

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


			

				Opublikowano 26 października 2015, autor: Jerzy Skalski			


					

				
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.

							

	
			

									
						Zaszufladkowano do kategorii PJWSTK - ASD					
					|
				
				
				4 komentarze

							

		


		
	

	
			

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


			

				Opublikowano 9 października 2015, autor: Jerzy Skalski			


					

				
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

							

	
			

									
						Zaszufladkowano do kategorii PJWSTK - UTP					
					|
				
				
				Dodaj komentarz