g501: 109北二4.旅遊的規劃
Tags :
Accepted rate : 11人/11人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-10-26 22:46

Content

阿龍是為程式設計師,他有個朋友小王是位嚮導,現在小王要接一批新的旅遊團,地點在**島,但是景點規劃還沒決定好。
該島總共有 25 個觀光景點,因為旅遊時間有限,因此最多只能規劃到 12 個景點。

為了幫助小王,小王的前輩給他之前參加**島的旅遊團覺得很棒的四組旅遊行程,每組行程的景點規劃都不一樣,
以下為該四組行程有去的景點,每個數字代表一個景點:

{1, 2, 3, 5, 6, 8, 11, 13, 17, 21, 22}

{2, 3, 5, 7, 8, 13, 16, 17, 21, 22, 24}

{1, 3, 5, 6, 7, 15, 16, 17, 22, 23, 24, 25}

{2, 4, 5, 7, 8, 15, 17, 21, 23, 25}

小王聽說阿龍之前做過推薦產品的程式專案,因此請教他如何用這四組行程來找出比較熱門的景點或景點組合。
小龍告訴小王一個流程概念,首先假設熱門的門檻值 H 為出現兩次:

1. 先計算出每個景點出現的次數,例如:景點 1 出現兩次、景點 3 出現三次。
2. 將沒有出現超過門檻 H ( = 兩次) 的景點從規劃中去掉。
3. 用超過門檻值的單一景點,組合出長度為二的景點規劃,例如:景點組合 (1, 3)。
4. 回去確認四組行程裡景點組合 (1, 3) 出現的次數,若超過門檻 H ( = 兩次) 則加入規劃中。
5. 重複上述組合的動作,以將景點組合成長度三、長度四、長度五......後再回去檢查是否有超過門檻值。
    例如:景點長度三 (1, 3, 5) 兩次,景點長度四 (2, 8, 17, 21) 三次。
    依此類推,可找出四組行程所有較熱門的景點或景點組合。

請你將阿龍講的方法用上面四組形成去找出較熱門的景點或景點組合。

Input

第一行為一正整數 H (1 ≤ H ≤ 4),代表熱門的門檻值。

第二行為一正整數 N (1 ≤ N ≤ 25),代表景點組合長度 N,
N 為 1 代表單一景點,N 為 3 則代表景點組合長度三,依此類推。

Output

輸出一個正整數,代表超過門檻值 H 且景點長度 N 的組合共有幾組。
例如:H = 2, N =3,代表出現超過兩次,景點組合長度為三的組合數量。

Sample Input #1
4
2
Sample Output #1
1
Sample Input #2
4
5
Sample Output #2
0
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1K
公開 測資點#4 (5%): 2.0s , <1K
公開 測資點#5 (5%): 2.0s , <1K
公開 測資點#6 (5%): 2.0s , <1K
公開 測資點#7 (5%): 2.0s , <1K
公開 測資點#8 (5%): 2.0s , <1K
公開 測資點#9 (5%): 2.0s , <1K
公開 測資點#10 (5%): 2.0s , <1K
公開 測資點#11 (5%): 2.0s , <1K
公開 測資點#12 (5%): 2.0s , <1K
公開 測資點#13 (5%): 2.0s , <1K
公開 測資點#14 (5%): 2.0s , <1K
公開 測資點#15 (5%): 2.0s , <1K
公開 測資點#16 (5%): 2.0s , <1K
公開 測資點#17 (5%): 2.0s , <1K
公開 測資點#18 (5%): 2.0s , <1K
公開 測資點#19 (5%): 2.0s , <1K
Hint :

記憶體限制 512 MB,每筆測資時間限制 2 s
皆比照真實比賽環境

Tags:
出處:
109北二區桃竹苗資訊學科能力複賽 [管理者:
mushroom.cs9... (mushroom)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」