Connection Status:
Competition Arena > KindAndCruel

KindAndCruel

TCO11 Qual 2 · 2011-05-07 · by Nickolas

TCO11 Qual 2 · 2011-05-07 · by Nickolas · Graph Theory, Search
Class Name: KindAndCruel
Return Type: int
Method Name: crossTheField
Arg Types: (string, int, int)
Problem Statement

Problem Statement

You are placed at one end of a field represented by a row of cells. Each cell of the field can be one of the following:
  • empty: is always passable (represented by a '.');
  • contains a kind creature (represented by a 'K'): is passable, unless the creature is in a bad mood. This happens if the number of the second at which you enter it is divisible by K;
  • contains a cruel creature (represented by a 'C'): is impassable, unless the creature in in a good mood. This happens if the number of the second at which you enter it is divisible by C.
You start at the leftmost cell of the field. You have to get to the rightmost cell of the field using a minimal number of seconds. Both leftmost and rightmost cells are empty. In one second you can move to a cell which is immediately to the left or to the right of the current cell, or stay where you are. You can not stay in a cell containing kind creature if the number of second is divisible by K, or in a cell containing cruel creature if the number of second is not divisible by C. The seconds are numbered with consecutive integers, starting with 1.
You are given a String field, where each character represents a cell in the field, from left to right. You are also given ints K and C. Return the minimal number of seconds which will bring you to the rightmost cell of the field. If you can't get there, return -1.

Constraints

  • field will contain between 2 and 50 characters, inclusive.
  • Each character in field will be '.', 'K' or 'C'.
  • The first and the last characters of field will be '.'.
  • K and C will be between 1 and 50, inclusive.
Examples
0)
"..."
2
5
Returns: 2

There are no creatures on the field, so you just go two cells to the right in two seconds.

1)
".K.C."
3
4
Returns: 5

At second 1, you move to the cell with the kind creature. At second 2, you move right to the empty cell. At second 3, you wait in the empty cell, because you can't enter the cell with the cruel creature yet. At second 4, the cruel creature is in a good mood and you can enter its cell. Finally, at second 5 you enter the rightmost cell.

2)
".CCCC."
3
5
Returns: -1

You can not pass.

3)
".CCCC."
3
1
Returns: 5

Seemingly cruel creatures are always in good mood, so you can pass easily.

4)
".K."
1
13
Returns: -1

Seemingly kind creature is always in bad mood, so you can not pass.

5)
".."
7
4
Returns: 1

Min test

6)
".C.KKKC.CKK."
4
5
Returns: 28

At most K-1 kind creatures can be in row, and at most 1 cruel, unless C=1

8)
".KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKC."
48
49
Returns: 2353

max test - 2353

9)
".KKKKKKKC..KKKKKKKC..KKKKKKKC..KKKKKKKC..KKKKKKKC."
8
49
Returns: 1961

several tests with series KKKKC repeated

11)
".KKKKKKKKKKKKKKKKKKKKKKC.KKKKKKKKKKKKKKKKKKKKKKC."
23
50
Returns: 2301

2300

12)
".CKKKKKKKKKKKKKKKKKKKKKK..CKKKKKKKKKKKKKKKKKKKKKK."
23
50
Returns: 2323

2323

13)
".CKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK."
48
49
Returns: 2400

better max test - 2400

71)
"....CCCC..........CCCCCCC.CCCCCCCCCCC."
1
1
Returns: 37

a challenge for solution which returns -1 if K=1 without checking whether there are any Ks

72)
"..K.KKKKKK......KKKK...KKKKKK.KKKKK."
7
13
Returns: 41

no Cs

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

Coding Area

Language: C++17 · define a public class KindAndCruel with a public method int crossTheField(string field, int K, int C) · 196 test cases · 2 s / 256 MB per case

Submitting as anonymous