Olá queridos Khabrovites. Uma série de artigos contém uma discussão sobre as tarefas que são dadas na 8ª série nas aulas de ciência da computação no Liceu de Física e Matemática de Chelyabinsk nº 31. Um pouco de história ... Nosso liceu é uma das instituições de ensino mais fortes da Rússia, que ocupa o 5º lugar no ranking de competitividade dos graduados, perdendo para as escolas de Moscou e São Petersburgo. Os alunos vencem regularmente competições a nível nacional e internacional.
Este artigo é desprovido de teoria; contém apenas métodos para resolver problemas. Detalhes sobre a pesquisa de posição são descritos aqui.
Então, vamos às tarefas. Essas tarefas envolvem o uso de pesquisa binária, incluindo a pesquisa de bin por respostas. Como sabemos, a pesquisa bin é um algoritmo para pesquisar objetos por um determinado atributo em um conjunto de objetos. Solicitamos listas classificadas em ordem crescente / decrescente. Apenas 4 tarefas, 2 das quais visam aplicar o "algoritmo sem passas" .
Nesta tarefa, você deve primeiro considerar os comprimentos da primeira e da segunda linhas e, em seguida, escrever cada próxima linha em uma lista. Depois, pegamos cada elemento da segunda lista e procuramos a borda direita e esquerda. Você pode perceber que, se o número não estiver na lista, os valores totais da borda esquerda e da borda direita na pesquisa de compartimento esquerdo e direito são iguais.
n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) for x in b: left = -1 right = len(a)
Aqui está este quebra-cabeça com uma torção! Aqui é necessário transformar a pesquisa para que ela seja realizada mesmo para números que não estão na lista da pesquisa. Aqui também procuramos o meio na "lista de limites" e, em seguida, o elemento que no meio é comparado com o número, se for menor, escrevemos o índice intermediário + 1 (ou seja, não inclui o meio passado na lista de limites) na borda esquerda (que é o índice), caso contrário, na borda direita, escrevemos o índice do meio. Fazemos tudo isso enquanto a borda esquerda é menor que a direita. Depois de encontrar a esquerda e a direita, consideramos o caso em que o número não está na lista e a distância para a esquerda é menor ou igual à da direita. Portanto, deduzimos a [esquerda - 1], caso contrário, a [esquerda].
n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) for x in b: left = 0 right = n - 1 while left < right: middle = (left + right) // 2 if a[middle] < x: left = middle + 1 else: right = middle if left > 0 and a[left] != x and abs(a[left - 1] - x) <= abs(a[left] - x): print(a[left - 1]) else: print(a[left])
Tadam! A tarefa de pesquisa binária por resposta. Para começar, na biblioteca de matemática, conectamos a função sqrt, que calcula a raiz quadrada, após a qual definimos 0 para a borda esquerda e 1e10 para a borda direita, ou seja, 10 bilhões, com base nas restrições especificadas na condição. Em seguida, como em uma pesquisa típica de lixeira, procuramos o meio, depois comparamos. Mas o que é interessante? Aqui o meio é x na equação. Em vista disso, determinamos o valor da equação e o comparamos com a resposta real (ou seja, C). Bem, movemos os limites, até que a diferença nos limites seja menor ou igual a 10 bilhões, essa é a precisão da medição. Mais tarde multiplicamos por um milhão, arredondamos, traduzimos em divisão int e real pelo mesmo milhão.
from math import sqrt c = float(input()) left = 0 right = 1e10
Já existe uma análise para esta tarefa, portanto, anexarei apenas o código.
n, x, y = map(int, input().split()) min1 = min(x, y) if n == 1: print(min1) else: left = 0 right = n * (x + y - min1 + 1) while right - left > 1: middle = (right + left) // 2 if n - 1 <= middle // x + middle // y: right = middle else: left = middle print(min1 + left + 1)
Para consolidar o material, você pode resolver problemas a partir daqui.