Hỏi thuật toán của bài tập trên toạ độ 2 chiều

Nhà của Việt ở toạ độ (0,0) và nhà của Nam ở toạ độ (a,b). Hỏi Việt có thể đến nhà Nam trong đúng s bước hay không ? Biết rằng, tại toạ độ (x,y), trong một bước di chuyển, ta chỉ có thể di chuyển đến 1 trong 4 toạ độ (x+1,y),(x−1,y),(x,y+1),(x,y−1) và ta có thể đi qua một toạ độ bất kì nhiều lần.

Input:

  • Dòng thứ nhất chứa 3 số nguyên a,b,s(−10^9≤a,b≤10^9;1≤s≤2∗10^9)

Output:

  • In ra “Yes” nếu Nam có thể đến nhà Việt và ngược lại in ra “No”

Ví dụ:

Input:

0 1 3

Output:

Yes

Giải thích:

Ta đi như sau: (0,0)→(0,1)→(0,2)→(0,1)

giúp em !

Thuật toán của bài này có vấn đề gì vậy bạn?
Bạn thử giải tay đề bài như sau xem:

  1. Nhà Nam ở (1, 2), hỏi Việt có thể đến nhà Nam đúng 0, 1, 2, 3, 4, 5, 6, 7, 8… bước hay không?
  2. Nhà Nam ở (3, 1), hỏi Việt có thể đến nhà Nam đúng 0, 1, 2, 3, 4, 5, 6, 7, 8… bước hay không?
3 Likes

bạn gặp khó khăn chỗ nào?
nhập/tính toán/xuất? bạn đã biết cách giải bằng tay chưa?

3 Likes

Ý tưởng mình đưa ra dưới đây có thể có lỗ hổng và dẫn đến sai trầm trọng. :thinking:

CHẴN - LẺ
Nếu bước đi ngắn nhất từ nhà Việt đến nhà Nam là số lẻ thì tất cả các số lẻ lớn hơn sẽ đúng, và số chẵn sẽ sai và ngược lại. Vì số bước đi thêm (quá/lớn hơn tọa độ đích) đều phải đi lại đúng bằng số bước đi thêm => số bước đi thêm luôn luôn chẵn.

Bước đi ngắn nhất từ (0, 0) đến (0, 1) là 1 bước => toàn bộ số lẻ đều trả về Yes.
Vì thế bạn chỉ cần tìm số bước đi ngắn nhất là có đáp án. Áp dụng toán tiểu học. :smiling_imp:

Viết xong thì đưa thành quả lên đây nhé.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?