102717: [AtCoder]ABC271 Ex - General General

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $600$ points

Problem Statement

Solve the following problem for $T$ test cases.

A piece is placed at the origin $(0, 0)$ on an $xy$-plane. You may perform the following operation any number of (possibly zero) times:

  • Choose an integer $i$ such that $1 \leq i \leq 8$ and $s_i=$ 1. Let $(x, y)$ be the current coordinates where the piece is placed.
    • If $i=1$, move the piece to $(x+1,y)$.
    • If $i=2$, move the piece to $(x+1,y+1)$.
    • If $i=3$, move the piece to $(x,y+1)$.
    • If $i=4$, move the piece to $(x-1,y+1)$.
    • If $i=5$, move the piece to $(x-1,y)$.
    • If $i=6$, move the piece to $(x-1,y-1)$.
    • If $i=7$, move the piece to $(x,y-1)$.
    • If $i=8$, move the piece to $(x+1,y-1)$.

Your objective is to move the piece to $(A, B)$.
Find the minimum number of operations needed to achieve the objective. If it is impossible, print -1 instead.

Constraints

  • $1 \leq T \leq 10^4$
  • $-10^9 \leq A,B \leq 10^9$
  • $s_i$ is 0 or 1.
  • $T$, $A$, and $B$ are integers.

Input

The input is given from Standard Input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Here, $\mathrm{case}_i$ denotes the $i$-th test case.

Each test case is given in the following format:

$A$ $B$ $s_1 s_2 s_3 s_4 s_5 s_6 s_7 s_8$

Output

Print $T$ lines in total.
The $i$-th line should contain the answer to the $i$-th test case.

Sample Input 1

7
5 3 10101010
5 3 01010101
5 3 11111111
5 3 00000000
0 0 11111111
0 1 10001111
-1000000000 1000000000 10010011

Sample Output 1

8
5
5
-1
0
-1
1000000000

Input

题意翻译

### 题目描述 给你一个终点 $G(A,B)$ 和一个向量集合 $S\subset S'=\{(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)\}$。初始有一个点 $P(0,0)$。每次你可以选择一个向量 $V\in S$，然后执行 $P\gets P+V$。求出在最优策略下执行几次可以使得 $P=G$，或者判断无解。 多组数据。 ### 数据范围 - $1\le T\le 10^4$。 - $-10^9\le A,B\le 10^9$。 - $T,A,B\in Z$。 ### 输入格式 第一行输入一个整数 $T$，表示数据组数。 接下来 $T$ 行，每行两个整数 $A,B$ 和一个长为 $8$ 的 $\texttt{0/1}$ 字符串 $s$。如果 $s_i=1$ 则表示 $S$ 中存在 $S'$ 中的第 $i$ 个元素。 ### 输出格式 对于每个测试用例，输出答案。 translated_by_nr0728

Output

分数：$600$分

问题描述

对于$T$个测试用例，解决以下问题。

在$xy$平面上的原点$(0, 0)$处放置一块棋子。你可以任意次数（包括零次）执行以下操作：

  • 选择一个整数$i$，使得$1 \leq i \leq 8$且$s_i=$ 1。棋子当前放置的坐标为$(x, y)$。执行以下操作之一：
    • 如果$i=1$，将棋子移动到$(x+1,y)$。
    • 如果$i=2$，将棋子移动到$(x+1,y+1)$。
    • 如果$i=3$，将棋子移动到$(x,y+1)$。
    • 如果$i=4$，将棋子移动到$(x-1,y+1)$。
    • 如果$i=5$，将棋子移动到$(x-1,y)$。
    • 如果$i=6$，将棋子移动到$(x-1,y-1)$。
    • 如果$i=7$，将棋子移动到$(x,y-1)$。
    • 如果$i=8$，将棋子移动到$(x+1,y-1)$。

你的目标是将棋子移动到$(A, B)$。找到实现目标所需的最小操作数。如果不可能，则打印-1。

约束条件

  • $1 \leq T \leq 10^4$
  • $-10^9 \leq A,B \leq 10^9$
  • $s_i$是0或1。
  • $T$，$A$和$B$是整数。

输入

输入从标准输入按以下格式给出：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

其中，$\mathrm{case}_i$表示第$i$个测试用例。

每个测试用例按以下格式给出：

$A$ $B$ $s_1 s_2 s_3 s_4 s_5 s_6 s_7 s_8$

输出

总共打印$T$行。
第$i$行应包含第$i$个测试用例的答案。

样例输入 1

7
5 3 10101010
5 3 01010101
5 3 11111111
5 3 00000000
0 0 11111111
0 1 10001111
-1000000000 1000000000 10010011

样例输出 1

8
5
5
-1
0
-1
1000000000

Source/Category

加入题单

算法标签：