No dia primeiro de junho, foram realizadas as finais do nosso campeonato de programação . Os nomes dos vencedores já são conhecidos. Em breve eles receberão seus prêmios e, enquanto isso, começamos a publicar análises das tarefas do campeonato. Primeiro, analisaremos as tarefas do estágio de qualificação entre os desenvolvedores de back-end.
A qualificação dura uma semana, e o número de participantes aos milhares, portanto, preparar tarefas, ao que parece, não é uma tarefa fácil. No total, tivemos que executar 24 tarefas e dividi-las entre as quatro opções, para que as opções fossem comparáveis em complexidade.
Desta vez, criamos seis tarefas, para cada uma das quais foi possível criar várias formulações alternativas: uma tarefa inventada deu origem a quatro de uma vez! Assim, as opções acabaram sendo comparáveis, tanto quanto possível.
Portanto, não publicarei análises de todos os 24 problemas. Em vez disso, analisarei as seis tarefas de uma das opções de qualificação: outras são resolvidas de maneira semelhante.
A. Alarmes
Condição da tarefaTrabalhar na maioria das empresas de TI tem muitas vantagens: não há código de vestuário, às vezes você pode trabalhar remotamente, colegas legais e inteligentes e, é claro, uma programação gratuita! No entanto, uma programação gratuita e a capacidade de trabalhar remotamente exigem muita força de vontade.
O programador Alexei gosta de trabalhar à noite e não gosta de vir trabalhar tarde. Para acordar precisamente de manhã, Alexey começa todas as noites N alarmes no seu telefone. Cada despertador é configurado para tocar todos os X minutos a partir do momento em que ele trouxe. Por exemplo, se um alarme foi definido em um ponto no tempo ti então ele liga às vezes ti , ti+X , ti+2 cdotX etc. Ao mesmo tempo, se dois alarmes começarem a tocar em um momento, apenas um deles será exibido.
Sabe-se que antes de acordar, Alexey ouve todas as manhãs K despertadores, após o que acorda. Determine o momento em que Alex acorda.
Todos os alarmes tocam em horários inteiros e todos os alarmes têm o mesmo período de adiamento da chamada. Se dois alarmes forem definidos nos momentos ti e tj , e esses pontos no tempo fornecem o mesmo restante quando dividido por X , você pode deixar apenas um despertador - aquele que toca o primeiro.
Portanto, o primeiro passo é eliminar os alarmes desnecessários: nós os agruparemos pelo valor do restante da divisão por X e de cada grupo, deixaremos apenas um despertador definido o mais cedo possível.
Agora, aprenderemos como determinar quantos alarmes tocaram em um determinado momento T . Se o alarme estiver definido a tempo ti , o número de chamadas dele no momento T será igual
max Big( fracT−tiX,0 Big).
Adicionando esses valores para todos os alarmes, obtemos o número total de alarmes tocando por tempo T .
Depois disso, o problema inicial é resolvido pela pesquisa binária por T : com aumento T o número de alarmes tocando não diminui (ou seja, a função é monótona); você pode selecionar 0 como a borda esquerda inicial e a resposta máxima possível no problema com a direita.
B. Torneio esportivo
Condição da tarefaEnquanto Masha estava de férias, seus colegas organizaram um torneio de xadrez no sistema olímpico. Durante o resto, Masha não prestou muita atenção a esse empreendimento, então mal consegue se lembrar de quem jogou com quem (não há nem uma palavra sobre a ordem dos jogos). De repente, Masha teve a idéia de que seria bom levar uma lembrança das férias para o vencedor do torneio. Masha não sabe quem venceu o jogo final, mas pode descobrir com facilidade quem jogou, se ela se lembrasse corretamente dos pares. Ajude-a a verificar se é esse o caso e identifique possíveis candidatos para os vencedores.
Este problema pode ser resolvido restaurando o gráfico dos jogos do torneio. Para começar, fica claro para cada participante em que estágio do torneio ele chegou: isso é determinado pelo número de jogos com sua participação.
Depois disso, você pode distribuir os jogos em passeios. Digamos, em todos os jogos do primeiro turno, um dos participantes decolou no primeiro turno e o outro decolou não antes do que no segundo. Ao processar um jogo de turnê com um número x é necessário verificar se todos os participantes deste jogo jogaram atualmente o mesmo número de jogos correspondente ao número x caso contrário, o torneio é inválido.
Depois de restaurar o esquema do torneio, tudo o que resta é deduzir a resposta.
C. jogo interessante
Condição da tarefaPetya e Vasya estão jogando um jogo interessante. Primeiro, Vasya anuncia quantos pontos você precisa marcar para o jogo terminar. Então Petya pega as cartas nas quais números inteiros não negativos são escritos e começa a colocá-las na mesa, uma a uma. Se houver um múltiplo de cinco no cartão, Vasya receberá um ponto. Se houver um múltiplo de três no cartão, um ponto recebe Petya. Se houver um número no cartão que não seja múltiplo de três ou cinco, ou vice-versa, múltiplo de ambos, ninguém receberá pontos.
Assim que um dos participantes ganha o número de pontos que Vasya nomeou no início do jogo, o jogo para e esse jogador se torna o vencedor. Se nenhum dos participantes marcou o número necessário de pontos, mas ao mesmo tempo todas as cartas terminaram, o jogador com mais pontos é considerado o vencedor. Se todas as cartas terminarem e os pontos forem igualmente divididos, um empate será declarado.
Petya e Vasya às vezes têm pressa, então não querem jogar o jogo completamente, mas descobrem imediatamente quem venceria com os dados iniciais conhecidos. Eles pediram que você escrevesse um programa que ajudasse a responder a essa pergunta.
O mais importante nesta tarefa é entender corretamente a partir da condição de quais jogadores e quantos pontos são concedidos após cada nova jogada, e também sob quais condições o jogador os ganha.
O problema é resolvido de maneira direta. Como as restrições são mais do que suaves, basta analisar os dados uma vez, interrompendo o processamento, se um dos jogadores no próximo passo marcar o número necessário de pontos. Se o número mínimo exigido de pontos não tiver sido marcado por nenhum dos jogadores, o vencedor é determinado no final do ciclo.
Em algumas versões desta tarefa, era necessário lidar ainda mais com a situação em que os jogadores podiam receber pontos ao mesmo tempo pela mesma carta.
Espera-se que esta tarefa seja a mais fácil entre todas as tarefas de qualificação.
D. Analisador de exceções
Condição da tarefaDescrevemos a sintaxe de uma linguagem de programação EX :
func f() {...} - declaração de função (entre colchetes - o corpo)maybethrow Exc é um comando que pode maybethrow Exc uma exceção do tipo Exc ou não.try {...} suppress Exc - se uma exceção do tipo Exc ocorrer dentro desse bloco, ela será suprimida.f() é uma chamada para f .
No idioma EX todas as instruções, exceto declarações de função, podem estar apenas no corpo de uma função. As funções não podem ser declaradas dentro de outras funções. Uma função pode ser chamada antes de ser definida, bem como em seu próprio corpo. Nomes de funções e exceções no idioma EX deve corresponder à expressão regular [a−zA−Z0−9 ]+ , seja único e não corresponda às palavras-chave func , try , suppress , maybethrow .
Um programa em idioma é inserido EX e número x . Para cada função do programa, não mais que x exceções que podem sair dela. Saída x lexicograficamente as menores exceções.
Essa tarefa acabou sendo a mais difícil de todas as tarefas de qualificação.
Para resolvê-lo, foi possível analisar o programa sintaticamente, construindo um gráfico de chamadas de função: nesse gráfico, cada função corresponde a um vértice e, na chamada de função, uma aresta. Depois disso, é necessário implementar diretamente a lógica da distribuição de exceções no gráfico - para isso, é adequado um deslocamento transversal do gráfico em largura.
Vamos escolher alguma exceção e todas as funções que podem dar origem a ela. Essas funções são chamadas de outras funções; talvez as chamadas estejam dentro do bloco try {...} suppress - nesse caso, a exceção não se aplica à função na qual a chamada ocorre. Assim, é possível determinar todas as funções a partir das quais essa exceção pode ser lançada usando a largura de travessia do gráfico.
Após o desvio ter sido realizado para todas as exceções possíveis, resta apenas formar uma resposta.
E. Decodificação
Condição da tarefaUm novo serviço apareceu na Internet. Infelizmente, ele não tem documentação. Empiricamente, a sequência s foi recebida do servidor. No entanto, alguns caracteres nesta linha são codificados - para obter uma resposta real, você precisa decodificar essa linha várias vezes. Como não há documentação para o serviço, para novas experiências, é necessário determinar o número máximo de vezes que essa linha pode ser decodificada de maneira não trivial. O procedimento de decodificação é o seguinte: você precisa encontrar todas as substrings do formato ~XY , em que X e Y são dígitos hexadecimais grandes ou pequenos e substitui-os simultaneamente por um caractere com um código ASCII 
(cada substring possui seu próprio). A decodificação é chamada trivial se não houver substrings desse tipo.
Em uma única linha, imprima o número máximo de decodificações não triviais consecutivas da sequência original.
Consideraremos os caracteres da sequência de origem sequencialmente, da esquerda para a direita. Se adicionar outro caractere resultar em uma sequência que pode ser decodificada, você precisará fazer isso. A decodificação deve ser repetida o maior tempo possível, ou seja, enquanto no final da linha atual há uma sequência do formulário definido pelas condições da tarefa.
Para cada caractere da sequência decodificada resultante, lembre-se de quantas vezes para obtê-la foi necessário decodificar a sequência original. É claro que o caractere adicionado à string é decodificado zero vezes. Se os símbolos decodificados participarem da próxima operação de decodificação r1,r2,...,rk vezes, então o símbolo que eles formaram requer max(r1,r2,...,rk)+1 operações de decodificação.
Deixe a sequência decodificada final conter caracteres a1,...,ak , para obter o que era necessário realizar a decodificação, respectivamente, r1,...,rk vezes. Então a resposta é a quantidade
max(r1,...,rk).
F. Encontrando uma confirmação de quebra
Condição da tarefaO Yandex Search implementa a política de "tronco verde": qualquer código que entra no repositório, com algumas ressalvas, é garantido para não interromper a montagem e os testes.
Os testes, no entanto, são extremamente difíceis, e executá-los em todos os commit é impraticável. Portanto, para casos particularmente difíceis, o seguinte procedimento é implementado: os testes são executados com alguma regularidade e um conjunto de confirmações é verificado imediatamente. Assim, por algum tempo n confirmações não testadas podem cair no tronco, entre as quais pelo menos uma contém um erro.
Em tal situação, o sistema de teste deve detectar o número m do primeiro commit que interrompeu os testes. Esse número tem a seguinte propriedade: todos confirmados com números menores que m passam nos testes com êxito e confirmados com números maiores ou iguais a m falhas nos testes. A tarefa assegura que uma confirmação com as propriedades especificadas necessariamente exista e seja exclusiva.
Para economizar recursos, o sistema de teste pode verificar apenas uma confirmação por vez. Você precisa escrever um programa que determine o número m.
Essa tarefa possui um protótipo em nossa produção: alguns testes dos componentes de pesquisa são realmente muito complicados, muito caros de executar para cada confirmação e, para eles, o procedimento para encontrar falhas semelhantes à descrita na tarefa é implementado. Obviamente, os desenvolvedores podem usar a verificação pré-auditoria e, como regra, fazer isso, portanto esse procedimento não é tão frequentemente necessário.
Versões diferentes da tarefa diferiam no número de confirmações que precisam ser verificadas ao mesmo tempo.
A solução aqui é bastante simples: você precisa implementar uma versão um pouco mais complexa da pesquisa binária . Digamos, se você deseja verificar quatro confirmações por vez, é necessário dividir igualmente o segmento atual com quatro números. Durante a implementação, alguns cuidados devem ser tomados para evitar loops quando o comprimento do segmento for menor que o número de confirmações verificadas simultaneamente. Também é importante notar que, de acordo com as condições do problema, você pode verificar o mesmo commit várias vezes - às vezes é necessário fazer isso, por exemplo, se houver dois commits no total e precisar verificar três commits por vez.
As tarefas da rodada de qualificação discutidas estão disponíveis como treinamento do Codeforces . Também fizemos um treinamento nas tarefas das finais .