In the problem Loan Repayment, there is potentially a faster way to check if an integer is viable (in theoretical time) thus speeding up the entire solution from to . After some brief googling, I couldn't find anyone who has posted about this method yet.

However, I couldn't quite get my solution to work and was wondering if someone would be willing to help out or let me know if this is a dead end.

So here's my process. Each day, Farmer John gives Bessie a certain amount of milk:

There's one problem with the process above, of course, and that is that the equations don't round down automatically. I'll come back to this later.

Looking at the pattern of the equations over a number of days, it can be deducted that each equation is a different layer of Pascal's triangle. From then, the equation of milk given each day can actually be factorised into a binomial with the use of the Binomial theorem.

For instance, let's look at Day 4:

So in summary:

Thus the general equation for the amount of milk given on a given day is:

At this point, the equation above can be rearranged to work out the number of days which Farmer John will give Bessie more than gallons of milk.

Then I can simply sum up the amount of milk that Bessie has been given from Day 1 to Day inclusive ( is floored) with the use of the equation for the sum of a Geometric series:

Finally, we can simply add on the remaining days () multipled by , and check if it is larger than .

Here is my code of the check function (, and are global variables):

However, there is a flaw with this method: it's not accurate enough. It's close, but not quite.

For example, if is and is (one of the actual test cases on USACO), when using the equation , the calculations can deviate from the actual amount of milk given on a day by less than (both positive and negative) because math (to my knowledge) cannot round down numbers. The first ten thousand digits and deviations can be viewed in this spreadsheet (Column B are the actual values, Column C are the values calculated with the formula and Column D are the differences between Column B and C). Because of the deviations (which can add up), I can't get this method to work.

I know this is a long shot, but if someone can let me know how to fix the inaccuracy issues, that would be amazing.

Bruce