GogoXReimuHakurai
SRM 530 · 2011-11-22 · by dolphinigle
Problem Statement
Like all other software engineers, Gogo likes to "read" virtual novels. In particular, he's currently "reading" a novel titled Touhou, with Reimu Hakurai as its main protagonist. There are N stages in Touhou, numbered 0 through N-1. A playthrough of the novel always starts at the stage 0. The playthrough then may visit some other stages, based on the player's choices. The sequence of visited stages is always strictly ascending. A playthrough is successful if it terminates by reaching the stage N-1.
In each stage, Gogo can either finish the playthrough or choose one of the available options that advance Reimu to other stages. You are given a
Gogo wants to make as many successful playthroughs as possible, one after another. However, there is an additional constraint: Each playthrough must contain at least one choice Gogo never made in any of the previous playthroughs.
Return the maximum number of successful playthroughs that Gogo can play. If there are no such playthrough, return 0.
Constraints
- choices will contain between 2 and 50 elements, inclusive.
- Each element of choices will contain N characters, where N is the number of elements in choices.
- Each character in choices will be either 'Y', or 'N'.
- If i >= j then choices[i][j] will be 'N'.
{
"NYY",
"NNY",
"NNN"}
Returns: 2
The two possible successful playthroughs: 0 -> 1 -> 2 0 -> 2 Gogo may play them both, in any order.
{
"NYNY",
"NNYY",
"NNNY",
"NNNN"}
Returns: 3
{"NNY"
,"NNY"
,"NNN"}
Returns: 1
{"NYYYY"
,"NNYYY"
,"NNNYY"
,"NNNNY"
,"NNNNN"}
Returns: 7
{"NYNNN"
,"NNYNN"
,"NNNYN"
,"NNNNY"
,"NNNNN"}
Returns: 1
Submissions are judged against all 134 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GogoXReimuHakurai with a public method int solve(vector<string> choices) · 134 test cases · 2 s / 256 MB per case