TheHomework
SRM 381 · 2007-12-08 · by Olexiy
Problem Statement
John has a list of integers first, and his task is to transform it so that it contains exactly the same elements as another list second (but not necessarily in the same order).
To achieve this goal, John will perform a number of operations in sequence. These are the three operations that can be performed on a list:
- Add some arbitrary integers to the list. The number of elements added must not be more than the size of the list before the operation.
- Delete some elements from the list. The number of elements deleted must not be more than half of the size of the list before the operation.
- Arbitrarily change some elements in the list. The number of elements changed must not be more than half of the size of the list.
You are given
Notes
- A list may contain repeated elements. When determining if two lists contain the same elements, all occurrences of each integer must exist in both lists.
Constraints
- first will contain between 1 and 50 elements, inclusive.
- second will contain between 1 and 50 elements, inclusive.
- Each element of first will be between 0 and 1000, inclusive.
- Each element of second will be between 0 and 1000, inclusive.
{1,2,3}
{2,3,4}
Returns: 1
It is enough just to change the 1 to a 4.
{0}
{1}
Returns: 2
We can add 1 and then delete 0.
{5,2,7,999,7}
{7,7,2,999,5}
Returns: 0
These lists already contain the same elements.
{12,13}
{1,1,1,1,1,1,1,1,1}
Returns: 4
Three additions and one deletion can be applied.
{7,7,7}
{8,8,8,8}
Returns: 3
Submissions are judged against all 215 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheHomework with a public method int transform(vector<int> first, vector<int> second) · 215 test cases · 2 s / 256 MB per case