Codeforces April Fools Day Contest 2014（附官方题解）

本文主要是介绍Codeforces April Fools Day Contest 2014（附官方题解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Codeforces2014年愚人节的坑题。。。但还是感觉挺好玩的。。。
A. The Great Game

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Two teams meet in The Game World Championship. Some scientists consider this game to be the most intellectually challenging game in the world. You are given two strings describing the teams' actions in the final battle. Figure out who became the champion.

Input

The input contains two strings of equal length (between 2 and 20 characters, inclusive). Each line describes the actions of one team.

Output

Output "TEAM 1 WINS" if the first team won, "TEAM 2 WINS" if the second team won, and "TIE" if there was a tie.
Sample test(s)
input
[]()[]8<
8<[]()8<
output
TEAM 2 WINS
input
8<8<()
[]8<[]
output
TIE
类似于剪刀石头布

AC代码如下：
#include <cstdio>
#include <cstring>int main() {char a[21], b[21];scanf("%s%s", a, b);int cnt1 = 0, cnt2 = 0;int len = strlen(a);for (int i = 0; i < len; i += 2) {if (a[i] == '8') {if (b[i] == '[') {cnt1++;} else if (b[i] == '(') {cnt2++;}} else if (a[i] == '[') {if (b[i] == '(') {cnt1++;} else if (b[i] == '8') {cnt2++;}} else if (a[i] == '('){if (b[i] == '8') {cnt1++;} else if(b[i] == '[') {cnt2++;}}}if (cnt1 > cnt2) {printf("TEAM 1 WINS\n");} else if (cnt1 < cnt2) {printf("TEAM 2 WINS\n");} else {printf("TIE\n");}return 0;
}
B. Mysterious Language

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

You are given a mysterious language (codenamed "Secret") available in "Custom Invocation" tab. Figure out what this language is and write a program which prints its name. Note that the program must be written in this language.

Input

This program has only one test (your program doesn't have to read anything).

Output

Output the name of the mysterious language. Note that the name is case-sensitive and might contain digits and special characters.

Sample test(s)

Note

Some scientists disagree on what should be considered as a language and what should be considered as a dialect.

看完AC代码已哭瞎，题中所指的Mysterious Language是Fortran，根本没听说过有木有！。。。

AC代码如下：
       print*, 'FORTRAN 77'END
C. Magnum Opus

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Salve, mi amice.

Et tu quidem de lapis philosophorum. Barba non facit philosophum. Labor omnia vincit. Non potest creatio ex nihilo. Necesse est partibus.

Rp:

    I Aqua Fortis

    I Aqua Regia

    II Amalgama

    VII Minium

    IV Vitriol

Misce in vitro et æstus, et nil admirari. Festina lente, et nulla tenaci invia est via.

Fac et spera,

Vale,

Nicolas Flamel

Input

The first line of input contains several space-separated integers a_i (0 ≤ a_i ≤ 100).

Output

Print a single integer.
Sample test(s)
input
2 4 6 8 10
output
1
题目内容是一名炼金术师Nicolas Flamel用拉丁文写的炼制某物质的配方，所以题中给出了要炼制一单位某东西需要五种物质的量分别为I(1)、I(1)、II(2)、VII(7)、IV(4)，问最多能制造多少单位的这种物质。

AC代码如下：
#include <cstdio>int main() {int a[5];for (int i = 0; i < 5; ++i) {scanf("%d", &a[i]);}a[2] /= 2;a[3] /= 7;a[4] /= 4;int MIN = a[0];for (int i = 1; i < 5; ++i) {if (MIN > a[i]) {MIN = a[i];}}printf("%d\n", MIN);return 0;
}
D. Big Data

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Little Petya wanted to give an April Fools Day present to some scientists. After some hesitation he decided to give them the array that he got as a present in Codeforces Round #153 (Div.2). The scientists rejoiced at the gift and decided to put some important facts to this array. Here are the first few of the facts:

