TopCoder

欸我好笨ㄛ
Why am I so weak mie pu

User's AC Ratio

97.1% (136/140)

Submission's AC Ratio

78.4% (262/334)

Tags

Description

雖然聖誕節快要到了,但這不是動態種樹問題,而是凍態眾樹問題(眾毆)。

所謂的眾數(英文叫做mode),就是指一些數字當中出現頻率最高的數。
對於已經給定的資料來說,計算眾數所需要的時間基本上是線性的,理論上對各位來說理應相當的簡單。

現在讓我們考慮一個不斷增加的動態集合(dynamic set),為了探討眾數的變化情況,我們想要知道每次增加一個數字以後,眾數有幾種以及最小的眾數數值。請你寫個程式來達成這個任務吧!

Input Format

一開始的動態集合為空,輸入的每一列有一個正整數A(1<=A<231)代表依序加入該動態集的元素。讀入A=0的時候代表輸入結束,請不要將0視為動態集當中的一個元素。

你可以假設輸入的元素最多只有100,000個。

Output Format

對於每一列輸入請輸出以一個空白隔開的兩個數字S,T,分別代表已經加入動態集的所有元素裡面,任一種眾數的個數以及最小的眾數數值
詳情請參考範例輸出。

Sample Input 1

1
2
3
3
2
1
0

Sample Output 1

1 1
1 1
1 1
2 3
2 2
2 1

Hints

Problem Source

原TIOJ1160 / 96 TWN Practice Contest 4。Problem Setter:Tmt。

Subtasks

No. Testdata Range Score
1 0 16
2 1 16
3 2 16
4 3 16
5 4 16
6 5 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1
1 1500 65536 262144 2
2 1500 65536 262144 3
3 1500 65536 262144 4
4 1500 65536 262144 5
5 1500 65536 262144 6