CandleTimerEasy
SRM 638 · 2014-08-25 · by cgy4ever
SRM 638 · 2014-08-25 · by cgy4ever · Brute Force
Problem Statement
Problem Statement
You have a lot of candles.
The candles burn at a uniform rate: if you ignite a candle of length L, it will burn completely in L units of time.
You can also ignite a candle at both ends, which makes it burn twice as fast.
You have arranged some candles into the shape of a tree. You want to use the tree to measure time. At the beginning, you will ingite some leaves of the tree (all at the same time). Then you will just wait and watch the flames spread across the entire tree. (Whenever a flame reaches an inner node of the tree, it spreads to all branches that meet at that node.) Note that you are not allowed to light new flames during the process. The time you will measure is the time between the moment when you lighted the fire(s) and the moment when the last part of the tree finished burning.
You are given a description of the tree as threeint[] s: a, b, and len, with N elements each.
The nodes of the tree are numbered 0 through N, inclusive.
For each valid i, there is a candle between the nodes a[i] and b[i] with length len[i].
Compute and return the number of different times you can measure when following the above procedure.
You have arranged some candles into the shape of a tree. You want to use the tree to measure time. At the beginning, you will ingite some leaves of the tree (all at the same time). Then you will just wait and watch the flames spread across the entire tree. (Whenever a flame reaches an inner node of the tree, it spreads to all branches that meet at that node.) Note that you are not allowed to light new flames during the process. The time you will measure is the time between the moment when you lighted the fire(s) and the moment when the last part of the tree finished burning.
You are given a description of the tree as three
Compute and return the number of different times you can measure when following the above procedure.
Constraints
- A will contain between 1 and 19 elements, inclusive.
- A, B and len will contain same number of elements.
- Each element in A will be between 0 and |A|, inclusive.
- Each element in B will be between 0 and |A|, inclusive.
- Each element in len will be between 1 and 1000, inclusive.
- A, B and len will describe a tree.
Examples
0)
{0,1}
{1,2}
{10,1}
Returns: 2
This tree looks the same as a single candle of length 11. If we light it on one end, we will measure the time 11. If we light it on both ends, we will measure the time 5.5.
1)
{0,0,0}
{1,2,3}
{1,1,1}
Returns: 2
This time we have 3 ends. If we ignite all of them the time is 1, otherwise the time is 2.
2)
{0,0,0}
{1,2,3}
{1,2,3}
Returns: 4
We can get 4 different outcomes: 2.5, 3, 4, 5.
3)
{0,1,1,2,3,3,2,4}
{1,2,3,4,5,6,7,8}
{5,3,2,4,6,8,7,1}
Returns: 7
4)
{0,0,0,0}
{1,2,3,4}
{123,456,789,1000}
Returns: 8
Submissions are judged against all 58 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CandleTimerEasy with a public method int differentTime(vector<int> A, vector<int> B, vector<int> len) · 58 test cases · 2 s / 256 MB per case