BCMARA spoj PTIT – Chạy đua marathon

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCMARA/

1. Đề bài BCMARA spoj PTIT

John cho các con bò của mình chạy đua marathon!  Thời gian bò N (1 <= N <= 5,000) về đích được biểu diễn theo dạng Số giờ (0 <= Số giờ <= 99), Số phút (0 <= Số phút <= 59), và số giây (0 <= Số giây <= 59). Để xác định nhà vô địch, John phải sắp xếp các thời gian (theo số giờ, số phút, và số giây) theo thứ tự tăng dần, thời gian ít nhất xếp đầu tiên.

Ví dụ: Với 3 thời gian như sau:

11:20:20
11:15:12
14:20:14

Kết quả sau khi sắp xếp là:

11:15:12
11:20:20
14:20:14

INPUT FORMAT:

* Line 1: 1 số nguyên: N

* Lines 2..N+1: Dòng i+1 chứa thời gian bò i được mô tả bởi 3 số nguyên cách bởi dấu cách : Số Giờ , Số Phút, Số giây.

OUTPUT FORMAT:

* Dòng 1..N: Mỗi dòng chứa thời gian của 1 con bò là 3 số nguyên cách nhau bởi dấu cách sau khi đã sắp xếp.

SAMPLE INPUT:

3
11 20 20
11 15 12
14 20 14

SAMPLE OUTPUT:

11 15 12
11 20 20
14 20 14

Gợi ý: đổi giờ phút sang giây và dùng thuật toán sắp xếp Quicksort để sắp xếp, sau đó xuất ra kết quả.

2. code tham khảo BCMARA spoj PTIT

const   fi='';
        nmax=5500;
type    data=longint;
        dulieu=record
                h,p,s,sum:data;
        end;
var
        A:array[0..nmax] of dulieu;
        n:data;
        f:text;

procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        readln(f,n);
        for i:=1 to n do
                begin
                        readln(f,a[i].h,a[i].p,a[i].s);
                        a[i].sum:=a[i].h*3600+a[i].p*60+a[i].s;
                end;
        close(f);
end;

procedure sort(l,r: longint);
      var
         i,j,x: longint;
         y:dulieu;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2].sum;
         repeat
           while a[i].sum<x do
            inc(i);
           while x<a[j].sum do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;


procedure xuli;
var     i:data;
begin
        for i:=1 to n do
                writeln(a[i].h,' ',a[i].p,' ',a[i].s);
end;

begin
        docfile;
        sort(1,n);
        xuli;
end.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *