Connection Status:
Competition Arena > SRMCards

SRMCards

SRM 500 · 2010-11-01 · by Chmel_Tolstiy

SRM 500 · 2010-11-01 · by Chmel_Tolstiy · Dynamic Programming, Greedy
Class Name: SRMCards
Return Type: int
Method Name: maxTurns
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Dmitry likes TopCoder Single Round Matches. Once, he registered for an SRM and was waiting for the coding phase to begin. To entertain himself while waiting, he decided to play the following game.

He makes a pile of cards, and on each card, he writes the number of an SRM in which he has competed. No two cards contain the same number. He then takes turns until the pile is empty. Each turn consists of the following sequence of actions:
  • Dmitry chooses an arbitrary card from the pile. Let A be the number written on this card.
  • The card with number A is removed from the pile.
  • If the pile contains a card with number A-1, that card is removed from the pile.
  • If the pile contains a card with number A+1, that card is removed from the pile.
The game is finished when the pile becomes empty. It's fun to play the game, so Dmitry wants to spend as much time as possible playing it.

You are given a int[] cards containing the numbers written on the cards in the pile before the start of the game. Return the largest possible number of turns in which Dmitry can finish the game.

Constraints

  • cards will contain between 1 and 50 elements, inclusive.
  • Each element of cards will be between 1 and 499, inclusive.
  • All elements of cards will be distinct.
Examples
0)
{498, 499}
Returns: 1

In the first turn, Dmitry can choose A = 498 or A = 499. In any of these cases both cards will be removed from the pile and the game will be finished.

1)
{491, 492, 495, 497, 498, 499}
Returns: 4

One out of many possible ways to spend 4 turns playing this game is to choose the following numbers in each turn: 497, 499, 495, 492.

2)
{1}
Returns: 1
3)
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Returns: 5
4)
{2, 4, 6, 8, 10}
Returns: 5
7)
{11, 12, 102, 13, 100, 101, 99, 9, 8, 1}
Returns: 6

Note that the elements of cards are not necessarily sorted in ascending order.

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

Coding Area

Language: C++17 · define a public class SRMCards with a public method int maxTurns(vector<int> cards) · 82 test cases · 2 s / 256 MB per case

Submitting as anonymous