Fundo:
Originalmente, eu postei essa pergunta na noite passada e recebi uma reação negativa por sua imprecisão. Desde então, tenho consultado muitas pessoas sobre não apenas a redação do problema, mas também sua complexidade (que não é O (1)). Esse problema de programação é um mal giro em uma pergunta de entrevista na Amazon.
Questão:
Dada uma sequência de números inteiros concatenados aleatoriamente [0, 250), 0 a 250 exclusivos, há UM número ausente na sequência. Seu trabalho é escrever um programa que calcule esse número ausente. Não há outros números ausentes na sequência além desse, e é isso que torna esse problema tão difícil e possivelmente computacionalmente difícil.
Fazer esse problema manualmente em Strings menores, como nos exemplos 1 e 2 abaixo, é obviamente muito fácil. Por outro lado, calcular um número ausente em conjuntos de dados incrivelmente grandes envolvendo números de três ou quatro dígitos seria incrivelmente difícil. A idéia por trás desse problema é construir um programa que fará esse processo para você.
Informação importante:
Uma coisa que parecia bastante confusa quando eu postei esse problema na noite passada foi: como exatamente um número ausente é definido. Um número ausente é o número DENTRO do intervalo especificado acima; NÃO necessariamente o dígito. No exemplo 3, você verá que o número ausente é 9, mesmo que apareça na sequência. Existem 3 locais em que o DIGIT 9 aparecerá em uma série de [0, 30): "9", "19" e "29". Seu objetivo é diferenciar entre eles e descobrir que 9 é o NÚMERO ausente (dentro do exemplo 3). Em outras palavras, a parte complicada está em descobrir quais seqüências de dígitos estão completas e quais pertencem a outros números.
Entrada:
A entrada é uma String S, contendo números inteiros de 0 a 249, inclusive, ou de 0 a 250 exclusivos (em outras palavras, [0, 250)). Esses números inteiros, como declarado acima, são embaralhados para criar uma sequência aleatória. NÃO há delimitadores ("42, 31, 23, 44") ou 0 de preenchimento (003076244029002); os problemas são exatamente como descrito nos exemplos. É garantido que haja apenas 1 solução nos problemas reais. Várias soluções não são permitidas para elas.
Critérios de vencimento:
Quem tiver o uso de memória mais rápido e mais baixo será o vencedor. No evento milagroso em que o tempo se liga, menor memória será usada para o intervalo. Por favor, liste o Big O se puder!
Exemplos:
Os exemplos 1 e 2 têm um intervalo de [0, 10)
Os exemplos 3 e 4 têm um intervalo de [0, 30)
(Os exemplos 1 a 4 são apenas para demonstração. Seu programa não precisa lidar com eles.)
Os exemplos 5 têm um intervalo de [0, 250)
1. 420137659
- Missing number => 8
2. 843216075
- Missing number => 9
3. 2112282526022911192312416102017731561427221884513
- Missing number => 9
4. 229272120623131992528240518810426223161211471711
- Missing number => 15
5. 11395591741893085201244471432361149120556162127165124233106210135320813701207315110246262072142253419410247129611737243218190203156364518617019864222241772384813041175126193134141008211877147192451101968789181153241861671712710899168232150138131195104411520078178584419739178522066640145139388863199146248518022492149187962968112157173132551631441367921221229161208324623423922615218321511111211121975723721911614865611197515810239015418422813742128176166949324015823124214033541416719143625021276351260183210916421672722015510117218224913320919223553222021036912321791591225112512304920418584216981883128105227213107223142169741601798025
- Missing number => 71
Test Data:
Problem 1: 6966410819610521530291368349682309217598570592011872022482018312220241246911298913317419721920718217313718080857232177134232481551020010112519172652031631113791105122116319458153244261582135510090235116139611641267691141679612215222660112127421321901862041827745106522437208362062271684640438174315738135641171699510421015199128239881442242382361212317163149232839233823418915447142162771412092492141987521710917122354156131466216515061812273140130240170972181176179166531781851152178225242192445147229991613515911122223419187862169312013124150672371432051192510724356172282471951381601241518410318414211212870941111833193145123245188102
Problem 2: 14883423514241100511108716621733193121019716422221117630156992324819917158961372915140456921857371883175910701891021877194529067191198226669314940125152431532281961078111412624224113912011621641182322612016512820395482371382385363922471472312072131791925510478122073722091352412491272395020016194195116236186596116374117841971602259812110612913254255615723013185162206245183244806417777130181492211412431591541398312414414582421741482461036761192272120204114346205712198918190242184229286518011471231585109384415021021415522313136146178233133168222201785172212108182276835832151134861116216716910511560240392170208215112173234136317520219
Problem 3: 1342319526198176611201701741948297621621214122224383105148103846820718319098731271611601912137231471099223812820157162671720663139410066179891663131117186249133125172622813593129302325881203242806043154161082051916986441859042111711241041590221248711516546521992257224020174102234138991752117924457143653945184113781031116471120421331506424717816813220023315511422019520918114070163152106248236222396919620277541101222101232171732231122301511263822375920856142187182152451585137352921848164219492411071228936130762461191564196185114910118922611881888513917712153146227193235347537229322521516718014542248813617191531972142714505519240144
Problem 4: 2492402092341949619347401841041875198202182031161577311941257285491521667219229672211881621592451432318618560812361201172382071222352271769922013259915817462189101108056130187233141312197127179205981692121101632221732337196969131822110021512524417548627103506114978204123128181211814236346515430399015513513311152157420112189119277138882021676618323919018013646200114160165350631262167910238144334214230146151171192261653158161213431911401452461159313720613195248191505228186244583455139542924222112226148941682087115610915344641782142472102436810828123731134321131241772242411722251997612923295223701069721187182171471055710784170217851
N
, não apenas250
? / E o232
problema? Todas as possibilidades ou uma? Sei que você sabia sobre esse problema, mas acho que não está claro na pergunta. / Se esse for o código mais rápido , deve haver uma maneira de medi-los. É claro que rodar em um supercomputador é diferente de rodar em um computador antigo. / Porque ninguém disse isso, - Bem vindo ao PPCG!N
para, digamos, 1000 ou 10000.Respostas:
Clingo , ± 0.03 segundos
Isso é rápido demais para ser medido com precisão - você precisará permitir casos de entrada maiores em vez de parar artificialmente em 250.
Exemplo de entrada
Entrada é uma lista de pares ( k , k ésimo dígito). Aqui está o problema 1:
Saída de exemplo
fonte
45879362100
comn = 11
e1
faltando (respostasmissing(0)
).missing(10)
também é válido)?C ++, 5000 casos de teste aleatórios em 6,1 segundos
Isso é praticamente rápido, mas pode haver alguns casos de teste que o tornam lento. Complexidade desconhecida.
Se houver várias soluções, imprimirá todas elas. Exemplo .
Explicação:
Conte as ocorrências de dígitos.
Liste todas as respostas possíveis.
Verifique se um candidato é uma resposta válida:
3-1. Tente dividir a (s) sequência (s) por números que ocorrem apenas uma vez e marque-a como identificada, exceto o candidato.
Por exemplo,
2112282526022911192312416102017731561427221884513
possui apenas um14
, para que possa ser dividido em211228252602291119231241610201773156
e27221884513
.3-2. Se qualquer seqüência de caracteres tiver comprimento 1, marque-a como identificada.
Se qualquer contradição for feita (identificada mais de uma vez), o candidato não é válido.
Se não conseguirmos encontrar o candidato na string, o candidato é válido.
3-3. Se qualquer divisão for feita, repita a etapa 3-1. Caso contrário, faça uma pesquisa de força bruta para verificar se o candidato é válido.
Experimente online!
fonte
Limpo , ~ 0.3s
Corrigido um erro enorme no algoritmo, preciso reimprimi-lo agora.
Ajuntar com
clm -h 1024M -s 16M -nci -dynamics -fusion -t -b -IL Dynamics -IL Platform main
Isso funciona pegando todos os números que a string precisa conter e contando o número de lugares que a sequência de dígitos necessária está presente na string. Em seguida, ele executa repetidamente estas etapas:
singles
)singles
)fonte