← 返回题目列表

AtCoder · ahc003_a

A. 最短路径查询

中文机器翻译题面 查看原题

故事

AtCoder 正在开发一款利用最短路径算法的路线导航应用程序。 服务区表示为以网格连接的 30x30 顶点的道路网络。 当用户指定当前位置的顶点和目的地的顶点时,应用程序将输出它们之间的最短路径。 问题在于,尽管预定的发布日期已经临近,但对最短路径计算至关重要的每条边的长度测量却根本没有完成。 因此,AtCoder 决定放弃提前测量边长,并允许应用程序输出不是最短的路径。 根据用户到达目的地的实际时间信息估计每条边的长度,应该可以逐步提高性能。

问题陈述

有一个无向网格图,其顶点为 30x30,边长未知。 让 (0, 0) 表示左上角顶点,并且 (i, j) 表示顶点 i从顶部开始的第行和 j左起第 列。 您的任务是处理以下查询 1000 次。

在 k-th 查询,您的程序首先接收顶点 来自标准输入的 s_k=(si_k,sj_k) 和 t_k=(ti_k,tj_k) ,格式如下:

si_k sj_k ti_k tj_k

然后,你的程序应该计算一条路径 P_k 来自 s_k to t_k。 让 U, D, L,和 R 代表运动 分别为 (i,j) to (i-1,j), (i+1,j), (i,j-1),和 (i,j+1)。 输出代表路径的字符串 P_k 到一行中的标准输出。 输出后,您必须刷新标准输出。 否则,提交的内容可能会被判定为 TLE。

当你的程序输出一条路径后,判断程序会计算长度 路径的 b_k ,生成一个统一的随机数 e_k 之间 0.9 和 1.1,并给出一个整数值 \mathrm{round}(b_k\times e_k) 到标准输入。 通过读取该整数, k第一个查询完成,您应该继续执行 k+1第一个查询。

示例

输入 输出
3 19 16 17
DDDDDDDDDDDDDLL
99561
26 18 13 18
UUUUUUUUUUUUU
72947

评分

让 a_k 和 b_k 是最短路径和输出路径的长度 k- 第一个查询 (1\leq k\leq 1000),分别。 那么测试用例的分数是

\mathrm{round}(2312311\times \sum_{k=1}^{1000}0.998^{1000-k} \frac{a_k}{b_k})

提交的分数是每个测试用例的总分。 如果您的程序输出非法路径(多次访问同一顶点,超出 30x30,或者不是来自 s to t),判断为 WA。 比赛结束后,将根据上次提交的系统测试结果确定最终排名。

  • 临时测试由 100 个测试用例组成。如果您得到的结果不是 AC 对于一个或多个测试用例,提交的分数将为零。
  • 系统测试由 3000 个测试用例组成。如果您得到的结果不是 AC 对于某些测试用例,只有这些测试用例的分数为零。我们将发布 种子.txt (md5=0cf5051d586e7f62c0b3527f6f7fbb1c) 比赛结束后。

输入生成

让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。 我们首先生成两个参数 D=\mathrm{rand}(100, 2000) 和 M=\mathrm{rand}(1, 2)。 让 h_{i,j} 是之间的边的长度 (i, j) 和 (i,j+1),让 v_{i,j} 是之间的边的长度 (i, j) 和 (i+1,j).

的一代 h_{i,j}

  1. 对于每个 i\in\{0,\ldots,29\} 和 p\in\{0,\ldots,M-1\},我们独立生成一个随机整数 H_{i,p}=\mathrm{rand}(1000+D,9000-D).
  2. 对于每个 i\in\{0,\ldots,29\} 和 j\in\{0,\ldots,28\},我们独立生成一个随机整数 \delta_{i,j}=\mathrm{rand}(-D,D).
  3. If M=1,对于每个 i\in\{0,\ldots,29\} 和 j\in\{0,\ldots,28\},我们设置 h_{i,j}=H_{i,0}+\delta_{i,j}.
  4. If M=2,对于每个 i\in\{0,\ldots,29\},我们生成一个随机整数 x_i=\mathrm{rand}(1,28),然后对于每个 j\in\{0,\ldots,x_i-1\},我们设置 h_{i,j}=H_{i,0}+\delta_{i,j},并且对于每个 j\in\{x_i,\ldots,28\},我们设置 h_{i,j}=H_{i,1}+\delta_{i,j}.

的一代 v_{i,j}

  1. 对于每个 j\in\{0,\ldots,29\} 和 p\in\{0,\ldots,M-1\},我们独立生成一个随机整数 V_{j,p}=\mathrm{rand}(1000+D,9000-D).
  2. 对于每个 i\in\{0,\ldots,28\} 和 j\in\{0,\ldots,29\},我们独立生成一个随机整数 \gamma_{i,j}=\mathrm{rand}(-D,D).
  3. If M=1,对于每个 j\in\{0,\ldots,29\} 和 i\in\{0,\ldots,28\},我们设置 v_{i,j}=V_{j,0}+\gamma_{i,j}.
  4. If M=2,对于每个 j\in\{0,\ldots,29\},我们生成一个随机整数 y_j=\mathrm{rand}(1,28),然后对于每个 i\in\{0,\ldots,y_j-1\},我们设置 v_{i,j}=V_{j,0}+\gamma_{i,j},并且对于每个 i\in\{y_j,\ldots,28\},我们设置 v_{i,j}=V_{j,1}+\gamma_{i,j}.

的一代 s_k, t_k

顶点 查询中给出的 s_k 和 t_k 是在所有顶点中均匀随机选择的。 如果曼哈顿之间的距离 s_k 和 t_k (|si_k-ti_k|+|sj_k-tj_k|)严格小于 10,我们重复随机选择,直到距离至少变为 10。

工具

  • 本地测试仪: 你需要一个编译环境 Rust 语言.
  • 展示台
  • 输入:如果您不使用上述本地测试器,则可以使用这 100 个输入(种子 0-99)进行本地测试。这些输入与实际测试用例不同。输入的格式如下,您可以自己编写判断程序来使用它们。
h_{0,0} \ldots h_{0,28}
\vdots
h_{29,0} \ldots h_{29,28}
v_{0,0} \ldots v_{0,29}
\vdots
v_{28,0} \ldots v_{28,29}
si_1 sj_1 ti_1 tj_1 a_1 e_1
\vdots
si_{1000} sj_{1000} ti_{1000} tj_{1000} a_{1000} e_{1000}

判断程序示例(伪代码)

string query(s, t, prev_result) {
    // WRITE YOUR SOLUTION HERE
}

int main() {
    if (LOCAL_TEST) {
        read_h_v();
    }
    prev_result = 0;
    score = 0.0;
    for (int k = 0; k < 1000; k++) {
        if (LOCAL_TEST) {
            read_s_t_a_e();
        } else {
            read_s_t();
        }
        path = query(s, t, prev_result);
        print(path);
        if (LOCAL_TEST) {
            b = compute_path_length(path);
            score = score * 0.998 + a / b;
            prev_result = round(b * e);
        } else {
            prev_result = read_result();
        }
    }
    if (LOCAL_TEST) {
        print(round(2312311 * score));
    }
    return 0;
}