28670번 - Обезвреживание бомбы
폭탄 해체
나이트 시티의 도시에서 많은 끔찍한 사건들이 일어나고 있습니다. 지금 V는 목숨을 걸고 왓슨 지역 중심부에 있는 폭탄을 해체하고 있습니다.
폭탄을 재빨리 조사한 V는 정확히 n개의 버튼이 있고 각각의 버튼에는 자연수가 적힌 것을 발견했습니다. 모든 버튼은 활성 및 비활성 상태일 수 있으며, 상태는 누름으로써 전환되고, 이때 정확히 1초가 걸립니다. 처음에는 모든 버튼이 활성 상태입니다.
신뢰할 수 있는 정보원으로부터 V는 카운트다운이 끝날 때 폭탄의 활성 상태 버튼 중 합이 정확히 k인 두 개의 버튼이 있는 경우에만 폭탄이 폭발할 것임을 알고 있습니다. 물론 그는 폭탄을 해체할 수 있는 최소한의 시간을 알고 싶어 합니다.
V는 이전 미션에서 빠른 계산을 위해 뇌 임플란트를 손상시켰고, 이제 그는 폭탄이 폭발하지 않기 위해 필요한 최소 버튼 누름 횟수를 알아내기 위해 여러분의 도움이 필요합니다.
----입력----
첫 번째 줄에는 두 개의 정수 n과 k가 포함됩니다. ( 1 <= n <= 100 000, 1 <= k <= 109)
다음 줄에는 버튼에 쓰여진 n개의 숫자가 포함됩니다. (1 <= ai <= 109 )
----출력----
단일 정수 --- 폭탄을 해체하는 데 필요한 최소 버튼 누름 횟수를 인쇄합니다.
댓글을 작성하려면 로그인해야 합니다.
coffee21 3년 전 3
폭탄 해체
나이트 시티의 도시에서 많은 끔찍한 사건들이 일어나고 있습니다. 지금 V는 목숨을 걸고 왓슨 지역 중심부에 있는 폭탄을 해체하고 있습니다.
폭탄을 재빨리 조사한 V는 정확히 n개의 버튼이 있고 각각의 버튼에는 자연수가 적힌 것을 발견했습니다. 모든 버튼은 활성 및 비활성 상태일 수 있으며, 상태는 누름으로써 전환되고, 이때 정확히 1초가 걸립니다. 처음에는 모든 버튼이 활성 상태입니다.
신뢰할 수 있는 정보원으로부터 V는 카운트다운이 끝날 때 폭탄의 활성 상태 버튼 중 합이 정확히 k인 두 개의 버튼이 있는 경우에만 폭탄이 폭발할 것임을 알고 있습니다. 물론 그는 폭탄을 해체할 수 있는 최소한의 시간을 알고 싶어 합니다.
V는 이전 미션에서 빠른 계산을 위해 뇌 임플란트를 손상시켰고, 이제 그는 폭탄이 폭발하지 않기 위해 필요한 최소 버튼 누름 횟수를 알아내기 위해 여러분의 도움이 필요합니다.
----입력----
첫 번째 줄에는 두 개의 정수 n과 k가 포함됩니다. ( 1 <= n <= 100 000, 1 <= k <= 109)
다음 줄에는 버튼에 쓰여진 n개의 숫자가 포함됩니다. (1 <= ai <= 109 )
----출력----
단일 정수 --- 폭탄을 해체하는 데 필요한 최소 버튼 누름 횟수를 인쇄합니다.