BÀI 4. ĐÔI BẠN CÙNG TIẾN Để đảm bảo đạt chỉ tiêu chất lượng cuối năm, thầy Hùng quyết định phân công cho các bạn có khả năng học tốt kèm cặp cho các bạn có lực học chưa đạt. Trong lớp có n bạn chưa đạt và m bạn học tốt. Nguyên tắc kèm là bạn học tốt phải có lực học hơn bạn chưa đạt một độ ít nhất là k. Ngoài chất lượng cuối năm, thầy Hùng còn phải đảm bảo các chỉ tiêu về học sinh giỏi cấp huyện và các cuộc thi khác, do đó thầy muốn chọn những bạn học tốt có lực học vừa đủ để kèm cặp bạn mình, để các bạn học tốt còn lại có thể tập trung cho nhiệm vụ khác. Em hãy giúp thầy lập ra danh sách những đôi bạn cùng tiến trong lớp. Dữ liệu vào: - Dòng đầu ghi 3 số nguyên dương n, m, k (n m 105, k 104), lần lượt là số lượng các bạn học chưa đạt, số lượng các bạn học tốt và độ lệch học lực ít nhất để bạn học tốt có thể kèm cặp bạn mình. Dữ liệu vào đảm bảo tìm được n bạn học tốt thỏa mãn yêu cầu. - Dòng thứ 2 ghi n số nguyên dương ai (ai 106), - Dòng thứ 3 ghi m số nguyên dương bi (bi 106) Dữ liệu ra: n dòng, mỗi dòng ghi 2 số nguyên lần lượt là lực học của bạn học chưa đạt và lực học của bạn học tốt, xếp tăng dần theo lực học của bạn chưa đạt. Ví dụ: DOIBAN.INP 4 6 4 1 2 3 1 6 6 7 8 5 2 DOIBAN.OUT 1 5 1 6 2 6 3 7

program DoiBan;

type
  Pair = record
    First: Integer;
    Second: Integer;
  end;

function DoiBan(n, m, k: Integer; var chua_dat, tot: array of Integer): array of Pair;
var
  chua_dat_sorted, tot_sorted: array of Pair;
  result_pairs: array of Pair;
  i, j: Integer;
  temp: Pair;
begin
  SetLength(chua_dat_sorted, n);
  SetLength(tot_sorted, m);
  SetLength(result_pairs, 0);

  for i := 0 to n - 1 do
  begin
    chua_dat_sorted[i].First := i + 1;
    chua_dat_sorted[i].Second := chua_dat[i];
  end;

  for i := 0 to m - 1 do
  begin
    tot_sorted[i].First := i + 1;
    tot_sorted[i].Second := tot[i];
  end;

  // Sắp xếp mảng theo yêu cầu
  for i := 0 to n - 1 do
    for j := i + 1 to n - 1 do
      if chua_dat_sorted[j].Second < chua_dat_sorted[i].Second then
      begin
        // Swap
        temp := chua_dat_sorted[j];
        chua_dat_sorted[j] := chua_dat_sorted[i];
        chua_dat_sorted[i] := temp;
      end;

  for i := 0 to m - 1 do
    for j := i + 1 to m - 1 do
      if tot_sorted[j].Second > tot_sorted[i].Second then
      begin
        // Swap
        temp := tot_sorted[j];
        tot_sorted[j] := tot_sorted[i];
        tot_sorted[i] := temp;
      end;

  i := 0;
  j := 0;
  while (j < m) do
  begin
    while (i < n) and (chua_dat_sorted[i].Second + k <= tot_sorted[j].Second) do
    begin
      SetLength(result_pairs, Length(result_pairs) + 1);
      result_pairs[High(result_pairs)].First := chua_dat_sorted[i].First;
      result_pairs[High(result_pairs)].Second := tot_sorted[j].First;
      i := i + 1;
    end;
    j := j + 1;
  end;

  Result := result_pairs;
end;

procedure Main;
var
  n, m, k, i: Integer;
  chua_dat, tot: array of Integer;
  result_pairs: array of Pair;
  file_in, file_out: TextFile;
begin
  AssignFile(file_in, 'DOIBAN.INP');
  Reset(file_in);

  ReadLn(file_in, n, m, k);

  SetLength(chua_dat, n);
  SetLength(tot, m);

  for i := 0 to n - 1 do
    Read(file_in, chua_dat[i]);
  ReadLn(file_in);

  for i := 0 to m - 1 do
    Read(file_in, tot[i]);
  ReadLn(file_in);

  CloseFile(file_in);

  result_pairs := DoiBan(n, m, k, chua_dat, tot);

  AssignFile(file_out, 'DOIBAN.OUT');
  Rewrite(file_out);

  for i := 0 to High(result_pairs) do
    WriteLn(file_out, result_pairs[i].First, ' ', result_pairs[i].Second);

  CloseFile(file_out);
end;

begin
  Main;
end.

$#lamtung$