そういえばgoogle code jam 2005
問題をコピペしといたんですが，放置してました．とりあえず置いときます．改行がずれて見づらいこともあるかもしれませんが，我慢してください．
250点問題
Problem Statement
????
You have a collection of music files with names formatted as "genre-artist-album
-song" (quotes for clarity only), where genre, artist, album, and song each cons
ist of only lowercase letters ('a'-'z') and spaces (but no leading/trailing spac
es). The collection is given in the vector <string> collection. You would like t
o filter the songs according to a set of criteria given in the vector <string> f
ilterInfo. Each element of filterInfo is an equality check formatted as "field=v
alue" (quotes for clarity only), where field is "genre", "artist", "album", or "
song", and value consists of only lowercase letters ('a'-'z') and spaces (but no
leading/trailing spaces). For a file to pass through the filter, it must satisf
y every equality check in filterInfo. For example, if filterInfo = {"genre=count
ry", "album=greatest hits"}, only songs from country greatest hits albums should
be returned. Return a vector <string> containing all the files that meet the gi
ven criteria in the same relative order as they appear in collection.
Definition
????
Class:
SongFilter
Method:
filter
Parameters:
vector <string>, vector <string>
Returns:
vector <string>
Method signature:
vector <string> filter(vector <string> collection, vector <string> filterInfo)
(be sure your method is public)
????
Constraints
-
collection will contain between 1 and 50 elements, inclusive.
-
Each element of collection will be formatted as described in the problem stateme
nt.
-
Each element of collection will contain between 7 and 50 characters, inclusive.
-
Each genre, artist, album, and song in collection will contain between 1 and 20
characters, inclusive.
-
collection will contain no duplicate elements.
-
filterInfo will contain between 1 and 4 elements, inclusive.
-
Each element of filterInfo will be formatted as described in the problem stateme
nt.
-
Each value in filterInfo will contain between 1 and 20 characters, inclusive.
Examples
0)
????
{"jazz-joe pass-virtuoso-cherokee",
"rock-led zeppelin-ii-lemon song",
"country-dwight yoakam-long way home-things change",
"metal-iron maiden-powerslave-aces high",
"pop-supremes-more hits-ask any girl",
"rock-faith no more-angel dust-rv",
"jazz-chuck mangione-feels so good-feels so good",
"rock-van halen-ii-spanish fly"}
{"genre=rock", "album=ii"}
Returns: {"rock-led zeppelin-ii-lemon song", "rock-van halen-ii-spanish fly" }
This filter returns all the rock songs from albums with the title "ii".
1)
????
{"rock-jimi hendrix-axis bold as love-little wing",
"rock-cars-cars-moving in stereo",
"rock-jimi hendrix-electric ladyland-gypsy eyes",
"blues-albert collins-ice pickin-ice pick",
"rock-jimi hendrix-axis bold as love-bold as love",
"rock-jimi hendrix-axis bold as love-exp"}
{"artist=jimi hendrix", "album=axis bold as love"}
Returns:
{"rock-jimi hendrix-axis bold as love-little wing",
"rock-jimi hendrix-axis bold as love-bold as love" }
This filter returns all the songs that are from the album "axis bold as love" by
the artist "jimi hendrix". The last element in the collection is not returned b
ecause there are two spaces between "jimi" and "hendrix".
2)
????
{"rock-ozzy osbourne-blizzard of ozz-dee",
"rock-marvelous three-hey album-let me go",
"rock-cheap trick-in color-downed"}
{"genre=soul"}
Returns: { }
There is no soul music in this collection, so an empty vector <string> is return
ed.
3)
????
{"country-topcoder-the country album-twangy",
"rock-topcoder-the rock album-rockin",
"jazz-topcoder-the jazz album-jazzy",
"soul-topcoder-the soul album-soulful",
"metal-topcoder-the metal album-thrash"}
{"artist=topcoder", "genre=jazz", "album=the jazz album", "song=jazzy"}
Returns: {"jazz-topcoder-the jazz album-jazzy" }
4)
????
{"pop-jackson five-abc-the love you save",
"rock-ac dc-powerage-riff raff"}
{"genre=pop", "genre=rock"}
Returns: { }
No single element of collection can represent more than one genre, so this filte
r returns an empty vector <string>.
This problem statement is the exclusive and proprietary property of TopCoder, In
c. Any unauthorized use or reproduction of this information without the prior wr
itten consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc.
All rights reserved.
750点問題
Problem Statement
????
An image editing application allows users to construct images containing multipl
e layers. When dealing with large images, however, it is sometimes necessary to
limit the number of layers due to memory constraints. If certain layers will not
be altered during an editing session, they can be merged together to reduce the
total number of layers in memory. You are given a macro containing commands to
open files and merge layers. Each time a file is opened, it is loaded into a new
layer of the current image. Layers are numbered starting at 0 for the bottommos
t layer, 1 for the layer directly on top of the bottommost layer, etc... Wheneve
r a new layer is created, it is positioned on top of the previous topmost layer.
An open command is formatted as "OPEN filename" where filename is the name of t
he file to open. Consecutive layers can be merged using the merge command, which
is formatted as "MERGE layer1-layer2", where layer1 and layer2 specify an inclu
sive range of layer numbers that exist in the current image. After multiple laye
rs are merged, all the layers are renumbered according to the original specifica
tion. For example, if an image contains four layers (0, 1, 2, 3), and layers 1 a
nd 2 are merged into a single layer, the final image will contain three layers n
umbered 0, 1, 2 from bottom to top, where layer 0 is the same as before, layer 1
was previously layers 1 and 2, and layer 2 was previously layer 3.
Given the vector <string> macro, perform all the operations in the macro in orde
r and return the final state of the image layers as a vector <string>. The vecto
r <string> should contain exactly the same number of elements as there are layer
s in the final image, and each element i should correspond to the ith layer. Eac
h element of the vector <string> should be a single space delimited list of the
filenames contained in that layer. The filenames should be sorted in alphabetica
l order within each layer.
Definition
????
Class:
ImageLayers
Method:
contents
Parameters:
vector <string>
Returns:
vector <string>
Method signature:
vector <string> contents(vector <string> macro)
(be sure your method is public)
????
Constraints
-
macro will contain between 1 and 50 elements, inclusive.
-
Each element of macro will be formatted as either "OPEN filename" or "MERGE laye
r1-layer2".
-
Each filename in macro will contain between 1 and 15 lowercase letters ('a'-'z'),
inclusive.
-
Each layer1 and layer2 in macro will be integers between 0 and n-1, inclusive, w
ith no leading zeros, where n is the number of layers that exist in the image im
mediately before the command is executed.
-
Within each element of macro that represents a merge command, layer1 will be les
s than layer2.
-
The first element of macro will be an OPEN command.
Examples
0)
????
{"OPEN background",
"OPEN aone",
"OPEN atwo",
"OPEN foreground",
"MERGE 0-2",
"OPEN border"}
Returns: {"aone atwo background", "foreground", "border" }
After the first four commands in macro are executed, the layers are (from bottom
to top):
0. background 1. aone 2. atwo 3. foreground
The merge command combines the bottom three layers into a single layer. There ar
e now only two layers (from bottom to top):
0. background aone atwo 1. foreground
Finally, one last file is opened and placed in a new layer on top. The final ret
urn value contains the filenames within each layer sorted alphabetically:
0. aone atwo background 1. foreground 2. border
1)
????
{"OPEN sky",
"OPEN clouds",
"OPEN ground",
"MERGE 0-1",
"OPEN grass",
"MERGE 0-2",
"OPEN trees",
"OPEN leaves",
"OPEN birds",
"MERGE 1-2",
"MERGE 0-1"}
Returns: {"clouds grass ground leaves sky trees", "birds" }
2)
????
{"OPEN a", "OPEN b", "OPEN a", "OPEN a", "MERGE 0-3"}
Returns: {"a a a b" }
This problem statement is the exclusive and proprietary property of TopCoder, In
c. Any unauthorized use or reproduction of this information without the prior wr
itten consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc.
All rights reserved.
