ﻣﺎﻫﺎﻥ ﺑﺮﺍﯼ ﺁﯾﻨﺪهی ﺧﻮﺩ ﺑﺮﻧﺎﻣﻪﺭﯾﺰﯼ ﺍﻗﺘﺼﺎﺩﯼ ﮐﺮﺩﻩ ﺍﺳﺖ ﻭ ﺍﮐﻨﻮﻥ ﻣﯽﺩﺍﻧﺪ ﺩﺭ ﻫﺮ ﯾﮏ ﺍﺯ $n$ ﺭﻭﺯ ﺁﯾﻨﺪﻩ، ﭼﻪ ﻣﻘﺪﺍﺭ ﭘﻮﻝ ﺍﺣﺘﯿﺎﺝ ﺩﺍﺭﺩ. ﺍﻭ ﻣﯽﺧﻮﺍﻫﺪ ﻣﺨﺎﺭﺝ ﻫﺮ ﺭﻭﺯﺵ ﺭﺍ، ﺻﺒﺢ ﺁﻥ ﺭﻭﺯ ﺍﺯ ﭘﺪﺭ ﻭ ﯾﺎ ﻣﺎﺩﺭﺵ ﺑﻪ ﻋﻨﻮﺍﻥ ﭘﻮﻝ ﺗﻮﺟﯿﺒﯽ ﺑﮕﯿﺮﺩ. ﻣﺎﻫﺎﻥ ﺩﻧﺒﺎﻟﻪﺍﯼ ﺑﻪ ﻃﻮﻝ $n$ ﺍﺯ ﻣﻘﺪﺍﺭ ﭘﻮﻟﻬﺎﯾﯽ ﮐﻪ ﻣﯽﺧﻮﺍﻫﺪ ﺩﺭ ﺭﻭﺯﻫﺎﯼ ﺁﯾﻨﺪﻩ ﺑﺪﺳﺖ ﺁﻭﺭﺩ، ﺗﺸﮑﯿﻞ ﺩﺍﺩﻩ ﺍﺳﺖ ﮐﻪ ﺑﻪ ﺁﻥ «دنبالهی ﻣﺎﻫﺎﻥ» ﻣﯽﮔﻮﯾﯿﻢ.
ﻫﺮ ﯾﮏ ﺍﺯ ﻭﺍﻟﺪﯾﻦ ﻣﺎﻫﺎﻥ ﻣﺴﺘﻘﻼً ﻣﯿﺰﺍﻥ ﭘﻮﻝ ﺗﻮﺟﯿﺒﯽﻫﺎﯾﯽ ﮐﻪ ﻣﺎﻫﺎﻥ ﺍﺯ ﺍﻭ ﻣﯽﮔﯿﺮﺩ ﺭﺍ ﺑﻪ ﺻﻮﺭﺕ ﺩﻧﺒﺎﻟﻪﺍﯼ ﺍﺯ ﺍﻋﺪﺍﺩ ﺛﺒﺖ ﻣﯽﮐﻨﺪ. ﻫﯿﭻ ﯾﮏ ﺍﺯ ﺁنها ﺩﻭﺳﺖ ﻧﺪﺍﺭﺩ ﻣﻘﺪﺍﺭ ﭘﻮﻟﯽ ﮐﻪ ﻣﺎﻫﺎﻥ ﺍﺯ ﺍﻭ ﻣﯽﮔﯿﺮﺩ ﺩﺭ ﻣﺮﻭﺭ ﺯﻣﺎﻥ ﺭﻭﻧﺪﯼ ﺻﻌﻮﺩﯼ ﺩﺍﺷﺘﻪ ﺑﺎﺷﺪ. ﺑﻪ ﻫﻤﯿﻦ ﺩﻟﯿﻞ ﻭﺍﻟﺪﯾﻦ، ﻃﻮﻝ ﺑﻠﻨﺪﺗﺮﯾﻦ زیردنبالهی ﺻﻌﻮﺩﯼ ﺩﺭ ﺩﻧﺒﺎﻟﻪﯼ ﺧﻮﺩ ﺭﺍ ﻣﺤﺎﺳﺒﻪ ﻣﯽﮐﻨﻨﺪ. ﺩﻭ ﻋﺪﺩ ﺑﻪ ﺩﺳﺖ ﺁﻣﺪﻩ ﺭﺍ «ﻋﺪﺩ ﭘﺪﺭ» ﻭ «ﻋﺪﺩ ﻣﺎﺩﺭ» ﻣﯽﮔﻮﯾﯿﻢ. ﺗﻮﺟﻪ ﮐﻨﯿﺪ ﮐﻪ ﺩﻧﺒﺎﻟﻪﺍﯼ ﺻﻌﻮﺩﯼ، ﻣﯽﺗﻮﺍﻧﺪ ﻋﻨﺎﺻﺮ ﺗﮑﺮﺍﺭﯼ ﻧﯿﺰ ﺩﺍﺷﺘﻪ ﺑﺎﺷﺪ.
ﻣﺎﻫﺎﻥ ﺩﻭﺳﺖ ﺩﺍﺭﺩ «ﻋﺪﺩ ﭘﺪﺭ» ﻭ «ﻋﺪﺩ ﻣﺎﺩﺭ» ﺭﺍ ﮐﻢ ﮐﻨﺪ. ﺍﻭ ﺑﻪ ﺳﺮﻋﺖ ﻓﻬﻤﯿﺪ ﻣﯽﺗﻮﺍﻧﺪ ﮐﺎﺭﯼ ﮐﻨﺪ ﮐﻪ ﻫﺮ ﺩﻭﯼ ﺍﯾﻦ ﺍﻋﺪﺍﺩ ﺍﺯ $\lceil \frac{L}{2} \rceil$ بیشتر ﻧﺸﻮﺩ ﮐﻪ $L$، ﻃﻮﻝ ﺑﻠﻨﺪﺗﺮﯾﻦ ﺯﯾﺮﺩنبالهی صعودی دنبالهی ماهان است.
ﺑﻪ ﻣﺎﻫﺎﻥ ﺩﺭ ﺍﻧﺘﺨﺎﺏ ﭘﺪﺭ ﯾﺎ ﻣﺎﺩﺭ، ﺑﺮﺍﯼ ﮔﺮﻓﺘﻦ ﭘﻮﻝﺗﻮﺟﯿﺒﯽ ﺩﺭ ﻫﺮ ﯾﮏ ﺍﺯ $n$ روز پیش رو، کمک کنید. دقت کنید که عدد پدر و عدد مادر نباید از $\lceil \frac{L}{2} \rceil$ بیشتر شود.
ﺑﺮﻧﺎﻣﻪﺍﯼ ﺑﻨﻮﯾﺴﯿﺪ ﮐﻪ: