AlgoLensArena
ContestlərProblemlərOtaqlar
Vizualizator
← Məsələlər

BAPC25-082.Boggle Sort

Medium · 1 s · 256 MB

  • icpc
  • bapc
  • 2025

It is the 25th of February, 2025. You have enjoyed another spirited evening of Boggle with your friends. After everybody left, you have thoroughly cleaned the apartment. All that is left is to bring the Boggle tray in order. You start to wonder: would it be possible to bring the Boggle tray in alphabetic order, without swapping any dice, but only by rotating them?

The Boggle tray consists of 161616 six-sided dice. Each die is labelled with a letter from the English alphabet on each face. A single die contains a face labelled “Qu”. No letter appears 444 or more times on the same die. By turning a die once, you can move any of the sideways-facing letters up. Turning a die twice moves the downwards-facing letter up.

Bring the tray into alphabetically nondecreasing order, using standard reading directions (left-to-right, top-to-bottom), using as few turns as possible. Letter case plays no role and the two-letter face is treated as “Q” followed by “U”, so “QuU” is sorted but “QuT” is not.

Giriş formatı

The input consists of:

• One line with 161616 letters, describing the currently upwards-facing faces of each die.

• Four lines with 161616 letters, describing the currently sideways-facing faces of each die.

• One line with 161616 letters, describing the downwards-facing faces of each die.

In each line, the iiith letter describes the iiith die for 1≤i≤161\leq i\leq 161≤i≤16.

All letters are English uppercase letters (A-Z).

The letter “Q” stands for the two-letter face “Qu” and appears exactly once in the input.

No letter appears 444 or more times on the same die.

Çıxış formatı

If it is possible to bring the tops of the dice into alphabetic order, output the minimum number of turns needed to do so. Otherwise, output “impossible”.

Qeyd

Source: Benelux Algorithm Programming Contest 2025 · Author: Thore Husfeldt · License: CC BY-SA 4.0 · Original: https://bapc.eu · Statement adapted for AlgoLens and shared under the same license.

Nümunələr

Giriş #1

IAZEEOXSPACKYIGF
APDSSAOHEQAOGGLY
LCERNRFILJINEEWE
BDVLOMRESBATLTRI
TEAAWSINUOOUKVIH
YMNCDHBPTMTDUNUE

Çıxış #1

15

Giriş #2

EXFETDMNMGDBRSRM
TIEGINOVRETACNUA
PRYKASAEATNTSHID
SOHUOEJDHVKYLPLC
UFIYAWBZONUIEIWE
LBELCOQASIOLAEGP

Çıxış #2

impossible