BÀI TẬP 50: THỨ HẠNG (Đề thi HSG cấp huyện Lấp Vò 2021-2022)

Trong kỳ thi lập trình, có n thí sinh tham gia. Các thí sinh được đánh số thứ tự từ 1 đến n. Kết quả chung cuộc thí sinh i đạt được điểm số a_i.

            Yêu cầu: Với mỗi thí sinh, hãy cho biết có bao nhiêu thí sinh có cùng thứ hạng với mình (kể cả chính thí sinh đó).

            Dữ liệu vào: Cho từ tệp văn bản THUHANG.INP gồm hai dòng:

·    Dòng thứ nhất ghi số nguyên dương n (2<=n<=10^5).    

·    Dòng thứ hai ghi n số nguyên a₁, a₂, …, a_n ­là điểm số của các thí sinh (1 <=ai<=10^9).

            Kết quả: Ghi ra tệp văn bản THUHANG.OUT gồm một dòng ghi n số nguyên, số thứ i cho biết số thí sinh có cùng thứ hạng với thí sinh thứ i (kể cả thí sinh thứ i).

Ví dụ:

THUHANG.INP	THUHANG.OUT
9 6 7 1 6 7 4 5 4 7	2 3 1 2 3 2 1 2 3

            Giải thích: Thí sinh thứ nhất và thí sinh thứ tư đạt 6 điểm, có 2 thí sinh cùng 6 điểm nên cùng thứ hạng. Thí sinh thứ hai, thứ năm và thứ chín cùng đạt 7 điểm, 3 thí sinh này đồng hạng,…

            Giới hạn:

·    Có 40% số test tương ứng 40% số điểm có giá trị n<=10³ và 1<=ai<=10^3).

·    Có 40% số test tương ứng 40% số điểm có giá trị n<=10⁵ và 1<=ai<=10^6)

·   Có 20% số test tương ứng 20% số điểm có giá trị n<=10⁵ và 1<=ai<=10^9).

CODE THAM KHẢO:

Program Thu_Hang;

Const fin  = 'THUHANG.INP';

      fout = 'THUHANG.OUT';

Var n,i,j,dem:Longint;

    a:array[1..100000] of Longint;

    f:Text;

Begin

  Assign(f,fin);

  Reset(f);

  Read(f,n);

  For i:=1 to n do Read(f,a[i]);

  Close(f);

  Assign(f,fout);

  ReWrite(f);

  For i:=1 to n do

    Begin

      dem:=0;

      For j:=1 to n do

        If a[i]=a[j] then dem:=dem+1;

      Write(f,dem,' ');

    End;

  Close(f);

End.