Maski bitowe

03.10.2009 - Damian Rusak
TrudnośćTrudnośćTrudność

 


Problem Komiwojażera

Limit czasowy 10s, limit pamięciowy : 128MB

Mając dane odległości pomiędzy wszystkimi parami miast, wyznacz najkrótszą ścieżkę biegnącą przez wszystkie miasta dokładnie raz i kończącą się w miejscu swego początku, niczym mityczny Uroboros, gryzący swój własny ogon.

Wejście:

Pierwsza linia wejścia zawiera liczbę całkowitą $ n\:\left(2 \leq n \leq 20\right) $, oznaczającą ilość miast. W następnych n liniach znajduje się po $ n $ liczb całkowitych $ a_{i,j} \left(1 \leq i,j \leq n , 0 \leq a_{i,j} \leq 1000\right) $, gdzie $ a_{i,j} $ to $ j $-ta liczba w $ i $-tym wierszu, oznaczająca koszt podróży z miasta $ i $ do miasta $ j $. Zawsze zachodzi $ a_{i,i} = 0 $. Odległości $ a_{i,j} $ oraz $ a_{j,i} $ mogą się różnić.

Wyjście:

Wyjście powinno składać się z jednej liczby całkowitej - najkrótszej szukanej ścieżki.

 

Przykład:

Wejście:

5
0 2 8 7 4
2 0 3 8 6
8 3 0 2 7
7 8 2 0 3
4 6 7 3 0

Wyjście:

14

 


 

Studenci

Limit czasowy 5s, limit pamięciowy 64MB

Oblicz, na ile sposobów można przydzielić n studnetom n prac do wykonania, tak aby każdy otrzymał dokładnie jedną pracę, którą może wykonać.

Wejście:

Pierwsza linia wejścia składa się z jednej liczby całkowitej $ n\:\left(1 \leq n \leq 20\right), $ oznaczającej ilość studentów i ilość prac. W następnych $ n $ liniach znajduje się n liczb całkowitych $ b_{i,j} \left(0 \leq b_{i,j} \leq 1\right) $, tak, że $ b_{i,j}  $ znajduje się na $ j $-tej pozycji w $ i $-tym wierszu $ i $ jest równe 1, jeśli $ i $-ty student może wykonać pracę o numerze $ j $, bądź 0 w przeciwnym razie.

Wyjście:

Na wyjściu powinna się pojawić jedna liczba całkowita, oznaczająca ilość różnych możliwych przyporządkowań prac dla studentów. Możesz założyć, że liczba ta zmieści się w 64-bitowej zmiennej

 

Przykład 1:

Wejście:

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

Wyjście:

3

 

Przykład 2:

Wejście:

10
1 0 0 1 0 0 0 1 0 1
1 0 1 0 1 0 0 0 1 0
1 0 1 0 1 1 1 0 1 1
1 1 0 0 0 0 0 1 0 1
1 1 0 1 0 0 0 1 1 1
1 0 1 0 0 0 1 1 1 0
1 1 1 1 0 0 1 0 1 0
0 0 0 1 0 1 0 1 0 0
0 0 0 1 0 1 0 1 0 0
0 0 0 0 1 1 1 0 1 0

Wyjście:

1404

 


 

Płytki

Limit czasowy 5s, limit pamięciowy 64MB

Rozważmy planszę rozmiaru $ n \times m $ składającą się z pól $ 1 \times 1 $. Niektóre z tych pól są pokryte. Na pozostałych należy umieścić płytki rozmiaru $ 1 \times 1 $ lub $ 2 \times 2 $, tak by pokryć całą planszę. Za każdą umieszczoną płytkę $ 1 \times 1 $ otrzymuje się $ 1 $ punkt, za każdą $ 2 \times 2 $ $ 16 $ punktów. Płytki nie mogą zachodzić na siebie, ani na początkowo pokryte pola. Należy obliczyć, ile najwięcej punktów można zdobyć za pomocą takiego pokrycia.

Wejście:

Pierwsza linia wejścia zawiera dwie liczby całkowite - $ n $ i $ m $ $ \left(1 \leq n,m \leq 16\right) $ oznaczające kolejno ilość wierszy i kolumn planszy. W następnych $ n $ liniach znajduje się po $ m $ liczb całkowitych $ b_{i,j} (0 \leq b_{i,j} \leq 1\right) $, tak, że $ b_{i,j} = 1 $ jeśli pole planszy w $ i $-tym wierszu i w $ j $-tej kolumnie jest początkowo pokryte, i $ b_{i,j} = 0 $ w przeciwnym razie.

Wyjście:

Wyjście powinno składać się z jednej liczby całkowitej - największej liczby punktów możliwych do uzyskania poprzez poprawne pokrycie planszy płytkami $ 1 \times 1 $ i $ 2 \times 2 $.

Przykład 1:

Wejście:
 
5 5
0 0 0 1 0
0 0 0 0 0
0 1 0 0 1
0 0 0 0 0
1 0 0 0 0

Wyjście:

69

Przykład 2:


Wejście:

