1514 - Competição
Você sabe o que é preciso para organizar uma boa maratona de programação?
Descrição
Solução
A descrição nos diz quatro condições que devem ser estabelecidas para se ter uma boa maratona. Junto com as condições, coloco as traduções do que elas querem dizer na prática:
Condição em extenso
Condição computacional
Ninguém resolveu todos os problemas
Para todo participante i
, seu número de problemas resolvidos deve ser menor do que M
Todo problema foi resolvido por pelo menos uma pessoa
Para todo problema i
, o número de participantes que o resolveu deve ser maior do que 0
Não há nenhum problema resolvido por todos
Para todo problema i
, o número de participantes que o resolveu deve ser menor do que N
Todos resolveram ao menos um problema
Para todo participante i
, seu número de problemas resolvidos deve ser maior do que 0
Ou seja, nosso problema se torna muito mais fácil se para cada participante tivermos o número de problemas resolvidos e para cada problema tiver o número de participantes que o resolveu.
Para checar as condições, usei duas formas diferentes, uma para linguagens de baixo nível e outra para linguagens de alto nível, confira qual das duas formas se encaixa melhor com sua lógica de programação. Se preferir, você pode usar a lógica de baixo nível nas linguagens de alto nível.
#include <string.h>
#include <stdio.h>
int main(){
int participantes[100], problemas[100];
int N, M, x, condicao1, condicao2, condicao3, condicao4;
while(scanf("%d %d", &N, &M) != EOF){
if(!N && !M) break;
memset(problemas, 0, sizeof(problemas));
memset(participantes, 0, sizeof(participantes));
for(int i = 0; i < N; ++i){
for(int j = 0; j < M; ++j){
scanf("%d", &x);
participantes[i] += x;
problemas[j] += x;
}
}
condicao1 = condicao2 = condicao3 = condicao4 = 1;
for(int i = 0; i < N; ++i){
if(participantes[i] == M) condicao1 = 0;
if(participantes[i] == 0) condicao4 = 0;
}
for(int i = 0; i < M; ++i){
if(problemas[i] == 0) condicao2 = 0;
if(problemas[i] == N) condicao3 = 0;
}
printf("%d\n", condicao1 + condicao2 + condicao3 + condicao4);
}
return 0;
}
Last updated
Was this helpful?