10.05.2017

Thời điểm gặp mặt

(Tin học trẻ toàn quốc - 2000 - Bảng B).
Một nhóm gồm n bạn học sinh của một lớp tham gia một câu lạc bộ tin học vào dịp nghỉ hè. Biết rằng khoảng thời gian mà bạn thứ i có mặt tại câu lạc bộ là [ai, bi] (ai<bi tương ứng là các thời điểm đến và rời khỏi câu lạc bộ). Cô giáo chủ nhiệm lớp muốn tới thăm các bạn trong nhóm này. Hãy giúp cô giáo chủ nhiệm xác định thời điểm đến câu lạc bộ sao cho tại thời điểm đó cô giáo có thể gặp được nhiều bạn trong nhóm nhất.
Dữ liệu: Vào từ file văn bản MEETING.INP:
   Dòng đầu tiên ghi số nguyên dương n (n   1000);
   Dòng thứ i trong số n dòng tiếp theo ghi 2 số nguyên không âm ai, bi , i = 1, 2, ..., n.
Kết qủa: Ghi ra file văn bản MEETING.OUT:
   Dòng đầu tiên ghi số nguyên dương k là số lượng bạn đang có mặt ở câu lạc bộ tại thời điểm cô giáo đến;
   Trong k dòng tiếp theo ghi chỉ số của k bạn có mặt ở câu lạc bộ tại thời điểm cô giáo đến, mỗi dòng ghi một chỉ số của một bạn.
Ví dụ:
   MEETING.INP     MEETING.OUT               MEETING.INP      MEETING.OUT
   6                             3                                          5                               1
   1  2                         1                                          1 2                           1
   2  3                         2                                          3 5
   2  5                         3                                          7 9
   5  7                                                                     11 15
   6  7                                                                     17 21
   9 11   
                                              Lời giải tham khảo
const
      fi='meeting.inp';
      fo='meeting.out';
 var
    f: text;
    a: array[1..2,1..1000] of integer;
    i,max,n,j,b,d: integer;
 begin
      assign(f,fi);
      reset(f);
               readln(f,n);
               for i:=1 to n do readln(f,a[1,i],a[2,i]);
      close(f);
      for i:=1 to n-1 do
          Begin
               d:=0;
               for j:=i+1 to n do
                   if (a[1,j]<=a[2,i]) and (a[2,j]>=a[1,i]) then d:=d+1;
               if d>max then
                  begin
                       max:=d;
                       b:=i;
                  end;
          End;
     assign(f,fo);
      rewrite(f);
                 writeln(f,max);
                 for i:=b to n do
                     if (a[1,i]<=a[2,b]) and (a[2,i]>=a[1,b]) then writeln(f,i]);
      close(f);
 end.

4 comments:

Cảm ơn bạn đã nhận xét