Matching a continuous sequence of numbers within the input data

From CS100 Homework 2-3

题目描述

You are first given a set of values based on user inputs. Name it set A.
Then, you are given another set of values B, where the number of values in set B should be smaller than that of set A (The size of B is smaller than that of A).
* The order of elements in a set is fixed. e.g. [1, 2, 3] and [3, 2, 1] are two different sets. You are not supposed to change the order of any set.
Then we try to find a continuous range of values (a subset) in set A, with the same length as set B, where the difference between set B and the range of values in A is minimized.

Definition: The difference between two equal-sized sets A = [a1, a2, a3, ...an] and B = [b1, b2, b3, ...bn] is

image

E.g. A = [1, 2, 4]; B = [5, 6, 1], then diff(A, B) = |1 - 5| + |2 - 6| + |4 - 1| = 11

Note: If there are many continuous ranges in A with the same minimum difference as B, you should output the left-most one.
E.g. A = [2, 4, 6, 8] and B = [3, 5], then B has the same difference with [2, 4] and [4, 6] (both equal to 1), but you should output [2, 4], instead of [4, 6].

The following is a demo process for the program if you can do it successfully: (red indicates input)

image
问题输入

Input contains n+m+2 lines.
The first n lines are values in set A. Each line contains a positive integer.
The (n+1)th line is -1, indicating the end of set A.
The next m lines are values in set B. Each line contains a positive integer.
The last line is -1, indicating the end of set B.

问题输出

First, you should output a prompt: Please input the set A:
Then, user will input n numbers, followed by a "-1" After you receive the "-1", you should output again a prompt:Please input the set B:
Then, user will input m numbers, followed by a "-1"
Note that there should be no whitespaces after each prompt, and you should end each prompt with a newline.
Once you need to resize your array, output a message like this:(resize) from 5 to 10
Then, after getting all the inputs, you should output ---Result--- ended with a newline.
Finally, output m integers, which is the continuous range (subset) you found in set A with the minimal difference to set B.

样例输入1
3
2
4
1
7
5
-1
2
3
5
-1
样例输出1
Please input the set A:
(resize) from 5 to 10
Please input the set B:
---Result---
3 2 4 






在线测试 (语言:C;时间限制:1s)
当前状态

无提交记录

有话想说?