DayAndNight
TCO17 Regional Wildcard · 2017-03-31 · by cgy4ever
Problem Statement
Some of the attractions are related to others, which implies an order in which a visitor should see them. You are given a list of pairs of such attractions. For each valid i, Ciel must visit attraction a[i] before attraction b[i]. It is guaranteed that there is at least one valid order of visiting all the attractions.
Each attraction opens twice a day: once during daytime and once late in the evening. The ticket price for visiting attraction i during daytime is day[i]. The ticket price for visiting attraction i in the evening is night[i]. For each attraction Ciel must choose whether to visit it during daytime or in the evening. These choices then cause her some additional costs, as described below:
- For any two consecutive days k and k+1: If Ciel visits an attraction during daytime on day k and in the evening on day k+1, she has a lot of spare time on day k+1. She will spend it by going shopping. On any day, this costs dayToNight.
- For any two consecutive days k and k+1: If Ciel visits an attraction in the evening on day k and during daytime on day k+1, she will need to drink coffee to wake up early on day k+1. On any day, this costs nightToDay.
- The two equally-long
int[] s a and b that restrict the valid viewing orders. - The
int[] s day and night with n elements each: the ticket prices for daytime and evening visits. - The
int s dayToNight and nightToDay: the extra costs.
Constraints
- n will be between 1 and 50, inclusive.
- a will contain between 0 and 200 elements, inclusive.
- a and b will contain the same number of element, inclusive.
- Each element in a and b will be between 0 and n-1, inclusive.
- For each valid i, a[i] != b[i].
- day and night will contain exactly n elements.
- Each element in day and night will be between 1 and 10,000, inclusive.
- dayToNight and nightToDay will be between 1 and 1,000,000, inclusive.
- There will exist a way to visit all attractions.
{0,1}
{1,2}
{10,100,10}
{100,10,100}
1
2
Returns: 33
There are 3 attractions. We have to visit them in the order 0, 1, 2. Switching from day to night and back is very cheap, so Ciel should simply buy the cheapest tickets and pay the extra costs. More precisely, she should visit attraction 0 during the day, pay 1 for shopping, visit attraction 1 in the evening, pay 2 for coffee, and visit attraction 2 during daytime again. The total cost is 10 + 1 + 10 + 2 + 10 = 33.
{0,1}
{1,2}
{10,100,10}
{100,10,100}
1000000
1000000
Returns: 120
This time the cost of switching is very expensive, so the optimal solution is to visit all attractions during the day.
{}
{}
{1,1000,1000,1,1,1000,1000,1000,1,1,1,1}
{1000,1,1,1000,1000,1,1,1,1000,1000,1000,1000}
100
1000000
Returns: 112
This time there are no constraints for the order. We should first visit each of the attractions 0,3,4,8,9,10,11 during daytime and then each of the remaining attractions in the evening.
{1,0,1,2,3,3}
{0,2,2,3,4,5}
{10,100,23,1000,36,178}
{100,99,25,327,38,124}
11
17
Returns: 633
{0,0,0,0,0}
{1,1,1,1,1}
{1,2}
{3,4}
5
6
Returns: 3
Submissions are judged against all 136 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DayAndNight with a public method int minimalCost(vector<int> a, vector<int> b, vector<int> day, vector<int> night, int dayToNight, int nightToDay) · 136 test cases · 2 s / 256 MB per case