AGAR - Agar.io

Giới hạn thời gian: 0.5 giây

Agar.io là một trò chơi nhiều người chơi tương tự như trò cá lớn nuốt cá bé vốn đã rất quen thuộc với trẻ em Việt Nam. Mục tiêu của trò chơi là tìm cách điểu khiển tế bào của mình ăn các tế bào khác để lớn hơn. Luật chơi đơn giản như sau:

 - Tế bào A (của người chơi A) có thể ăn tế bào B (của người chơi B) khi và chỉ khi kích thước của A lớn hơnB. Khi va chạm nếu A>B thì A ăn B, nếu A<B thì B ăn A.
 - Nếu A ăn B, kích thước của A sẽ tăng lên đúng bằng B.
 - Khi tế bào bị ăn, người chơi đó ngay lập tức bị thua cuộc.
 - Kích thước càng lớn thì di chuyển càng chậm.
 - Hai tế bào chỉ có thể ăn nhau khi chúng va chạm vào nhau.

--Ares-- vì muốn gây ấn tượng với bạn gái của mình rằng mình không chỉ giỏi lập trình mà còn chơi game giỏi nên đã quyết tâm thắng được Theghost2 là một đàn anh của --Ares-- và cũng đang là một trong những người chơi xuất sắc nhất hiện tại của trò chơi này. Nghĩ rằng tự mình khó có thể thắng được Theghost2 nên --Ares-- quyết định nhờ đến sự giúp đỡ của bạn mình. Cậu có N người bạn cùng chơi, kích thước thước hiện tại của N người bạn trên là S₁, S₂, ..., S_N. Một số người bạn sẽ hy sinh va chạm với Ares để --Ares-- trở nên lớn hơn và sau đó --Ares-- ăn được Theghost2. Mặc dù các bạn của --Ares-- rất tốt và sẵn sàng giúp đỡ bạn bè nhưng chắc chắn chẳng ai vui vẻ gì khi thấy mình thua cuộc cả nên --Ares-- muốn ăn càng ít bạn càng tốt. Hãy giúp --Ares-- tính xem cậu ta cần ăn ít nhất bao nhiêu người bạn để sau đó chiến thắng Theghost2 nhé.

Dữ liệu nhập:

 - Dòng đầu tiên chứa 3 số nguyên dương N, A, G (N ≤ 10⁵, 1 ≤ A ≤ 10⁹, 1 ≤ G ≤ 2*10⁹) lần lượt là số bạn của --Ares--, kích thước hiện tại của --Ares-- và kích thước hiện tại của Theghost2.

- Dòng thứ hai chứa N số nguyên dương S₁, S₂,..., S_N (1 ≤ S_i ≤ 10⁹).

Dữ liệu xuất:

- Nếu không có cách để ăn được Theghost2, in ra -1.

- Nếu có cách để ăn được Theghost2:
   + Dòng đầu tiên là số nguyên K - số lượng người bạn ít nhất mà --Ares-- cần phải ăn.
   + Nếu K > 0, dòng thứ hai là K số nguyên là chỉ số của những người bạn được chọn để --Ares-- ăn đúng theo thứ tự (người bị ăn trước xuất trước), mỗi số cách nhau một khoảng trắng. Nếu có nhiều cách ăn, chỉ cần in ra một cách bất kỳ.

Ví dụ

• input
  3 10 15
  1 5 10
  output
  2
  2 3
• input
  7 15 1000
  1 2 3 4 5 6 7
  output
  -1

Trong test 1, kích thước của --Ares-- lần lượt là 10 -> 15 ->  25, lúc này ăn được Theghost2 (kích thước 15)

Lần 1:

*Đặc điểm:
- n = 10^5.

* Ý tưởng đầu tiên:

- Thì theo lỗi suy nghĩ thông thường thôi, đầu tiên là sắp xếp theo kích thước của dãy a (nlogn), sau đó mỗi lần duyệt B-search, tìm ra phần tử lớn nhất nhỏ hơn A lúc hiện tại và loại bỏ nó ra khỏi danh sách (logn)!

* Chú ý:

Cái cần chú ý ở đây là cấu trúc dữ liệu sử dụng phải có đặc điểm sau đây:

- Hỗ trợ random access: tức là có khả năng truy cập tức thì vào phần từ thứ i của mảng. (a[i])

- Có khả năng remove một phần tử trong mảng

=> Sau khi điều tra thì có kiểu deque phù hợp với miêu tả.

*Test:

Code: http://ideone.com/JY0oyy

Bị TLE ở test số 28.

Lần 2: 

* Review:

Như vậy là cách 1 đã bị TLE ở đâu đó.

* Sau khi đi tham khảo bài làm của các bạn, thì mọi người chủ yếu tìm cách xử lý tinh tế chỗ sử dụng B-search để tìm kiếm và cách remove phần tử đã tìm được trước đó.

* Sau khi được gọi ý là sử dụng Stack thì cũng biết cách làm thì ra nó cũng dễ!

- 1 stack tên smaller: chuyên chứa các phần tử nhỏ hơn A theo thứ tự từ nhỏ đến lớn, mà đỉnh của nó là phần tử lớn nhất.

- 1 stack tên bigger: chuyên chứa các phần tử lớn hơn A cũng theo thứ tự, mà đỉnh của nó là phần tử nhỏ nhất.

-> Tức là ta đã chia dãy a thành 2 stack, 1 cái nhỏ hơn và 1 cái lớn hơn.

Công việc của chúng ta như sau:

- Chừng này đỉnh của dãy smaller vẫn còn nhỏ hơn A và smaller ko bị rỗng, tức là A vẫn còn có cái có thể ăn được.

- Lúc đó A sẽ ăn đỉnh của smaller.

- Sau khi ăn xong, vì giá trị của A bị thay đổi nên phải chuyển hết cách phần tử từ bigger có size nhỏ hơn A sang smaller theo đúng thứ tự đã quy định.

- Cứ như thế cho đến khi A > B hoặc A không thể ăn gì trong smaller nữa!

Code: http://ideone.com/wGJzmX

Bài học:

- Ôn tập lại cách viết B-search (cách ra điều kiện tìm thấy)

- Biết thêm một số kiểu dữ liệu mới (deque,priority_queue)

- Nhớ đến việc sử dụng stack trong trường hợp cần chia một dãy sắp xếp thành 2 dãy, theo một tiêu chí nào đấy.

#namlunoy