← CSES Better

Count Digit Strings with Alternating Trends

ZIO · 2025 · Zonal Informatics Olympiad · P2

Open official problem ↗
Ask AI

Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.

Open Claude Desktop

strings · dynamic-programming · counting

The organizer’s problem statement is available at the official source link.

sequence

Adjacent comparisons cannot keep turning the same way

With equal neighbors forbidden, every triple must avoid being strictly increasing or strictly decreasing.

digit_i < digit_(i+1) -> upup -> downdown -> up
  1. 1

    Record each step

    Each neighboring pair contributes an up or down direction because equal digits are disallowed.
  2. 2

    Reject repeated direction

    Two consecutive ups make an increasing triple; two consecutive downs make a decreasing triple.
  3. 3

    Count valid extensions

    Build strings by last digit and previous direction, summing counts modulo 997.
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|12 lines, 156 chars

Run output

Run your code to see output.