Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2425

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2425

Banco

Por OBI - Olimpíada Brasileira de Informática 2012 BR Brazil

Timelimit: 1

A legislação em vigor obriga os bancos a iniciarem o atendimento a um cliente em no máximo 20 minutos após a entrada do cliente na fila única da agência bancária. A fila é única, assim um caixa livre solicita ao primeiro cliente da fila que venha ao seu guichê para ser atendido. (Vamos ignorar aqui o problema dos clientes prioritários, idosos, gestantes, portadores de necessidades especiais, etc.) Estamos supondo também que nenhum caixa atende dois clientes ao mesmo tempo.

Seu programa receberá o número de caixas ativas na agência, o número de clientes e, para cada cliente, duas informações, a saber, o momento de entrada do cliente na fila, e a duração do atendimento daquele cliente.

Inicialmente todos os caixas estão vazios, já que a agência acabou de abrir.

Seu problema é determinar o número de clientes que esperarão mais de 20 minutos para ter seu atendimento iniciado.

Entrada

A primeira linha da entrada contém dois inteiros separados por um espaço em branco. O primeiro, C (1 ≤ C ≤ 10), é o número de caixas ativas na agência bancária. O segundo, N (1 ≤ N ≤ 1000), o número de clientes que procurarão atendimento na agência naquele dia.

As próximas N linhas terão cada uma informações sobre um cliente, consistindo de dois inteiros, T (0 ≤ T ≤ 300) e D (1 ≤ D ≤ 10), separados por um espaço em branco. O inteiro T fornece o momento em que o cliente entra na fila, em minutos, a partir do instante de abertura da agência. O inteiro D fornece, em minutos, o tempo necessário para atender o cliente.

 As linhas estão ordenadas por entrada dos clientes na fila.

Saída

A saída deverá conter apenas uma linha, contendo um único inteiro, o número de clientes cujo atendimento será iniciado mais do que 20 minutos após sua entrada na fila.

Exemplos de Entrada Exemplos de Saída

1 5

0 10

0 10

1 10

2 10

30 10

1

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
#define MAXN 1010
int caixas[11], c, n, resposta, disponivel, t, d;
int min() {
    int indice = 0;
    for (int i = 1; i  <  c; i++) {
        if (caixas[i] < caixas[indice]) indice = i;
    }
    return indice;
}
int main() {
    scanf("%d %d", &c, &n);
    for (int i = 0; i  <  n; i++) {
        scanf("%d %d", &t, &d);
        disponivel = min();
        if (t > caixas[disponivel])
            caixas[disponivel] = t + d;
        else {
            if (caixas[disponivel] - t > 20) resposta++;
            caixas[disponivel] += d;
        }
    }
    printf("%d\n", resposta);
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
1 5
0 10
0 10
1 10
2 10
30 10

Output

x
+
cmd
1
Advertisements

Demonstration


Previous
#2424 Beecrowd Online Judge Solution 2424 Tira-teima Solution in C, C++, Java, Js and Python
Next
#2427 Beecrowd Online Judge Solution 2427 Chocolate Solution in C, C++, Java, Js and Python