Sắp xếp lại đồ đạc

  • Problem:

+ Andryusha là một người rất gọn gàng và ngăn nắp. Cậu ta mới mua một chiếc tủ mới và đang sắp xếp đồ đạc vào tủ. Andryusha có n đôi tất(vớ) đang bị đảo lộn , và đã được đánh số thứ tự từ 1 đến n, cậu muốn sắp xếp chúng theo từng đôi rồi xếp gọn gàng vào tủ.

+ Andryusha sẽ đặt từng chiếc tất lên bàn. Nếu trên bàn đã có một chiếc tất(vớ) mang số thứ tự trùng với số thứ tự chiếc tất (vớ) mà Andryusha đang cầm thành một đôi thì cậu sẽ ghép chúng lại rồi xếp vào tủ. Nếu cái tất (vớ) mà cậu đang cầm có số thứ tự không trùng với cái nào trên bàn thì cậu sẽ đặt nó lên bànlấy chiếc tất(vớ) tiếp theo,

+ Cuối cùng thì Andryusha cũng sắp xếp xong, lúc đó cậu tự hỏi không biết tại một thời điểm có  nhiều nhất thì có bao nhiêu chiếc tất trên bàn nhỉ?

  • Input:

+ Dòng đầu tiên chứa số tự nhiên(1 ≤ n ≤ 105) – là số đôi tất (vớ) của Andryusha

+ Dòng thứ 2 là dãy chứa 2n số tự nhiên x1, x2, …, x2n (1 ≤ xi ≤ n) là số thứ tự được đánh trên các chiếc tất mà  Andryusha đã lấy ra( theo thứ tự thời gian cái nào lấy ra trước ghi số thứ tự của nó trước)

  • Output:

+ Số lượng chiếc tất tối đa trên bàn tại một thời điểm.

  • Examples:

Ex1:

  • input

  • output

– Ví dụ 1 Andryusha có 1 đôi tất(vớ) n=1.

– Khi cậu cầm chiếc tất số 1 lên trên bàn trống nên cậu đặt nó xuống bàn. Trên bàn lúc này có 1 chiếc tất

– Sau đó cầu cầm chiếc tất còn lại lên nó mang số thứ tự là 1 và trùng với chiếc trên bàn. Cậu lấy 2 chiếc đặt vào tủ. Trên bàn không có chiếc nào.

=> tại một thời điểm chỉ có nhiều nhất 1 chiếc tất trên bàn.

+ Ex2:

  • input

  • output

– Ví dụ 2: Andryusha có 3 đôi tất, n=3

– Cậu lấy chiếc tất đầu tiên ra nó có số thứ tự 2 rồi đặt lên bàn. Trên bàn lúc này có 1 chiếc.

– Cậu lấy chiếc tất tiếp theo nó mang số 1, và trên bàn chưa có chiếc tất số 1 nào nên cậu đặt nó xuống. Lúc này trên bàn có 2 chiếc(2;1)

– Chiếc tt tiếp theo được lấy ra có số thứ tự là 1, trên bàn cũng có 1 chiếc tất số 1 nên cậu gom 2 chiếc tất lại rồi cất đi. Lúc này trên bàn có 1 chiếc tất số 2

– Chiếc tất số 3 được lấy ra và tất nhiên nó sẽ được đặt xuống bàn. Lúc này trên bàn có 2 chiếc tất — (2;3).

– Chiếc tất số 2 được lấy ra tiếp trên bàn có 1 chiếc tất số 2, hai chiếc sẽ được ghép đôi và cất đi. Trên bàn chỉ còn 1 chiếc tất số 3.

– Chiếc tất cuối cùng được lấy ra mang số thứ tự là 3 và được ghép với chiếc tất đang trên bàn. Lúc này trên bàn không còn chiếc tất nào.

=> tại một thời điểm có nhiều nhất 2 chiếc tất trên bàn.

 

Link bài gốc: http://codeforces.com/contest/782/problem/A

Translator: phuongtn

The following two tabs change content below.

phuongtn