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.|

ETI07E6 - Zimowe zapasy

Po skończonej pracy w ogrodzie Jaś postanowił poświęcić się swoim zainteresowaniom myrmekologicznym. W ogrodzie znajduje się mrowisko, którego dzieje Jaś obserwuje z zapałem od lat. Podglądając pracę mrówek, które zbierają pokarm z okolicy i zanoszą go do mrowiska w sposób pozornie chaotyczny, Jaś sformułował następujący problem matematyczny. Oznaczmy przez mi, xi, yi odpowiednio masę oraz położenie jednego z n <= 100000 pokarmów znajdujących się wokół mrowiska położonego w początku układu współrzędnych, czyli w punkcie (0,0). Zadaniem mrówek jest przetransportowanie jak najwięcej pokarmu do mrowiska. Sprawę komplikuje fakt, że inne owady też biorą udział w wyścigu po pokarm, w związku z tym część pokarmu ulega utracie w trakcie upływu czasu (również podczas transportu pokarmu do mrowiska). Jaś ten fakt zamodelował w taki sposób, że w każdej minucie ubywa w sposób ciągły dokładnie (1/k) * mi pokarmu, gdzie k jest liczbą całkowitą dodatnią nie większą niż 100000. Zakładając, że w danym momencie mrówki transportują co najwyżej jeden pokarm ze stałą dla wszystkich pokarmów prędkością równą 1 m/s, należy wyznaczyć maksymalną ilość pokarmu, którą przetransportują mrówki, oraz czas (w sekundach), w którym zostanie on dostarczony do mrowiska.

Wejście

W pierwszym wierszu znajduje się liczba pokarmów n oraz wartość k. W kolejnych n wierszach znajdują się trójki liczb całkowitych określające masę (o wartościach nie większych niż 1000) oraz współrzędne położenia pokarmów (z zakresu od -100000 do 100000).

Wyjście

Maksymalna możliwa do przetransportowania ilość pokarmu oraz czas, w którym zostanie on dostarczony do mrowiska. Wynik należy podać z dokładnością do dwóch miejsc po przecinku.

Przykłady

Zestaw przykładowy 1

Wejście:
4 2
2 4 0
8 0 4
4 -4 2
3 0 -2

Wyjście:
14.99 28.94

Zestaw przykładowy 2

Wejście:
6 1
3 1 1
6 -1 -1
6 1 2
9 2 5
7 15 7
10 2 3

Wyjście:
25.51 28.11

Dodane przez:mima
Data dodania:2006-11-15
Limit czasu wykonania programu:1s-5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU

ukryj komentarze
2011-07-24 14:34:36 Piotr KÄ…kol
Tak, nadal. Na forum był kiedyś podany nieefektywny, ale wzorcowy algorytm, ale już niestety nie ma. Może ktoś znów poda.
[edit by narbej: ależ jest, zobacz link, w komentarzu Charyzjusz'a]

Ostatnio edytowany: 2015-02-26 11:53:48
2011-07-24 13:00:23 Damian Straszak
Czy w tym zadaniu nadal są niepoprawne testy? Zanim zacznę się zastanawiać wolę to wiedzieć.
2011-02-18 21:09:41 Piotr KÄ…kol
Hmm. A teraz jak mamy uzyskać maksymalną liczbę punktów za to zadanie, skoro Narbej usunął niepoprawny (ale w tym zadaniu pożądany) szkic algorytmu?
2010-10-29 16:26:02 Charyzjusz Chakier
Wszystkim którzy pomimo rozlicznych prób nie są w stanie dostarczyć akceptowanej ilości pokarmu w akceptowanym czasie (gdyż najprawdopodobniej starają się rozwiązać zadanie zbyt sumiennie) polecam zapoznanie się z tym wątkiem: wątek na forum

Ostatnio edytowany: 2015-02-26 11:12:47
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.