《2001年第13届国际信息学奥赛试题》由会员分享，可在线阅读，更多相关《2001年第13届国际信息学奥赛试题（73页珍藏版）》请在金锄头文库上搜索。
1、 2001年第13届国际信息学奥赛试题解析芬 兰第一题 Ioiwari 游戏Ioiwari GameDay 1. Source file ioiwari. *Available memory: 32MB. Maximum running time: 1s.Problem:The Mancala family of games with beads and pits is among the oldest forms of human entertainment. This task introuduces a version of the game especially developed f
2、or the IOI. The game is played by two players on a round board with seven pits around the edge. In addition, there is a bank for each player. The game begins by randomly distributing 20 beads into the pits so that each pit contains at least 2 and at most 4 beads. The two players move alternately. To
3、 move, the player chooses a non-empty pit and takes all beads out of the pit, and holds them in her hand. As long as there are beads in the players hand, she considers the pits in clockwise order, starting one after the emptied one, and performs the following operations:More than one bead in your ha
4、nd: If the current pit already contains 5 beads , then take one bead out of the current pit and place it into your bank, otherwise place one bead from your hand into the current pit.One bead in your hand: If the current pit contains at least one and at most four beads then move all beads from the pi
5、t and the one from your hand into your bank, otherwise(the pit contains 0 or 5 beads)place the bead in your hand into the opponents bank.The game is over when all pits are empty and the winner is the player with most-beads in her bank.The starting player always has a winning strategy. You are to wri
6、te a program, which plays Iloiwari as the starting player and wins. The evaluation opponent plays optimally, that is, once given a chance, it will win and your program will lose.Input and output:Your program reads input from standard input and writes output to standard output. Your program is player
7、 1, and the opponent is player 2. When your program is started, it must first read a line with 7 integers p1, . p7, the initial number of beads in pits 1, .7, respectively. The pits are labeled with integers from 1 to 7 in clockwise direction on the board. After this ,the game starts with empty bank
8、s, Your program should play as follows:If it is your programs turn to move, then your program should write the label of the pit describing the move to standard outputIf it is your programs opponents turn to move, then your program should read the label of the pit defining the move(the pit from which
9、 the beads are removed) from standard input.Tools:You are given a program(ioiwari2 on Linux, ioiwari2, exe on Windows), which plays from one initial game position optimally as Player2. It will first write to standard output the first line your program is supposed to read, describing the initial valu
10、es of beads in that game: 4 3 2 4 2 3 2 After this, the program will play the game, trying to read Player 1s move from standard input and writing its own moves to standard output. You can run your program and ioiwari2 in separate windows and transfer the conversation manually to both programs. ioiwa
11、ri2 records the dialogue in the file ioiwari. Outprogramming instructions:In the examples below, you are reading the last integer of the input into variable last and the variable, mymove contains your move.If you program in C+ and use iostreams, you should use the following implementation for readin
12、g standard input and writing to standard output:cout mymove endl last;If you program in C or C + + and use scanf and printf, you should use the following implementation for reading standard input and writing to standard output:Printf (“%dn”, mymove); fflush(stdout);Scanf (“%d”, & last);If you progra
13、m in Pascal, you should use the following implementation of reading standard input and writing to standard output:Writeln(mymove); Readln(last);Example:Here is a correct sequence of 6 movesPit and bank contents after the operationOperation/Pit ladel1.2.3.4.5.6.7.Bank1Bank2Initial situaion432423200Pl
14、ayer 1s move:2403503230Player 2s move:3400414034Player 1s move:5400400084Player 2s move:4000011189Player 1s move:50000001109Player 2s move:70000000119Scoring:If your program wins a test run, then you get 4 points for that test, a tie in a test gives you 2 points for that test, and otherwise you get
15、0 points for a test.参考译文：Ioiwari 游戏（Day 1 文件名:ioiwari. *内存限制：32MB时间限制1s）问题描述由小珠与小洞（小格）构成的Mancala游戏家族是人类娱乐中最古老的形式之一。该题目采用了一个特别为IOI所开发的游戏版本。游戏由两个参赛者在一张有7个小洞环绕边缘的圆板上进行。此外，每个参赛者各有一个仓库。游戏开始时将20颗小珠随机放在小洞里，每个洞最少有2颗且最多有4颗小珠。两个参赛者轮流走子。走子开始时，参赛者先选择一个非空的洞，并把洞内的所有小珠全取出来放在手中，然后从清空了的小洞按顺时针方向的下一个小洞开始，按以下规则不断进行取珠和放珠的操作（总是按顺时针方向选下一个小洞），直到手中无珠为止。当手中小珠的个数大于1时：如果当前的小洞已经有5个小珠，则从其中取走一个，并把它放进自己的仓库中；否则从自己手中取出一个小珠放进当前的小洞里。当手中小珠的个数等于1时：如果当前的小洞有最少1个且最多4个小珠，则把洞里所有小珠取出再加上自己手里的一个小珠全部放进自己的仓库；否则（洞里小珠的个数等于0或等于5），把
