#24719: 一定不會出現需要重複開關同顆燈泡的狀況
yes51851823@gmail.com
(wseds)
學校
:
國立花蓮高級工業職業學校
編號 : 108813
來源 : [114.36.212.168]
最後登入時間 ：
2024-10-17 21:35:26
f651. 開關燈
| From: [111.243.209.119] |
發表日期
:
2021-03-17 19:27
一次最多關掉三顆燈泡 而任何正整數和3取餘的可能情況僅0、1、2三種
若餘數為0則代表燈泡數為3的倍數 此時最佳解大家都知道是N÷3 ____ A
若餘數為2則最佳解狀況是先將第一顆(或最後一顆)燈泡關閉 剩下的燈泡數即是3之倍數 所以最佳解為 ((N-2)÷3)+1 ____ B
若餘數為1則最佳解狀況是先將頭尾的燈泡關閉 則中間的燈泡數必為3的倍數 所以最佳解為 ((N-4)÷3)+2 ____ C
由於int運算時相當於無條件捨去小至整數位 所以B又可簡化為(N÷3)+1 C也可簡化為(N÷3)+1
所以最佳解情況即為 (N÷3)+((N%3)>0)
#25153: Re:一定不會出現需要重複開關同顆燈泡的狀況
hank931012@gmail.com
(ĘŁĪÆÌGĖR VØX)
學校
:
不指定學校
編號 : 143178
來源 : [180.177.88.105]
最後登入時間 ：
2021-11-06 18:16:46
f651. 開關燈
| From: [140.124.8.103] |
發表日期
:
2021-04-24 16:47
一次最多關掉三顆燈泡 而任何正整數和3取餘的可能情況僅0、1、2三種
若餘數為0則代表燈泡數為3的倍數 此時最佳解大家都知道是N÷3 ____ A
若餘數為2則最佳解狀況是先將第一顆(或最後一顆)燈泡關閉 剩下的燈泡數即是3之倍數 所以最佳解為 ((N-2)÷3)+1 ____ B
若餘數為1則最佳解狀況是先將頭尾的燈泡關閉 則中間的燈泡數必為3的倍數 所以最佳解為 ((N-4)÷3)+2 ____ C
由於int運算時相當於無條件捨去小至整數位 所以B又可簡化為(N÷3)+1 C也可簡化為(N÷3)+1
所以最佳解情況即為 (N÷3)+((N%3)>0)
有點小小的疑惑，餘數為2和餘數為1的敘述是否反了?
#29173: Re:一定不會出現需要重複開關同顆燈泡的狀況
ZeroJudge Forum