Olá Habr!

Uma vez, tendo estudado outro livro sobre a notória Data Science, cheguei à conclusão de que seria hora de colocar em prática o conhecimento acumulado e ver a vida do departamento de análise com meus próprios olhos. Felizmente, a Yandex lançou uma seleção para um estágio de seis meses na direção apropriada, e eu não pude passar. A aceitação das inscrições para 2020 já terminou, portanto, neste artigo, analisarei, com a consciência limpa, as tarefas que o Yandex se propôs a resolver para os candidatos na primeira etapa. Haverá código Python. Spoiler: difícil, mas interessante.

Tarefa 1. Prazo

A tarefa

O analista iniciante está tentando resolver o problema. Se o problema não puder ser resolvido, ele perde a motivação e a probabilidade de sucesso na próxima tentativa cai. Uma tentativa leva um dia e o prazo da tarefa é de 90 dias. A probabilidade de o analista resolver o problema a partir da i-ésima tentativa é:

$\frac{1}{(i+1)}$
$\frac{1}{(i+1)^2}$

Qual a probabilidade do analista resolver o problema antes do prazo?

Decisão

Você já deve ter digitado: "@nice_one, você disse que seria difícil, mas o que é isso?" Paciência, amigos, esta é uma tarefa simples para aquecer, mas há algo a perder se você não pensar sobre a condição. Vamos examinar o exemplo do primeiro parágrafo. É necessário calcular a probabilidade total de que o analista resolva o problema em qualquer um dos 90 dias disponíveis na reserva, enquanto a probabilidade de sucesso a cada i-ésimo dia é fornecida. Uma opção tentadora pode parecer substituir na expressão um número de 1 a 90 em vez de ie adicionar, mas isso não é verdade. Essa expressão indica a probabilidade de sucesso em um i-dia específico, mas, para chegar a esse i-dia, o analista deve falhar nos últimos (i - 1) dias. Se a probabilidade de sucesso no i-ésimo dia for

\frac{1}{(i + 1)}

$\frac{1}{(i+1)}$ , então a probabilidade de falha neste dia é, portanto, igual a

1 - \frac{1}{(i + 1)} = \frac{i}{i + 1}

$1 - \frac{1}{(i+1)} = \frac{i}{i+1}$ . Como você sabe, para encontrar a probabilidade da ocorrência simultânea de vários eventos, é necessário multiplicar a probabilidade de cada ocorrência. Assim, a probabilidade de o analista lidar em exatamente n dias é

(\prod_{k = 1}^{n - 1} \frac{k}{k + 1}) \cdot \frac{1}{n + 1}

$\biggl(\prod\limits_{k=1}^{n-1}\frac{k}{k+1}\biggr)\cdot\frac{1}{n+1}$ .

Os membros sob o signo do trabalho são responsáveis pelo fracasso em cada um dos primeiros

(n - 1)

$(n - 1)$ dias, é necessário multiplicar o produto pela probabilidade de sucesso no n-ésimo dia.
Portanto, por qualquer número de dias, sabemos a probabilidade de sucesso exatamente nesse período. Estamos interessados na probabilidade total de sucesso para cada período possível de até 90 dias, inclusive. Agora você pode substituir números de 1 a 90, mas já na fórmula resultante. A maneira mais fácil é escrever um loop em algum python que calcule e adicione probabilidades, o que eu fiz.

O código

import numpy as np

n = 90

probs = []

for i in range(1, n+1): #   

    prob_now = 1/(i+1) #      

    prob_not_before = []
    
    for k in range(1, i): #      
        prob_not_before.append(k/(k+1))
        
    prob_not_before = np.array(prob_not_before).prod() # 

    probs.append(prob_not_before * prob_now)

s = sum(probs) #   

print(s)

A decisão do segundo parágrafo é completamente semelhante à do primeiro, apenas a fórmula difere. Vou deixar o código resolvendo o segundo ponto - acho que tudo ficará claro.

