#45155: 我居然不用遞迴和位元運算過了!?(0.4s, 140KB)


kk20180820@gmail.com (Wayne Yang)

學校 : 國立鳳山高級中學
編號 : 172018
來源 : [27.247.166.142]
最後登入時間 :
2025-02-06 02:14:04
b936. Kevin 愛橘子 -- 有一天Kevin走在路上 | From: [110.30.112.115] | 發表日期 : 2025-01-17 16:17

既然有心想解,請務必有耐心

整體概念就是幫水桶裝水,
當不斷將n加上1時,
加上去的1平均分配給每桶水,
且水桶的數量使得n=m*2^?+??,
同時保有最大值(至少 >= 2^?)。

今已知n為m*2^?+??,
求得? = (n/m最多可以除2幾次),
然後2^?將成為基礎數量(就是已經裝滿到m水量的水桶),
而??的數值會平均再分配給2^?(那些已經裝滿到m水量的水桶)
以這個基礎數量去加上後來又裝滿到2m水量的水桶數量即為答案,
當n=m*2^?+(m*2^? - 2^?)時,
??=(m*2^? - 2^?),
各個水桶即將裝滿到2m,
此時n每每往上加1,
都會再均分出一桶裝滿m水量的水桶,
加1的狀態持續直到n=m*2^(?+1)時停止。
-------------------------
總結,答題流程不使用遞迴,這次也沒用到位元運算bitset,

可以直接用long long p = ( log2(n)-log2(m)+0. 000 000 000 000 001 )取得?是多少,
這裡必須要做到小數點後十五位修正,十分刁鑽!

接著求得2^?的數值,我使用快速冪實作,

最後印出2^? + (?? - 2^?)就大功告成

Fp = 2^?
化簡:Fp + ( n%(m*Fp) - m*Fp ) = Fp-m*Fp+n%(m*Fp)

輸入輸出全部scanf和printf下去,然後記得全部使用long long

引入的標頭檔案:
<stdio.h>用在scanf, printf
<math.h>用在log2(n) - log2(m)

程式架構:
快速冪副函式共7行(外框3行,內碼4行)
主程式共10行(外框3行,內碼7行)

執行結果:(0.4s, 140KB)

期望你也做得到ouob
--------------------------
以下是窮舉推敲的過程
 6 = 3*2^1>>2
 7 = 3*2^1...1>>2
 8 = 3*2^1...2 >>2
 9 = 3*2^1...3>>2
10 = 3*2^1...4 >>2  每桶水皆差1即滿溢到可以再均分為兩桶水,共有2^?桶水,?=1
11 = 3*2^1...5>>3  該階段滿溢開始(第一桶)
12 = 3*2^2>>4  該階段滿溢結束(第2^?桶也是最後一桶,?=1)
13 = 3*2^2...1>>4
14 = 3*2^2...2>>4
15 = 3*2^2...3>>4
16 = 3*2^2...4>>4
17 = 3*2^2...5>>4
18 = 3*2^2...6>>4
19 = 3*2^2...7>>4
20 = 3*2^2...8>>4  每桶水皆差1即滿溢到可以再均分為兩桶水,共有2^?桶水,?=2
21 = 3*2^2...9>>5  該階段滿溢開始(第一桶)
22 = 3*2^2...10>>6
23 = 3*2^2...11>>7
24 = 3*2^3>>8  該階段滿溢結束(第2^?桶也是最後一桶,?=2)
25 = 3*2^3...1>>8
.
.
.

 
ZeroJudge Forum