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

C11CAVE - Hang động

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/c11cave


Một con đom đóm bay vào một cái hang đầy những chướng ngại vật gồm: măng đá (nhô lên từ mặt đất) và nhũ đá (đâm xuống từ trần hang). Hang này dài N đơn vị (N chẵn) và cao H đơn vị. Khi vào hang, vật cản đầu tiên là măng đá, sau đó là nhũ đã, rồi lại đến măng đá, ... cứ thế thay phiên nhau.

Đây là một ví dụ về một hang dài 14 đơn vị và cao 5 đơn vị.

Con đom đóm này không phải là loài có thể bay quanh các chướng ngại vật. Thay vào đó, nó sẽ chọn một mức chiều cao bắt đầu rồi bay từ đầu đến cuối hang, phá hết tất cả các chướng ngại vật trên đường bay của nó.

Theo ví dụ trên, nếu chọn mức 4, con đom đóm sẽ phá tất cả là 8 chướng ngại vật.

Đây không phải là lựa chọn tốt nhất vì con đom đóm sẽ ít mệt hơn nếu chọn mức 1 hoặc mức 5, lúc này nó chỉ cần phá 7 chướng ngại vật.

Bạn được cho chiều dài, chiều cao và kích thước của tất cả các chướng ngại vật. Hãy xác định số chướng ngại vật tối thiểu mà con đom đóm cần phá để thoát khỏi hang, và có bao nhiêu cách chọn khác nhau đưa đến kết quả đó.

Dữ liệu

  • Dòng 1: Hai số nguyên N và H (1 ≤ N ≤ 2.105 và 1 ≤ H ≤ 5.105) là chiều dài và chiều cao của hang.
  • Mỗi dòng trong N dòng tiếp theo là một số nguyên dương - kích thước của chướng ngại vật. Tất cả các kích thước đều nhỏ hơn H.

Kết quả

Gồm 2 số nguyên cách nhau là số chướng ngại vật ít nhất cần phá và số cách chọn khác nhau để có được kết quả đó.

Giới hạn

Trong tối đa là 1/3 số test, N * H không vượt quá 106.

Ví dụ

Input 1:
6 7
1
5
3
3
5
1 Output 1: 2 3  Input 2: 14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3 Output 2: 7 2

Được gửi lên bởi:Quan To
Ngày:2012-10-30
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU PERL6 PYPY RUST SED

hide comments
2014-05-27 16:24:19 Thcs Ðặng Chánh Kỷ
bài chấm nhanh hầy, Ac
2014-05-27 16:20:58 [GOD]
Không khó, đưa vào 2 mảng mẫu đá, nhũ đá, rồi quicksort, chặt nhị phân 2 mảng, Độ phức tạp O(N*log2(100000)*2)
2014-05-27 16:19:54 [GOD]
40 hoài do đọc dư liệu bằng 1 mảng độ lớn 200000 sau thay bằng 2 mảng độ lớn 100000 lại ac, hài vl
2014-05-26 04:47:44 Lollipop
QS+chặt np
tí nữa TLE time 0,99 =))

Last edit: 2014-05-26 04:51:38
2013-12-14 05:25:55 Nguyễn Trường Giang
làm như truy vấn 1 của QMAX
2012-12-16 01:58:35 anh chỉ yêu mình em.....VTNN......
lam theo qhd
2012-11-07 15:08:27 Nguyễn Trung Ðức
làm sao mà dc 100 vậy ><
2012-11-05 18:41:31 dhkhtn
de bai kho hieu the, muc 4 sao lai ve o 3.5.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.