Ponto 2

import numpy as np

n = 90

probs = []

for i in range(1, n+1): #   

    prob_now = 1/((i+1)**2) #      

    prob_not_before = []
    
    for k in range(1, i): #      
        prob_not_before.append(1 - (1/((k+1)**2)))
        
    prob_not_before = np.array(prob_not_before).prod() 

    probs.append(prob_not_before * prob_now)

s = sum(probs) #   

print(s)

Tarefa 2. O destino do hamster

A tarefa

Para sobreviver no inverno, o hamster faminto e ganancioso decidiu roubar uma fábrica de castanhas localizada a 1000 metros de seu buraco. Restavam 3.000 castanhas na fábrica. Um máximo de 1000 nozes são colocadas nas bochechas do hamster. Em todos os lugares e não importa com o que o hamster vá, a cada metro ele precisa ser reforçado com uma porca. O hamster já está na fábrica e é perigoso. Qual é o número máximo de nozes que ele pode estocar? A resposta deve ser arredondada para o número inteiro mais próximo.

Decisão

Fortemente remanescente da tarefa de um jipe, não é? Assim é, diante de nós é a sua próxima variedade. No caso geral, um veículo (neste caso, um hamster) aparece no problema do jipe, que precisa percorrer uma certa distância em condições de capacidade limitada do recipiente de combustível (bochechas do hamster). A ideia subjacente à solução para qualquer problema desta classe - ao longo do caminho, você pode deixar suprimentos de combustível e voltar para um novo. Caso contrário, não existe um algoritmo de solução única, pois as condições e os objetivos iniciais podem ser muito diferentes. A opção proposta aqui é interessante porque é necessário não apenas percorrer a distância da fábrica até o buraco (o que é fundamental, porque o hamster pode conter exatamente 1000 nozes, o que é suficiente para 1000 metros), mas transferir o máximo de nozes possível para ele. É melhor desenhar um diagrama,representando um comprimento de 1000 me um estoque de nozes na fábrica, e pense em como agir com o hamster se ele quiser transportar 3000 nozes para o buraco, comendo o mínimo possível, ou seja, tendo passado o mínimo possível a distância total. Vamos tentar avançar nos menores degraus, 1 m cada, transferindo todas as 3000 porcas com você em várias viagens.

Obviamente, para transferir 3000 nozes para qualquer ponto, o hamster precisará retornar ao anterior pelo menos 3 vezes. Quando restarem 2000 nozes e o restante for consumido ao longo do caminho, o hamster precisará de 2 viagens ao ponto anterior para movê-las para uma nova. Quando o combustível tem menos de 1.000 unidades, você não precisa voltar atrás, tudo se encaixa nas bochechas do hamster. Assim, o processo de transferência de porcas pode ser dividido em três etapas correspondentes. Vamos ver o que o hamster terá "consumo de combustível" em cada um. Quando houver mais de 2.000 nozes, para mover 1 metro, o hamster terá que:

Pegue as bochechas cheias de nozes e caminhe 1 m
Descarregar 998 nozes (1 comeu no caminho, 1 deixou para voltar)
Volte 1 m novamente para o estoque de nozes
Repita as etapas 1 a 3 para os segundos mil nozes
Pegue os últimos mil e siga em frente 1 m

Assim, 1 m de deslocamento com todas as presas custa um hamster 5 nozes. Quando as nozes se tornam <2000, e isso acontece após 200 m de movimento, o algoritmo é o seguinte:

Pegue as bochechas cheias de nozes e caminhe 1 m
Descarregar 998 nozes (1 comeu no caminho, 1 deixou para voltar)
Volte 1 m novamente para o estoque de nozes
Pegue os últimos mil e siga em frente 1 m

