Programowanie i algorytmy

DOMINO - znajdź kamień

Chcesz zagrać ze mną w DOMINO? Uważasz, że jesteś w stanie mnie pokonać? Być może masz rację, ale muszę się do czegoś przyznać. Zgubiłem jeden kamień domina. Niestety nie pamiętam który, jeśli więc chcesz ze mną zagrać, musisz go znaleźć. 

Wejście

W pierwszym wierszu znajduje się jedna liczba określająca liczbę zestawów danych (nie więcej niż 1000). Każdy zestaw składa się z jednego wiersza, a w nim 27 kamieni domina w formacie [liczba oczek]|[liczba oczek].

Wyjście

Dla każdego zestawu testowego szukany kamień domina w formacie [liczba oczek]|[liczba oczek]. Liczbę oczek ustawiamy w ciągu niemalejącym.

Przykład

Wejście:
1 
2|5 4|5 0|1 3|4 3|6 3|1 2|6 0|0 3|3 5|3 6|6 1|1 3|0 2|2 6|4 4|2 0|4 2|3 0|2 1|6 2|1 5|0 0|6 1|4 6|5 4|4 5|1

Wyjście:
5|5

Szkic rozwiązania

Przykładowe rozwiązanie. Tworzymy tablicę dwuwymiarową 7x7, zerujemy ją. Następnie przy wczytywaniu kamienia i|j ustawiamy wartość komórki tablicy [i][j] oraz [j][i] na 1. Indeksy komórki, która ostatecznie będzie miała wartość 0, będą szukanym kamieniem.

Profesor Algobit w przedszkolu

Po pierwszej prelekcji w najlepszym bajtockim przedszkolu, po namowach przedszkolaków (taka jest wersja pani przedszkolanki), piękna pani opiekunka postanowiła ponownie zaprosić profesora Algobita na przeprowadzenie kolejnego fascynującego wykładu na temat algorytmów. Wykładowca i tym razem zgodził się na spotkanie z mądrymi dzieciakami. Opowiedział on o całkowaniu numerycznym i kilku algorytmach, które je realizują. Na koniec naukowiec przedstawił podstawy matematyczne na temat całkowania - omówił całki pojedyncze, podwójne oraz potrójne, pokazał także jak całkuje się po okręgu. Tym razem na koniec prelekcji, Jasiu chciał się odwdzięczyć za niespodziankę przygotowaną na poprzednim spotkaniu i przedstawił swój szyfrogram. Uczeń nie skończył jeszcze prezentować szyfrogramu, gdy profesor przedstawił rozwiązanie. A ile tobie to zajmie?

Wejście

W pierwszym i jedynym wierszu szyfrogram złożony z co najmniej jednego i nie więcej niż miliona znaków.

Wyjście

Oryginalna wiadomość

Przykład 1

Wejście:
Aaltao km a

Wyjście:
Ala ma kota

Przykład 2

Wejście:
BkoelleokL  i

Wyjście:
Bolek i Lolek

Szkic rozwiązania

Przeanalizujmy w jaki sposób powstał szyfrogram. Oryginalna wiadomość „Ala ma kota”. Bierzemy najpierw pierwszą literę, potem ostatnią, drugą, przedostatnią itd.: Aalt…. Żeby odwrócić sytuację wystarczy wypisać najpierw co drugą literę z lewej do prawej jednocześnie usuwając ją, następnie wypisać od końca wyrazu te, które pozostały.

Klucznik

Muszę otworzyć dziś drzwi, za którymi znajduje się coś specjalnego. W ręku mam zestaw kluczy - co najmniej jednym z nich mogę je otworzyć. Niestety jest ciemno i jestem prawie pewien, że klucz, który będzie pasował, wybiorę jako ostatni. Sprawdź to!

Wejście

W pierwszym wierszu znajdują się liczby n i m określające wymiary macierzy przedstawiającej zamek (n < 101, m < 101). Macierz składa się wyłącznie z zer i jedynek. Zbiór jedynek oznacza, że w tym miejscu jest dziurka. W zamku jest tylko jedna dziurka do klucza oraz co najmniej jedna jedynka.

Następnie n wierszy po m kolumn reprezentujących zamek.

W kolejnym wierszu jedna niewielka liczba określająca liczbę kluczy do sprawdzenia.

Specyfikacja każdego klucza (klucz zdefiniowany jest w pewnym układzie współrzędnych, który może być obrócony o krotność dziewięćdziesięciu stopni):

W pierwszym wierszu jedna liczba w określająca ilość współrzędnych klucza (w < 10001).

W kolejnych w wierszach po dwie współrzędne x i y, takie że |x| < 1000, |y| < 1000. Współrzędne są unikatowe i nie są posortowane.

Wyjście

Dla każdego klucza napis pasuje lub napis nie pasuje w zależności od sytuacji. 

Uwaga! Klucz musi idealnie pasować do dziurki - każda 'jedynka' z zamka musi mieć odpowiadającą sobie współrzędną klucza (być może obróconego).

Przykład

Wejście:
6 7
0000000
0011100
0110110
0011100
0001100
0000000
2
10
0 2
-1 1
0 1
1 1
-2 0
-1 0
1 0
-2 -1
-1 -1
0 -1
12
0 2
-1 1
0 1
1 1
-2 0
-1 0
1 0
-2 -1
-1 -1
0 -1
1 -1
0 -2

Wyjście:
nie pasuje
pasuje

Szkic rozwiązania

Przykładowe rozwiązanie. „Wycinamy” prostokąt w którym znajduje się klucz. Wykonujemy jego cztery wersje, obracając każdą o kolejne 90 stopni. Dla danego układu współrzędnych reprezentujących klucz wykonujemy translację do pierwszej ćwiartki tak, aby najbardziej wysunięty punkt na lewo leżał na osi OX a najbardziej wysunięty punkt w dół leżał na osi OY. W ostatnim kroku dopasowujemy wycięty prostokąt we wszystkich czterech wersjach do układu współrzędnych.

Liczby podzielne przez 3 - ciąg dalszy

Załóżmy, że rozpatrujemy liczby podzielne przez trzy. Rozpatrywana liczba może mieć niektóre cyfry przysłonięte znakiem gwiazdki. Dodatkowo wiadomo, że cyfry, które zostały przysłonięte zawierają się w pewnym zbiorze. Określ, ile może powstać w ten sposób liczb podzielnych przez 3, jeśli zamiast gwiazdki, możesz użyć cyfr, które zostały wcześniej zdefiniowane.

Wejście

W pierwszym wierszu jedna liczba c określająca liczbę cyfr, które możemy zastąpić za gwiazdki 0 < c < 11.

W drugim wierszu c cyfr systemu dziesiętnego. Każda cyfra wystąpi co najwyżej raz.

Następnie jedna liczba t określająca liczbę zestawów danych (t < 10001).

Każdy zestaw składa się z jednej liczby, maksymalnie 1000 znaków. Gwarantuje się, że najbardziej znacząca cyfra nie jest gwiazdką.

Wyjście

Dla każdego zestawu jedna liczba określająca liczbę liczb podzielnych przez 3. Wynik przedstaw modulo 1010101011.

Przykład

Wejście:
3
1 6 2
5
1
1*
111
3*
3***

Wyjście:
0
1
1
1
9

Szkic rozwiązania

W tym zadaniu należy zastosować podejście dynamiczne. Dla każdej gwiazdki spamiętujemy ile może powstać liczb, które dadzą nam resztę 0, 1 lub 2. Rozwiązaniem będzie liczba, która dla ostatniej gwiazdki będzie przechowywana dla reszty równej 0 uwzględniając sumę odkrytych cyfr.