Giải bài đa hệ thống chấm

Điểm: 5,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Bạn cần giải $n$ bài tập trên một hệ thống chấm bài chính (gọi là Decoforces). Bài thứ $i$ có độ khó $a_{i}$ (là một số nguyên dương). Độ khó được đo thống nhất giữa tất cả các hệ thống chấm bài: một bài có độ khó $d$ trên Decoforces khó tương đương một bài có độ khó $d$ trên bất kỳ hệ thống chấm bài nào khác.

Bạn có thể giải các bài đã chọn theo thứ tự tùy ý, nhưng chỉ có thể giải bài có độ khó $a_{i}$ nếu trước đó đã giải được ít nhất một bài có độ khó không nhỏ hơn $⌈ a_{i} / 2 ⌉$ (trên bất kỳ hệ thống chấm bài nào, không nhất thiết là Decoforces).

Trước khi bắt đầu danh sách này, bạn đã giải các bài với độ khó tối đa là $k$ (tức là bạn đã từng giải ít nhất một bài có độ khó $k$ ).

Với mọi số nguyên dương $y$ , luôn tồn tại một bài tập có độ khó $y$ trên ít nhất một hệ thống chấm bài khác (ngoài Decoforces). Bạn có thể giải các bài trên hệ thống chấm khác vào bất kỳ thời điểm nào — không bắt buộc phải làm các bài Decoforces liên tiếp.

Hãy tính số lượng tối thiểu các bài cần giải trên những hệ thống chấm bài khác để có thể giải hết $n$ bài đã chọn trên Decoforces.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $k$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ — độ khó của các bài cần giải trên Decoforces.

Dữ liệu ra

In ra một số nguyên duy nhất là số lượng bài tối thiểu cần giải trên những hệ thống chấm khác.

Ràng buộc

$1 \leq n \leq 10^{3}$
$1 \leq k \leq 10^{9}$
$1 \leq a_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 20 10 3 6 3	0	Mọi $a_{i}$ đều có $⌈ a_{i} / 2 ⌉ \leq 5 \leq k = 20$ , nên có thể giải hết các bài mà không cần đến hệ thống chấm khác.
3 3 2 1 9	1	Giải bài 1 (độ khó 1) và bài 2 (độ khó 2) trước, vẫn có $k = 3$ . Để giải bài độ khó 9 thì cần đã giải một bài độ khó $\geq 5$ . Giải một bài độ khó 6 trên hệ thống chấm khác (đủ điều kiện vì $⌈ 6 / 2 ⌉ = 3 \leq k$ ). Sau đó giải được bài độ khó 9. Tổng cộng 1 bài "ngoài".

Bình luận

Không có bình luận tại thời điểm này.