当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1957:A number game

题目描述
The wide dissemination of calculators and computers is not without disadvantages. Teachers all over the world find out that even students in technical disciplines tend to have a surprising lack of calculating ability. Accustomed as they are to the use of calculators and computers, many of them are unable to make calculations like 7*8 mentally, or to factor 91 by heart.

We all know, but who cares?

Professor Bartjens cares. Professor Bartjens is a bit old-fashioned. He decided to give his students some training in calculating without electronic equipment - even without a slide rule. He invented a two-person game involving mental calculations.

Professor Bartjens would write a positive number on the blackboard. During the game more positive numbers may appear on the blackboard. The two players will then make moves in turn. A player on move is obliged to make a move, unless the blackboard is empty, in which case the game
is over. A move is one of the following:
--If you see the number 1 on the blackboard, you may take it. That means: you gain one point,and the number disappears from the blackboard.
--If you see a prime number p on the blackboard, you may subtract one. That is: you gain one point, and the p on the blackboard is replaced by p -1.
--If you see a composite number c on the blackboard, you may replace it by two smaller (positive) numbers, a and b, such that a * b = c. You do not gain any points.

The goal is of course to obtain as many points as you can.

Professor Bartjens was hoping that his students would find the game so interesting that they would spend all day playing, thereby improving their skills in calculation. Indeed his students did find the game interesting, and spent many hours, not so much playing the game as discussing optimal strategies.
The students came to two conclusions. First, the sum of the two players' points after any given game are the same regardless of the actual scheme played. Thus," a player maximising his own points also minimises his opponent's! Second, it is always best to take a point when you have the
chance. Thus, whenever prime numbers or ones are written on the blackboard, the player on move takes one of them.

Here is your problem: given a starting number, and assuming both players play to maximise their own points, what will be the outcome?
输入解释
On the first line of the input is a single positive integer n, telling the number of test scenarios to follow. Each scenario consists of a single line containing the positive integer m<1000000, the number initially written on the blackboard.
输出解释
For each test scenario, output one line containing two numbers separated by one space character, equal to the points gained by the two players, both playing to maximise their own points. The first number is the number of points gained by the first player.
输入样例
6
1
2
3
4
5
6
输出样例
1 0
1 1
2 1
2 2
3 2
2 3
来自杭电HDUOJ的附加信息
Recommend wangye

该题目是Virtual Judge题目,来自 杭电HDUOJ

题目来源 NWERC2003

源链接: HDU-1957

最后修改于 2020-10-25T22:49:16+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
5000/1000MS(Java/Others) 65536/32768K(Java/Others)