(Adapted from Problem C of the first qualifier of the ACM Programming Contest of 2012/2013)
Presentation
Let's consider a set of Arrays (A1, A2, A3, ... ,An) of variable sizes. All the elements in these arrays are integers. All the arrays are sorted in an ascending order.
A sandwich is a set of indices (i1, i2, i3, ..., in) such as:
A1[i1] <= A2[i2] <= A3[i3] <= .. <= An[in] where "<=" is the inequality sign for "lesser than or equal"
Example
Consider the following arrays:
Given a set of arrays given as input, write a program that will calculate the number of valid sandwiches.
You are free to format your input in any way you want, and use any language you want. If your language of choice has a builtin function that does this (or something close enough), avoid using it.
Presentation
Let's consider a set of Arrays (A1, A2, A3, ... ,An) of variable sizes. All the elements in these arrays are integers. All the arrays are sorted in an ascending order.
A sandwich is a set of indices (i1, i2, i3, ..., in) such as:
A1[i1] <= A2[i2] <= A3[i3] <= .. <= An[in] where "<=" is the inequality sign for "lesser than or equal"
Example
Consider the following arrays:
A1 = [1, 5, 7, 10]
A2 = [2, 6, 6, 8, 12]
A3 = [4, 5, 9]
Here are some examples of valid sandwiches of the above set:
Exercise
- (0, 0, 0) // Because 1 <= 2 <= 4
- (1, 3, 2) // Because 5 <= 8 <= 9
Given a set of arrays given as input, write a program that will calculate the number of valid sandwiches.
You are free to format your input in any way you want, and use any language you want. If your language of choice has a builtin function that does this (or something close enough), avoid using it.