루미 알고리즘

#1334골드Limousinen

PO 2014 결선코딩출제 Oskar Werkelin Ahlin스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

I Taipei har IOI satt igång med ett intensivt schema av föreläsningar, lekar, förberedelser, matpauser, sömnpauser och tävlingar. Men arrangörerna har lämnat en timme fri för alla att göra vad de vill. Detta är ett problem som lagledarna inte alls förberett de tävlande på. Förvirring och kaos uppstår i de tävlandes hjärnor, och när fritidstimmen är slut så är de N tävlande utspridda vid olika korsningar i storstaden och har inte en aning om hur de ska hitta tillbaka. Lyckligtvis hade tävlingsledningen installerat ett chip i varje tävlandes väska som gör att de kan se exakt vid vilken gatukorsning som varje vilsen tävlande befinner sig.

Limousinföraren Simon har fått i uppdrag att plocka upp de tävlande och köra dem, en i taget, till tävlingsarenan. Han vill naturligtvis undsätta dem i en ordning som gör att han hinner skjutsa tillbaka så många som möjligt innan nästa föreläsning börjar (vilket sker om T minuter). Taipei kan modelleras som ett oändligt regelbundet rutnät där heltalskoordinater är korsningar och det finns lodräta och horisontella vägar. Det tar exakt 1 minut att köra från en korsning till en närliggande korsning.

Simon börjar vid tävlingsarenan på adressen (0, 0), kör till den första personen och hämtar upp den och kör sedan hem personen till arenan. Därefter kör han till nästa person, o.s.v. Han fortsätter så tills tiden tar slut, och han kan alltså bara skjutsa en i taget. Om han väljer ordningen han hämtar upp de tävlande i optimalt, hur många hinner han hämta upp och skjutsa tillbaka inom T minuter?

Indata

På första raden i indata står två heltal N (1 ≤ N ≤ 100000), antalet tävlande som ska plockas upp, och T (1 ≤ T ≤ 10^9), hur lång tid Simon har på sig i minuter.

Sedan följer N rader (en rad per tävlande). Varje rad består av två heltal -10^8 ≤ x, y ≤ 10^8, x- och y-koordinater för personens nuvarande position.

Utdata

Skriv ut hur många tävlande som Simon hinner köra hem innan tiden är slut, givet att han väljer ordningen optimalt.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängvärdeGränser
120N ≤ 10, -1000 ≤ x,y ≤ 1000
230N ≤ 1000, -10^6 ≤ x,y ≤ 10^6
350Inga ytterligare begränsningar

Förklaring av exempelfall

Förklaring av exempelfall 1: Simon har 5 minuter på sig, och det finns tre tävlande att hämta upp. Att hämta den första tävlande tar 4 minuter, att hämta den andra tar 6 minuter, och att hämta den trejde tar 4 minuter (om han åker optimalt). Eftersom han bara har 5 minuter på sig så hinner han då bara hämta en person.

Förklaring av exempelfall 2: Simon hinner inte hämta någon alls.

Förklaring av exempelfall 3: Simon hinner precis hämta en person, personen som befinner sig vid (-100, 0).

예제

예제 1

입력
3 5
1 1
2 1
2 0
출력
1

예제 2

입력
2 1
1 0
0 1
출력
0

예제 3

입력
2 200
-100 0
231 -53
출력
1

출처 표기

출처: Programmeringsolympiaden 2014년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.