CF1036B Diagonal Walking v.2

    • 58通过
    • 109提交
  • 题目来源 CodeForces 1036B
  • 评测方式 RemoteJudge
  • 标签
  • 难度 普及/提高-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    在一个笛卡尔平面上(就是平面直角坐标系), 从点(0, 0)开始出发, 每一步可以向周围的八个点走. 例如, 从(0, 0), 可以走到的点是:

    (1, 0);

    (1, 1);

    (0, 1);

    (-1, 1);

    (-1, 0);

    (-1, -1);

    (0, -1);

    (1, -1).

    如果一步从点(x1, y1)走到(x2, y2), 且x1 != x2 && y1 != y2, 则称这一步为diagonal move(斜步).

    现在有 q 个询问, 第 i 个询问的目标是走正好 ki 步到达点(ni, mi). 在所有可能的移动中希望能走斜步最多的一种. 你的目标是找到最多的“斜步”数量, 或者是发现无法用刚好 ki 步从(0, 0)走到(ni, mi).

    记住可以访问任意一个点任意次数.

    输入:

    第一行有一个整数 q (1 <= q <= 1e4), 表示询问个数.

    接下来 q 行, 在这 q 行中的第 i 行有三个整数 ni, mi, ki (1 <= ni, mi, ki <= 1e18), 分别表示目标坐标的 x 轴, y 轴和要求的步数.

    输出:

    q 个整数, 如果第 i 个询问无解, 则输出 -1 , 否则就输出最大的“斜步”步数.

    题目描述

    Mikhail walks on a Cartesian plane. He starts at the point $ (0, 0) $ , and in one move he can go to any of eight adjacent points. For example, if Mikhail is currently at the point $ (0, 0) $ , he can go to any of the following points in one move:

    • $ (1, 0) $ ;
    • $ (1, 1) $ ;
    • $ (0, 1) $ ;
    • $ (-1, 1) $ ;
    • $ (-1, 0) $ ;
    • $ (-1, -1) $ ;
    • $ (0, -1) $ ;
    • $ (1, -1) $ .

    If Mikhail goes from the point $ (x1, y1) $ to the point $ (x2, y2) $ in one move, and $ x1 \ne x2 $ and $ y1 \ne y2 $ , then such a move is called a diagonal move.

    Mikhail has $ q $ queries. For the $ i $ -th query Mikhail's target is to go to the point $ (n_i, m_i) $ from the point $ (0, 0) $ in exactly $ k_i $ moves. Among all possible movements he want to choose one with the maximum number of diagonal moves. Your task is to find the maximum number of diagonal moves or find that it is impossible to go from the point $ (0, 0) $ to the point $ (n_i, m_i) $ in $ k_i $ moves.

    Note that Mikhail can visit any point any number of times (even the destination point!).

    输入输出格式

    输入格式:

    The first line of the input contains one integer $ q $ ( $ 1 \le q \le 10^4 $ ) — the number of queries.

    Then $ q $ lines follow. The $ i $ -th of these $ q $ lines contains three integers $ n_i $ , $ m_i $ and $ k_i $ ( $ 1 \le n_i, m_i, k_i \le 10^{18} $ ) — $ x $ -coordinate of the destination point of the query, $ y $ -coordinate of the destination point of the query and the number of moves in the query, correspondingly.

    输出格式:

    Print $ q $ integers. The $ i $ -th integer should be equal to -1 if Mikhail cannot go from the point $ (0, 0) $ to the point $ (n_i, m_i) $ in exactly $ k_i $ moves described above. Otherwise the $ i $ -th integer should be equal to the the maximum number of diagonal moves among all possible movements.

    输入输出样例

    输入样例#1: 复制
    3
    2 2 3
    4 3 7
    10 1 9
    
    输出样例#1: 复制
    1
    6
    -1
    

    说明

    One of the possible answers to the first test case: $ (0, 0) \to (1, 0) \to (1, 1) \to (2, 2) $ .

    One of the possible answers to the second test case: $ (0, 0) \to (0, 1) \to (1, 2) \to (0, 3) \to (1, 4) \to (2, 3) \to (3, 2) \to (4, 3) $ .

    In the third test case Mikhail cannot reach the point $ (10, 1) $ in 9 moves.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。