Warehouse rush
After some time, Mio has finally found a job (she is terrible at finding jobs). She got a job in a warehouse, which is very similar to her last job, but this time, it is more brainy (last time it was all about cleaning).
She needs to count how many different products are stored in the warehouse. Unfortunately, warehouse can be enormous and Mio wants to be prepared for her job as soon as possible. This is where you step in.
Make a program that will do the counting. In input (input is through the file "warehouse.in") there will be few (10) simulations. The number of simulations is the firs number in the file. Input for each simulation is done in the following manner: Firstly, two positive integers and , in this order, are given. In the following rows, there will be numbers. Each number (a number from row and column ) represents the code of a product. Products with same codes are considered as the same. In the output, a number of different products for its simulation should be returned/written.
Sum of all countings (10 of them) shall be entered as the answer. Let's help Mio :)
The file can be downloaded by clicking here .
Useful information:
Example
Input:
3 4
19 12 12 18
14 16 16 1
4 10 18 13
Output:
9
If anything is left unclear, feel free to ask it here
The answer is 156586.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Solution:
Since I am a user of C++, my solution will be in C++ spirit.
My idea was to view input as an array. It looks tempting to solve it like a matrix, but I prefer this option. First two elements m , n are information on the length of the array. Length of the array, will be labeled as k from now on, is equal to m × n . When the k is calculated, we just load in all the elements.
Next thing we do, will be sorting the array. This can be done making optimal sort, like merge sort or perhaps quick sort , or just using template function sort from header <algorithm> .
After that, we just count how many different elements we have. The given example would be solved in the following manner:
k = m × n = 1 2
s o r t e d A r r a y = { 1 , 4 , 1 0 , 1 2 , 1 2 , 1 3 , 1 4 , 1 6 , 1 6 , 1 8 , 1 8 , 1 9 }
s o l u t i o n = 9