algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

problem.txt (1494B)


      1 # Problem
      2 
      3 A. Boredom
      4 time limit per test
      5 1 second
      6 memory limit per test
      7 256 megabytes
      8 
      9 Alex doesn't like boredom. That's why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it.
     10 
     11 Given a sequence a consisting of n integers. The player can make several steps. In a single step he can choose an element of the sequence (let's denote it ak) and delete it, at that all elements equal to ak + 1 and ak - 1 also must be deleted from the sequence. That step brings ak points to the player.
     12 
     13 Alex is a perfectionist, so he decided to get as many points as possible. Help him.
     14 Input
     15 
     16 The first line contains integer n (1 ≤ n ≤ 105) that shows how many numbers are in Alex's sequence.
     17 
     18 The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 105).
     19 
     20 ---
     21 
     22 # Constraints
     23 
     24 - step
     25     - choose an element of the sequence
     26     - delete it
     27     - delete all elements with n-1 or n+1 values where n was the value of the deleted element
     28     - player then gets n points
     29 
     30 - perform as many steps as needed, score the most points
     31 
     32 ---
     33 
     34 # Thoughts
     35 
     36 - can we just sort the collection and iterate in reverse over it?
     37 	- this would be an greedy approach
     38 	- this breaks down when we have multiple instances of the same number 
     39 - hmm, would we have to do the dp version of this?
     40 
     41 ---
     42 
     43 # Examples
     44 
     45 2
     46 1 2
     47 
     48 take 2 because it's the largest value
     49 
     50 
     51 3
     52 1 2 3
     53 
     54 Take 3, take 2
     55 
     56 9
     57 1 2 1 3 2 2 2 2 3
     58 
     59 leave 3, take 2
     60 
     61 2 * 5 = 10