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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/*
"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:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
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
  }
}
?
1
 
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

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
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):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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ń:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
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:

?
1
2
3
4
5
6
7
8
9
10
11
// 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ń:

?
1
2
3
4
5
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):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#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):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
/*
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:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#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