1 m de deslocamento custa ao hamster 3 nozes. Quando ele atingir o ponto de 534 m, um total de 2001 nozes serão consumidas, e o hamster terá que pegar as últimas 999 nozes e calmamente passar os 466 metros restantes no buraco. Quando ele chegar lá, 533 nozes permanecerão nas bochechas - esta será a resposta para o problema.

Quero observar que as tarefas dessa classe são bastante populares na teoria dos algoritmos, bem como em entrevistas em grandes empresas. A melhor maneira de aprender a resolvê-los é a prática. Não existe um mecanismo único para resolvê-lo (bem, ou ele passou por mim), mas é bem possível ajudá-los e desenvolver o pensamento criativo.

Tarefa 3. Distribuição analítica

A tarefa

Yandex quer criar

M

$M$ equipes de analistas. Ao contratar, cada analista escolhe aleatoriamente um grupo para onde ele trabalhará. O líder da equipe quer descobrir qual número mínimo de milhares de analistas é suficiente para contratar, para que seu grupo seja mais provável

P

$P$ não foi menos

N

$N$ pessoa?

Você deve escrever um programa Python que aceite

N

$N$ ,

M

$M$ e

P

$P$ em uma linha, e a saída fornece o número de milhares de analistas.

1 \leq N \leq 100

$1 \leq N \leq 100$ ,

1 \leq M \leq 100000

$1 \leq M \leq 100000$ ,

0 \leq P \leq 1

$0 \leq P \leq 1$

Decisão

Bem, o conhecimento de estatística, ou seja, a distribuição binomial , foi útil . Denotamos o número de analistas contratados pela Yandex para

X

$X$ . Cada um dos analistas contratados escolhe uma equipe. Do ponto de vista do líder da equipe, a contratação de um analista para o trabalho é um experimento com dois resultados: um novato entra na nossa equipe ou não. Probabilidade de acerto igual a

\frac{1}{M}

$\frac{1}{M}$ , a probabilidade do analista escolher outro grupo, respectivamente, é

\frac{M - 1}{M}

$\frac{M-1}{M}$ . No total, tais experimentos com a escolha da equipe serão

X

$X$ . O número de acessos em nossa equipe

n

$n$ do

X

$X$ a eleição de analistas é distribuída binomialmente, a função de distribuição é igual a:

P (n ⩽ N) = \sum_{k = 0}^{N} (\binom{X}{k}) (\frac{1}{M})^{k} (\frac{M - 1}{M})^{X - k}

$\mathbb{P}(n \leqslant N) = \sum\limits_{k=0}^{ N} \binom{X}{k}\, \biggl(\frac{1}{M}\biggr)^k \biggl(\frac{M-1}{M}\biggr)^{X-k}$

Esta função mostra a probabilidade de que o número de ocorrências seja menor ou igual ao especificado

N

$N$ . Estamos interessados na probabilidade de que o número de ocorrências seja maior ou igual ao número especificado, portanto, a tarefa é assim:

X : 1 - P_{x} (n ⩽ N) = P; X - ?

$X: 1 - \mathbb{P_x}(n \leqslant N) = P; X-?$

Ou seja, você precisa encontrar o número de analistas contratados

X

$X$ em que a equipe recebe pelo menos

N

$N$ pessoa para uma determinada probabilidade

P

$P$ .

Bem, descobrimos a matemática - como encontrá-la agora

X

$X$ ? Rebentando. Você pode escrever um ciclo que classifique o número de analistas contratados, aumentando-o até a probabilidade de obter pelo menos

N

$N$ analistas não serão satisfatórios.

O código

def c(n, k): #   ,    
    if 0 <= k <= n:
        nn = 1
        kk = 1
        for t in range(1, min(k, n - k) + 1):
            nn *= n
            kk *= t
            n -= 1
        return nn // kk
    else:
        return 0

def bin_prob(trials, k, m): #      

    return c(trials, k) * ((1/m)**k) * ((1 - 1/m)**(trials - k))

