SESCOMP Marathon 2018 — Federal University of Ceará — TUTORIAL

Revision en8, by Dambola, 2018-10-15 22:33:44

Problem A – Academia

ENGLISH

PORTUGUESE

Esta é uma questão de programação dinâmica e/ou simulação. Ela é uma derivada do clássico Problema da Mochila.

Primeiro faremos um vetor, de tamanho de 0 até Tmax (Tmax + 1), onde simularemos o "quão pesada está nossa mochila", ou seja, o quanto tempo gastamos.

Inicialmente o vetor estará preenchido com zeros, pois não teremos nenhum Poder de Musculação.

Para cada exercício faremos as seguintes ações:

1) Iremos ver o vetor entre [0, Tmax - Texercício], esse vetor é nosso armazenamento para cada teste.

2) Para ti entre [0, Tmax - Texercício] iremos propagar a soma do Poder de Musculação do vetor[ti] e o Pexercício para o próximo tempo.

3) Faremos então:

vetor[ti + Texercício] = maior(vetor[ti] + Pexercício, vetor[ti + Texercício])

OBS: Fazer ti entre [0, Tmax - Texercício] ir da direita para esquerda para não haver sobreposição de Poder de Musculação

No final procurar o maior valor de P no vetor e imprimir.

Tempo: O(Tmax * n).

Problem B – Bento

ENGLISH

It is a brute force question. It is not given the size of the rectangular room, so it can be any value. The principle question is you analyze if is possible to make something rectangular with a number N of tiles, independently of the room size.

Than the number of tiles will be the number of tiles in colummn multiplied by the number of tiles in row.

For example, 8 tiles -> you can use 2 for column and 4 for row, and vice-versa, being: 2 * 4 = 8.

So we want to know if L * C = N, but L and C cant be 1, so N have to be multiple of L and C.

For that, if N is prime than it cant done, otherwise it can be done.

Since the maximum size of N is 1012 it is needed to make a faster method to analyze divisors of N, verifying from 1 to , if some of it in this interval divide N, than it is not prime, otherwise it is prime.

The worst case of N is 1012, than we do up to maximum, that is equals to 106.

Another observation, 1012 overflows the size of integer in C/C++/JAVA, for that we use 'unsigned long long int' for C/C++ or 'BigInteger' for Java. Outra observação, 1012 estoura o tamanho de inteiro em C/C++/JAVA, por isso em C/C++ use 'unsigned long long int' ou 'BigInteger' no Java.

Time:

PORTUGUESE

É uma questão de força bruta. Não é dado o tamanho da sala retangular, então pode ser de qualquer valor. O princípio da questão é você analisar se, independentemente do tamanho da sala, é possível fazer algo retangular com o número N de azulejos.

Então o número de azulejos vai ser o número de azulejos "em coluna" vezes o número de azulejos "em linha".

Por exemplo, 8 azulejos -> você pode usar 2 pra coluna e 4 pra linha, e vice-versa, ficando: 2 * 4 = 8.

Então queremos saber se L * C = N, porém L e C não podem ser 1, logo N tem que ser Múltiplo de L e C.

Para isso, se N é primo então não dá pra fazer, se N não é primo então dá pra fazer.

Como o tamanho máximo de N é 1012 é preciso fazer o método rápido para analisar os divisores de N, verificando de 1 até , se algum desses neste intervalo divide N, então não é primo, caso contrário é primo.

Então para o pior caso de N ser 1012, faremos até que é igual a 106.

Outra observação, 1012 estoura o tamanho de inteiro em C/C++/JAVA, por isso em C/C++ use unsigned long long int ou BigInteger no Java.

Tempo:

Problem C – Codex

ENGLISH

PORTUGUESE

É uma questão com duas soluções viáveis uma com implementação com técnica de programação (Busca Binária) ou implementação com Map/Hash. Explicaremos a forma mais fácil.

Criaremos dois Maps (Um para dado o índice ter o elemento e outro para dado o elemento ter o índice):

MapM, M[índice] = elemento.

MapV, V[elemento] = índice.

Iremos manipular os dois.

Para operação 1:

índice = V[elemento]

Unable to parse markup [type=CF_TEX]

índicepróximo = V[próximo]

V[elemento] = índicepróximo

V[próximo] = índice

M[índice] = próximo

M[índicepróximo] = elemento

A partir daí teremos trocas em tempo O(logn).

Para a operação teremos  - 1 será análogo, porém para o anterior, lembrando do caso do elemento ser o menor e trocar com o maior.

Para imprimir o resultamos, faremos um laço de i indo de 0 até n - 1 imprimindo M[i].

Problem D – Dijkstra

ENGLISH

PORTUGUESE

