QOJ.ac

QOJ

Límite de tiempo: 1 s Límite de memoria: 512 MB Puntuación total: 100

#4503. 高尔夫机器人

Estadísticas

你喜欢高尔夫吗?我讨厌它。我讨厌高尔夫,以至于我决定制造终极高尔夫机器人,一个永远不会打丢球的机器人。我只需把它放在球上,选择正确的方向和距离,它就能完美地将球击入洞中。高尔夫将永远成为历史。

不幸的是,它并没有按计划工作。所以,现在我站在果岭上,准备我的第一次击球,却发现内置的距离选择旋钮并没有包含所有的距离选项!不过还没完全绝望,因为我有两次击球机会。

题目描述

给定我当前的机器人,我能在 2 杆或更少杆数内完成多少个球洞?

输入格式

第一行包含一个整数 $N$,表示高尔夫机器人可以击球的距离种数。 接下来的 $N$ 行,每行包含一个整数 $k_i$,表示旋钮上标记的第 $i$ 个距离。 下一行包含一个整数 $M$,表示球场上的球洞数量。接下来的 $M$ 行,每行包含一个整数 $d_j$,表示从高尔夫机器人到第 $j$ 个球洞的距离。

数据范围

$1 \le N, M \le 200\,000$ $1 \le k_i, d_j \le 200\,000$

输出格式

你应该输出一个整数,表示高尔夫机器人能够完成的球洞数量。 高尔夫机器人不能故意击球超过球洞后再向后击球。

样例

输入格式 1

3
1
3
5
6
2
4
5
7
8
9

输出格式 1

4

说明

高尔夫机器人可以击出 3 种不同的距离(1、3 和 5),球场上有 6 个球洞,距离分别为 2、4、5、7、8 和 9。高尔夫机器人能够将球打入其中的 4 个:

  • 第 1 个球洞,距离为 2,可以通过两次击球,每次距离为 1 来达到。
  • 第 2 个球洞,距离为 4,可以通过一次力度为 3 的击球和一次力度为 1 的击球(反之亦然)来达到。
  • 第 3 个球洞可以通过一次力度为 5 的击球达到。
  • 第 5 个球洞可以通过力度为 3 和 5 的两次击球达到。

第 4 个和第 6 个球洞永远无法达到。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.