def cdf(maximum, trials, m): #   
    value = 0
    for i in range(maximum + 1):
        value += bin_prob(trials, i, m)
    return value

n, m, p = [(float(i)) for i in input().split()] #       
n = int(n)
m = int(m)


x = 1000 
while (1 - cdf(n, x, m)) < p: #      
    x += 1000 #   

print(int(x / 1000)) #

Tarefa 4. Pesquisa de presentes

A tarefa

Papai Noel trouxe Anastasia 100 presentes e os colocou debaixo da árvore de Natal. A árvore é grande e fofa, por isso é difícil navegar por Anastasia. Anastasia examina os presentes da seguinte maneira: acidentalmente estende a mão do lado aleatório da árvore para um intervalo aleatório, pega um presente, o examina e o coloca de volta. Acontece que toda vez que Anastasia pode igualmente receber qualquer presente daqueles que estão debaixo da árvore. Encontre a expectativa da parcela de presentes que Anastasia considerará por 100 trechos aleatórios?

Decisão

À primeira vista, a tarefa parece muito simples, até parece que uma solução pode ser encontrada por alguma fórmula elementar, mas nem tudo é tão simples. Não tão simples. Passei muito tempo indecentemente nessa tarefa, tentando pintar opções e derivar uma fórmula, mas não obtive sucesso. Depois fui ao Google e, para minha surpresa, tive que me aprofundar nos fóruns, antes de encontrar uma solução para o caso geral . Portanto, se selecionarmos aleatoriamente elementos de um conjunto com retorno, a probabilidade será

n

$n$ seleções de

m

$m$ elementos do conjunto retirar exatamente

k

$k$ iguais iguais:

P (m, k, n) = \frac{(\binom{m}{k}) \cdot k! \cdot S_{2} (n, k)}{m^{n}}

$P(m, k, n) = \frac{\binom{m}{k}\cdot k! \cdot S_2(n, k)}{m^n}$

Onde

S_{2}

$S_2$ existe um número Stirling do segundo tipo - o número de partições não ordenadas do conjunto de

n

$n$ itens em

k

$k$ subconjuntos não vazios. Bem, para encontrar a expectativa, é necessário somar as probabilidades calculadas por esta fórmula para cada fração possível dos presentes únicos examinados - de um centésimo a um todo. Isso pode ser feito usando um loop no Python.

O código

import math
import numpy as np
import sys
import sympy #     -   

sys.setrecursionlimit(10**9)

def c(n, k): # C

    return (math.factorial(n))/(math.factorial(k) * math.factorial(n-k))

def s(n, k): #      

    return sympy.functions.combinatorial.numbers.stirling(n, k)

    
def p(m, k, n): #    k

    return c(m, k) * math.factorial(k) * s(n, k) / (m**n)


pr = []
#      ,    ...
for j in range(1, 101): 
    pr.append(p(100, j, 100))
    
pr = np.array(pr)
#...    100
frac = np.array([i for i in range(1, 101)]) / 100


print(sum(pr*frac)) #

Tarefa 5. Viajante equivalente

A tarefa

O viajante começa a se mover ao longo das bordas de uma grade bidimensional com nós inteiros estritamente para a direita ou para cima. Ele se move de um ponto

(0, 0)

$(0, 0)$ exatamente

(100, 100)

$(100, 100)$ . Qual a probabilidade de atravessar um rio em linha reta, conectando os pontos inicial e final, se assumirmos que todas as rotas possíveis são igualmente prováveis? Acredita-se que o viajante atravessou o rio se estivesse na mesma rota estritamente acima e abaixo do rio. Uma entrada no rio não é considerada um cruzamento.

Decisão

Encontramos a probabilidade de cruzar a abordagem clássica - dividimos o número de rotas com interseção pelo número total de rotas possíveis. Deixe ser

n

$n$ - o comprimento das arestas da grade quadrada. Em seguida, o número total de rotas possíveis:

N = \frac{(2 n!)}{(n!)^{2}}

