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 ...
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
3
42
42
19
4
7
99
99
7
5
11
12
13
14
15
Output:
42
7
11
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | 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. |
