C11CAVE spoj - Hang động - Kiến Thức 24h

Nguồn đề bài: http://vn.spoj.com/problems/C11CAVE/

1. Đề bài C11CAVE spoj

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

spoj C11CAVE

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.

c11cave

Đâ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.10⁵ và 1 ≤ H ≤ 5.10⁵) 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á 10⁶.

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

2. Hướng dẫn bài C11CAVE SPOJ

– xây dựng mảng D bằng QHĐ. với D[i] là số lượng chướng ngại vật nằm trên độ cao i.

– việc còn lại là duyệt tìm kết quả bài toán.

để xây dựng mảng D bằng QHD bạn có thể tham khảo bài MTHCN.

3. Code tham khảo C11CAVE spoj

[sociallocker]

const   fi='';
        nmax=500000;
type    data=longint;
var
        f:text;
        A:array[0..nmax+1] of data;
        n,h:data;
procedure xuli;
var     i,j,x:data;
        res,slres:data;
begin
        assign(f,fi); reset(f);
        readln(f,n,h);
        for i:=0 to h+1 do
                a[i]:=0;
        for i:=1 to n do
                begin
                        read(f,x);
                        if i mod 2 <> 0 then
                                begin
                                        inc(a[1]);
                                        dec(a[x+1])
                                end
                        else
                                inc(a[h-x+1]);
                end;
        res:=a[1];
        slres:=1;

        for i:=2 to h do
                begin
                        a[i]:=a[i]+a[i-1];
                        if res=a[i] then
                                inc(slres)
                        else
                                if a[i]<res then
                                        begin
                                                res:=a[i];
                                                slres:=1;
                                        end;
                end;
        writeln(res,' ',slres);
        close(f);
end;

begin
        xuli;
end.

[/sociallocker]

SPOJ vn, C11cave, hang động, bài giải, code mẫu, solution

C11CAVE spoj – Hang động