$N = \frac{(2n!)}{(n!)^2}$

A derivação da fórmula é descrita aqui . Mas como descobrir o número de rotas de travessia fluvial para cada

n

$n$ ? Tendo ficado intrigado com essa pergunta, decidi pegar alguns comprimentos de grade menores, desenhar campos e calcular manualmente quantas rotas atravessam o rio, na esperança de rastrear a dependência (eu recomendo que você também pegue um pedaço de papel e uma caneta e experimente desenhar pequenas grades e caminhos).

Deixe haver uma grade de tamanho 3 por 3 células. A diagonal lateral da grade é ocupada pelo rio, o viajante está no canto inferior esquerdo.

Cenário

O desenho não é perfeito, mas eu tentei, honestamente

Assim que fiz o desenho, percebi que seria muito mais fácil rastrear as rotas que o rio não atravessa, ou seja, as rotas abaixo do rio. Então será possível multiplicar seu número por 2, levando em consideração os caminhos dos espelhos acima do rio. Como também sabemos o número total de rotas, encontramos o número de pessoas que atravessam o rio. Mas voltando à tarefa principal - precisamos de um relacionamento entre

n

$n$ e o número de caminhos de travessia do rio.

Na figura acima, no caso de 3x3, marquei em azul algumas rotas "terrestres" acessíveis ao viajante: as rotas marcadas passam pelas bordas das células com uma coordenada horizontal de 2, o viajante não entra antes nas bordas esquerda e superior das células. Existem 3 rotas, ou seja,

n

$n$ . Agora vamos descobrir as rotas que passam pela célula na coluna 1.

Cenário

Marquei os novos caminhos em vermelho. Portanto, é claro que, se um viajante virar para a esquerda e depois para a borda superior da célula (1, 0), apenas dois dos três caminhos pelas células com uma coordenada horizontal de 2 estarão acessíveis para ele, porque você só pode mover para cima e para a direita - o terceiro caminho fica mais baixo . Assim, adicionando uma nova célula da coluna 1 à rota, aumentamos o número total de caminhos pelo número de rotas que passam pelas células da coluna 2 que não são inferiores à nossa nova célula.

Pegue uma grade 4 por 4 e continue a desvendar o emaranhado. Tornou-se claro que a adição de uma nova célula a uma coluna aumenta o número de caminhos pelo número de rotas que passam pela próxima coluna não abaixo da borda superior da célula adicionada. Não marcarei as rotas com cores, limitarei-me a uma descrição textual, mas se você considerar necessário, desenhe - no processo de resolução, desenhei uma dúzia de grades diferentes antes de conseguir sentir com confiança a dependência.

Cenário

A coluna mais à direita novamente nos fornece

n

$n$ rotas. A borda superior da célula (2, 0) será adicionada a nós

n - 1

$n-1$ rota. A borda superior da célula (2, 1) adicionará

n - 2

$n-2$ rota. A borda superior da célula (1, 0) adicionará tantas rotas quanto as células (2, 0) e (2, 1) foram adicionadas. Se desejar, você pode desenhar uma grade maior e continuar a considerar as rotas com o mesmo algoritmo. Nossa tarefa é calcular as rotas para uma grade 100x100. Para fazer isso, você pode escrever um programa que aceite a entrada

n

$n$ e construir uma matriz

n \times n

$n\times n$ a partir da coluna

n

$n$ e, em seguida, para cada célula das colunas anteriores, contando o número de caminhos adicionados pela célula com base nos dados da coluna anterior. Assim, será encontrado o número de caminhos que não são rios.

O código

import numpy as np
import math

def routes_total(n): #   
    return math.factorial(2*n) / (math.factorial(n)**2)

