Connection Status:
Competition Arena > Trekking

Trekking

SRM 345 · 2007-04-21 · by rusolis

SRM 345 · 2007-04-21 · by rusolis · Simple Search, Iteration, String Manipulation
Class Name: Trekking
Return Type: int
Method Name: findCamps
Arg Types: (string, vector<string>)
Problem Statement

Problem Statement

You are planning a small trek over at the local mountain range. It will involve walking for several days and spending the nights in a tent. The mountains are not very friendly (they're steep and rocky), and therefore many locations are not suitable for setting up a camp. You will be given a String trail which represents the locations in the order in which you are visiting them. trail[i] is '.' if it's possible to camp at the i-th location, and '^' otherwise.

You have several alternative plans to follow, given in the String[] plans. plans[i][j] is lowercase 'w' if according to the i-th plan you are going to walk through location j, and uppercase 'C' if you are going to camp there. A plan is invalid if it involves camping at a location that's not suitable for it.

Given trail and plans return the minimum number of nights that must be spent in the mountains, according to one of the valid plans. If all plans are invalid, return -1

Constraints

  • trail will contain between 2 and 50 characters, inclusive.
  • trail will contain only the characters '.' and '^'.
  • plans will contain between 2 and 50 elements, inclusive.
  • Each element of plans will contain the same number of characters as trail.
  • Each element of plans will contain only the characters 'w' and 'C'.
Examples
0)
"^^....^^^..."
{"CwwCwwCwwCww",
 "wwwCwCwwwCww",
 "wwwwCwwwwCww"}
Returns: 2

The first plan is not valid because it involves camping in the first visited location, which is not suitable for camping. The other two plans are valid, but the third involves only two camps, so it's the best one.

1)
"^^^^"
{"wwww",
 "wwwC"
}
Returns: 0
2)
"^^.^^^^"
{"wwCwwwC",
 "wwwCwww",
 "wCwwwCw"}
Returns: -1
3)
"^^^^....^.^.^."
{"wwwwCwwwwCwCwC",
 "wwwwCwwCwCwwwC",
 "wwwCwwwCwwwCww",
 "wwwwwCwwwCwwwC"}
Returns: 3
4)
".............."
{"CwCwCwCwCwCwCw",
 "CwwCwwCwwCwwCw"}
Returns: 5

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

Coding Area

Language: C++17 · define a public class Trekking with a public method int findCamps(string trail, vector<string> plans) · 66 test cases · 2 s / 256 MB per case

Submitting as anonymous