Logical
SRM 113 · 2002-09-10 · by brett1479
Problem Statement
(<Var> or <Var>) and (<Var> or <Var>) and ... and (<Var> or <Var>)<Var> can be a capital letter, or '~'(not) followed by a capital letter. Each "(<Var> or <Var>)" is called a BLOCK. For example:
"(P or P) and (~R or P) and (Q or Q)" is a logical statement with 3 BLOCKs.A logical statement can be MADE TRUE if there is a way of assigning truth values to the capital letters used, such that the entire statement evaluates to true. The previous example can be MADE TRUE since setting P and Q to true, and R to either true or false will make the statement true. Given a logical statement as a String[] of blocks, you will determine the minimum number of blocks that have to be removed such that the statement can be MADE TRUE. For example:
statement = {"P or Q","~P or ~P"}
This corresponds to the statement "(P or Q) and (~P or ~P)".
This statement can already be MADE TRUE so your method would return 0.
statement = {"P or P","~P or ~P"}
This corresponds to the statement "(P or P) and (~P or ~P)".
Removing either block will enable this statement to be MADE TRUE.
Your method would return 1.
Create a class Logical that contains the method howMany, which takes a String[] statement, and returns an int that represents the minimum number of blocks that need to be removed such that the statement can be MADE TRUE.Constraints
- statment must contain between 1 and 10 elements inclusive
- Each element of statement must be of the form(quotes for clarity): " or " where can be either a capital letter ('A'-'Z'), or '~' followed by a capital letter
{"P or P","~R or P","Q or Q"}
Returns: 0
This was one of the examples stated in the problem. The statement can already be MADE TRUE by making P, and Q true and R either false or true.
{"P or Q","~P or ~P"}
Returns: 0
This example was also mentioned in the problem statement. Making P false and Q true will make this statement true thus the statement can be MADE TRUE as is.
{"P or P","~P or ~P"}
Returns: 1
As mentioned in the problem, this statement cannot be MADE TRUE. If we remove either block the statement can be MADE TRUE.
{"P or P","Q or Q","P or P","Q or Q","~P or ~Q","~P or ~Q"}
Returns: 2
This example shows that statements can be duplicated.
{"A or B","B or C","C or D","D or E","A or C","~C or ~C","~A or ~A","~C or ~A"}
Returns: 1
Submissions are judged against all 16 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Logical with a public method int howMany(vector<string> statement) · 16 test cases · 2 s / 256 MB per case