Problemas de Otimização, Linguagem Maluca e Sequências sem Repetições

Prévia do material em texto

TIUP 2010
19 de Maio de 2010, 17:00 às 20:00
http://acm.ist.utl.pt/tiup10/
acm@dei.ist.utl.pt
Problems
A - Areas
B - Crazy Language
C - No Repetitions
D - Rookie DJ
E - Straws
Scientific Committee
• Alexandre Francisco
• Lúıs Miguel Silveira
• Lúıs Guerra e Silva
• José Carlos Monteiro
• Sara Madeira
• Vasco Manquinho
Available Compilers
Language Compiler Version Command Line Extension
C gcc 4.1.2 gcc -Wall -lm $file .c
C++ gcc 4.1.2 g++ -Wall $file .cpp
Java jdk 1.6.0 02 javac -nowarn $file .java
Areas
Problem
Multicriteria optimization problems arise in several areas when different
criteria should be optimized. There are problems for which no single solution
exist that is optimal for all the different criteria.
Consider that we have two criteria to be maximized and let f(X) and
g(X) denote the values of solution point X for the two criteria. We say
that a solution point X dominates all other solution points Y for which
f(X) ≥ f(Y ) and g(X) ≥ g(Y ). A solution point X is said to be optimal if
it is not dominated by any other solution point. As a result, a given problem
can have several optimal solutions.
Figure 1: Example
Figure 1 presents an example where points X1 to X5 represent optimal
solutions. Notice that each point Xi dominates a given area of the solution
space. Areas in gray represent areas dominated by more than one point,
while areas in white are dominated by a single point.
Given a set of optimal points, your goal is to determine the total area of
the solution space which is dominated by one single point and the total area
dominated by more than one optimal point. In order to determine these
areas, consider that f(X) ≥ 0 and g(X) ≥ 0 for any possible point X of the
problem.
Input
The input is a set of N optimal points. Each point X is defined by its value
f(X) and g(X).
• One line with one integer N , where N represents the number of optimal
points.
• A list of N lines where each line represents a given optimal solution
point Xi. Each line contains two integers that denote respectively the
values of f(Xi) and g(Xi).
Limits
0 ≤ N ≤ 10000
0 ≤ f(X) ≤ 10000
0 ≤ g(X) ≤ 10000
Output
The output are two integers presented in two lines. First, the total area of
the solution space that is dominated by one single optimal point. Next, the
total area of the solution space that is dominated by more than one optimal
point.
Sample Input 1
4
7 7
1 8
8 6
10 2
Sample Output 1
15
45
Sample Input 2
4
2 12
8 3
3 10
7 9
Sample Output 2
32
41
Crazy Language
Problem
We have found an alien planet where natives speak a very crazy language.
As far as we were able to understand, it does not matter the order of the
sounds or symbols. We just need to count the number of occurrences of
patterns of a given size in each sequence. As you may be thinking, there are
several sequences that can represent exactly the same. Thus, we would like
to find a way for detecting whenever two sequences of symbols are identical,
so that we can reduce our effort to learn their language. We think that by
sorting the sequences and keeping the number of the occurrences of patterns
of a given size, we will be able to reduce the number of different sequences
and sort out when a sequence is different.
In this context, assume that each sequence s is over the alphabet {a, e,
i, o, u}. For each sequence, given k ∈ IN , we want the lexicographically
smallest variation of s where the number of patterns with length k, k-lets,
is the same as in the original sequence.
Input
• One line with two integers n and k, where n represents the number of
sequences in this run and k the size of the patterns.
• A list of n lines where each line contains one sequence to process.
Limits
0 < k ≤ |s| ≤ 106
Output
The output contains n lines, where the sequence in the i-th line is the lexi-
cographically smallest sequence for the i-th sequence in the input.
Sample Input
2 3
aeeiouuuauauioeeou
euiaiuouaeouoaiaaaiiuooeuiooiuee
Sample Output
aeeioeeouuuauauiou
euiaaaiaiiuoaiuouaeouooeuiooiuee
No Repetitions
Problem
Professor Richards loves sequences of new things. When he looks at num-
bers, he always tries to find sequences without repetitions.
Given a sequence S of size N , let Si denote the i-th element in S. Let R
denote a sequence of size m without repetitions such that R ⊆ S. Therefore,
we have that R must be a sequence Si, Si+1, Si+2, . . . , Si+m−1, such that
Sj 6= Sk for all i ≤ j < k ≤ i + m− 1.
Given a sequence S of numbers, your objective is to help Professor
Richards in finding the largest sequence R, such that R ⊆ S and there
are no repetitions in R.
Input
The input is a sequence S of positive integers between 1 and a positive
integer K.
• One line with one integer N , where N represents the size of the se-
quence S.
• One line with one integer K that defines the maximum value in se-
quence S.
• A list of N lines where each line contains one integer Si such that
0 < Si ≤ K.
Limits
0 < K < N ≤ 107
Output
The output is a single integer with the size of the largest sequence R such
that R ⊆ S and R does not contain any repetitions.
Sample Input 1
8
7
1
3
5
7
3
1
4
6
Sample Output 1
6
Sample Input 2
9
5
1
2
1
3
1
4
1
5
1
Sample Output 2
3
Rookie DJ
Problem
You are a novice dance music DJ that was invited by a friend to perform
in his nightclub. Unlike experienced DJs, you are not yet able to intuitively
come up with neat mixes during a performance. Therefore, you decide to
plan things in advance and quickly code a program that will help you in
devising the best sequence of tracks to be played, among all the tracks
available in your collection.
In dance music there are no gaps between consecutive tracks. Therefore,
during the trasition from one track to the other, both tracks are played
simultaneously (mixed together). Since this transition can last for as long
as several minutes, it is necessary to ensure that both tracks can be combined
harmoniously. The trick for a good mix is that you should never mix together
tracks with very different tempos, or with very different keys.
You have a database with the tempos and keys of every track in your
collection. Tempos are given by an integer value that represents the number
of beats-per-minute (BPM). Keys are represented by an integer code from
1 to 24. Further, you know the rules for a good mix:
• only mix tracks with tempos that are no more than 20 BPM apart;
• only mix tracks with keys that are no more than 1 unit apart, or if
their modulo 12 is the same.
Your program should extract from the track database the size of the longest
sequence of tracks, where any two consecutive tracks must obey to the rules
above. Additionally, the first track must have a tempo not higher than 95
BPM, and the last track must have a tempo not lower than 140 BPM.
Input
The input is a text file containing the keys and tempos for every track in
your dance music collection (track database), in the following format:
• one line, containing an integer N , which is the number of tracks in the
collection, and therefore the number of subsequent lines;
• N lines, where each line contains 2 integers separated by spaces:
– the first integer, tempo, is the tempo in BPM of the track;
– the second integer, key, is the key of the track.
Limits
• 0 < N ≤ 10000
• 50 ≤ tempo ≤ 200
• 1 ≤ key ≤ 24
Output
The output is a single integer, which is the size of the longest sequence of
tracks that obey the rules previously stated.
Sample Input 1
8
102 8
134 18
95 7
114 19
150 17
93 21
108 18
86 9
Sample Output 1
7
Sample Input 2
4
95 1
116 1
136 1
156 1
Sample Output 2
0
Straws
Problem
Jose took straws of the same length and cut them randomly until all parts
became at most 50 units long. Now he wants to return the straws to the
original state, but he forgot how many straws he had and how long they
were originally. Please help him and design a program which computes the
smallestpossible original length of those straws. All lengths expressed in
units are integers greater than zero.
Input
The input file contains blocks of 2 lines. The first line contains the number
of straws parts after cutting, N . The second line contains the lengths of
those parts separated by the space, li. The last line of the file contains zero.
Limits
• maximum number of straw parts, N ≤ 80.
• maximum length of any straw part, li ≤ 50.
Output
The output file contains the smallest possible length of the original straws
for each input block, one per line.
Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output
6
5