def fill_matrix(n): #  ,       
    net = np.zeros((n, n)) 
    net[0, 0] = n #    n 
    for i in range(n-2):
        net[1, i] = n - i - 1 

    for i in range(2, n):
        for j in range(n - i - 1): 
            net[i, j] = 0
            for g in range(j, n - i + 1):
                net[i, j] += net[i - 1, g]
    
    #      2,     
    return (2 * sum(sum(net))) 

#      -    1
print(1  - fill_matrix(100) / routes_total(100))

Tarefa 6. Estado da distribuição linear

A tarefa

O Estado de Distribuição Linear é uma multidão de cidades, algumas das quais conectadas por estradas.

Uma vez que o rei do Estado tomou conhecimento de que o povo dos pontos de ruptura estava prestes a invadir suas fronteiras. Como o Estado não estava pronto para a defesa, o rei tomou uma decisão difícil - dividir o Estado em muitos pequenos, cada um dos quais defenderá independentemente suas fronteiras.

Foi decidido que duas cidades podem e devem ser deixadas em um estado, se for possível chegar à segunda de uma cidade, mesmo que o Povo dos Pontos de Interrupção tome uma estrada entre duas cidades do Estado de Distribuição Linear. Em todos os outros casos, as cidades devem estar em diferentes estados.

Em cada estrada que cruze a fronteira de dois novos estados, é necessário colocar um bastião. Isso é necessário caso um desses estados seja capturado pelo People of Breakpoints. Então o segundo poderá continuar a defender suas fronteiras. Em outras palavras, o bastião será colocado na estrada que liga cidades de diferentes estados.

O rei pediu que você desse a ele uma lista de estradas nas quais você precisa colocar bastiões.

Formato de entrada e saída do programa

Formato de entrada

n

$n$

m

$m$ — .

(1 \leq n \leq 20000, 1 \leq m \leq 200000)

$(1 \leq n \leq 20000, 1 \leq m \leq 200000)$ . m . i

b_{i}, e_{i}

$b_i, e_i$ — ,

(1 \leq b_{i}, e_{i} \leq n)

$(1 \leq b_i, e_i \leq n)$

b — , . b — , , . , .

, , , , — .

Decisão

E aqui está o problema da teoria dos grafos. Por longas histórias sobre o destino do Estado da Distribuição Linear, os redatores ocultaram a tarefa bastante interessante de encontrar pontes em um gráfico cujos nós são cidades e as bordas são estradas. Resumidamente, uma ponte é uma aresta de um gráfico, cuja remoção cortará uma certa parte deste gráfico de outros vértices. Essa é a idéia de capturar a estrada - se a ponte for capturada, a comunicação entre algumas cidades será interrompida; caso contrário, sempre haverá uma estrada alternativa entre as cidades, pois são as pontes que os estados dividem, é necessário colocar bastiões nas pontes.

Algoritmo de pesquisa de ponte com base na pesquisa de profundidade(Pesquisa profundidade-primeira, DFS) - um método de travessia de gráfico no qual todas as arestas provenientes do vértice inicial são examinadas e, se a aresta leva a um vértice que ainda não foi considerado, o algoritmo inicia recursivamente imediatamente a partir desse vértice. O fato a seguir ajudará na busca de pontes:

Vamos procurar em profundidade, procurando agora todas as arestas do vértice V. Então, se a aresta atual (V, U) é tal que, do vértice U e de qualquer um de seus descendentes na árvore transversal, não há inverso caminho para o pico de V ou qualquer de seus ancestrais, a borda considerada é uma ponte.

