Cong ty Cong Nghe Tin hoc Nha truong http://www.vnschool.net
Đề thi IOI2009 - Bài 1: Xạ thủ bắn cung (Archery)
16/09/2009

Một cuộc thi bắn cung được tổ chức theo các luật sau. Có N đích được xếp thành một hàng và được đánh số từ 1 đến N tương ứng với vị trí của nó trên hang (trái nhất là đích 1 và phải nhất là đích N). Có 2*N cung thủ. Tại mỗi thời điểm của cuộc thi có đúng 2 cung thủ đứng trước mỗi đích. Mỗi vòng thi đấu của cuộc thi được tổ chức như sau:


Hai cung thủ tại mỗi đích đấu với nhau và xác định ra người thắng cuộc, người thua cuộc giữa họ. Sau đó các cung thủ được sắp xếp lại như sau:

Người thắng cuộc tại các đích từ số 2 đến số N chuyển sang đích bên trái của họ (nghĩa là tương ứng chuyển đến các đích từ số 1 đến số N-1).

Người thua cuộc tại các đích từ số 2 đến số N, cũng như người thắng cuộc tại đích số 1 giữ nguyên vị trí.

Người thua cuộc tại đích số 1 chuyển đến đích số N.

Cuộc thi thực hiện liên tục R vòng, với R ≥2*N.

Bạn là cung thủ duy nhất đến với cuộc thi đúng giờ. Tất cả 2*N – 1 cung thủ còn lại đều đến sớm và họ đã xếp vào hàng. Việc bạn cần làm bây giờ là đứng chèn vào chỗ nào đó trong hàng cùng với họ. Bạn biết rằng, sau khi bạn vào vị trí, 2 cung thủ trái nhất sẽ bắt đầu cuộc thi tại đích số 1, 2 người tiếp theo sẽ thi đấu tại đích số 2,… và 2 người ở ví trí phải nhất sẽ thi đấu tại đích số N.

Tất cả 2*N cung thủ tại cuộc thi (bao gồm cả bạn) được xếp hàng theo trình độ, trong đó thứ hạng nhỏ hơn ứng với trình độ cao hơn. Không có hai cung thủ nào cùng hạng. Ngoài ra, cuộc đấu giữa 2 cung thủ luôn kết thúc bằng chiến thắng của người có hạng bé hơn.

Biết trình độ của mọi đối thủ của mình, bạn muốn xếp mình vào vị trí sao cho đảm bảo bạn sẽ kết thúc cuộc thi tại đích có số hiệu nhỏ nhất có thể. Nếu có nhiều cách để làm như vậy, bạn sẽ muốn chọn cách ứng với vị trí bắt đầu tại đích có số hiệu càng lớn càng tốt.

BÀI TOÁN

Viết chương trình nhận vào thứ hạng của tất cả các cung thủ, bao gồm cả của bạn, lẫn cách sắp xếp các đối thủ của bạn trên hàng, xác định vị trí bạn sẽ bắt đầu cuộc thi sao cho bạn đạt được mục tiêu trên.

GIỚI HẠN

1 ≤ N ≤ 200000 Số lượng đích; cũng bằng đúng một nửa số cung thủ.

2x N ≤ R ≤ 1000000000 Số lượng vòng đấu của cuộc thi.

1 ≤ Sk ≤ 2xN Thứ hạng của cung thủ thứ k.

INPUT

Chương trình của bạn phải đọc từ standard input dữ liệu sau:

Dòng đầu tiên chứa các số nguyên N và R, cách nhau bởi một dấu cách.

2 * N dòng tiếp theo liệt kê thứ hạng của các cung thủ. Dòng đầu tiên trong các dòng này chứa thứ hạng của bạn. Các dòng còn lại chứa thứ hạng của các cung thủ khác, mỗi cung thủ một dòng, theo trình tự họ đứng trên hàng (từ trái sang phải). Mỗi dòng trong 2 * N dòng này chứa duy nhất một số nguyên có giá trị trong khoảng từ 1 dến 2 * N. Hạng 1 ứng với trình độ cao nhất và hạng 2 * N ứng với trình độ thấp nhất. Thứ hạng của cung thủ đôi một khác nhau.

OUTPUT

Chương trình của bạn phải xuất ra standard output một dòng chứa một số nguyên duy nhất có giá trị trong khoảng từ 1 đến N: số hiệu của đích mà bạn sẽ bắt đầu cuộc thi.

CÁCH CHẤM ĐIỂM

Sẽ có một nhóm các test với tổng điểm là 60, trong đó N sẽ không vượt quá 5000.

Cũng trong số này sẽ có một số test với tổng điểm là 20, trong đó N sẽ không vượt quá 200.

VÍ DỤ

Bạn là cung thủ có trình độ kém thứ hai. Nếu bạn đứng tại đích số 1, bạn sẽ đến đích số 4 và sẽ đứng yên tại đó cho đến cuối cuộc thi. Nếu bạn đứng tại đích số 2 hoặc số 4, bạn sẽ đứng tại chỗ cho đến cuối cuộc thi. Nếu bạn đứng tại đích số 3, bạn sẽ thắng người có trình độ kém nhất, sau đó chuyển qua đích số 2 và đứng luôn tại đây.

Bạn là cung thủ có trình độ tốt thứ hai. Người có trình độ cao nhất đã đứng tại vị trí số 1 và sẽ đứng tại đây cho đến cuối cuộc thi. Vì vậy, dù bạn bắt đầu tại đâu, bạn sẽ luôn chuyển từ vị trí của bạn, qua tất cả các đích 4 đến 1 một cách tuần tự qua mỗi vòng đấu cho đến khi kết thúc cuộc thi. Do đó, để bạn đứng tại đích số 1 khi kết thúc cuộc thi sau 9 vòng đấu, bạn phải bắt đầu tại đích số hai.
URL của bài viết này::http://www.vnschool.net/modules.php?name=News&file=article&sid=3512
© Cong ty Cong Nghe Tin hoc Nha truong contact: sales@schoolnet.vn