logo AlgoBeat OnlineJudge
登录 注册

#215024. [NHSPC 2024] 數字叢集

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

小明暑假期間在某實驗室實習,主要工作就是協助實驗室整理大量的實驗數據。 實驗室累積了許多數據資料,但因設備及管理等問題,小明發現有些數據可能登記錯誤; 這些記錯的數字恰好為原數字的兩個位數被互換, 例如數字 被記錄成 或者數字 被記成 等等。

小明希望你寫出一個程式檢查哪些資料有可能被登記錯誤,具體來說他定義了一個關係函式 , 若 將某兩個位數互換後與 相等,則 ;否則 。 舉例來說 , 因為 的第一位數和第三位數互換時會變成 ; 但 ,因為交換任何兩個位數都無法變成相同的數字。

小明想要將 個相異的非負整數 運用關係函式 來加以分群。 開始時,每一個數字可以自成一群, 對於一個數字 和一個群 , 如果 有一個成員 使得 , 則將 所在的群與 合併,形成更大的群。

小明想知道這些數據可以分成幾群,群的個數越小越好,和最大的群有多少數字。請寫一個程式幫助小明完成此任務。

输入格式

  • 代表數字的個數。
  • 代表第 個想分群的整數。

输出格式

  • 代表分群後群的個數。
  • 代表分群後最大的群有幾個數字。

样例

样例输入 1

2
1234 1324

样例输出 1

1 2

样例输入 2

6
1234 1324 2134 7 3 30

样例输出 2

3 3

数据范围与提示

測資限制

  • 的位數小於等於 個數字皆相異且數字的前面不會有不必要的 (leading zero)。
  • 輸入的數皆為非負整數。

評分說明

本題共有三組子任務,條件限制如下所示。 每一組可有一或多筆測試資料,該組所有測試資料皆需答對才會獲得該組分數。

子任務 分數 額外輸入限制
1 15 的位數等於
2 28 的位數小於等於
3 57 無額外限制。