The highest mountain above sea level in the world is Mount Everest. Its peak rises to 8848 m.
The largest board game tournament consisted of 958 participants playing chapaev.
The largest online maths competition consisted of 12766 participants.
The Nile is credited as the longest river in the world. From its farthest stream in Burundi, it extends 6695 km in length.
While not in flood, the main stretches of the Amazon river in South America can reach widths of up to 1100 km at its widest points.
Angel Falls is the highest waterfall. Its greatest single drop measures 807 m.
The Hotel Everest View above Namche, Nepal — the village closest to Everest base camp – is at a record height of 31962 m
Uranium is the heaviest of all the naturally occurring elements. Its most common isotope has a nucleus containing 146 neutrons.
The coldest permanently inhabited place is the Siberian village of Oymyakon, where the temperature of -68°C was registered in thetwentieth century.
The longest snake held in captivity is over 25 feet long. Its name is Medusa.
Colonel Meow holds the world record for longest fur on a cat — almost 134 centimeters.
Sea otters can have up to 10000 hairs per square inch. This is the most dense fur in the animal kingdom.
The largest state of USA is Alaska; its area is 663268 square miles
Alaska has a longer coastline than all of the other 49 U.S. States put together: it is 154103 miles long.
Lake Baikal is the largest freshwater lake in the world. It reaches 1642 meters in depth and contains around one-fifth of the world’s unfrozen fresh water.
The most colorful national flag is the one of Turkmenistan, with 106 colors.

Input

The input will contain a single integer between 1 and 16.

Output

Output a single integer.
Sample test(s)
input
1
output
1
input
7
output
0
题的内容和题目完全不沾边，都是吓唬人的。这道题是判断上面的几个说法是否正确，正确输出“1”，反之输出“0”。

AC代码如下：
#include <cstdio>char s[] = "1001010111001010";
int main() {int n;scanf("%d", &n);printf("%c\n", s[n-1]);return 0;
}
F. 000001

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Input

The input contains a single integer a (1 ≤ a ≤ 64).

Output

Output a single integer.
Sample test(s)
input
2
output
1
input
4
output
2
input
27
output
5
input
42
output
6
题目描述过于简单，唯一的线索就是题目000001。其实000001是oeis网站上第一个数字序列，名为Number of groups of order n，即n阶群数目。只需要打开网站找到A000001序列即可得到本题的答案。

AC代码如下：
#include <cstdio>int a[]={1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51,1,2,1,14,1,2,2,14,1,6,1,4,2,2,1,52,2,5,1,5,1,15,2,13,2,2,1,13,1,2,4,267};int main() {int n;scanf("%d", &n);printf("%d\n", a[n-1]);return 0;
}
H. A + B Strikes Back

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

A + B is often used as an example of the easiest problem possible to show some contest platform. However, some scientists have observed that sometimes this problem is not so easy to get accepted. Want to try?

Input

The input contains two integers a and b (0 ≤ a, b ≤ 10³), separated by a single space.

Output

Output the sum of the given integers.
Sample test(s)
input
5 14
output
19
input
381 492
output
873
又一道神坑题，没窍门，改改输出格式多交几遍就过了，代码Pass。。。

附官方题解：

April Fools Day Contest 2014: editorial

Unfortunately, the most anybody could solve was 7 problems out of 9 total. 1289 participants solved at least one problem — this is less than the last year's numbers, but not bad either. Anyways, the key point is the total quantity of fun the people had!

409A - The Great Game

The Most Intellectually Challenging Game In The World turned out to be the famous rock-paper-scissors. One could deduce this from the examples — ok, the rock () didn't look itself, but paper [] and especially scissors 8< looked really lifelike!

Team competition is organized like this: players are split into pairs, with one player of each team in each pair, and pairs play against each other (the first line of input has "moves" of first team's players, the second line — of second team's players). The team which scores more individual victories wins.

By the way, the game is not so trivial as it looks — there are big tomes written about the strategies, game ethics and organizing clubs and competitions, the tournaments run in many countries, and the largest tournament had over 6500 participants!

409B - Mysterious Language

Attempting to run nearly any code in Mysterious Language resulted in a pack of compilation errors, among them — "Unclassifiable statement at (1)". This pointed to Fortran language immediately, but then the doubts began. There are quite a few Fortrans out there, and even more compilers, so what exactly needs to be printed out? My idea was that the compiler should have been configured to accept only fixed format of Fortran programs, which points to FORTRAN 77 (Fortran 90 and later supported free format, without uppercasing commands and indentation). Judging from the questions and the comments, something went wrong here, and some programs in free format compiled fine... Anyways, the answer is "FORTRAN 77".

