BallsConverter
Member SRM 489 · 2010-03-12 · by rng_58
Problem Statement
This machine accepts N types of balls. First, Hanako puts some balls into the machine. While the machine contains at least two balls, it chooses two different balls, throws them away, and creates a new ball. The types of the two balls that the machine throws away determine the type of the new ball. If it throws away a type-i ball and a type-j ball, the type of the new ball is described by convert[i][j]. If convert[i][j] is 'A', 'B', ..., 'Z', the type of the new ball is 0, 1, ..., 25, respectively. If convert[i][j] is 'a', 'b', ..., 'x', the type of the new ball is 26, 27, ..., 49, respectively.
If the type of the last ball can be always determined uniquely from the initial configuration of the box (regardless of which balls the machine throws away at each step), it's called a good machine. If the machine is good, return "Good". Otherwise return "Bad".
Constraints
- convert will contain between 1 and 50 elements, inclusive.
- Each element of convert will contain exactly N characters, where N is the number of elements in convert.
- convert[i][j] will be equal to convert[j][i] for all valid i and j.
- Each character in convert will be a letter corresponding to an integer between 0 and N-1, inclusive, where N is the number of elements in convert.
{"AB", "BA"}
Returns: "Good"
The parity of the number of type-1 ball never changes. If the machine contains even number of type-1 balls at first, the last ball will be type-0. If the machine contains odd number of type-1 balls at first, the last ball will be type-1.
{"BA", "AA"}
Returns: "Bad"
For example, if the machine contains one type-0 ball and two type-1 balls, the type of the last ball can't be uniquely determined. If two type-1 balls are chosen in the first operation, the last ball will be type-1. If one type-0 ball and one type-1 ball are chosen in the first operation, the last ball will be type-0.
{"ACB", "CBA", "BAC"}
Returns: "Bad"
{"AAAA", "ABBB", "ABCC", "ABCD"}
Returns: "Good"
{"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcd",
"ACEGIKMOQSUWYacACEGIKMOQSUWYac",
"ADGJMPSVYbADGJMPSVYbADGJMPSVYb",
"AEIMQUYcCGKOSWaAEIMQUYcCGKOSWa",
"AFKPUZAFKPUZAFKPUZAFKPUZAFKPUZ",
"AGMSYAGMSYAGMSYAGMSYAGMSYAGMSY",
"AHOVcFMTaDKRYBIPWdGNUbELSZCJQX",
"AIQYCKSaEMUcGOWAIQYCKSaEMUcGOW",
"AJSbGPYDMVAJSbGPYDMVAJSbGPYDMV",
"AKUAKUAKUAKUAKUAKUAKUAKUAKUAKU",
"ALWDOZGRcJUBMXEPaHSdKVCNYFQbIT",
"AMYGSAMYGSAMYGSAMYGSAMYGSAMYGS",
"ANaJWFSBObKXGTCPcLYHUDQdMZIVER",
"AOcMaKYIWGUESCQAOcMaKYIWGUESCQ",
"APAPAPAPAPAPAPAPAPAPAPAPAPAPAP",
"AQCSEUGWIYKaMcOAQCSEUGWIYKaMcO",
"AREVIZMdQDUHYLcPCTGXKbOBSFWJaN",
"ASGYMASGYMASGYMASGYMASGYMASGYM",
"ATIbQFYNCVKdSHaPEXMBUJcRGZODWL",
"AUKAUKAUKAUKAUKAUKAUKAUKAUKAUK",
"AVMDYPGbSJAVMDYPGbSJAVMDYPGbSJ",
"AWOGcUMEaSKCYQIAWOGcUMEaSKCYQI",
"AXQJCZSLEbUNGdWPIBYRKDaTMFcVOH",
"AYSMGAYSMGAYSMGAYSMGAYSMGAYSMG",
"AZUPKFAZUPKFAZUPKFAZUPKFAZUPKF",
"AaWSOKGCcYUQMIEAaWSOKGCcYUQMIE",
"AbYVSPMJGDAbYVSPMJGDAbYVSPMJGD",
"AcaYWUSQOMKIGECAcaYWUSQOMKIGEC",
"AdcbaZYXWVUTSRQPONMLKJIHGFEDCB"}
Returns: "Good"
Submissions are judged against all 170 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BallsConverter with a public method string theGood(vector<string> convert) · 170 test cases · 2 s / 256 MB per case