a099: C. 新 · 3N +1
標籤 : 2014國中組初賽
通過比率 : 3人/5人 ( 60% ) [非即時]
評分方式:
Strictly

最近更新 : 2023-08-07 12:31

內容

2014 網際網路程式設計全國⼤賽 國中組初賽

寧寧是個對程式極有興趣的國中⽣。有天,當她在網路上悠遊時看到了⼀個令她覺得神奇的問題:3N+1問題。

3N+1問題是這樣的:給⼀個正整數 N,如果它現在是偶數就除以⼆,否則乘以三加⼀,重複

⼀直做下去,問你要做幾步才會變成⼀。

寧寧雖然覺得不可思議,也質疑是否所有的數字到最後都會變成⼀,但聰穎的她仍很快的解出了這題。然⽽⾝為⼀個精益求精的好學⽣,她並不滿⾜於此。「題⽬規定只能乘以三加⼀,那如果改成乘以 A B 會怎麼樣呢?」寧寧問著⾃⼰。

使得將原問題中的乘以三加⼀換成乘以為了挑戰⾃⼰的智慧,她定義了新 · 3AN加+1B問題:給⼀個正整數後數字最快變成⼀。N ,請找到最佳的正整數 A,B 不幸的,這個問題變得太難,以⾄於寧寧無法快速解出來。你有辦法幫助她嗎?

輸入說明

輸⼊的第⼀⾏有⼀個正整數 T,代表測試資料的筆數。

每⼀筆測試資料包含⼀個正整數 N,代表新 · 3N+1問題中給定的 N

  • T ≤ 3000009 • N ≤ 10
輸出說明

對於每⼀筆測試資料請輸出⼀⾏,包含兩個最佳的正整數 A,B。若有多組解,請輸出 A 最⼩的。若仍有多組,請輸出 B 最⼩的。

範例輸入
2
4
5
範例輸出
1 1
1 3
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (100%): 1.0s , <10M
提示 :
  • 第⼀筆範例中,不論 A,B 是多少,N 都會⼀直除以⼆,故直接輸出最⼩的 A,B 即可。
  • 第⼆筆範例中,最短的過程為5 → 8 → 4 → 2 → 1。
標籤:
2014國中組初賽
出處:
NPSC [管理者:
account404 (username)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」