Teaching
SRM 427 · 2008-11-25 · by rasto6sk
Problem Statement
A language teacher in Antarctica wants his students to be able to read as many words as possible. However, he only has time to teach them K letters. After that, the students will only be able to read words containing only those K letters. Your task is to determine which K letters should be taught to maximize the number of words that the students will be able to read.
The Antarctican language is famous because it only contains words that start with "anta" and end with "tica" (quotes for clarity only). You are given a
Constraints
- words will contain between 1 and 50 elements, inclusive.
- Each element of words will contain between 8 and 15 lowercase letters ('a'-'z').
- Each element of words will start with "anta" and end with "tica" (quotes for clarity).
- All elements of words will be distinct.
- K will be between 0 and 26, inclusive.
{"antarctica","antahellotica","antacartica"}
6
Returns: 2
If you choose the letters a, c, i, n, t and r, students will be able to read the first and last words.
{"antaxxxxxxxtica","antarctica"}
3
Returns: 0
No word in the Antarctican language contains 3 or fewer distinct letters.
{"antabxjeoictica","antacgappsktica","antauayfybjtica","antaortiulctica","antadnjzwzmtica","antaykddorltica","antaiknauajtica","antaejljsmytica","antazqbttdjtica","antaxjinuhvtica","antakdmdvovtica","antaocaimhptica","antapcyxecztica","antaooxdlyytica","antadoqtckatica","antarlzwxtftica","antaigavwbltica","antaclxyuhjtica","antawzygbfetica","antalxnuclktica","antaguiczibtica","antamgxgpyctica","antasjlaqjntica","antavizdwjdtica","antalqeznrstica","antajppuwdrtica","antajrsmijztica","antacafjtmmtica","antazcbcllqtica","antawyvwjoytica","antacuyrzhltica","antaannxdautica","antasuhnjsqtica","antambhtjpftica","antadjvwjugtica","antamgbhuaytica","antafejrpfctica","antafyyowhrtica","antazcqbvjxtica","antaftvflqjtica","antaecmzhketica","antasdbuqkttica","antarrmqoyptica","antafbmfegftica","antaexdffiptica","antadxhftebtica","antattatcantica","antagwegtigtica","antamehquoqtica","antanzowdfutica"}
14
Returns: 7
{"antabtica","antaxtica","antadtica","antaetica","antaftica",
"antagtica","antahtica","antajtica","antaktica"}
8
Returns: 3
{"antadkykntica","antaykghtica","antayytica","antakftica","antaobiwmuptica","antaptghqgtica","antajsotica","antafnttica","antabssvtica","antafdhjqrptica","antapbmtica","antaltica","antauhmgtica","antaogtica","antaeyxtica"}
0
Returns: 0
Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Teaching with a public method int count(vector<string> words, int K) · 77 test cases · 2 s / 256 MB per case