/* 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); }