/* 2013/2014 University of Chicago
Invitational Programming Contest
Problem ?
Integer Estate Agent
M. K. Furon. 2014-03-14. */
#include
int coins, i, rc, result;
int runsum[1420];
int main (int argc, char *argv[], char *envp[])
{
/* Build the table of minimum sums for a given number of consecutive
houses. These are the sums of integers from 2 to i. */
runsum[1] = 2;
for (i = 2; i < 1420; i++)
runsum[i] = runsum[(i - 1)] + i + 1;
/* Process each coin count in the input. */
while ((scanf ("%d", &coins)) == 1)
{
if ((coins < 0) || (coins > 1000000))
(void) fputs ("Coin input value out of range.\n", stderr);
else if (!coins) /* If zero, end of input */
break;
else if (coins == 1) /* If one, cannot buy anything */
result = 0;
else
{
/* For any given number n of consecutive houses, all possible
sums of n consecutive integers will be the sum of 2 though
(n + 1) plus a multiple of n. Check the possibilities by
subtracting the sums, and as long as the result is not
negative, checking to see if the remainder is a multiple
of n. If it is, increment the count as it is possible to
buy n consecutive houses. */
result = 1; /* Can always buy one house */
for (i = 2; runsum[i] <= coins; i++)
{
if (!((coins - runsum[i]) % i)) /* If even multiple */
result++;
}
}
(void) printf ("%d\n", result);
}
return (0);
}