30066번 - Išmaniosios svarstyklės 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 6 | 6 | 5 | 100.000% |
문제
Martynas nusipirko išmaniąsias svarstykles ir nori sukurti programėlę savo svoriui sekti. Tačiau svarstyklėmis naudosis ne jis vienas – kartais pasinaudos svečiai, draugai, arba ant svarstyklių gali netyčia užlipti ir jo katinas.
Martynas sugalvojo algoritmą, kaip sekti, kiek skirtingų klientų naudojasi svarstyklėmis. Iš pradžių, svarstyklėmis nesinaudoja nei vienas klientas. Kai yra naujas matavimas, jis priskiriamas klientui pagal tokias taisykles:
- Jei matavimas nuo visų esamų klientų paskutinio svorio matavimo skiriasi daugiau negu $D$ gramų, tai laikoma, kad sveriasi naujas klientas ir jis yra užregistruojamas.
- Priešingu atveju, matavimas priskiriamas tam klientui, kurio paskutinis svorio matavimas yra artimiausias šiam matavimui.
- Jei yra keli klientai, kuriems tinka sąlyga (2), matavimas priskiriamas tam klientui, kurio paskutinis svorio matavimas yra mažesnis.
Pavyzdžiui, tarkime, jog svarstyklės užregistravo tokius matavimus iš eilės:
- $75000$ gramų: Martynas pasisvėrė ryte.
- $75500$ gramų: Martynas pasisvėrė vakare.
- $3000$ gramų: Pasisvėrė katinas.
- $78500$ gramų: Martyno draugas išbandė svarstykles.
- $2950$ gramų: Ant svarstyklių vėl užlipo katinas.
- $77000$ gramų: Vėl pasisvėrė Martynas (pavalgęs).
Su parametru $D = 1500$, Martyno algoritmas sugebėtų teisingai atskirti, jog svartyklėmis iš viso naudojosi trys klientai:
Jums duota $N$ svorio matavimų, kuriuos užregistravo išmaniosios svarstyklės, ir parametras $D$. Pagal Martyno sugalvotą algoritmą suskaičiuokite, kiek skirtingų klientų (žmonių, katinų, pelių...) iš viso pasinaudojo svarstyklėmis.
입력
Pirmoje eilutėje įrašyti su sveikieji skaičiai $N$ ir $D$. Toliau seka $N$ eilučių, kuriose įrašyta po vieną svorio matavimą $m_i$ (gramais).
출력
Išveskite vieną skaičių – kiek klientų pasinaudojo išmaniosiomis svarstyklėmis.
제한
- $1 ≤ N ≤ 10\,000$
- $0 < D, m_i ≤ 200\,000$
예제 입력 1
6 1500 75000 75500 3000 78500 2950 77000
예제 출력 1
3
Pavyzdys nagrinėtas sąlygoje.
Atkreipkite dėmesį, kad paskutinio matavimo atveju taikoma taisyklė (3), kadangi matavimas $77000$ skiriasi tiek pat nuo paskutinio Martyno svorio ($75500$ gramai), kiek ir nuo jo draugo svorio ($78500$ gramai).
예제 입력 2
8 2000 60000 61000 79000 62000 81000 60000 59000 80000
예제 출력 2
2
Šiuo atveju svarstyklėmis naudojosi du klientai: vienas sveriantis apie $60$ kg, ir kitas – apie $80$ kg.