The divisor conquers
Time limit8sMemory limit512 MB
Place the N cards one at a time so each new card divides the sum of the cards already down, and print the lexicographically smallest winning order or No.
- Level
Medium7 of 10
- Topics
- Backtracking, Greedy, Math, Dynamic programming
- Solved
- No attempts yet
Problem
"Divisor is the Conquerer" is a solitaire card game. The rules follow.
First, draw cards from a deck. The game uses only the drawn cards, and the rest of the deck stays out of play.
Then put the cards down on the table one at a time. The first card can be any of them. After that you may put down only a card that conquers the cards already on the table. A card conquers a set of cards when the number on the card divides the sum of the numbers in the set. For example, card conquers the set , but card does not conquer the set .
You win once all drawn cards are on the table. You lose if at some point no card can be put down.
Input
The input holds several test cases.
Each test case is two lines. The first line has the number of cards (). The second line has the numbers on the cards, (), separated by spaces. Within one test case at most four cards carry the same number.
A in place of ends the input.
Output
Print one line for each test case.
If a winning order exists, print the order the cards are put down as integers separated by single spaces. When several winning orders exist, print only the lexicographically smallest one. For two sequences and of the same length, is lexicographically smaller than if at the smallest index with .
If no winning order exists, print No.