É uma questão de Grafo utilizando o conhecimento de LCA (Lowest Common Ancestor — Menor Ancestral Comum). Qualquer solução ingênua é aceita desde que tenha a lógica de um LCA. Primeiro iremos enraizar o grafo a partir de um vértice qualquer.

Exemplo do caso 2, vamos enraizar em 1. Para enraizar podemos usar o algoritmo de Busca em Profundidade ou Largura, onde armazenaremos o pai e o nível do vértice i. Para o pai de 1 é -1 e o nível de 1 é 0, por padrão.

Agora para saber quem é o menor ancestral comum temos seguinte algoritmo.

Temos u e v que é o número do vértice. Vamos fazer com que o u seja o vértice de maior nível, e v é o vértice de menor nível.

Vamos subir o u para ficar no mesmo nível de v.

Enquanto nível[v] != nível[u] faça
    u = pai[u]

Após isso, você vai subir simultaneamente v e u até achar um vértice que seja comum e retornará ele.

Enquanto u != v faça
    u = pai[u]
    v = pai[v]
retorne u

Tempo: O(n), pior caso, seja uma lista encadeada.

Problem E – Finding Paths

ENGLISH

PORTUGUESE

Problem F – Making life easier for Miguel

ENGLISH

It is a brute force question, with binary search if you like.

The binary number formed by 1's is a decimal number in the form 2k - 1.

For that we need to find a k that satisfy that condition, where 1018 ≤ 260, then we need just to make 60 iteracions to analyze.

The easyest and fastest method is to use a bit-to-bit operation. Doing the following: N&(N + 1), for example:

Than, if N&(N + 1) is equals to 0, than N is in 2k–1 form, otherwise no.

Time: Bit-to-Bit "O(1)", Analyze O(logk).

PORTUGUESE

É uma questão de força bruta, com otimização em busca binária se quiser.

O número em binário onde é formado só por 1's é um número decimal da forma 2k - 1.

Para isso só precisamos achar um k que satisfaça essa condição, onde 1018 ≤ 260, então precisaremos fazer 60 iterações de análise.

O método mais fácil e rápido é utilizar operação bit-a-bit. Fazemos o seguinte: N&(N + 1), por exemplo:

Então, se N&(N + 1) é igual a 0, então N é da forma 2k–1, caso contrário não.

Tempo: Bit-a-Bit "O(1)", Analise O(logk).

Problem G – Gaining Points

ENGLISH

PORTUGUESE

Problem H – Hiperspace

ENGLISH

It is a brute force/implementation question. We just have to make 3 verifications, if n ≤ 299 you show 'Hiperespaco nao esta disponivel', else if n ≤ 499 you show 'Hiperespaco esta disponivel', else you show 'Hiperespaco ativado'.

Time: O(1).

PORTUGUESE

É uma questão de força bruta/implementação. São apenas 3 verificações, se n ≤ 299 você imprime 'Hiperespaco nao esta disponivel', se não, se n ≤ 499, você imprime 'Hiperespaco esta disponivel', senão você imprime 'Hiperespaco ativado'.

Tempo: O(1).

Problem I – Isolated

ENGLISH

PORTUGUESE

Problem J – Zumbie Game

ENGLISH

PORTUGUESE

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en23 English Dambola 2018-10-17 05:03:27 0 (published)
en22 English Dambola 2018-10-17 05:01:54 2130
en21 English Dambola 2018-10-17 04:43:36 68
en20 English Dambola 2018-10-17 04:42:00 592
en19 English Dambola 2018-10-17 04:35:51 1889
en18 English Dambola 2018-10-17 04:24:43 234
en17 English Dambola 2018-10-16 00:02:50 12
en16 English Dambola 2018-10-16 00:01:21 1420
en15 English Dambola 2018-10-15 23:50:48 184
en14 English Dambola 2018-10-15 23:38:09 1229
en13 English Dambola 2018-10-15 23:26:16 40
en12 English Dambola 2018-10-15 23:24:20 896
en11 English Dambola 2018-10-15 23:00:23 999
en10 English Dambola 2018-10-15 22:46:53 7569
en9 English Dambola 2018-10-15 22:39:24 32
en8 English Dambola 2018-10-15 22:33:44 1460
en7 English Dambola 2018-10-15 22:18:06 23
en6 English Dambola 2018-10-15 22:16:37 946
en5 English Dambola 2018-10-15 22:10:18 21
en4 English Dambola 2018-10-15 22:09:48 1047
en3 English Dambola 2018-10-10 23:06:30 2 Tiny change: 'he form $2 - 1$.\n\n' -> 'he form $2^k - 1$.\n\n'
en2 English Dambola 2018-10-10 23:02:39 4
en1 English Dambola 2018-10-10 23:00:57 4961 Initial revision (saved to drafts)