codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1042B.md (2073B)


      1 Source: https://codeforces.com/problemset/problem/1042/B
      2 
      3 B. Vitamins
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Berland shop sells $n$ kinds of juices. Each juice has its price $c_i$. Each juice includes some set of vitamins in it. There are three types of vitamins: vitamin "A", vitamin "B" and vitamin "C". Each juice can contain one, two or all three types of vitamins in it.
     22 
     23 Petya knows that he needs all three types of vitamins to stay healthy. What is the minimum total price of juices that Petya has to buy to obtain all three vitamins? Petya obtains some vitamin if he buys at least one juice containing it and drinks it.
     24 
     25 Input
     26 
     27 The first line contains a single integer $n$ $(1 \le n \le 1\,000)$ — the number of juices.
     28 
     29 Each of the next $n$ lines contains an integer $c_i$ $(1 \le c_i \le 100\,000)$ and a string $s_i$ — the price of the $i$-th juice and the vitamins it contains. String $s_i$ contains from $1$ to $3$ characters, and the only possible characters are "A", "B" and "C". It is guaranteed that each letter appears no more than once in each string $s_i$. The order of letters in strings $s_i$ is arbitrary.
     30 
     31 Output
     32 
     33 Print -1 if there is no way to obtain all three vitamins. Otherwise print the minimum total price of juices that Petya has to buy to obtain all three vitamins.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 4  
     41 5 C  
     42 6 B  
     43 16 BAC  
     44 4 A
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 15
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 2  
     57 10 AB  
     58 15 BA
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 -1
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 5  
     71 10 A  
     72 9 BC  
     73 11 CA  
     74 4 A  
     75 5 B
     76 ```
     77 
     78 Output
     79 
     80 ```
     81 13
     82 ```
     83 
     84 Input
     85 
     86 ```
     87 6  
     88 100 A  
     89 355 BCA  
     90 150 BC  
     91 160 AC  
     92 180 B  
     93 190 CA
     94 ```
     95 
     96 Output
     97 
     98 ```
     99 250
    100 ```
    101 
    102 Input
    103 
    104 ```
    105 2  
    106 5 BA  
    107 11 CB
    108 ```
    109 
    110 Output
    111 
    112 ```
    113 16
    114 ```
    115 
    116 Note
    117 
    118 In the first example Petya buys the first, the second and the fourth juice. He spends $5 + 6 + 4 = 15$ and obtains all three vitamins. He can also buy just the third juice and obtain three vitamins, but its cost is $16$, which isn't optimal.
    119 
    120 In the second example Petya can't obtain all three vitamins, as no juice contains vitamin "C".