Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DESCULPA - Pedido de Desculpas

Cuca saiu para jogar futebol com os amigos e esqueceu do encontro que tinha com a namorada. Ciente da mancada, Cuca deseja elaborar um pedido especial de desculpas. Resolveu então enviar flores e usar o cartão da floricultura para escrever um pedido especial de desculpas.

Cuca buscou na internet um conjunto de frases bonitas contendo a palavra ‘desculpe’ (que pode ocorrer mais de uma vez na mesma frase). No entanto, o cartão da floricultura é pequeno, e nem todas as frases que Cuca colecionou poderão ser aproveitadas.

Cuca quer aproveitar o espaço do cartão, onde cabe um número limitado de caracteres, para escrever um sub-conjunto das frases coletadas de modo que apareça o máximo de vezes possível a palavra ‘desculpe’.

Tarefa

Escreva um programa que, dados o número de caracteres que cabem no cartão e a quantidade de frases coletadas (com os respectivos comprimentos e os números de ocorrências da palavra ‘desculpe’), determine o número máximo de vezes que a palavra aparece, utilizando apenas as frases colecionadas, sem repetí-las.

Entrada

A entrada é constituída de vários casos de teste. A primeira linha de um caso de teste contém dois números inteiros C e F indicando respectivamente o comprimento do cartão em caracteres (8 <= C <= 1000) e o número de frases coletadas (1 <= F <= 50). Cada uma das F linhas seguintes descreve uma frase coletada. A descrição é composta por dois inteiros N e D que indicam respectivamente o número de caracteres na frase (8 <= N <= 200) e quantas vezes a palavra ‘desculpe’ ocorre na frase (1 <= D <= 25). O final da entrada é indicado por C = F = 0.

Saída

Para cada caso de teste seu programa deve produzir três linhas na saída. A primeira identifica o conjunto de teste no formato “Teste n”, onde n é numerado a partir de 1. A segunda linha deve conter o máximo número de vezes que a palavra ‘desculpe’ pode aparecer no cartão, considerando que apenas frases coletadas podem ser utilizadas, e cada frase não é utilizada mais de uma vez. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo

Entrada:
200 4
100 4
100 1
120 2
80 5
40 3
10 1
10 1
20 2
0 0

Saída:
Teste 1
9

Teste 2
4

Restrições

8 <= C <= 1000 (C = 0 apenas para indicar o fim da entrada)
1 <= F <= 50 (S = 0 apenas para indicar o fim da entrada)
8 <= N <= 200
1 <= D <= 25

Adicionado por:Wanderley Guimarăes
Data:2007-03-09
Tempo limite:0.333s-0.666s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL
Origem:Olimpiada Brasileira de Informatica 2005 Programacao Nivel 2

hide comments
2016-08-30 06:46:50
No meu código todos os casos de teste funciona, porém o spoj está colocando resposta errada.
2016-04-09 19:06:57 Elsio [UFABC]
Pedido de desculpas... aceito! kkk
2014-12-19 02:46:30 Luciano Ribeiro
Algoritmos Maliciosos...
2014-12-08 20:45:18 so falta testar
kkkkkkk Gananciosa é foda....
2013-06-02 22:32:38 Isabel Bustamante [introComp]
Alguém tem mais casos de teste? Todos os testes que fiz funcionaram, mas o SPOJ deu resposta errada
2012-09-04 23:28:10 Lucas Porto Maziero [UNIS]
Realmente Matheus Flauzino, é Knapsack problem.
2012-04-21 04:07:35 Monael
Estratégia Gananciosa năo funciona...
2011-10-11 14:02:39 Matheus Flauzino [UNIS-MG]
Knapsack problem
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.