← CSES Better

Minimize Light Changes to Display a Larger Number

ZIO · 2025 · Zonal Informatics Olympiad · P1

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

digits · dynamic-programming · greedy

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

state transition

Track whether the prefix is already larger

At each display, choose a digit and pay the number of lights that change; the final fixed-width number must exceed X.

State table
Prefix stateNext digit dCost / next state
equald >= input_isegmentDiff(input_i,d)
greaterany dsegmentDiff(input_i,d)
endgreater onlyminimum total cost
  1. 1

    Compare one position

    A chosen digit smaller than X is allowed only after an earlier position made the output larger.
  2. 2

    Pay the light cost

    For each digit pair, the cost is the count of differing light positions in their seven-segment patterns.
  3. 3

    Keep two states

    Dynamic programming stores the minimum cost for an equal prefix and for a prefix already greater; accept only the greater state at the end.
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.