Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2325

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

Repositórios

 

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

Timelimit: 1

Uma das boas práticas ao administrar um conjunto de computadores é manter os aplicativos sempre atualizados. Entretanto, em uma grande corporação com milhares de aplicativos instalados, a simples verificação do que precisa ser atualizado pode tornar-se uma tarefa bem complicada. Para facilitar isso, alguns fabricantes armazenam todos os aplicativos existentes em grandes bases de dados chamadas repositórios e um programa é responsável por verificar esse repositório e atualizar as versões dos aplicativos.

M.V.Lzr, um administrador de sistemas e rapper nas horas vagas, trabalha em uma empresa que, infeliz-mente, não utiliza um sistema com repositórios. Para facilitar sua vida, ele decidiu que era a hora de ter o seu próprio sistema e pediu a sua ajuda.

Periodicamente ele varre a Internet em busca das páginas que possam conter os aplicativos e constrói uma lista com as versões dos aplicativos que deseja instalar disponíveis em cada página. Um programa deve verificar então qual a versão de cada programa instalado nos computadores (todos eles possuem os mesmos aplicativos instalados e nas mesmas versões) e instalar todos aqueles que ainda não foram instalados ou cuja versão instalada seja anterior a versão mais recente. Como ele não sabe programar direito, ele pediu sua ajuda.

Dado uma lista de aplicativos instaladas nos computadores da empresa, com suas respectivas versões e uma lista de aplicativos disponíveis na internet que devem ser instalados, determinar quais devem ser instalados e em quais versões.

 

Entrada

 

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém dois inteiros C (1 ≤ C ≤ 10.000) e N (1 ≤ N ≤ 1.000) que representam o número total de aplicativos e versões disponíveis na internet e o número total de programas instalados na empresa, respectivamente. As C linhas seguintes possuem dois inteiros cada, Pc (1 ≤ Pc ≤ 1.000.000.000) e Vc (1 ≤ Vc ≤ 1.000.000.000), representando o número do programa e o número da versão instalada nos computadores. Todo aplicativo está instalado uma única vez em cada máquina e em uma única versão. Em seguida, as As N linhas seguintes possuem dois inteiros cada, Pn (1 ≤ Pn ≤ 1.000.000.000) e Vn (1 ≤ Vn ≤ 1.000.000.000), representando o número do programa e o número da versão disponível na internet. Um dado programa pode estar disponível em mais de uma versão na internet.

 

Saída

 

Seu programa deve imprimir, na saída padrão, diversas linhas, cada uma contendo dois inteiros, Ps e Vs com o número do programa e a versão que deve ser instalada. Em todo caso de teste existe pelo menos um programa que deve ser instalado

 

 

 

Exemplos de Entrada Exemplos de Saída

1 1
5215 1
5215 3

5215 3

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
#include <map>
#include <set>
using namespace std;
int main() {
    int n, m;
    map < int, int> mapa;
    set<int> instalar;
    scanf("%d %d", &n, &m);
    for (int i = 0; i  <  n; i++) {
        int programa, codigo;
        scanf("%d %d", &programa, &codigo);
        mapa[programa] = codigo;
    }
    while (m--) {
        int davez, versao;
        scanf("%d %d", &davez, &versao);
        if (mapa[davez]  <  versao) {
            mapa[davez] = versao;
            instalar.insert(davez);
        }
    }
    for (set < int>::iterator it = instalar.begin(); it != instalar.end(); it++) {
        printf("%d %d\n", *it, mapa[*it]);
    }
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
1 1
5215 1
5215 3

Output

x
+
cmd
5215 3
Advertisements

Demonstration


Previous
#2323 Beecrowd Online Judge Solution 2323 Móbile Solution in C, C++, Java, Js and Python
Next
#2326 Beecrowd Online Judge Solution 2326 Sacoleiro Solution in C, C++, Java, Js and Python