LIB - Literature List

no tags 

In separate lines of a file you are given the titles of publications, written in lower-case letters. With nothing at your disposal but the Brainf**k language, write a converter from this style of naming to a format in which the first letter of each word is upper-case and a title ends with a dot.

The Brainf**k language consists of eight commands, listed below. A Brainf**k program is a sequence of these commands, possibly interspersed with other characters (which are ignored). The commands are executed sequentially, except as noted below.

The Brainf**k language uses a simple machine model which (apart from the executed code) consists of an array of 32,768 int32 cells initialized to zero, a movable pointer to an array cell (initialized to point to the leftmost cell of the array), and two streams of ints for input and output (most often connected to a keyboard and a monitor respectively, and using the ASCII character encoding).

The eight language commands, each consisting of a single character, are the following :
'>' : increment the pointer (to point to the next cell to the right).
'<' : decrement the pointer (to point to the next cell to the left).
'+' : increment (increase by one) the byte at the pointer.
'-' : decrement (decrease by one) the byte at the pointer.
',' : accept one byte of input (stdin), storing its value in the byte at the pointer.
'.' : output (to stdout) the value of the byte at the pointer.
'[' : jump forward to the command after the corresponding ']' if the byte at the pointer is zero.
']' : jump back to the command after the corresponding '[' if the byte at the pointer is nonzero.

Brainf**k programs can be translated into C using the following interpreter:

The program should be as small as possible of course.


t – the number of lines [10 <= t <= 99]. In each of the following t lines there is one publication title consisting of several words (length of a line <= 1000 symbols, length of a word <= 40). Each line ends with the ASCII symbol '\n' = 10. Publication names consist of lower-case letters: 'a'-'z' and space: ' '.


Each publication title should be placed in a separate line. Each word of the publication title should begin with an upper-case letter and there should be a dot at the end of the publication title.


The score of the program is inversely proportional to its source size, i.e. score = 100/(1+R), where R stands for the source code size in bytes (only Brainf**k commands are counted, all other characters are ignored).


joint power management of memory and disk
instruction scheduling for dynamic hardware configuration
hierarchical variance analysis for analog circuits based on graph modeling
lifetime modeling of a sensor network
symmetric multiprocessing on programmable chips made easy
a time slice based scheduler model for system level design

Joint Power Management Of Memory And Disk.
Instruction Scheduling For Dynamic Hardware Configuration.
Hierarchical Variance Analysis For Analog Circuits Based On Graph Modeling.
Lifetime Modeling Of A Sensor Network.
Symmetric Multiprocessing On Programmable Chips Made Easy.
A Time Slice Based Scheduler Model For System Level Design.

hide comments
Mitch Schwartz: 2014-05-27 18:55:33

@to_test: The previous interpreter used 32-bit cells as well, and I'm pretty sure the program "-[-]" would have timed out back then. (Someone actually asked about the compiler options here and received a reply, but I don't think there are any options that would have made a difference for that.) It's not possible to "revert" to something that was never used. Also, the first part of my previous comment isn't relevant anymore, since it was about possible unfairness competing against Alex Gevak's score.

You can test your BF programs on ideone, which uses the same interpreter as SPOJ, or by downloading it from the author's website (!/bff ).

Last edit: 2014-05-27 22:01:19
to_test: 2014-05-27 10:09:44

could you not revert to the previous compiler, [-] gives me TLE every time.

An interpreter such as at

Mitch Schwartz: 2012-08-05 08:53:40

Based on the problem description and some forum posts, Thomas Cort's BF2C was used on SPOJ when the problem was published, but now clearly Alex Pankratov's bff is used, and I've had trouble determining whether this is an issue. The problem is that BF2C relies on GCC version and compiler options, so for example it's tough to say how a program like "-[-]" would have run when the problem was published. As far as I can tell, my current best solution would NOT have gotten AC at that time, and it may be possible that some old AC solutions wouldn't get AC now, so this is potentially an issue.

If the problem setter is still available, a comment addressing this would be appreciated.

Clarification on how the judge handles whitespace in output would also be nice; from what I remember, it's something like: program's output is compared with judge output on a line by line basis, and program output for any particular line must match judge output character-for-character except that trailing whitespace is allowed, and arbitrary extra whitespace is also allowed at the end of the program output. But making experiments is annoying, and I can't see why the standard "ignores extra whitespaces" judge wasn't used in the first place.

Last edit: 2012-08-05 12:08:33
Jared Deckard: 2012-01-31 01:55:21


Mitch Schwartz: 2012-01-30 08:17:46

Be careful: the judge for this problem is somehow strict regarding whitespace in output. I don't know the exact details because it requires too many experiments.

blashyrkh: 2011-06-28 13:06:49

Local link to bf2c.c is invalid

Added by:Roman Sol
Time limit:0.100s
Source limit:20000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:ZCon 2006