ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1515. Cashmaster

Cool problem! My method.
Posted by jagatsastry 11 Feb 2008 22:37
Wow. This problem is really cool. Try using the naive method and you're sure to get TLE#26.
Well, my solution(AC 0.234) goes this way:

if the first term is not 1 then the ans is 1.
if the first i terms are 1<<0, 1<<1, 1<<2, ... 1<<(i-1) then all numbers from 1 to (1<<i) - 1 can be expressed as a sum of some of the above terms. Thus if a number k is present all numbers from k to k+((1<<i) - 1) can be skipped. Proceed using this approach.

By the way 1<<i represents pow(2, i).
Re: Cool problem! My method.
Posted by Denis Koshman 18 Jul 2008 16:09
And how do you plan to proceed with this approach? :)
Re: Cool problem! My method.
Posted by Juve45 11 Mar 2017 02:19
how is your algorithm working on this test:
6
1 2 3 6 9 18
Re: Cool problem! My method.
Posted by Didi (OSU11) 11 Oct 2018 20:09
My brain burned in notebook on that algorithm!