EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
ICPC 2008
ICPC 2008

B. Always an Integer

Input file: always.in Combinatorics is a branch of mathematics chiefly concerned with counting discrete objects. For instance, how many ways can you pick two people out of a crowd of n people? Into how many regions can you divide a circular disk by connecti...

Updated May 21, 2026
Track ICPC
Year 2008
Statement Text + PDF
TeXC++Statement textStatement PDF
Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF
Input file always.in

Combinatorics is a branch of mathematics chiefly concerned with counting discrete objects. For instance, how many ways can you pick two people out of a crowd of n people? Into how many regions can you divide a circular disk by connecting n points on its boundary with one another? How many cubes are in a pyramid with square layers ranging from 1 × 1 to n × n cubes?

Figure 1: If we connect six points on the boundary of a circle, at
most 31 regions are created.

Many questions like these have answers that can be reduced to simple polynomials in n. The answer to the first question above is n(n-1)/2, or (n^2-n)/2. The answer to the second is (n^4-6n^3+23n^2-18n+24)/24. The answer to the third is n(n+1)(2n+1)/6, or (2n^3+3n^2+n)/6. We write these polynomials in a standard form, as a polynomial with integer coefficients divided by a positive integer denominator.

These polynomials are answers to questions that can have integer answers only. But since they have fractional coefficients, they look as if they could produce non-integer results! Of course, evaluating these particular polynomials on a positive integer always results in an integer. For other polynomials of similar form, this is not necessarily true. It can be hard to tell the two cases apart. So that, naturally, is your task.

Input

The input consists of multiple test cases, each on a separate line. Each test case is an expression in the form (P)/D, where P is a polynomial with integer coefficients and D is a positive integer denominator. P is a sum of terms of the form Cn^E, where the coefficient C and the exponent E satisfy the following conditions:

  1. E is an integer satisfying 0 ≤ E ≤ 100. If E is 0, then Cn^E is expressed as C. If E is 1, then Cn^E is expressed as Cn, unless C is 1 or -1. In those instances, Cn^E is expressed as n or -n.
  2. C is an integer. If C is 1 or -1 and E is not 0 or 1, then the Cn^E will appear as n^E or -n^E.
  3. Only non-negative C values that are not part of the first term in the polynomial are preceded by +.
  4. Exponents in consecutive terms are strictly decreasing.
  5. C and D fit in a 32-bit signed integer.

See the sample input for details.

Input is terminated by a line containing a single period.

Output

For each test case, print the case number (starting with 1). Then print Always an integer if the test case

polynomial evaluates to an integer for every positive integer n. Print Not always an integer otherwise. Print

the output for separate test cases on separate lines. Your output should follow the same format as the sample output.

Sample Tests

Sample
Sample Input 
(n^2-n)/2
(2n^3+3n^2+n)/6
(-n^14-11n+1)/3
.
Sample Output 
Case 1: Always an integer
Case 2: Always an integer
Case 3: Not always an integer
Editorial

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

  • Write the structural observations that make the problem tractable.

  • State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.

  • If the constraints matter, explain exactly which part of the solution they enable.

Algorithm

  1. Describe the data structures and the state maintained by the algorithm.

  2. Explain the processing order and why it is sufficient.

  3. Mention corner cases explicitly if they affect the implementation.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

State the first key claim.

Proof.

Provide a concise proof.

Lemma 2.

State the next claim if needed.

Proof.

Provide a concise proof.

Theorem.

The algorithm outputs the correct answer for every valid input.

Proof.

Combine the lemmas and finish the argument.

Complexity Analysis

State the running time and memory usage in terms of the input size.

Implementation Notes

  • Mention any non-obvious implementation detail that is easy to get wrong.

  • Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.

Implementation

Code

C++ solution used for this page.

C++

Clean code view with a raw-file link when you want the original source.

Raw file 
#include <bits/stdc++.h>
using namespace std;

namespace {

void solve() {
    // Fill in the full solution logic for the problem here.
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
TeX write-upcompetitive_programming/icpc/2008/B-always-an-integer/solution.texC++ implementationcompetitive_programming/icpc/2008/B-always-an-integer/solution.cppStatement textcompetitive_programming/icpc/2008/B-always-an-integer/statement.txtStatement PDFcompetitive_programming/icpc/2008/B-always-an-integer/statement.pdfMetadatacompetitive_programming/icpc/2008/B-always-an-integer/meta.jsonYear packetcompetitive_programming/icpc/2008/contest_problems.pdf