Problem hidden

This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Zadanie w systemie SPOJ (srednie)

865. Bombardier Jaś

Kod zadania: PZPI06_2

Kanonier Jaś, po wspaniałym występie w Bajtlandzkich Igrzyskach Wojskowych, otrzymał propozycję awansu na stopień bombardiera. Ponieważ w wojsku Bajtlandii, oprócz umiejętności praktycznych, liczy się również wiedza teoretyczna, Jaś musiał zdać odpowiedni egzamin.

Jedno z zadań na egzaminie polegało na wyznaczeniu prędkości obrotowej obracającej się (przeciwnie do wskazówek zegara) platformy, na której umieszczone zostało strzalające w równych odstępach czasu działo. Dla każdego strzału zapamiętywana była wartość k < n wskazująca na kąt 0 <= 2*PI*k/n < 2*PI wyznaczający kierunek, w którym został on oddany. Wartość n jest wspólna dla wszystkich kątów. Zakładać będziemy, że żadne dwa strzały nie zostały oddane w tym samym kierunku.

Wejście

W pierwszej linii podana została liczba testów t <= 10. W pierwszej linii każdego zestawu testowego podana została para liczb m n, oznaczająca odpowiednio liczbę strzałów oraz wartość mianownika potrzebną do wyznaczenia kątów. W drugiej linii zestawu testowego podane zostały wartości k dla wszystkich kątów, posortowane w porządku rosnącym. Przyjmiemy ograniczenia: 2 <= m < n <= 5000.

Wyjście

Dla każdego testu należy wyznaczyć minimalną wartość prędkości obrotowej platformy, z której mogły nastąpić zadane kątami strzały. Podana na wyjściu liczba całkowita a wskazywać będzie na prędkość obrotową równą 2*PIa/n [1/s].

Przykład

Wejście:
4
2 4
0 3
3 7
0 2 5
5 15
0 4 7 8 11
3 9
1 4 7

Wyjście:
1
2
4
3

Dodane przez:	Michał Małafiejski
Data dodania:	2006-06-01
Limit czasu wykonania programu:	10s
Limit długości kodu źródłowego	50000B
Języki programowania:	All except: PERL 6

ukryj komentarze

2012-04-08 21:30:36 Piotr Kąkol
In:
1
8 16
1 2 5 8 11 12 14 15
Out:
3

2012-02-20 18:11:19 Marcin Nowak
Też się z tym męczyłem... chodzi o to, że prędkość obrotowa jest STAŁA, więc trzeba znaleźć minimalną, STAŁĄ prędkość obrotową, która pozwala trafić w te wszystkie punkty. Pozdrawiam!

2011-07-08 14:29:48 narbej
Rysunek czwarty na [mat.pl] opisałeś:
"Widzimy, że znów nieważne gdzie zaczniemy, i tak naszą odpowiedzią będzie 120", a tak naprawdę jest to jedyny przypadek [z przedstawionych czterech], w którym nie ważne w którym punkcie oddamy pierwszy strzał. Na rysunku 3, żeby być w zgodzie z założeniami zadania, pierwszy strzał oddajemy w punkcie E, a następnie w pkt.: E, C, B, F, D.
Jeżeli to przemyślisz i przeanalizujesz, to może znajdziesz błąd w swoim algorytmie.
Pozdrawiam
PS
poprawka oczywiście C, B, F, D [z E był pierwszy strzał]

Ostatnio edytowany: 2011-07-08 14:42:52

2011-07-07 23:26:44 Piotr Kąkol
Podświetlany jest wynik z każdej kategorii gdy otrzyma się maxa (tak więc gdy Nartith zrobi jeszcze te 4 zadania będzie miał 2 czerwone pola). Jeśli masz jakieś propozycje nie krępuj się napisać na forum. :-)

Co do zadania to podałem swój algorytm na mat.pl + tutaj go streściłem (z tym wybieraniem 2giej największej wartości - na mat.pl jest podana przyczyna takiego algorytmu).
A czemu być zaczął od punktu E?

2011-07-07 21:37:31 narbej
Wracając do zadania. Na matpl, przy trzecim rysunku piszesz, że startujesz z dowolnego punktu,a moim zdaniem musisz zacząć z punktu E. Nie wiem jaki masz algorytm więc jak mam znaleźć błąd w twoim toku myślenia?

2011-07-07 21:29:54 narbej
Dokładnie o te podświetlanie. Przydało by się jeszcze takie podświetlanie w innych kategoriach i innych kolorach [np Nartith w średnich zrobił już 115 zadań, Gratulacje];)

2011-07-07 18:22:59 Piotr Kąkol
Dzięki za odpowiedź.
"druga największa wynosi 72 a nie 96" - nie. Przy wyliczaniu drugiego największego kąta korzystam tak jakby z multiseta a nie seta. Czyli każda wartość jest barana pod uwagę.
Ok, skasuję.
To jakbyś kiedyś miał czas na przejrzenie kodu jeszcze raz i znalezienie błędu (nie mówię o podaniu algorytmu) w moim toku myślenia, byłbym wdzięczny.
Edit: A z tą koszulką to chodziło Ci o to podświetlenie na czerwono punktów jeśli jest to maksymalna liczba w danej kategorii?

Ostatnio edytowany: 2011-07-07 18:24:03

2011-07-07 15:25:30 narbej
A zatem .....
Proponuję przenieść zadanie do kategorii trudnych;-)
PS
Zmusiłem się do przypomnienia sobie jak to zadanie rozwiązałem i moja wcześniejsza podpowiedź nie była całkowicie zgodna [albo nawet była całkowicie niezgodna] z metodą jaką sam zastosowałem do rozwiązania tego zadania.

Ostatnio edytowany: 2011-07-07 15:27:07

2011-07-07 00:08:49 narbej
PS
Jak uzyskasz AC skasuj te komentarze, bo rysunki na mat.pl + te dwa komentarze podają algorytm prawie na tacy;)

2011-07-07 00:04:34 narbej
Rysunki na matematyka.pl są dobre i przedstawione tam rozumowanie tez. Nie ma tam jednak algorytmu jak to liczysz. Jeżeli to ma być druga największa różnica[kątowa] to wg trzeciego rysunku druga największa wynosi 72 a nie 96: [1]=24, [2]=72, [3]=96. Może to jest ten błąd?
Więcej nie mogę Ci pomóc, bo już sam nie pamiętam dokładnie jak to zrobiłem [musiałbym bardzo wczytać się w swój bałaganiarski kod], a poza tym byłoby to niefer;)

Gratuluję czerwonej koszulki lidera!

POLSKI SPOJ