P157PROA spoj PTIT - ROUND 7A - Số may mắn

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

1. Đề bài P157PROA spoj

Để chọn ra con số may mắn của riêng CLB IT – PTIT, chủ nhiệm CLB yêu cầu mỗi thành viên lựa chọn một số nguyên dương bất kỳ trong khoảng từ 1 đến 1000. Sau đó con số nào được chọn bởi nhiều người nhất thì sẽ là số may mắn. Nếu có nhiều con số được chọn nhiều lần như nhau thì sẽ ưu tiên chọn con số nhỏ hơn.

Giả sử số thành viên của CLB cũng không thể quá 1000 người. Hãy giúp CLB chọn ra số may mắn.

Input

Dòng đầu tiên ghi số bộ test (không quá 100). Dòng đầu của mỗi bộ test ghi số N, là tổng số thành viên của CLB.

Tiếp theo là N dòng, mỗi dòng ghi một giá trị được chọn.

Output

Với mỗi bộ test, ghi ra trên một dòng số may mắn tìm được.

Example

Input:
3

Output:
42

2. Gợi ý P157PROA spoj PTIT

– sắp xếp các số mà thành viên chọn, sau đó đếm số lượng số xuất hiện nhiều nhất.

– Tuy nhiên việc sắp xếp bằng Quicksort nay nổi bọt là không hay bằng đếm phân phối bằng mảng đánh dấu , và đếm phân phối trong bài này sẽ dễ nhất.

3. Code tham khảo P157PROA spoj PTIT

Đếm phân phối + Quicksort

a. Code Đếm phân phối

const   fi='';
        nmax=1000;
type    data=longint;
var
        f:text;
        A:array[0..nmax+1] of data;
        n,test:data;

procedure docfile;
var     i,j,x,sl:data;
begin
        assign(f,fi); reset(f);
        readln(f,test);
        for i:=1 to test do
                begin
                        fillchar(a,sizeof(a),0);
                        readln(f,n);
                        sl:=0;
                        for j:=1 to n do
                                begin
                                        readln(f,x);
                                        inc(a[x]);
                                end;
                        for j:=1 to 1000 do
                                if a[sl]<a[j] then
                                        sl:=j;
                        writeln(sl);
                end;
        close(f);
end;

begin
        docfile;
end.

b. Code Quicksort

const fi = '';
      fo = '';

var   n, i, count, d, min, count1, nTest, iTest:longint;
      a : array[1..1005] of longint;

procedure Qsort(x, y : longint);
var i,j,t,tam:longint;
begin
  if x >= y then exit;
  i:=x;  j:=y;
  t:=a[(x+y)div 2];
  repeat
   while a[i]<t do inc(i);
   while a[j]>t do dec(j);
   if i<=j then
    begin
     tam:=a[i];
     a[i]:=a[j];
     a[j]:=tam;
     inc(i);
     dec(j);
    end;
 until i > j;
 Qsort(x,j);  Qsort(i,y);
end;

begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  readln(nTest);
  for iTest:=1 to nTEst do
    begin
      readln(n);
      for i:=1 to n do readln(a[i]);
      qsort(1,n);

      d:=1; min:=a[1];
      count:=0;
      for i:=1 to n do
        if a[i]<>a[i+1] then
          begin
            if d >count then count:=d;
            d:=1;
          end
        else inc(d);
      d:=1;
      for i:=1 to n do
        if a[i]<>a[i+1] then
          begin
            if d = count then
              begin
                writeln(a[i]);
                break;
              end;
            d:=1;
          end
        else inc(d);
    end;

  close(input);close(output);
 end.

P157PROA spoj PTIT – ROUND 7A – Số may mắn