4 5
0 0 0 0 1
0 0 1 0 1
0 0 0 0 0
1 0 0 0 1

Wyjście:

39

 


 

Płytki II

Limit czasowy 5s, limit pamięciowy 64MB

Mamy daną planszę $ n \times m $, złożoną z pól $ 1 \times 1 $. Mamy dane $ k $ superpłytek, po jednej rozmiaru $ a_{i} \times b_{i} $ o wartości $ c_{i} $. Niektóre pola na planszy są pokryte. Pozostałe pola należy w pełni pokryć płytkami $ 1 \times 1 $ oraz superpłytkami, tak aby nie zachodziły na siebie oraz na pierwotnie pokryte pola. Superpłytki powinny być ustawione "pionowo", tj. bokiem długości $ a_{i} $ równolegle do boku planszy długości $ n $. Za każdą wykorzystaną płytkę $ 1 \times 1 $ otrzymuje się $ 1 $ punkt, za każdą superpłytkę ilość punktów odpowiadającą jej wartości. Każdą superpłytkę można wykorzystać co najwyżej raz. Należy obliczyć, ile co najwyżej punktów można uzyskać poprzez poprawne pokrycie.

Wejście:

Pierwsza linia wejścia składa się z liczb $ n, m, k \left(1 \leq n,m \leq 12, 1 \leq k \leq 5\right) $ oznaczających kolejno wysokość i szerokość planszy oraz ilość superpłytek. W następnych $ k $ wierszach znajdują się trójki liczb $ a_{i}\: b_{i}\: c_{i} \left(1 \leq a_{i} \leq n, 1 \leq b_{i} \leq 2, 1 \leq c_{i} \leq 200\right) $. W następnych $ n $ liniach znajduje się po $ m $ liczb całkowitych $ v_{i,j} \left(0 \leq v_{i,j} \leq 1\right) $, tak, że $ v_{i,j} = 1 $ jeśli pole planszy w $ i $-tym wierszu i w $ j $-tej kolumnie jest początkowo pokryte, i $ v_{i,j} = 0 $ w przeciwnym razie.

Wyjście:

Wyjście powinno składać się z jednej liczby całkowitej - największej liczby punktów możliwych do uzyskania poprzez poprawne pokrycie planszy płytkami $ 1 \times 1 $ i superpłytkami.

Przykład:

Wejście:

5 8 4
3 2 7
4 1 6
3 1 10
2 2 30
0 0 1 1 0 1 0 1
0 1 0 0 0 0 1 0
1 1 0 0 0 1 1 0
0 0 0 1 1 1 0 0
0 1 1 0 0 0 0 0

Wyjście:

60

 

 


Szeregowanie zadań

Limit czasowy 5s, limit pamięciowy 64MB

Mamy $ n $ zadań do wykonania. Zadania należy wykonywać po kolei, w całości - rozpoczętego zadania nie można przerwać. Każde zadanie posiada swój czas wykonania, termin wykonania, oraz karę za zwłokę. Jeżeli skończymy wykonywać pewne zadanie po jego terminie wykonania, nakładana jest kara równa iloczynowi różnicy czasu zakończenia zadania i terminu wykonania razy kara za zwłokę danego zadania. Jeśli więc zadanie skończyliśmy w chwili $ T $, a miało zostać wykonane w chwili $ t $, a kara za zwłokę to $ c $, nałożona kara to $ max\left(0, (T-t)\cdot c\right) $. Należy napisać program, który obliczy, jaka jest minimalna kara możliwa do uzyskania przy wykonaniu wszystkich zadań w dowolnej kolejności.

Wejście:

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $ n \left(1 \leq n \leq 20\right), $ oznaczającą ilość zadań do wykonania. W następnych $ n $ liniach znajdują się trójki liczb całkowitych $ t_{i} \:d_{i} \:c_{i} \left(1 \leq t_{i} \leq 100, 1 \leq d_{i} \leq 1000, 1 \leq c_{i} \leq 1000) $, oznaczające kolejno czas wykonania zadania, termin jego wykonania oraz karę za zwłokę za to zadanie.

Wyjście:

W jedynej linii wyjścia powinna znajdować się jedna liczba całkowita - najmniejsza możliwa do uzyskania kara za wykonanie po kolei wszystkich zadań (w dowolnej kolejności).

Przykład:

Wejście:

5
1 1 6
9 6 10
8 10 3
9 7 10
5 6 5

Wyjście:

316

Najlepiej najpierw wykonać zadanie nr 1, nie płacąc kary. Potem wykonujemy zadanie nr 2, płacąc za zwłokę (1+9 - 6)*10 = 40. Następnie zadanie nr 4 i kara (1+9+9 - 7)*10 = 120. Potem zadanie nr 3 i kara (1+9+9+5 - 6)*5 = 90. Na koniec zadanie nr 3 i kara (1+9+9+5+8 - 10)*3 = 66. Łącznie 0 + 40 + 120 + 90 + 66 = 316.

 

 


Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
5
Twoja ocena: Brak Ocena: 5 (7 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com