Hinty do zadań obowiązkowych, dla tych z nas którzy nie są tak uzdolnieni algorytmicznie, a zapisali się na MIA 
Request:
-
GUARDMARK -
NPOK
-
RONALD
-
262144
-
Podzielność
1 polubienie
NPOK: Zapisujemy {n}\choose{k} jako \frac{n*(n-1)*...*(n-k+1)}{k!} i najpierw liczymy iloczyn w liczniku modulo p. Następnie przemnażamy to przez odwrotność modulo p mianownika, którą można znaleźć rozszerzonym algorytmem Euklidesa.
4 polubienia
GUARDMARK: Dynamik po podzbiorach krów. Dla każdego zbioru krów chcemy policzyć, czy jest dobry (tzn. można z niego zbudować wieżę) i jaki ma maksymalny czynnik bezpieczeństwa. Odpowiedzią jest maksimum czynników bezpieczeństwa dobrych zbiorów o wysokości przynajmniej H. Dla każdego zbioru przeglądamy jego podzbiory o jeden mniejsze i jeśli podzbiór jest dobry, to sprawdzamy, czy krowę, którą różnią się te dwa zbiory, można wsadzić na sam dół. Jeśli tak, to aktualizujemy maksymalny czynnik bezpieczeństwa zbioru i zaznaczamy, że jest dobry. Jeśli wysokość zbioru wynosi co najmniej H, to aktualizujemy odpowiedź. Zbiory trzeba przeglądać tak, żeby w momencie rozważania zbioru wszystkie jego podzbiory były już rozpatrzone. Można to zrobić traktując liczby od 0 do 2^n-1 jak podzbiory zbioru wszystkich krów i przechodząc je od najmniejszej do największej.
RONALD: Każdy wierzchołek możemy zmienić zero razy lub jeden raz, bo po dwóch zmianach wracamy do stanu początkowego. Jeśli na początku krawędź istnieje, to chcemy jej końce zmienić parzyście wiele razy, jeśli nie istnieje - nieparzyście wiele razy, więc dla każdej krawędzi dostajemy warunek na parzystość sumy liczb zmian końców tej krawędzi. Załóżmy, że pierwszy wierzchołek zmieniamy. Możemy wtedy policzyć dla każdego wierzchołka, czy trzeba go zmienić. Gdy mamy to policzone, sprawdzamy, czy wszystkie warunki są spełnione. Jeśli tak, to ok, jeśli nie, to zakładamy, że pierwszego wierzchołka nie zmieniamy i robimy to samo. Jeśli warunki są spełnione, to ok, w przeciwnym wypadku nie da się.
2 polubienia
Może ktoś więcej chciałby się czymś podzielić?
- 262144
- Podzielność
262144
Bessie likes downloading games to play on her cell phone, even though she does find the small touch screen rather cumbersome to use with her large hooves.
She is particularly intrigued by the current game she is playing. The game starts with a sequence of N positive integers (2 ≤ N ≤ 262144), each in the range 1…40. In one move, Bessie can take two adjacent numbers with equal values and replace them a single number of value one greater (e.g., she might replace two adjacent 7s with an 8). The goal is to maximize the value of the largest number present in the sequence at the end of the game. Please help Bessie score as highly as possible!
Input
The first line of input contains N, and the next N lines give the sequence of N numbers at the start of the game.
Output
Please output the largest integer Bessie can generate.
Podzielność
Jasio, jak każdy informatyk uwielbia cyfry 0 i 1. Lubi także liczby podzielne przez N. Chciałby połączyć te dwa zainteresowania i wymyślił zadanie.
Zadanie
Napisz program, który: wczyta liczbę N, wyznaczy najmniejszą dodatnią liczbę złożoną tylko z cyfr 0 i 1, która jest podzielna przez N i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym i jedynym wierszu wejścia znajduje się jedna liczba naturalna N (1 \le N \le 10^6) .
Wyjście
W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba całkowita - najmniejsza możliwa złożona tylko z cyfr 0 i 1, podzielna przez N.
Podzielność: Przeglądamy liczby składające się z zer i jedynek od najkrótszej do najdłuższej, dopisując do poprzednich zera i jedynki. Każdą liczbę reprezentujemy jako jej resztę z dzielenia przez n, pamiętając liczbę (resztę) z której powstała i cyfrę przez dopisanie której powstała. Zaczynamy z jedynką w kolejce. Wyciągamy pierwszą liczbę z kolejki (niech to będzie k), dopisujemy 0 i liczymy resztę z dzielenia przez n. Jeśli nie było jeszcze takiej reszty, to zapisujemy, że ta reszta powstaje z k przez dopisanie zera i wrzucamy ją na koniec kolejki. Jeśli już była, to nic nie robimy. Powtarzamy to samo dla jedynki. Gdy trafimy na resztę 0, kończymy przeszukiwanie i odtwarzamy wielokrotność korzystając z tego, że zapamiętywaliśmy, skąd i jak przychodzimy. Dzięki temu, że każdą resztę odwiedzamy tylko raz, nie przejrzymy więcej niż n liczb, a dzięki temu, że do kolejki wrzucamy liczby od najkrótszej do najdłuższej i najpierw dopisujemy 0, a potem 1, znajdziemy najmniejszą możliwą liczbę.
262144: http://www.usaco.org/current/data/sol_262144_platinum_open16.html
3 polubienia
W tym zadaniu p jest pierwsze, więc można nawet prościej liczyć odwrotność modularną, używająć Małego Twierdzenia Fermata i szybkiego potęgowania.
2 polubienia
RONALD: Niech a, b, c będą wierzchołkami grafu. Można pokazać, że jeśli w którymkolwiek momencie w grafie są dokładnie dwie krawędzie między a, b, c, to odpowiedzić jest nie. Stąd już łatwo można wywnioskować, że odpowiedź jest tak wtedy i tylko wtedy, gdy graf na wejściu jest rozłączną sumą dwóch klik (z których być może jedna jest pusta).