Thông thạo 7 Yasuo

View as PDF

Submit solution


Points: 300 (partial)
Time limit: 1.0s
Memory limit: 1023M
Input: stdin
Output: stdout

Author:
Problem types

Khôi rất thích chơi Liên Minh Huyền Thoại, đặc biệt là vị tướng Yasuo. Tuy nhiên anh ấy chơi Yasuo rất tệ nên anh ấy đang tập luyện để chơi vị tướng này một cách thành thạo.

Biết rằng từ tọa độ ~(x,y)~ Yasuo có thể lướt thẳng đến một trong các vị trí ~(x-1,y), (x+1,y), (x,y-1), (x,y+1) ~

hoặc lướt chéo đến một trong các vị trí ~(x-1,y-1), (x-1,y+1), (x+1,y-1), (x+1,y+1)~

Khôi sẽ tập luyện lướt Yasuo trong ~Q~ trận, trong trận thứ ~i~ mục tiêu của anh ấy là lướt tới điểm ~(n,m)~ từ tọa độ ~(0,0)~ trong chính xác ~k~ lần lướt. Tuy nhiên vì để được Thông Thạo 7 Yasuo, Khôi sẽ lướt đến điểm ~(n,m)~ với số lần lướt chéo là nhiều nhất.

Câu hỏi của bạn là, trong trận thứ ~i~, bạn hãy xác định số lần lướt chéo nhiều nhất của Khôi hoặc nói rằng Khôi không thể lướt từ điểm ~(0,0)~ tới điểm ~(n,m)~ trong chính xác ~k~ lần lướt.

Input

  • Dòng đầu tiên: Số nguyên dương ~Q~ ~(Q \leq 10^4)~ - số câu hỏi
  • ~Q~ dòng tiếp theo chứa số nguyên dương ~n~, ~m~, ~k~ ~(n,m,k \leq 10^{18})~

Output

  • Gồm ~Q~ dòng, tại dòng thứ ~i~, in ra ~“-1”~ nếu Khôi không thể lướt từ điểm ~(0,0)~ đến điểm ~(n,m)~ trong chính xác ~k~ lần lướt, ngược lại in ra số lần lướt chéo nhiều nhất của Khôi

Sample Input 1

3
2 2 3
4 3 7
10 1 9

Sample Output 1

1
6
-1

Giải thích

  • Một trong những cách lướt trong câu hỏi 1: ~(0,0)→(1,0)→(1,1)→(2,2)~
  • Một trong những cách lướt trong câu hỏi 2 ~(0,0)→(0,1)→(1,2)→(0,3)→(1,4)→(2,3)→(3,2)→(4,3)~
  • Câu hỏi 3: Khôi không thể lướt từ ~(0,0)~ đến ~(10,1)~ trong ~9~ lần lướt

Ràng buộc

  • 50% test ~n,m \leq 10~
  • 50% test ~n,m \leq 10^{18}~

View comments (5)

Comments


  • 0
    algorit  commented on 9:12 p.m. 23 jun, 2020

    cho mình hỏi là trong truy vấn 1: sao không lướt (0;0) -> (1;1) -> (2;2) để được 2 lần lướt chéo nhỉ ? :v


    • 0
      SPyofgame  commented on 9:18 p.m. 23 jun, 2020

      Rồi sao nó đến ô kết thúc trong 1 nước khi nó đang ở ô đó ạ ?


      • 0
        algorit  commented on 9:08 p.m. 28 jun, 2020

        Mình chưa hiểu đề lắm :"<


        • 0
          SPyofgame  commented on 2:42 p.m. 29 jun, 2020

          Đề yêu cầu: Từ vị trí xuất phát ~(0, 0)~, mình đi ô liền kề nó sao cho sau đúng ~k~ bước thì mình đến ô đích ~(m, n)~ và đếm số lượng nước đi chéo tối đa có thể thực hiện


  • 0
    Lê_Gia_Khánh  commented on 10:27 p.m. 22 jun, 2020

    Anh Khôi đam mê quá :))