Problem A – Academia
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 possibe to make something rectangular with a number N of tiles, independently of the room size.
Than the number of tiles will be the number os tiles in colummns 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
Problem D – Dijkstra
Problem E – Finding Paths
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 2 - 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
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).