Connection Status:
Competition Arena > Anonymous

Anonymous

SRM 133 · 2003-02-05 · by Yarin

SRM 133 · 2003-02-05 · by Yarin
Class Name: Anonymous
Return Type: int
Method Name: howMany
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

If you want to write a message anonymously, one way to do it is to cut out letters from headlines in a newspaper and paste them onto a blank piece of paper to form the message you want to write. Given several headlines that you have cut out, determine how many messages from a list you can write using the letters from the headlines. You should only consider each message by itself and not in conjunction with the others, see example 2.

Create a class Anonymous which contains the method howMany which takes as parameters a String[] headlines containing the headlines which you have cut out as well as a String[] messages with the messages you may want to write, and returns an int which is the total number of messages you can write.

Notes

  • All letters that you cut out can be used both as upper or lower case in a message.
  • Spaces should be ignored in elements in both headlines and messages.

Constraints

  • headlines will contain between 1 and 50 elements, inclusive.
  • messages will contain between 1 and 50 elements, inclusive.
  • The length of each element in headlines will be between 1 and 50 characters, inclusive.
  • The length of each element in messages will be between 1 and 50 characters, inclusive.
  • Each element in headlines will only contain the letters 'A'-'Z', 'a'-'z' and space.
  • Each element in messages will only contain the letters 'A'-'Z', 'a'-'z' and space.
Examples
0)
{"Earthquake in San Francisco",
 "Burglary at musuem in Sweden",
 "Poverty"}
{"Give me my money back",
 "I am the best coder",
 "TOPCODER"}
Returns: 2

In the first message we have three 'm's, but there are only two 'm's among the headlines (both in the word "museum"), so this message can't be written. The second message can be written. Note that the first letter, 'I', only appears as lower case in the headlines, but that's allowed. The last message can also be written, so the method should return 2.

1)
{"Programming is fun"}
{"program","programmer","gaming","sing","NO FUN"}
Returns: 4

The messages "program", "gaming", "sing" and "NO FUN" can all be written but not "programmer" (no 'e's exist). The method should return 4.

2)
{"abcdef","abcdef"}
{"AaBbCc","aabbbcc","   ","FADE"}
Returns: 3

All messages except the second one can be written, because it contains three 'b's but there are only two 'b's available. Also note the message only containing spaces - such a message can of course always be written.

3)
{"WHKC OHA It","OHWMU","z YlGclDUwMOtr jKNhbTDHCmGhkLFFYoF AjrG","vuV qWGMQ  syoj ","kN elIL l ABxeurth OvS  oAPN","V  XpaNz cKtiSZQ"}
{"HScumeBpvpnGFTPBRQ   YeOtcS","MYFF XcuK MvpvcTHCJTGh pnrY AWmZJj nkjuIrMBqa"," ","xlvNmjRCddJ dXC g  af EcO Namx","Fk czwxl ak","ek N  LdEz  AXAaq FepDw bjiZfDkjo pb A TL n","oxM f n zQfKcelOUIYvfIO CHPxS xpV SKcxdyt BMkr","MfXAPWjXfnCKIO detaavE g KUyyGqnmPZtY","VO"," UJB nf","BXkENvf rKjkW","uCVl SO ","L vyx QAxvJ fZlrf yIuMC Uc WiHJqZCmhGv ","vmVn","SI","wiEue lFMn uDUbZ  wrQbovB oHPnO b wdkESINM tCpG","vAN","E AW  empNWpnaNgKxapPfxbxN","uTIbu","Xh lVjLryDgAzqQePQrIeuNaZb eaVz iZw j ","YwdYyke dcvZhdD GI"," LKEchcYdN WkaOiLjYjI X  g","DclQfiPt i pBEQJZRguasyrcYw qMabMN OhYxr","DLuScSdImbd GePaNpvYuYmXaR ","NHJQL iHIrqKifmVkG SrwrSi ek wkOl gPlHBCX ItqQiI","qSnmQ  mhGDu","dIrXHOLbBa","b  fLPkXpt nSM K  qhq rvvwJjkajIjBxl qG","PsEdbFytHRNFjgp    HHmVsVMr Qb MkMu","kGvJV YZFs p","L uTIw xenCFzUlWT ScwDWFckPaxR on TiR","L HVOFyEUrN W pGQb","AxpHA  Z  p","DC Isy yfeZHqP WJ pAASd HQMQBfc jQbK G tjsM RMsA"}
Returns: 21
4)
{"hOXun Kpa txIt M  MmNGCPp  nMOSOmBHanadYOdEBbr","drVSdHggN Xwpsj LSz","dvHNdIDKLOlY xONhlciTBVSct TIQ Hkl vht XE","ATxIhJdi tOiXetJn lLqGzxB fXIqxKhrJgempIkON","jTEbpVi wAOamtup"}
{"XpJFQq   UfhOtK aXDI  yNViq","gtCo"," W   s","LD","hz UlaIidJdzDhl"," MXUhVept   WoRNX","b   M  ","zQHLT NqTzXLWHpY QX","vZsCUuHkUNMjwlwrt","BTfwAtP A aU sMAjwumJe HJuS c M","wLmRwUyKczTgwOlysT tBWp HefEsQtFpnffhgkZO","hwbw T Ngw u","cz isifBo emVAaIWzzeR ULgh "," qR VbGRE  TkvN   spR gaP yWoL","SppZOCR  S  iExLBQHgORwTyGybc AZ CFtQ k wto","nXBqHyDjNPfkQFh","dUR rxYLv","k XFuYU xkdC","damjr upwUsJB SjHyrdo SAjSgK TvG C  nkKDUiLBaxX","B aYoXtpbrDzaeVNxRV","YCybOZqJwJ SakCR","G krMyJXldfinetRLusqfywnrCVUqykcHIl kkjv d"," JJHwNEpVAAdlEa","O rKuvKwA WOQX Jdn  p DVLcNAGGMsHXwfn ","hakQ NZkjl i zrrsIHBBCqlRmYiq wOc ","  wDtU YyRJ","KJUdTDN U  ZovUgTJbnIna","BCvBjmetHULkws VLfWHip "," BTza vDwJFqfPL xP aeg","PwPW yKHSFjYGTZ","iZcgQb  aVcMXTl KAY WtQ  WQ"," hWkZIorUcAA  MHDe vwlOB PWGi gjrlnuppwa j","xDDK   RR dvw Jy b VaLFVtztgBNeCQRFcTA QBrZzSqG z","xChsHSP fZvpXrb ONxCPItfcRmxJAHHumIN vTo P tLD o","zuOghBCGLD QfRTH","zJvD EbCMKkpKtblYt veYjnzA","b gF KkbXOFXpkrUm r XeoXyuPxZCgm","ilDMGGAWWgd"," AkT k GIMwTLBzN uitlIiwVJhty smrp CAQ lYLXogYL","lo "}
Returns: 23

Submissions are judged against all 30 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Anonymous with a public method int howMany(vector<string> headlines, vector<string> messages) · 30 test cases · 2 s / 256 MB per case

Submitting as anonymous