PGDF
Power Member
Boa tarde pessoal,
Tenho um novo problema a minha frente (que bom
), mas quanto mais olho não sei por onde pegar, não sei onde pegar mas não é em termos de programação, mas sim como fazer o meu programa processar de modo a não perder muita memoria ou a ficar segundos e segundos ate chegar ao resultado.
Questão: como fazer para que o programa demore menos tempo possível sem perder a performance ???
TAREFA:
A sua tarefa é escrever um programa para calcular o preço do passe, dado o valor que administração pretende, o número máximo de notas que a máquina aceita, o conjunto dos valores que podem ser pagos com moedas e o valor nominal de cada uma das notas que a máquina aceita. O preço deve ser o menor valor maior ou igual ao preço pretendido pela administração que pode ser formado usando notas e moedas: o número de notas deve ser menor ou igual ao máximo que a máquina aceita; os valores que podem ser pagos em moedas correspondem às quantias que podem ser formadas com entre 0 e quatro moedas inclusive, e, ao contrário do problema anterior, já estão pré-calculados.
RESTRIÇÕES:
O número máximo de valores que podem ser introduzidos só com moedas não é especificado. O número máximo de tipos de notas que a máquina aceita também não.
Note bem: o número de valores que podem ser introduzidos só com moedas pode ser zero (o que representaria uma situação em que a máquina não aceita moedas) e analogamente para o número de notas. No entanto, em nenhum teste esses dois números serão zero simultaneamente.
Em todos os casos de teste o problema tem solução: isto é, existe sempre um valor maior ou igual ao preço pretendido pela administração que pode ser pago de acordo com as regras (moedas mais notas em número inferior ao igual ao máximo permitido).
INPUT:
A primeira linha do ficheiro de input contém um número inteiro representando o preço pretendido pela administração, em cêntimos; a segunda linha contém um número inteiro representando o número máximo de notas que a máquina aceita numa operação; seguem-se um conjunto de linhas, em número indeterminado, contendo cada uma delas um número inteiro representando um valor que pode ser pago só com moedas, expresso em cêntimos. Esse conjunto de linhas está ordenado por ordem crescente, sem repetições e termina quando surge uma linha contendo o separador -1; a seguir ao separador, seguem-se um segundo grupo de linhas, cada uma com um número, representado o valor nominal em cêntimos de cada uma das notas que a máquina aceita, por ordem crescente sem repetições.
OUTPUT:
O seu programa escreverá uma única linha contendo o preço para o passe, calculado de acordo com as regras apresentadas
Exemplo 1
Input
550
1
20
40
60
-1
500
Output
560
Explicação:A administração pretende que o preço do passe seja €5.50. A máquina só aceita uma nota, que pode ser de cinco euros ou de dez euros. Os valores que podem ser pagos com moedas são 20 cêntimos, 40 cêntimos ou 60 cêntimos. Logo, o valor do passe dever ser €5.60
Exemplo 2
Input
5130
3
5
10
15
20
25
30
35
40
-1
100
500
1000
2000
5000
Output
5130
Explicação: Neste caso, o preço pretendido, 5130, pode ser aceite: moedas no valor de 30 (que é uma das quantias listadas como sendo possíveis de formar só com moedas), uma nota de 100 e uma de 5000.
Exemplo 3
Input
5130
3
5
10
15
20
25
30
35
40
-1
500
1000
2000
5000
Output
5500
Explicação:O preço pretendido é 5130. O menor valor maior ou igual a esse que se consegue é 5500, usando uma nota de 500 e uma de 5000. Neste caso, não se usam moedas.
Exemplo 4
Input
305
5
2
4
6
8
-1
17
88
Output
306
Explicação: 306 = 88*3 + 17*2 + 8.
ATENÇÃO: os valores das moedas não são as moedas que existem, mas sim o conjunto dos valores que se podem fazer:
Neste caso:
Input
305
5
2
4
6
8
-1
17
88
com as moedas podemos fazer 2 centimos OU 4 centimos OU 6 centimos OU 8 centimos. NAO SE PODE juntar o 8 com o 2 e fazer 10 centimos.
Cumps
PGDF
Tenho um novo problema a minha frente (que bom
), mas quanto mais olho não sei por onde pegar, não sei onde pegar mas não é em termos de programação, mas sim como fazer o meu programa processar de modo a não perder muita memoria ou a ficar segundos e segundos ate chegar ao resultado.Questão: como fazer para que o programa demore menos tempo possível sem perder a performance ???
TAREFA:
A sua tarefa é escrever um programa para calcular o preço do passe, dado o valor que administração pretende, o número máximo de notas que a máquina aceita, o conjunto dos valores que podem ser pagos com moedas e o valor nominal de cada uma das notas que a máquina aceita. O preço deve ser o menor valor maior ou igual ao preço pretendido pela administração que pode ser formado usando notas e moedas: o número de notas deve ser menor ou igual ao máximo que a máquina aceita; os valores que podem ser pagos em moedas correspondem às quantias que podem ser formadas com entre 0 e quatro moedas inclusive, e, ao contrário do problema anterior, já estão pré-calculados.
RESTRIÇÕES:
O número máximo de valores que podem ser introduzidos só com moedas não é especificado. O número máximo de tipos de notas que a máquina aceita também não.
Note bem: o número de valores que podem ser introduzidos só com moedas pode ser zero (o que representaria uma situação em que a máquina não aceita moedas) e analogamente para o número de notas. No entanto, em nenhum teste esses dois números serão zero simultaneamente.
Em todos os casos de teste o problema tem solução: isto é, existe sempre um valor maior ou igual ao preço pretendido pela administração que pode ser pago de acordo com as regras (moedas mais notas em número inferior ao igual ao máximo permitido).
INPUT:
A primeira linha do ficheiro de input contém um número inteiro representando o preço pretendido pela administração, em cêntimos; a segunda linha contém um número inteiro representando o número máximo de notas que a máquina aceita numa operação; seguem-se um conjunto de linhas, em número indeterminado, contendo cada uma delas um número inteiro representando um valor que pode ser pago só com moedas, expresso em cêntimos. Esse conjunto de linhas está ordenado por ordem crescente, sem repetições e termina quando surge uma linha contendo o separador -1; a seguir ao separador, seguem-se um segundo grupo de linhas, cada uma com um número, representado o valor nominal em cêntimos de cada uma das notas que a máquina aceita, por ordem crescente sem repetições.
OUTPUT:
O seu programa escreverá uma única linha contendo o preço para o passe, calculado de acordo com as regras apresentadas
Exemplo 1
Input
550
1
20
40
60
-1
500
Output
560
Explicação:A administração pretende que o preço do passe seja €5.50. A máquina só aceita uma nota, que pode ser de cinco euros ou de dez euros. Os valores que podem ser pagos com moedas são 20 cêntimos, 40 cêntimos ou 60 cêntimos. Logo, o valor do passe dever ser €5.60
Exemplo 2
Input
5130
3
5
10
15
20
25
30
35
40
-1
100
500
1000
2000
5000
Output
5130
Explicação: Neste caso, o preço pretendido, 5130, pode ser aceite: moedas no valor de 30 (que é uma das quantias listadas como sendo possíveis de formar só com moedas), uma nota de 100 e uma de 5000.
Exemplo 3
Input
5130
3
5
10
15
20
25
30
35
40
-1
500
1000
2000
5000
Output
5500
Explicação:O preço pretendido é 5130. O menor valor maior ou igual a esse que se consegue é 5500, usando uma nota de 500 e uma de 5000. Neste caso, não se usam moedas.
Exemplo 4
Input
305
5
2
4
6
8
-1
17
88
Output
306
Explicação: 306 = 88*3 + 17*2 + 8.
ATENÇÃO: os valores das moedas não são as moedas que existem, mas sim o conjunto dos valores que se podem fazer:
Neste caso:
Input
305
5
2
4
6
8
-1
17
88
com as moedas podemos fazer 2 centimos OU 4 centimos OU 6 centimos OU 8 centimos. NAO SE PODE juntar o 8 com o 2 e fazer 10 centimos.
Cumps
PGDF
Última edição:
