#14252: 最後三組測資怎麼過?


qqqq123 (unknown)

School : 國立嘉義高級中學
ID : 79351
IP address : [180.217.209.27]
Last Login :
2019-06-04 19:52:31
c658. 小新的提款卡密碼 -- it's david | From: [1.200.55.139] | Post Date : 2018-07-06 10:33

我用next_permutation(),但是會TLE。。。

 
#14757: Re:最後三組測資怎麼過?


asnewchien@gmail.com (david)

School : Not Student
ID : 68108
IP address : [36.233.39.194]
Last Login :
2019-06-20 10:36:51
c658. 小新的提款卡密碼 -- it's david | From: [61.223.63.205] | Post Date : 2018-08-02 16:00

我用next_permutation(),但是會TLE。。。



用 next_permutation() 無法 AC

 
#17153: Re:最後三組測資怎麼過?


hq8398 (一群牛)

School : 國立花蓮高級中學
ID : 88824
IP address : [114.37.123.49]
Last Login :
2019-06-19 22:23:52
c658. 小新的提款卡密碼 -- it's david | From: [118.169.195.241] | Post Date : 2019-03-17 15:31

我用next_permutation(),但是會TLE。。。


我用DFS也是炸後面三組

 
#17156: Re:最後三組測資怎麼過?


rollfc (胖胖貓)

School : Not Student
ID : 81012
IP address : [61.222.86.91]
Last Login :
2019-06-20 16:20:29
c658. 小新的提款卡密碼 -- it's david | From: [140.113.136.220] | Post Date : 2019-03-18 03:54

我用next_permutation(),但是會TLE。。。


我用DFS也是炸後面三組



DFS會出現TLE,代表要找齊一樣是相同位數的可能性數字,再檢驗他是不是某個數字平方的方式是不可行。

當位數最大是10位數時每次排序的可能範圍最多是 9x9! 種可能(雖然檢驗的時間成本可以視為O(1))。

不如換個角度,題目要找到最少4位數,最多10位數的數字中(該數字剛好是個平方數且每個位數都不包含0)

那就搜集所有可以形成上述條件數字的平方數,也就是介於[ 34, 99999]之間的平方數並剔除包含0的數字,

針對每個數字拆成各個位數排序,用 HashTable 的方式紀錄,例如第一筆測資的 1296 2916 9216 可以把這三組都歸類到 1269 這組key

之後只要輸入數字就將他拆成各個位數後排序再組成一個數字後,檢查 HashTable 裡面有沒有這組 key 存在沒有就是輸出 -1,有就輸出所有的 value 即可。

 

 
#17157: Re:最後三組測資怎麼過?


rollfc (胖胖貓)

School : Not Student
ID : 81012
IP address : [61.222.86.91]
Last Login :
2019-06-20 16:20:29
c658. 小新的提款卡密碼 -- it's david | From: [140.113.136.220] | Post Date : 2019-03-18 04:01

 

DFS會出現TLE,代表要找齊一樣是相同位數的可能性數字,再檢驗他是不是某個數字平方的方式是不可行。

當位數最大是10位數時每次排序的可能範圍最多是 9x9! 種可能(雖然檢驗的時間成本可以視為O(1))。

不如換個角度,題目要找到最少4位數,最多10位數的數字中(該數字剛好是個平方數且每個位數都不包含0)

那就搜集所有可以形成上述條件數字的平方數,也就是介於[ 34, 99999]之間的平方數並剔除包含0的數字,

針對每個數字拆成各個位數排序,用 HashTable 的方式紀錄,例如第一筆測資的 1296 2916 9216 可以把這三組都歸類到 1269 這組key

之後只要輸入數字就將他拆成各個位數後排序再組成一個數字後,檢查 HashTable 裡面有沒有這組 key 存在沒有就是輸出 -1,有就輸出所有的 value 即可。

 



說錯,找不到時是輸出 0 。

這邊補充一下方便偵錯:

          #合法平方數  ->  #不重複的key

二位數             44   ->     40

三位數           512   ->    400

四位數          4046  ->   2470

五位數         32440 -> 12345

 
ZeroJudge Forum