ECOO '16 R3 P3 - CamelCase

View as PDF
Submit solution
Points: 10 (partial)
Time limit: 2.5s
Python 7.0s
Memory limit: 64M
Python 128M
Problem type

Many programmers use CamelCase when naming variables, functions, classes and other entities. In CamelCase, when a name consists of multiple words concatenated together, such as myawesomevariablename, the first letter of every distinct word is capitalized. Sometimes there is more than one way to turn a string of letters into CamelCase.

Lower Upper
CamelCase myAwesomeVariableName MyAwesomeVariableName

In Lower CamelCase the first word is the only word not capitalized, whereas in Upper CamelCase all of the words are capitalized.

The input will contain a dictionary, followed by 10 test cases.

The dictionary starts with an integer N where (1 \le N \le 2 \times 10^5) followed by N lines, each containing a word.
A word consists of a string of lowercase English letters and the apostrophe character ' (ASCII 39).

Each of the 10 lines following the dictionary will contain a single test case. Each test case consists of a string of lowercase English letters of length 2000 or less, created by concatenating words from the dictionary.

Your program should output 10 integers (one per line), representing the minimum number of capitalizations required to convert each test word to Lower CamelCase, so that it can be read as a string of legal words from the dictionary.

Note that the sample input below contains only 4 test cases, but the real data files will contain 10.

Sample Input

26
aid
all
app
apple
brown
come
country
crab
crabapple
dogs
for
fox
good
is
jumps
lazy
men
now
of
orchard
over
quick
the
their
time
to
apple
appleorchard
crabapple
thequickbrownfoxjumpsoverthelazydogs

Sample Output

0
1
0
8

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org

Comments


  • 0
    Plasmatic  commented on June 17, 2019, 3:49 a.m. ← edited

    \mathcal{O}(N^3) ACs


  • 1
    aeternalis1  commented on Aug. 11, 2017, 4:27 a.m.

    I'm just wondering, but when ECOO questions are graded, is there a difference between receiving a row of checkmarks or a row of O's for each test case?


    • 1
      wleung_bvg  commented on Aug. 11, 2017, 5:40 a.m.

      They both mean the same thing.


  • 1
    Phoenix1369  commented on May 1, 2017, 5:22 a.m.

    With the influx of recent submissions, it figures the judge should grade this problem in a manner more reflective of judges during the actual ECOO competition. All submissions have been rejudged.

    Additional feedback for individual cases can be found on the submission page.


    • 2
      P234rex  commented on May 1, 2017, 12:53 p.m.

      What does the line of Os mean on the AC submissions?


  • 20
    P234rex  commented on March 15, 2017, 7:45 p.m. ← edit 5

    That sweet moment when the fastest submission is in Python (I'm counting the days that this lasts) (2017/03/15 - 2017/03/16) (RIP) Back on top baby (2017/04/10-2017/05/01)rip rejudging For the Glory of Python