Problema: 1999
Enunciado:
Todos os anos, os reinos da Cubiconia, Quadradonia e Noglônia organizam um baile para comemorar o fim da guerra que devastou a região por um longo tempo. Algum número de nobres de cada reino é convidado a participar do evento, e espera-se cada par de convidados de diferentes reinos dancem juntos exatamente uma vez. Ou seja, cada convidado de Cubiconia deve dançar uma vez com todos os convidados de Quadradonia e Noglônia, e da mesma forma a cada convidado Quadradonia deve dançar uma vez com todos Noglônia. Porém, os hóspedes de um mesmo reino nunca devem dançar juntos. Para ajudar a organizar o baile, o numero total de danças é determinado antecipadamente, então é preciso ter cuidado ao escolher o numero de convidados de cada reino. Por exemplo, se você decidir que o baile tem N = 20 danças, uma possibilidade é convidar 6 nobres de Cubiconia, 2 de Quadradonia e 1 de Noglônia, que pode ser representado pela expressão (6, 2, 1). Esta é uma opção válida, porque a quantidade total de danças seria 6 × 2 + 6 × 1 + 2 × 1 = 20. Tradições, cuja origem ninguém se lembra, indicam que o número de convidados Cubiconia deve ser maior ou igual ao número de convidados de Quadradonia, e por sua vez o número de convidados Quadradonia deve ser maior ou igual o número de convidados Noglônia. Assim, para N = 20 danças há exatamente 5 possíveis formas de escolher o número de convidados em cada reino (5, 4, 0), (4, 2, 2), (10, 2, 0), (20, 1, 0) e o acima mencionado (6, 2, 1). Com tantas restrições, o comitê organizador da cerimônia tem problemas em encontrar o número de convidados de cada reino. Sua missão é ajudar o comitê a contar as diferentes formas que os convidados podem ser escolhidos para um baile com N danças. Duas maneiras de escolher o número de convidados de cada reino são consideradas diferentes se eles diferem no número de convidados em pelo menos um dos reinos.
Se for feito os três for completos, o problema fica extremamente lento e dá erro no tempo limite. Então o segundo for é acelerado podendo ir até ( j = n/i ). Para verificar se uma dança é válida é feita a soma de dois em dois de i, j e k. Ao final, é impresso o valor sum, mostrando o resultado final.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | #include <iostream> using namespace std; int main() { int n; cin >> n; while(n>=0){ int sum = 0; for(int i=0;i<=n;i++){ for(int j=0;(i>0 and j<=i and j<=n/i);j++){ for(int k=0; k<=j;k++){ int dancas = i*j + i*k + j*k; if(dancas == n){ sum++; } } } } cout << sum << endl; cin >> n; } return 0; } |
