W tym dziale będą pojawiały się, co tydzień w piątek, nowe wyzwania programistyczne. Zadania te są nieobowiązkowe i przeznaczone jedynie dla ochotników, chcących sprawdzić swoje umiejętności algorytmiczne i programistyczne, podczas kodowania w języku C.

Czas na wykonanie każdego z wyzwań weekendowych upływa w niedzielę, o godzinie 23:59. Trzy osoby, które najszybciej prześlą największą liczbę poprawnych rozwiązań, zostaną zwolnione z konieczności oddania części prac domowych oraz uzyskają wyższą ocenę końcową z Wykładu. Kryterium podstawowym jest liczba poprawnie wykonanych wyzwań (pozytywny test maszynowy && pozytywna ocena wykładowcy). Kryterium dodatkowym jest czas przesłania odpowiedzi (pole Data przesłania odpowiedzi w raporcie maszynowym).

Życzymy powodzenia! :)

<spoiler |Wyniki>

Wartość +1 w zadaniu Enigma oznacza punkt bonusowy za spostrzegawczość :) Wartość +1 w zadaniu Cuda oznacza punkt bonusowy za wykorzystanie rekurencji.

</spoiler>

Napisz program, który pobierze od użytkownika tablicę o wymiarach 30 x 30, a następnie odnajdzie drogę prowadzącą z punktu (0,0) do punktu (29, 29). Komórki, po których można się poruszać są oznaczone wartościami 1 we wczytanej macierzy. Z punktu startowego do końcowego prowadzi wyłącznie jedna droga, bez ślepych zaułków. Program ma wypisać, w kolejnych liniach, współrzędne wszystkich komórek, jakie odwiedził w drodze z punktu startowego do mety włącznie z nimi.

<spoiler |Przykład> Przykładowe wejście:

 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 
 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 1 0 
 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 
 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 
 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 
 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 
 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 
 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 
 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 
 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 

Przykładowe wyjście:

0 0
0 1
0 2
1 3
1 4
2 5
3 5
4 6
5 6
6 6
7 7
6 8
5 8
4 9
3 10
2 11
1 12
2 13
2 14
3 15
4 15
5 15
6 16
6 17
7 18
7 19
7 20
7 21
7 22
7 23
8 24
8 25
8 26
9 27
9 28
10 29
11 29
12 29
13 29
14 29
15 29
16 29
17 29
18 29
19 29
20 29
21 29
22 29
23 29
24 29
25 29
26 29
27 29
28 29
29 29

</spoiler>

* DEPESZA Z CENTRALI WYWIADU *

Udało nam się przechwycić komunikat przesłany przez naszych wrogów. Niestety, jest on zakodowana. Nasz agent, zakonspirowany w sztabie wroga, dostarczył nam jedno z użytych słów w tekście. Przekazał nam również cenną wskazówkę - nasz przeciwnik nie jest zbyt biegły w dziedzinie kryptografii. Przypuszcza się, iż tekst jest zaszyfrowany pewną wariacją szyfru Cezara, gdzie długość klucza jest mniejsza o jeden od długości znanego nam wyrazu a szyfrowanie polega na zmianie wartości kolejnych znaków na podstawie kolejnych liczb klucza.

Czy dasz radę pomóc swojej Ojczyźnie i odszyfrować przechwyconą wiadomość?

<spoiler |Przykład> Przykładowe wejście:

Podaj tekst:
Uvzkk kkcu nooktio ob unlpjyxbti ufqcu
Podaj uzyte slowo:
tekst

Przykładowe wyjście:

Tutaj jest miejsce na odkodowany tekst

</spoiler>

W starożytnej Grecji mieliśmy powiedzenie „Kto nie liczy ten nie je” (które później ewoluowało do „Kto nie koduje w C ten nie je”). Rozumiał je Archimedes, krzycząc Heureka! Rozumieli je wszyscy. Brutalnie przekonał się o tym król perski Kserkses, który źle policzył przewagę swoich sił pod Termopilami. Aby nie popełnić jego błędu, musisz zrozumieć, co naprawdę oznacza „liczyć” a następnie nauczyć tego swój komputer. Bądź jak Pitagoras! :)

<spoiler |Przykład> Przykładowe wejście:

Podaj wyrażenie: 
4+88-69-3+75+53+89/18-34/48-62-62/3*53-86

Przykładowe wyjście:

-1056

</spoiler>

Święta to czas cudów. Spotykamy się w cudownie miłej atmosferze, jemy cudownie pysznego karpia. Wyczekujemy cudowniej pierwszej gwiazdki. Nieco inaczej ma Święty Mikołaj. W ciągu jednego wieczora musi odwiedzić miliardy dzieci w miliardach domów, rozdać miliardy prezentów pod miliardy choinek. Wszystkie te liczby, z którymi ma on do czynienia, jak by na nie nie patrzeć, są również cudownie wielkie. Pomóż więc Mikołajowi w dodawaniu tych wielkich liczb i napisz program, który zrobi to za niego.

<spoiler |Przykład> Przykładowe wejście:

Podaj pierwsza liczbe: 90467506859757021571
Podaj druga liczbe: 42901800079275915926

133369306939032937497

</spoiler>

Pomysły na prezenty, jakie mają dzieci, są różne jak Świat długi i szeroki. Antoś z Krakowa chce konsole, Marysia z Warszawy latawiec a Gosia z Sosnowca nowy rowerek. Z tymi prezentami Mikołaj nie ma problemu ale czasem zdarzają się dzieci bardziej wymagające. W tym roku Mikołaj natrafił na Piotrusia i Tomusia z Łodzi, którzy chcieli dostać pod choinkę program komputerowy. A ponieważ dzieci są małe, nie potrafiły w pełni przekazać Mikołajowi, co taki program ma robić. Dostarczyły tylko to:

<spoiler |Przykład> Przykładowe wejście:

Podaj liczbe linii: 8
Podaj tekst: Drodzy Studenci!
Zyczymy Wam spokojnych Swiat Bozego Narodzenia,
spedzonych razem z bliskimi
w cieplej i rodzinnej atmosferze.
A w nadchodzacym Nowym Roku zyczymy Wam energii,
sukcesow w realizacji upragnionych marzen
oraz cierpliwosci i wytrwalosci w pracy nad soba!
Piotr Duch i Tomasz Jaworski
Podaj zakodowane hasło: 
107327110719305104118530 120718223140619

Przykładowe wyjście:

Wesolych Swiat

</spoiler> Mikołajowi pomysł bardzo się spodobał, więc zlecił prace nad prezentem swoim Elfom - Wam, drodzy Studenci. Czy podołacie zadaniu i sprawicie radość dwójce małych urwisów?

Mamy nadzieję, że tak

Napisz program który, dla podanego obrazu o wymiarach z zakresu 1×1 - 50×50 punktów, znajdzie i wyświetli wszystkie obiekty nie będące tłem. Wartości punktów tła to 0 a obiektów to 1. Obiektów może być wiele. Program powinien poprosić o dwie liczby całkowite: wysokość i szerokość obrazu a następnie wczytać wartości kolejnych punktów. Jako wynik program ma wyświetlić liczbę znalezionych obiektów a następnie wyświetlić informacje o każdym obiekcie. Te informacje to: jego numer (1, 2…), powierzchnia, oraz współrzędne XY środka ciężkości, z dokładnością do dwóch miejsc po przecinku. Przed wyświetleniem obiekty należy posortować ze względu na współrzędne środa, w porządku: od góry do dołu, od lewej do prawej.

Przyjmij następujące założenia:

1. Układ współrzędnych do liczenia środka ciężkości ma 0,0 w lewym górny rogu obrazu (pierwsza liczba), wartość X zwiększa się od lewej do prawej, wartość Y zwiększa się z góry na dół
2. Punkt należy do obiektu wtedy i tylko wtedy, gdy leży nad/pod/na lewo/na prawo od dowolnego punktu należące do do tego obiektu

Przykład:

    Jeden obiekt   Cztery obiekty:
      #                 #
     ###               # #
      #                 #

<spoiler |Przykład>

Wejście:

5 5
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0

Wyjście:

Liczba obiektow: 4
Obiekt 1 powierzchnia p=1 srodek ciezkosci x=1.00 y=1.00
Obiekt 2 powierzchnia p=1 srodek ciezkosci x=3.00 y=1.00
Obiekt 3 powierzchnia p=1 srodek ciezkosci x=1.00 y=3.00
Obiekt 4 powierzchnia p=1 srodek ciezkosci x=3.00 y=3.00

</spoiler>

Tym razem Twoim zadaniem jest napisanie programu, który wykrywa krawędzie w obrazie wejściowym i generuje obraz wyjściowy. Obraz wejściowy dany jest w postaci macierzy liczb całkowitych z zakresu 0-255, o wymiarach 250 x 250. Macierz ta to obraz monochromatyczny a liczby reprezentują poszczególne piksele. Wartość 0 to piksel czarny a 255 to biały.

Obraz wyjściowy to macierz liczb całkowitych o wymiarach 496 x 248. Zakres i znaczenie wartości w macierzy jest takie samo, jak w wejściowym. Obraz wyjściowy jest sklejeniem dwóch obrazów:

• obrazu krawędzi pionowych (górna połowa obrazu wyjściowego) oraz
• obrazu krawędzi poziomych (dolna połowa obrazu wyjściowego).

Do wykrywania krawędzi należy skorzystać z dwóch masek o wymiarach 3 x 3, wbudowanych w kod źródłowy (nie są określone danymi wejściowymi).

Maska dla krawędzi pionowych:

  1  2  1
  0  0  0
 -1 -2 -1

Maska dla krawędzi poziomych:

  1  0 -1
  2  0 -2
  1  0 -1

Operację wykrywania krawędzi należy przeprowadzić następująco:

• Wybraną maskę przykładamy do obrazu w jego lewym górnym rogu. Maskę należy przyłożyć tak, aby jej elementy nie „wystawały” poza obraz.
• Wyznaczamy sumę dziewięciu iloczynów par wartości: wartości danej komórki maski z leżącą pod nią wartością piksela.
• Wyznaczoną sumę przetwarzamy, wyznaczając jej moduł i ograniczając go do wartości nie większej niż 255.
• Przetworzoną sumę zapisujemy jako wartość punktu w lewym górnym rogu obrazu wyjściowego.
• Maskę przesuwamy o jeden piksel ze strony lewej na prawą oraz z góry na dół i dla każdej pozycji wykonujemy powyższe operacje matematyczne.

Obraz wynikowy należy wyświetlić na ekranie jako macierz 496 x 248 liczb całkowitych.

Przykład wejścia: Dane wejściowe do programu. Obraz odpowiadający tym danym:

Przykład wyjścia: Dane wyjściowe z programu. Obraz odpowiadający tym danym: