Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
Score In E-mail
(1 vote)
Người viết: Ngô Minh Đức   
21/04/2008

Score

Bài toán

Score là một trò chơi trên một bảng cho hai người di chuyển cùng một mã thông báo từ vị trí này sang vị trí khác trên bảng. Bảng có N vị trí được đánh số từ 1 đến N, và một số mũi tên. Mỗi mũi tên chỉ từ một điểm này đến một điểm khác. Mỗi vị trí đều thuộc về một trong hai người chơi (gọi là người sở hữu). Mỗi vị trí còn một giá trị dương. Tất cả các giá trị đều khác nhau. Vị trí 1 là vị trí bắt đầu. Ban đầu cả hai người chơi đều có số điểm là 0.

Trò chơi được thực hiện như sau. Ta xác định vị trí hiện tại của mã thông báo trước khi thực hiện nước đi từ C. Bắt đầu trò chơi C ở vị trí 1. Một nước đi gồm các thao tác sau: 

1.      Nếu giá trị của C lớn hơn số điểm hiện tại của người sở hữu C, thì giá trị của C trở thành số điểm mới của người sử hữu C. Ngược lại, số điểm của người sở hữu C không đổi. Số điểm của người chơi còn lại không thay đổi trong trường hợp này.

2.      Sau đó, người sở hữu C chọn một trong số các mũi tên ngoài vị trí của mã thông báo hiện tại và đích của mũi tên trở thành vị trí mới của mã thông báo hiện tại. Một người chơi có thể thực hiện nhiều nước đi liên tục. 

Trò chơi kết thúc khi mã thông báo trở về vị trí bắt đầu. Người chiến thắng là người chơi có số điểm cao hơn khi trò chơi kết thúc. 

Các mũi tên được sắp xếp sao cho các điều kiện sao luôn thỏa mãn: 

-         Luôn có thể chọn được một mũi tên ngoài vị trí của mã thông báo hiện tại.

-         Mỗi vị trí P đều có thể đến được từ vị trí bắt đầu nghĩa là có một chuỗi các mũi tên từ điểm bắt đầu đến P.

-         Trò chơi chắc chắn kết thúc sau một số hữu hạn nước đi.

Hãy viết chương trình chơi trò chơi và chiến thắng. Tất cả các trò chơi được dùng để đánh giá đều có thể thắng tuỳ vào việc bạn thực hiện nước đi trước hay sau. Đối thủ của bạn luôn chơi một cách tối ưu nghĩa là kho có cơ hội anh ta sẽ chiến thắng và chương trình của bạn thua.

Input và Output

Chương trình của bạn là ngời chơi thứ nhất và đối thủ là người chơi thứ hai. Khi chương trình của bạn bắt đầu chạy, nó sẽ đọc dữ liệu vào từ input gồm: dòng thứ nhất chứa 1 số nguyên chỉ số vị trí N, 1<=N<=1000. N dòng tiếp theo mỗi dòng chứa N số nguyên chứa thông tin về các mũi tên. Nếu có một mũi tên chỉ từ vị trí i đến vị trí j, thì số thứ j trên dòng thứ i trong số N dòng là 1, nếu không nó sẽ là 0.

Dòng tiếp theo chứa N số nguyên chỉ người sở hữu các vị trí. Nếu vị trí i thuộc về người chơi 1 (bạn), thì số nguyên thứ i là 1, nếu không nó sẽ  là 2.

Dòng tiếp theo chứa N số nguyên chỉ giá trị các vị trí. Nếu số nguyên thứ ij, thì giá trị của vị trí ij. j luôn thoả mãn 1<=j<=N và tất cả các giá trị đều khác nhau.

Sau đó, trò chơi bắt đầu với vị trí mã thông báo hiện tại là 1. Chương trình chơi như sau và sẽ thoát ra khi mã thông báo trở lại ví trí 1:

·         ·        Nếu đến lượt chương trình của bạn thực hiện nước đi, thì nó sẽ viết số vị trí tiếp theo  P, 1<= P<=N, vào output

·         ·        Nếu đến lượt đối thủ của chương trình của bạn thực hiện nước đi, thì chương trình đọc số vị trí tiếp theo P, 1<=P<=N, từ input.

Xét ví dụ dưới. Bảng được minh họa trong hình 1. Các vị trí được đánh dấu tròn thuộc về người chơi thứ nhất và các vị trí đánh dấu vuông thuộc về người chơi thứ hai 2. Mỗi vị trí có một giá trị được viết trong dấu tròn hoặc vuông và các vị trí được đánh số bên cạnh các dấu đó. Trò chơi bắt đầu.

Kết thúc trò chơi, người chơi 1 được 3 điểm và người chơi 2 được 2 điểm. Người chơi 1 thắng.

Hướng dẫn lập trình

Trong ví dụ dưới, target là biến nguyên của vị trí.

Nếu bạn lập trình bằng C++ và dùng iostreams, hãy dùng lệnh sau để đọc input và viết vào output:          

cin>>target;

cout<<target<<endl<<flush;  

Nếu bạn lập trình bằng C hoặc C++ và dùng scanf và printf, hãy dùng lệnh sau để đọc input và viết vào output: 

scanf ("%d", &target);           

printf("%d\n",target); fflush (stdout);

Nếu bạn lập trình bằng Pascal, hãy dùng lệnh sau để đọc input và viết vào output: 

Readln(target);

Writeln(target);

Công cụ

Cho trước một chương trình (score2 trên Linux, score2.exe trên Windows). Chương trình đọc mô tả trò chơi từ tệp score.in theo định dạng như trang trên. Chương trình sẽ viết thông tin này vào output theo đúng định dạng đó. Output có thể được dùng làm input cho chương trình của bạn với mục đích thử nghiệm. Sau đó, chương trình chơi theo cách ngẫu nhiên đọc các nước đi từ input và viết nước đi của nó vào output.
 
< Trước   Tiếp >