#P13067. [GCJ 2020 #3] Thermometers

    ID: 12872 Type: RemoteJudge 30000ms 1024MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>动态规划 DP贪心2020Google Code Jam

[GCJ 2020 #3] Thermometers

题目描述

You are part of a team of researchers investigating the climate along the coast of an island. The island's coast is modeled as a circle with a circumference of KK kilometers. There is a lighthouse on the coast which occupies a single point on the circle's circumference. Each point on the coast is mapped to a real number in the range [0,K)[0, K); formally, point xx is the point on the coast that is xx kilometers away from the lighthouse when walking clockwise along the coast. For example, if K=5K = 5, point 00 is the point where the lighthouse is, point 1.51.5 is the point that is 1.51.5 kilometers away from the lighthouse in the clockwise direction, and point 2.52.5 is the point that is located at the diametrical opposite of the lighthouse.

You are in charge of studying coastal temperatures. Another team installed a coastal temperature measuring system that works as follows: a number of thermometers were deployed at specific points to measure the temperature at those points. No two thermometers were placed at the same point. In that team's model, points without thermometers are assumed to have the same temperature as the one measured by the closest thermometer. For points that are equidistant from two thermometers, the thermometer in the clockwise direction is used (the first one you would encounter if walking clockwise from the point).

Unfortunately, you do not know how many thermometers the system used or where they were placed, but you do have access to the system's temperature data. It is given as two lists of NN values each X1X_1, X2X_2, \dots, XNX_N and T1T_1, T2T_2, \dots, TNT_N, representing that each point xx where Xix<Xi+1X_i \leq x < X_{i+1} is assigned temperature TiT_i, for each 1i<N1 \leq i < N, and each point xx where 0x<X10 \leq x < X_1 or XNx<KX_N \leq x < K is assigned temperature TNT_N. The points are enumerated in the clockwise direction, so Xi<Xi+1X_i < X_{i+1}, for all ii.

You want to determine the smallest number of thermometers that, when placed in some set of locations, could have produced the observed data.

输入格式

The first line of the input gives the number of test cases, TT. TT test cases follow; each consists of three lines. The first line of a test case contains two integers KK and NN: the circumference of the island and the size of the lists representing the temperature data. The second line contains NN integers X1X_1, X2X_2, \dots, XNX_N. The third line contains NN integers T1T_1, T2T_2, \dots, TNT_N. The way in which the integers in the second and third line represent the temperatures is explained above.

输出格式

For each test case, output one line containing Case #x: y, where xx is the test case number (starting from 1) and yy is the minimum number of thermometers that could have produced the observed input data, as described above.

3
2 2
0 1
184 330
3 2
0 1
184 330
10 3
1 5 9
184 200 330

Case #1: 2
Case #2: 3
Case #3: 3

提示

Sample Explanation

In Sample Case #1, at least 2 thermometers are needed because there are two different temperatures measured. It is possible to produce the data using exactly 2 thermometers, with one thermometer (measuring 184) at point 0.5 and another (measuring 330) at point 1.5. Note that point 0 and point 1 are equidistant from both thermometers, so the thermometer in the clockwise direction is used. The temperature measured at point 0 comes from the thermometer at point 0.5 and the temperature measured at point 1 comes from the thermometer at point 1.5.

The data from Sample Case #2 could not be produced with just 2 thermometers. It could be produced with 3 thermometers if they were placed at point 0.2, point 1.8, and point 2.8, measuring 184, 330 and 330, respectively. There are other ways to place 3 thermometers that would also yield the input data.

In Sample Case #3, one way to produce the data with 3 thermometers is to place them at point 0, point 2 and point 8, measuring 330, 184 and 200, respectively.

Limits

  • 1T1001 \leq T \leq 100.
  • 2Nmin(100,K)2 \leq N \leq \min(100, K).
  • 0X10 \leq X_1.
  • Xi<Xi+1X_i < X_{i+1}, for all ii.
  • XN<KX_N < K.
  • 184Ti330184 \leq T_i \leq 330, for all ii.
  • TiTi+1T_i \neq T_{i+1}, for all ii.
  • T1TNT_1 \neq T_N.

Test Set 1 (5 Pts, Visible Verdict)

  • 2K102 \leq K \leq 10.

Test Set 2 (19 Pts, Hidden Verdict)

  • 2K1092 \leq K \leq 10^9.