Para aprender como verificar esse fato para o vértice V, introduzimos o horário de entrada no disco do vértice [V](do inglês. descoberto). Nesta variável, a etapa do algoritmo em que o vértice foi processado será registrada. Além disso, com cada vértice V, a variável [V] mais baixa será associada , à qual escreveremos o tempo de entrada do vértice U mais antigo, que pode ser alcançado a partir do vértice V. Durante o processamento inicial do vértice, menor [V] = disco [V] (para o vértice anterior a você não se entende), mas mais tarde, no processo de busca em profundidade, podemos encontrar um filho V, um dos quais leva ao ancestral de V (vamos chamá-lo de S). Nesse caso, atualizaremos o menor [V]: menor [V] = disco [S]. E quando podemos ligar a ponte? Então, quando procuramos em profundidade, chegamos ao topo, que não tem filhos que ainda não foram considerados (novamente, chamamos de U). Nesse caso, verificaremos qual o vértice mais antigo que pode ser alcançado a partir de U e se esse vértice mais antigo ocorre depois do pai imediato de U (isso é possível, por exemplo, quando U não tem filhos, então menor [U] = disco [U ] ), a conexão de U com o pai é uma ponte.

O código do algoritmo implementado com comentários está anexado abaixo. É conveniente não criar variáveis separadas para disco e menor de cada vértice, mas colocar matrizes para cada valor, em que o índice é o número do vértice ao qual o valor pertence.

O código

import sys
from collections import Counter
import numpy as np
sys.setrecursionlimit(10**6) 

n, m = [int(i) for i in input().split()]
roads = [None] #    -    
graph = {}  #      ,    
for i in range(1, n+1):
    graph[i] = []
for i in range(1, m+1):
    twns = [int(j) for j in input().split()]
    graph[twns[0]].append(twns[1])
    graph[twns[1]].append(twns[0])
    roads.append(frozenset([j for j in twns]))
    
disc = [0] * (n+1) #  discovered
lowest = disc.copy() #  lowest
used = disc.copy() #  used. ,    
c = Counter(roads)

timer = 0 #   
nbridges = 0 #  
bridges = [] #  

def dfs(v, parent): #    ,    
    
    global timer
    global nbridges
    global bridges
    
    timer += 1 #   
    disc[v] = timer 
    lowest[v] = timer
    used[v] = True #     
    for u in graph[v]: #      
        if u == parent:
            continue #      ,    ,    
        if used[u]: #  ,    ,  
            lowest[v] = min(lowest[v], disc[u]) # ,       ;  lowest 
        else: #   
            dfs(u, v) #      
            #           cc  U:
            lowest[v] = min(lowest[v], lowest[u])  
            if lowest[u] > disc[v]: #   u    v   ,   
                twns = [] # ,  
                twns.append(u)
                twns.append(v)
                if c[frozenset(twns)] > 1: #     ,  ,    
                    continue
                nbridges += 1
                bridges.append(roads.index(set(twns)))

dfs(1, 0) #      

print(nbridges)
bridges = np.sort(bridges)
for bridge in bridges:
    print(bridge)

A fonte a seguir me ajudou a lidar com o problema de várias maneiras , por isso considero necessário deixar um link para ele. Vale a pena assistir e aqui está este vídeo - há uma boa animação do algoritmo.

Conclusão

Essas são as tarefas que um especialista que solicita um estágio em Yandex deve resolver com confiança. O conjunto de tarefas acima recebeu cinco horas - em minha opinião, um período bastante curto, mas todos trabalham no seu próprio ritmo.

Minhas decisões foram testadas e elas fornecem as respostas corretas, no entanto, não tenho dúvidas de que existem maneiras mais eficazes de lidar com as tarefas propostas. Se você estiver pronto para oferecer uma solução mais rápida ou compreensível ou se encontrar algum erro comigo, não hesite em escrever sobre isso.

Desejo que todos encontrem uma posição para si!

Estágio de analista em Yandex: análise de tarefas de teste

Tarefa 1. Prazo

A tarefa

Decisão

Tarefa 2. O destino do hamster

A tarefa

Decisão

Tarefa 3. Distribuição analítica

A tarefa

Decisão

Tarefa 4. Pesquisa de presentes

A tarefa

Decisão

Tarefa 5. Viajante equivalente

A tarefa

Decisão

Tarefa 6. Estado da distribuição linear

A tarefa

Formato de entrada

Decisão

Conclusão

More articles: