ToolsBox
SRM 453.5 · 2009-11-20 · by andrewzta
SRM 453.5 · 2009-11-20 · by andrewzta · Search
Problem Statement
Problem Statement
You are a carpenter and you want to build several pieces of furniture. Unfortunately, you've lost all your tools. You are given a String[] need, the i-th element of which is a space separated list of the tools required to construct the i-th piece of furniture. Return the number of different tools you must buy to construct all the furniture.
Constraints
- need will contain between 1 and 50 elements, inclusive.
- Each element of need will contain between 1 and 50 characters, inclusive.
- Each element of need will contain only uppercase letters ('A'-'Z') and spaces (' ').
- Each element of need will contain no leading, trailing, or consecutive spaces.
- For each element of need, all tool names in it will be distinct.
Examples
0)
{"SAW HAMMER SCREWDRIVER","SCREWDRIVER HAMMER KNIFE"}
Returns: 4
You need four tools: "SAW", "HAMMER", "SCREWDRIVER" and "KNIFE".
1)
{"SAW"}
Returns: 1
You need only "SAW".
2)
{"SAW","SAW"}
Returns: 1
Now you want to build two furniture items, but you need only "SAW" for both of them.
3)
{"S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S","S"}
Returns: 1
4)
{"L J D G I R X Y Z A K N B O Q E S P F M U V C T W","B P R U G O E F M J Y L H X N Q T I V C S A D W K","T H Z W M J L B A Y R N Q G U P E F X C O K S D V","H T B E C L R F N J M O S Y A K X Q G V W U Z P I","Z D T G P U S Q E F Y J X A M H O N C I R V K W B","R L C N K B G D P U Q W J Y V S A Z E M X F I O H","K V M A R I Q S J L U E H G B C Z Y O W F P N X T","P K N T L H C D B Y W R O M E V J I S G Q Z A U F","T L I Y W D Z A E S K O R B C F M V Q X J N G U H","U W Q E J I O M N L Y R K H F A C Z T D X B V S P","R J S T Z V C A F U Q H L M D E G N P Y O I X W K","X W A F J R I N B Q M L S U P V G O E K T C H Y D","B G T X H N Y R M I Z J A F Q C L S U P O V K E W","I Q X E A C K V S L G O P N Z U H J R M Y D B W F","E X M H B V Z K G Q I D C L J A U P O S W Y F R T","S W I A M L E H F U D X K P J B C G T Y R Z V O Q","C D T E X Z I N O H K L J P V B F W R G Q M A S Y","A G O C W Y K M F X S L T D J U P E H Q N V R I B","N K A W P V E L B Q D O Y F H U R Z M I T X G J S","J C O S V X Z H D N Y Q F T W G K M P I E U A L B","Z N F I K R X Q P H Y M L J A B G D O T S W V E C","Q R G J D K P M S N A I U X Y F Z E H L W C O V T","A P E U F D V B I X J T S R Q O N K Z C Y W H G M","T Z E S R M L B D O W Q I J N Y U X V K C G F P A","J V T M K R W Y G Q D X C L U B E A O H I S N F P","M A F L G Z R N H S W K Y X I U P J C V D Q B O E","C E B F O X Y S Z U I A N V T W H R J L G K D M P","E F G V S Z A D M O P W H R C T Y I Q N K L J U X","R C K G U Q X P S A L B O Y V N I Z W F D E J H T","S E O Z B H D C Y X A U G V Q M K P W R L F J T I","Y S X N U K A F G E W O M L H Z I B T Q V R D P C","U W S X V Y T N L G P E Q K D I O F Z A C M H J R","U C V G L R A I S P Y K F M T D Q W H B E J N Z O","H F T Y O E A J I P K D L M X S C U N B Z G Q R V","F A W E Z V Q U H Y M N X S O L I P T J C R K D B","Q N X C G K E J B Z W U D I A M V O Y F P S T R H","D J P Z W X K V I N S M B Y T C U F A R O E G Q L","G Q O S E F R B T C N K U Z Y W J M X I A H D L P","K Q P C X O E R Z D G B A I N Y L F M U T V J H S","E A L G R I B Q W J Z N O Y K U F T M H D C S V X","G V Q R Y E H D J C Z B N L X P I O M W S F T K U","Q I A J T O U B S R Y D C P F W H M Z V E N G K L","Z P F E A W B O J R S C Y M D I N K V U G H Q T X","Z E Q W U M I G B C D N F L Y A K P X T J V R S H","P Q F Z I Y U E H B N M O G K T R C J D W V L X A","V U C L H D Q K S P N J I F G X B M R Z T A W Y E","U G W K I X A J D O S R N Q F T C Y E V Z B M L P","D U A S W L X C H E F B P O R Q I V Z T N G Y M K","E U Z X R V T C P S L H B D O K Q G A M F W I J N","X G F Y H U D O R Q C N M I W A E J V T L P K B Z"}
Returns: 26
Submissions are judged against all 60 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ToolsBox with a public method int countTools(vector<string> need) · 60 test cases · 2 s / 256 MB per case