Maski bitowe
03.10.2009 - Damian Rusak
Problem KomiwojażeraLimit 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ą , oznaczającą ilość miast. W następnych n liniach znajduje się po liczb całkowitych , gdzie to -ta liczba w -tym wierszu, oznaczająca koszt podróży z miasta do miasta . Zawsze zachodzi . Odległości oraz 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 Wyjście: 14
StudenciLimit 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 oznaczającej ilość studentów i ilość prac. W następnych liniach znajduje się n liczb całkowitych , tak, że znajduje się na -tej pozycji w -tym wierszu jest równe 1, jeśli -ty student może wykonać pracę o numerze , 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 Wyjście: 3
Przykład 2: Wejście: 10 Wyjście: 1404
PłytkiLimit czasowy 5s, limit pamięciowy 64MB Rozważmy planszę rozmiaru składającą się z pól . Niektóre z tych pól są pokryte. Na pozostałych należy umieścić płytki rozmiaru lub , tak by pokryć całą planszę. Za każdą umieszczoną płytkę otrzymuje się punkt, za każdą 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 - i oznaczające kolejno ilość wierszy i kolumn planszy. W następnych liniach znajduje się po liczb całkowitych , tak, że jeśli pole planszy w -tym wierszu i w -tej kolumnie jest początkowo pokryte, i 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 i . Przykład 1: Wejście:
Płytki IILimit czasowy 5s, limit pamięciowy 64MB Mamy daną planszę , złożoną z pól . Mamy dane superpłytek, po jednej rozmiaru o wartości . Niektóre pola na planszy są pokryte. Pozostałe pola należy w pełni pokryć płytkami 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 równolegle do boku planszy długości . Za każdą wykorzystaną płytkę otrzymuje się 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 oznaczających kolejno wysokość i szerokość planszy oraz ilość superpłytek. W następnych wierszach znajdują się trójki liczb . W następnych liniach znajduje się po liczb całkowitych , tak, że jeśli pole planszy w -tym wierszu i w -tej kolumnie jest początkowo pokryte, i 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 i superpłytkami. Przykład: Wejście: 5 8 4 Wyjście: 60
Szeregowanie zadańLimit czasowy 5s, limit pamięciowy 64MB Mamy 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 , a miało zostać wykonane w chwili , a kara za zwłokę to , nałożona kara to . 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ą oznaczającą ilość zadań do wykonania. W następnych liniach znajdują się trójki liczb całkowitych , 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 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.
(7 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com