409C - Magnum Opus

Magnum Opus is an alchemy name for the process of philosophical stone creation. This (and also the signature "Nicolas Flammel") hints that the problem describes a recipe of the philosophical stone, and our task is to create it. If we recognize the statement as a text in Latin (although there were attempts to interpret is as Italian) and go to Google Translate for help, we can enjoy the literary beauty and deep irony of the letter, in which a mature alchemist shares the secrets of trade with his younger colleague. Or you can neglect the twists and fast forward to solving the problem, if you notice that the input has 5 numbers, and the recipe contains 5 ingredients in given proportion (proportions are given with easily recognizable Roman numbers before the names of ingredients).

Overall the problem asked how much of philosophical stone we can create, if we have given quantities of ingredients and a smoothly running manufacturing procedure. The answer is min(a[0],a[1],a[2]/2,a[3]/7,a[4]/4).

409D - Big Data

A lot of facts with big numbers is not yet big data. Especially if half of them are wrong! The biggest board games tournament had 43 thousand chess players, the math competition — over a million participants, and Colonel Meow, while a gorgeous cat (you can enjoy the photos at Guinness World Records site ), still doesn't feature a meter-long fur!

The problem asked you to figure out the truth of the given facts, and print 1 or 0 depending on whether i-th fact is true or not-so-true.

409E - Dome

This geometry problem (a joke itself :-) ) was described with a single picture: a hemisphere inscribed in a pyramid. An extra kick is that the problem is kind of inverse problem — you are not given the pyramid and asked to find the radius of a hemisphere, but rather given the hemisphere and asked to build a pyramid around it. Fortunately, pyramid parameters height h and base side length a took only integer values from 1 to 10. The easiest way to tackle this was to try all possible pairs of a and h, calculate all radii (as height in a right-angled triangle with sides h and a/2) and check whether the resulting radius is close to the given one. Note that some radii can be obtained from several pyramids.

409F - 000001

Imagine, initially I wanted to put this problem first, and less than 30 people solved it :-) This is a problem writer's dream — a problem without a statement. Given 4 examples, it's rather tricky to guess an int -> int function for 64 input values. More or less evident theories like "the smallest power of 2 greater than or equal to a" turn out to be wrong (the contest discussion has several more elegant but totally wrong ideas).

Two heuristics* help: 1) even if a problem has no statement, it has a name, and 2) any strange function int -> int can be looked for in Online Encyclopedia of Integer Sequences. Combine them, and you'll get a sequence http://oeis.org/A000001. To solve the problem you don't even have to figure out what "groups of order n" are — the first 64 elements of the sequence are given in the article about it.

Note that using a third heuristic (even if a problem has no statement, it has the constraints) is misleading in this case.

409G - On a plane

This problem was written by Skiminok; I'm quite a trickster myself, but I wouldn't have dreamed of giving the statement in samples. And not just giving it; the points from each sample had to be plotted on a 2D plane to get a picture like this

and read from it the statement: 5 + AVG Y (each sample represented one letter).

409H - A + B Strikes Back

This problem caused plenty of emotions and questions "how can it be, I had correct answers for the pretests, and the submission fails the very first test?". See, today is April 1st, and even the checker might feel a bit playful today. For example, it might refuse to accept the solution, and it will require some persuasion for it to stop being naughty. The authors' idea was to reject the first five attempts on the problem right away, and to start actually checking the submissions only starting with the 6th attempt. I do hope that it looked like this from participants' point of view :-)

409I - Feed the Golorp

This problem was contributed by kit1980.

Golorp's name (have anyone noticed that "golorp" is "prolog" spelled backwards?) is an expression in Prolog. The jaws (left part up to ":-") contains the list of variables (possibly with repetitions) separated by arithmetic characters. The characters are just separators and have no deep meaning, they can be replaced with commas. The stomach (right part after ":-") lists the inequalities that must hold for the variables from the jaws.

The task is to find lexicographically smallest set of variable values which satisfy the constraints. In fact, you have to perform topological sorting. The easiest way is to iterate infinitely through the inequalities, find the ones which are not satisfied yet and increase the value of the variable which must be greater than the other one in it. As soon as one of the variables grows to be 10, the answer is false. Otherwise we will stop when all inequalities are satisfied. With the given constraints the solution is fast enough.