TopCoder

User's AC Ratio

16.7% (1/6)

Submission's AC Ratio

34.4% (11/32)

Description

新奇公司一向以購物網站為行銷產品的主要管道,最近新奇公司的營收大幅減少,
業務部門決定針對購物網站的行銷狀況做一檢討。
專家認為由分析網站的瀏覽與購物狀況可了解客戶的購物行為,藉此可改善行銷策略,以增加營收。

首先需要了解客戶的網站瀏覽時段,據此可加強重點時段的廣告,以增進效益。
系統必須分別於每個客戶登入與登出時,記錄其時間,以便統計客戶瀏覽的高峰值與高峰時段:
瀏覽高峰值即為專家有興趣的統計時段中同時瀏覽購物網站之使用者的最大值;
瀏覽高峰時段即為瀏覽高峰值發生之子時段,此種時段可能有兩段以上。
其次為掌握客戶的購物需求,增加受歡迎商品的樣式與供貨量,系統亦須回報最受歡迎商品,
亦即統計時段中被購買最多次數的商品,此種商品可能會有兩個以上。

請寫一個程式協助專家分析客戶的瀏覽與購物狀態。

條件限制
1. 時間以分為單位,是0(零時零分)到1439(二十三時五十九分)的整數。
2. 統計時段之起點S≥0,終點E≤1439,且S<E。
3. 統計時段內至少會有一個客戶登入。
4. 專家只對統計時段中的事件有興趣。
5. 客戶帳號為1到100的整數。
6. 物品的標號為A到Z的英文字母。
7. 客戶登入、登出、與購買時間皆以零時零分為起點計算。
8. 每位客戶某一時間點的購買物品只能有一項,且個數為一。
9. 某一客戶有可能於登入時段沒有任何購買商品。
10. 某一客戶有可能於同一段登入時間內購買兩個以上的同一項商品。

Input Format

輸入檔案第一行是紀錄總筆數n,表示統計時段內,共有n筆登入登出紀錄(客戶可重複登入)。
第二行為專家有興趣的統計時間之起點S與終點E,中間以空白隔開,例如:82 840表示統計時間為1時22分到14時0分。
接下來的n 行每一行代表一筆客戶登入登出資料:
每行資料第一個數字是客戶帳號,第二個與第三個數字分別為登入與登出時間,
第四個數字代表此次登入所採購之商品數量,第五個以後的資料會成對出現,分別代表購買時間與購買商品品項。

Output Format

輸出檔案共有3行,第一行是一個數字,代表瀏覽高峰值。
第二行是瀏覽高峰時段,由開始時間與結束時間組成(中間以空白隔開),
若有兩段以上,則中間以空白分開,且以時段起點時間做排序,
例如:224 312 730 891 表示3時44分到5時12分,以及12時10分到14時51分兩個時段,
連續時段不可分開輸出,例如:33 55不可分開為33 40與41 55兩時段。
第三行是最受歡迎商品品項,若統計時段內所有客戶皆沒購買,則品項以?表示,
若最受歡迎商品有兩個以上,則以空白分開,且依字母順序由A到Z排列。

Sample Input

輸入檔範例 1
6
88 840
21 30 177 2 61 R 90 A
38 600 825 0
15 563 1021 3 630 A 663 B 921 A
21 153 543 1 273 B
32 73 404 1 312 R
8 427 650 1 571 B

輸入檔範例 2
3
260 1330
21 612 1003 0
8 30 273 0
51 420 608 0

Sample Output

輸出檔範例 1
3
153 177 600 650
B

輸出檔範例 2
1
260 273 420 608 612 1003
?

Hints

Problem Source

原TIOJ1681 / 98北市賽(prob 5)

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536