Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: IOI's 1992 Problems
发信站: 哈工大紫丁香 (2002年03月29日13:18:51 星期五), 站内信件

IOI'92 Problems - Bonn, Germany, July 1992
TASK 4.1.1: "MYSTERIOUS CONTINENTS"
===================================
A MAP is a 48 by 16 rectangle of COORDINATES. Two coordinates are
CONNECTED if they are neighbours either in south-north or in east-west
direction. Initially each coordinate is only known to be either WATER
(W) or GROUND (G).
There are four GROUND TYPES (GT): G, M, P, and C.
And there are four WATER TYPES (WT): W, O, B, and L.
It is assumed that outside the map there is OCEAN (O).
There are certain geographic rules for changing the type of a
coordinate (RELABELING). It may become a:
- MOUNTAIN (M): If a GT is connected to 4 other GT.
- PENINSULA (P): If a GT is connected to 3 WT,
or to 2 WT and at least 1 P,
or to 1 WT and at least 2 P.
- COASTLINE (C): If a GT is not M and not P.
- OCEAN (O): If a WT is connected to at least one O.
- BAY (B): If an O is connected
to at least 2 B and at most one O,
or to 1 B and at least 2 GT,
or to at least 2 GT and at least one O.
- LAKE (L): If a W remains unchanged till no other relabeling is
possible any more.
It may happen, that after a certain coordinate has been relabeled,
it can be relabeled once again later, because the types of some
neighbours have changed in the meantime.
A map is EXPLORED if no relabeling is possible any more.
PROBLEM STATEMENT
=================
Implement a program which does the following in that order:
1. Read a map of an unknown continent from an ASCII input file and
display it on the screen, together with the initial coordinate
type statistics, as shown in Example-1.
2. Explore the map and relabel the coordinates correctly with
M, P, C, O, B, or L according to the geographic rules.
3. Display the explored map on the screen, with the final coordinate
type statistics, as shown in Example-2.
4. Write a screen copy showing the explored map and the final
coordinate type statistics to an ASCII output file.
TECHNICAL CONSTRAINTS
=====================
Constraint-1: Put your solution program into an ASCII text file named
"C:\IOI\DAY-1\411-PROG.xxx". Extension .xxx is:
- .BAS for BASIC programs, .C for C programs,
- .LCN for LOGO programs, .PAS for PASCAL programs.
Constraint-2: The name of the ASCII input file for reading an unknown
map from must be "C:\IOI\DAY-1\411-MAP.IN".
Constraint-3: The name of the ASCII output file for writing explored
map and statistics to must be "C:\IOI\DAY-1\411-MAP.OU".
EXAMPLE(S)
==========
Example-1: The screen display, including initial statistics, of the
unknown map in file "C:\IOI\DAY-1\411-MAP.IN" should look like:
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWGGGGGGWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWGGWWGGWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWGGGWGGWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWGGWWGGWWWGGGWGWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWGGGGGGGGGGGGGWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWGGGWWWGGWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWGGGWWWGGWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWGGGGWWGGWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWGGWWWGGWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWGWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWGWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWGGGWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
MYSTERIOUS: G=61 W=707 ALL=768
Example-2: The screen display of the explored map, including final
statistics and the file "C:\IOI\DAY-1\411-MAP.OU" should look like:
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOCCCCCCOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOCCLLCCOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOCMPLCCOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOCCLLCCBBBCCCBPOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOBCCCCCCCCMCCCCBOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOBCMCBBBCCOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOCMCBOOCCOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOCMMPOOCCOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOBCCBOOCCOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOBPBOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOBPBOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOPPPOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
EXPLORED: P=8 C=47 M=6 O=685 B=17 L=5 ALL=768
SAMPLE FILES
============
We provided these correct example files for your convenience:
"C:\IOI\DAY-1\411-MAP.IN" and "C:\IOI\DAY-1\411-MAP.OU".
WARNING: Successful execution of your program with Example-1 above
does not necessarily guarantee that your program is correct !!!
CREDITS
=======
Read from a file and display unknown map correctly ......... 5 points
All Mountains correctly relabeled with M ................... 10 points
All Peninsulas correctly relabeled with P .................. 20 points
All Coastlines correctly relabeled with C .................. 5 points
All Ocean correctly relabeled with O ....................... 10 points
All Bays correctly relabeled with B ........................ 20 points
All Lakes correctly relabeled with M ....................... 5 points
Initial Statistics correct ................................. 5 points
Final Statistics correct ................................... 10 points
Structure of output file correct ........................... 5 points
Technical constraints completely obeyed .................... 5 points
----------------------------------------------------------------------
maximal 100 points
TASK 4.1.2: "A MAZING WORKSHOP"
===============================
A MAZE completely covers an AREA of N times M squares. It consists
of many WALL squares and of many SPACE squares, the latter of which
include one ENTRY square and one TREASURE square.
A PATH is a sequence of adjacent space squares (bounded by walls) from
the entry to a dead end, we refer to as an ENDPOINT. The LENGTH of a
path is the number of squares it covers, including entry and endpoint.
The maze must be such that paths may fork but do not join, so for
example no two paths can have the same endpoint. The entry is located
somewhere at the top of the maze. The treasure is positioned at the
endpoint of a path with maximal length.
The N times M area should be covered with paths as much as possible.
It is nice to watch a maze growing over an area while it is computed.
Because the algorithm is too fast for the eye, a DELAY TIME after
each drawn square is necessary.
PROBLEM STATEMENT
=================
Implement the following set of TOOLS dealing with mazes. The tools
should be executable in any order and repetition through a main menue:
Tool-1: Set the main maze parameters N and M interactively.
Tool-2: Set a DELAY TIME interactively.
Tool-3: Compute a new correct maze basically using a random
generator and display the maze while it is growing.
Tool-4: Write a generated maze and its size parameters to an
ASCII text file, exactly as it is shown in Example-2.
Tool-5: Read an unknown maze from an ASCII text file
and highlight the path from entry to treasure.
TECHNICAL CONSTRAINTS
=====================
Constraint-1: Represent each square by a two-character string:
- walls by two times ASCII character #219 ...... "[["
- paths and entry by two blanks ................ " "
- treasure by T and blank ...................... "T "
- highlighted paths by full-stop and blank ..... ". "
Constraint-2: N and M must be greater than 2 and not larger than 20.
Constraint-3: Put your solution program into an ASCII text file named
"C:\IOI\DAY-1\412-PROG.xxx". Extension .xxx is:
- .BAS for BASIC programs, .C for C programs,
- .LCN for LOGO programs, .PAS for PASCAL programs.
Constraint-4: The name of the ASCII text file for reading and writing
mazes must be "C:\IOI\DAY-1\412-MAZE.IO".
EXAMPLE(S)
==========
Example-1: A screen display of sample file "C:\IOI\DAY-1\412-MAZ1.IO"
by Tool-5 should look like:
N = 10, M = 8, DELAY TIME = 100
[[[[[[[[[[[[. [[[[[[
[[[[[[ . . [[ [[
[[[[ [[. [[ [[
[[ [[ . . [[ [[
[[ [[ [[. . [[
[[[[ [[ [[. [[[[
[[ [[T . . . [[
[[[[[[[[[[[[[[[[[[[[
LENGTH = 13
Example-2: The same maze's file output by Tool-4 should look like:
10 8
[[[[[[[[[[[[ [[[[[[
[[[[[[ [[ [[
[[[[ [[ [[ [[
[[ [[ [[ [[
[[ [[ [[ [[
[[[[ [[ [[ [[[[
[[ [[T [[
[[[[[[[[[[[[[[[[[[[[
SAMPLE FILES
============
We provided these correct example files for your convenience:
"C:\IOI\DAY-1\412-MAZ1.IO" and "C:\IOI\DAY-1\412-MAZ2.IO".
WARNING: Successful execution of your program with these examples
does not necessarily guarantee that your program is correct !!!
CREDITS
=======
Main menue with all tools available ........................ 5 points
Tools available in any order and repetition ................ 10 points
Tool-1 enables setting N and M ............................. 5 points
Tool-2 enables setting DELAY TIME .......................... 5 points
Tool-3 computes structurally correct mazes ................. 30 points
Tool-3 displays the maze while it is growing ............... 10 points
Tool-4 writes maze to a file exactly as in example-2 ....... 5 points
Tool-5 reads unknown maze and highlights longest path ...... 20 points
Technical constraints completely obeyed .................... 10 points
----------------------------------------------------------------------
maximal 100 points
Problem Chosen for the first session ( 5 hours )
***TASK 4.1.3 "ISLANDS IN THE SEA"
===============================
The SEA is represented by an N times N grid. Each ISLAND is a "*" on
that grid. The task is to reconstruct a MAP of islands only from some
CODED INFORMATION about the horizontal and vertical distribution of
the islands. To illustrate this code, consider the following map:
* * * 1 2
* * * * 3 1
* * * 1 1 1
* * * * * 5
* * * * 2 1 1
* 1
1 1 4 2 2 1
1 2 3 2
1
The numbers on the right of each row represent the order and size of
the groups of islands in that rows. For example, "1 2" in the first
row means that this row contains a group of one island followed by a
group of two islands; with sea of arbitrary length to the left and
right of each island group. Similarly, the sequence "1 1 1" below the
first column means that this column contains three groups with one
island each, etc.
PROBLEM STATEMENT
=================
Implement a program which repeats the following steps until a given
input file containing several information blocks has been read
completely:
1. Read the next information block from an ASCII input file
(for the data structure of that file see also the examples below)
and display it on the screen.
Each information block consists of the size of the square grid,
followed by the row constraints and the column constraints. Each
constraint for a single row or column appears on a single line as
a sequence of numbers separated by spaces and terminated by 0.
2. Reconstruct the map (or all of the maps, if more then one solution
is possible, see Example-4) and display it/them on the screen.
3. Write the map(s) to the end of an ASCII output file. Each blank
must be represented by a pair of spaces. Each island should be
represented by a '*' followed by a space. Different maps satisfying
the same constraints should be separated by a blank line. If there
is no map satisfying the constraints, indicate it by a line saying
"no map". The solutions to the different information blocks must be
separated by a line saying "next problem".
TECHNICAL CONSTRAINTS
=====================
Constraint-1: N must be not less than 1 and not larger than 8.
Constraint-2: Put your solution program into an ASCII text file named
"C:\IOI\DAY-1\413-PROG.xxx". Extension .xxx is:
- .BAS for BASIC programs, .C for C programs,
- .LCN for LOGO programs, .PAS for PASCAL programs.
Constraint-3: The name of the ASCII input file for reading the coded
information from must be "C:\IOI\DAY-1\413-SEAS.IN".
Constraint-4: The name of the ASCII output file for writing the
map(s) to must be "C:\IOI\DAY-1\413-SEAS.OU".
EXAMPLE(S)
==========
6 Example-1 (the problem above): 6 is the size of the grid.
1 2 0 <-- The start of the first line constraint
3 1 0
1 1 1 0
5 0
2 1 1 0
1 0
1 1 1 0 <-- The start of the first column constraint
1 2 0
4 0
2 3 0
2 0
1 2 0
4 Example-2. Solution: columns: 1 2 3 4
0 row 1:
1 0 row 2: *
2 0 row 3: * *
0 row 4:
0
1 0
2 0
0
2 Example-3. Note that there is no map
0 satisfying the constraints.
0
2 0
2 0
2 Example-4. Note that there are two different maps
1 0 satisfying the constraints.
1 0
1 0
1 0
SAMPLE FILES
============
We provided these correct example files for your convenience:
"C:\IOI\DAY-1\413-SEAS.IN" and "C:\IOI\DAY-1\413-SEAS.OU".
WARNING: Successful execution of your program with these examples
does not necessarily guarantee that your program is correct !!!
CREDITS
=======
Read an information block from
the input file and display it .............................. 5 points
Process all information blocks one by one
until the input file is read completely .................... 10 points
Reconstruct one map for each information
block (if it has a solution) and display it ................ 35 points
Write the solution map to the output file .................. 5 points
Reconstruct all possible maps (if there
are several solutions) and display them .................... 20 points
Write all solution maps correctly
separated to the output file ............................... 10 points
Identify information blocks having no solution ............. 5 points
Technical constraints completely obeyed .................... 10 points
----------------------------------------------------------------------
maximal 100 points
Second Session Problems
TASK 4.2.1: "HAMILTON'S ROBOT"
==============================
On a plane there are given N positions P1, P2, ..., PN with
integer coordinates (X1,Y1), (X2,Y2), ..., (XN,YN).
A robot should move through all these positions starting at P1.
It should come to each position only once with the exception of P1
which also has to be the position at the end of the tour.
There are constraints on the robot's movements. It can only move along
straight lines. From P1 it can start in any direction. Reaching
one of the Pi, before moving on to another position it must turn
90 degrees either to the left or to the right.
A robot program consists of five types of statements:
1. "ORIENTATION Xk Yk": usable as the first statement only.
The robot turns to the direction of the
position Pk (k between 2 and N).
2. "MOVE-TO Xj Yj" : if the robot can reach Pj without changing its
current orientation, then it moves to the
position Pj (j between 1 and N).
Otherwise the statement is not executable.
3. "TURN-LEFT" : the robot changes its orientation
90 degrees to the left.
4. "TURN-RIGHT" : the robot changes its orientation
90 degrees to the right.
5. "STOP" : deactivates the robot. This is the necessary
last statement of each robot program.
PROBLEM STATEMENT
=================
Implement a program that does the following:
1. Read the value of N and the coordinates for N given positions
from an ASCII input file (see Example) and display the data on
the screen.
2. Develop a robot program for a valid tour through all positions
(as defined above) if one exists.
3. If there is no possible tour, the robot program
must consist just of the "STOP"-statement.
4. Display on the screen, whether a tour is possible or not and, if there
exists one, its length (rounded, 2 digits after the decimal point).
The length of a tour the sum of the lengths of the straight line
pieces.
5. Write the robot program to an ASCII output
file exactly as is shown in Example.
TECHNICAL CONSTRAINTS
=====================
Constraint-1: Put your solution program into an ASCII text file named
"C:\IOI\DAY-2\421-PROG.xxx". Extension .xxx is:
- .BAS for BASIC programs, .C for C programs,
- .LCN for LOGO programs, .PAS for PASCAL programs.
Constraint-2: The name of the ASCII input file for reading the
positions from must be "C:\IOI\DAY-2\421-ROBO.IN".
Constraint-3: The name of the ASCII output file for writing the robot
program to must be "C:\IOI\DAY-2\421-ROBO.OU".
Constraint-4: Program must reject inputs where N is less than 4 or
greater than 16, without trying to find a tour!
EXAMPLE(S)
==========
Input: An input file contains in the first line the value for
N and in the following N lines the X and Y coordinates
of the selected positions, for example:
4
2 -2
0 2
-1 -1
3 1
Output: For these 4 positions one shortest robot program with
length = 12.65 is:
ORIENTATION 3 1
MOVE-TO 3 1
TURN-LEFT
MOVE-TO 0 2
TURN-LEFT
MOVE-TO -1 -1
TURN-LEFT
MOVE-TO 2 -2
STOP
SAMPLE FILES
============
We provide these correct files with the above input and output for
your convenience:
"C:\IOI\DAY-2\421-ROBO.IN" and "C:\IOI\DAY-2\421-ROBO.OU".
WARNING: Successful execution of your program with this example
does not necessarily guarantee that your program is correct !!!
CREDITS
=======
Read input data correctly from every file and display it.... 5 points
Algorithm for computing a valid tour ok .................... 30 points
Generated robot program syntactically correct,
if tour does not exist .................................. 10 points
Generated robot program syntactically correct,
if tour does exist ...................................... 15 points
Screen display gives all required information .............. 5 points
Displayed length of computed tour correct .................. 10 points
Robot program correctly written to a file .................. 10 points
Technical constraints obeyed ............................... 15 points
----------------------------------------------------------------------
maximal 100 points
Problem Chosen for the second session ( 5 hours )
***TASK 4.2.2: "CLIMBING A MOUNTAIN"
===================================
A mountain climbers club has P members, numbered from 1 to P. Every
member climbs at the same speed and there is no difference in speed
between climbing up and down. Climber number i consumes C(i) units
of SUPPLIES per day and can carry at most S(i) such units. All C(i)
and S(i) are integer numbers.
Assume that a climber with a sufficient amount of supplies would need
N days to reach the top of the mountain. The mountain may be too high,
so that a single climber cannot carry all the necessary supplies.
Therefore a GROUP of climbers starts at the same place and at the same
time. A climber who descends prematurely before reaching the top gives
his unneeded supplies to other climbers. The climbers do not rest
during the expedition.
The PROBLEM is to plan a schedule for the climbing club. At least one
climber must reach the top of the mountain and all climbers of the
selected group return to the starting point.
PROBLEM STATEMENT
=================
Implement a program which does the following:
1. Read from the keyboard the integer number N of days needed to
arrive at the top, the number P of climbers in the club, and
(for all i from 1 to P) the numbers S(i) and C(i).
You may assume that the inputs are integers.
Reject inputs that make no sense.
2. Try to find a schedule for climbing the mountain. Determine a
possible group a(1), ..., a(k) of climbers who should
participate in the party and (for all j from 1 to k) the number
M(j) of supplies which climber a(j) carries at the start.
Note that there may not exist a schedule for all combinations
of N and the S(i) and C(i).
3. Output the following information on the screen:
a) the number k of climbers actually participating in the party,
b) the total amount of supplies needed,
c) the climber numbers a(1), .., a(k),
d) for all a(j), j between 1 and k, the
initial amount M(j) of supplies to carry for climber a(j),
e) the day D(j) when climber a(j) starts descending.
4. A schedule is OPTIMAL if
a) the number of participating climbers is minimal and
b) among all groups satisfying condition a) the total of consumed
supplies is minimal.
Try to find a nearly optimal schedule.
TECHNICAL CONSTRAINTS
=====================
Constraint-1: Put your solution program into an ASCII text file named
"C:\IOI\DAY-2\422-PROG.xxx". Extension .xxx is:
- .BAS for BASIC programs, .C for C programs,
- .LCN for LOGO programs, .PAS for PASCAL programs.
Constraint-2: Programs must reject inputs where N is less than 1 or
greater than 100. P must be not less than 1 and not
greater than 20.
EXAMPLE(S)
==========
The following could be a dialogue with your program:
Days to arrive to top: 4
Number of club members: 5
Maximal supply for climber 1 : 7
Daily consumption for climber 1 : 1
Maximal supply for climber 2 : 8
Daily consumption for climber 2 : 2
Maximal supply for climber 3 : 12
Daily consumption for climber 3 : 2
Maximal supply for climber 4 : 15
Daily consumption for climber 4 : 3
Maximal supply for climber 5 : 7
Daily consumption for climber 5 : 1
2 climbers needed, total amount of supplies is 10.
Climber(s) 1, 5 will go.
Climber 1 carries 7 and descends after 4 day(s)
Climber 5 carries 3 and descends after 1 day(s)
Plan another party (Y/N) Y
Days to arrive to top: 2
Number of club members: 1
Maximal supply for climber 1 : 3
Daily consumption for climber 1 : 1
Climbing party impossible.
Plan another party (Y/N) N
Good bye
SAMPLE FILES
============
For your convenience, some files containing test data and correct
sample output have been prepared; please look into the directory
"C:\IOI\DAY-2".
WARNING: Successful execution of your program with these examples
does not necessarily guarantee that your program is correct !!!
CREDITS
=======
User dialogue as illustrated above.......................... 10 points
Find a solution for the special case where all C(i)=1 and
all S(i) are equal ...................................... 20 points
Find a solution for general case ........................... 20 points
Find a nearly optimal solution for general case ............ 30 points
Detect unsolvable situations ............................... 10 points
Technical constraints obeyed ............................... 10 points
----------------------------------------------------------------------
maximal 100 points
TASK 4.2.3: "RUBIK'S TOOLKIT"
=============================
This problem is based on the puzzle game "Rubik's cube".
If you already know Rubik's cube you may skip this paragraph and the
next one. Rubik's cube is a cube that consists of 3 x 3 x 3 smaller
cubes. Initially each of the six faces of Rubik's cube is coloured
uniformly in a different colour; we call this the initial cube.
Every face of Rubik's cube consists of 3 x 3 faces of a layer of
nine smaller cubes.
Imagine you are looking at any of the six faces of Rubik's cube. The
layer of 3 x 3 smaller cubes you see can be rotated by a multiple of
90 degrees, where the axis of rotation is orthogonal to the face and
goes through its centre. The result is another 3 x 3 x 3 cube where
the colour pattern of the face you are looking at has been rotated
and the colour patterns of the four neighbouring faces have changed.
In our problem the faces of the cube are given names instead of
colours: U=Up, R=Right, F=Front, B=Back, L=Left and D=Down. Any move
sequence to turn the cube may be described as a string of the letters
{U, R, F, B, L, D} where each letter stands for a basic rotation:
the 90 degrees clockwise rotation of the corresponding face.
PROBLEM STATEMENT with EXAMPLE(S)
=================================
Write a program that allows the user to repeatedly solve any of the
given three subproblems in any order. You may assume that the length
of each input string is at most 35.
1. This subproblem is the translation of a given move sequence into
a move sequence where no primitive rotation is applied more than
3 times in sequence. Your algorithm should reject non-legal input
sequences. Some examples are provided for clearness:
Input Output
L --> L
LL --> LL
LLL --> LLL
LLLL --> "the empty sequence"
LLLLL --> L
LLRRRFFFFRLB --> LLLB
HELLO --> "error"
2. The second subproblem is to find out whether two given move
sequences yield the same result when applied to the initial
cube. The examples may illustrate this:
Input, Input, Output
1st sequence 2nd sequence
RL LR yes
RU UR no
RRFFRRFFRRFFRRFF FFRRFFRR yes
RRFFRRFFRRFFRRFF RRFFRRFF no
3. The third subproblem is to determine how many times a given move
sequence has to be applied to the initial cube until the cube is
in its initial state again. The smallest such number greater zero
is sought.
We provide some examples:
Input Output
L 4
DD 2
BLUB 36
RUF 80
BLUFF 180
TECHNICAL CONSTRAINTS
=====================
Constraint-1: Put your solution program into an ASCII text file named
"C:\IOI\DAY-2\423-PROG.xxx". Extension .xxx is:
- .BAS for BASIC programs, .C for C programs,
- .LCN for LOGO programs, .PAS for PASCAL programs.
SAMPLE FILES
============
none
CREDITS
=======
Main menu and user dialogue o.k. ........................... 15 points
Subproblem 1: Transformation o.k. .......................... 20 points
Rejects wrong inputs ......................... 10 points
Subproblem 2: Correctness .................................. 25 points
Subproblem 3: Correctness .................................. 25 points
Technical constraints obeyed ............................... 5 points
----------------------------------------------------------------------
maximal 100 points


--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]