Matemática pura, física, lógica (braingames.ru): jogos cerebrais não relacionados com o comércio - página 213

 

Um problema para os programadores (o peso do problema é 4):

Um megabrain num texto muito longo precisa de substituir todas as letras "A" por "B" e todas as letras "B" por "A". O editor de texto permite que um conjunto arbitrário de caracteres seja substituído por outro em todo o texto. Por exemplo, a substituição de "AA"->"BSAA" fará com que a corda "AAAAAL" se torne "BSAABSAAL". Como completa ele a tarefa?

FAQ (a partir do sítio web):

Вы не знаете алфавита текстового редактора. Единственное, что вы знаете, это то, что он содержит символы "А" и "Б".

(Explicação de Mathemat: no primeiro campo (O QUE substituir) e no segundo (O QUE substituir) só se pode usar os caracteres A e B e nada mais, nem mesmo espaços: o alfabeto do texto e do editor de texto é-nos desconhecido. Ainda não está claro para mim porque é que este esclarecimento chave está ausente do texto do problema em si, mas infelizmente está).

A condição não diz isto explicitamente, mas presumo que todos os outros caracteres, excepto A e B, devem permanecer inalterados. Será isto correcto?

Sim.

O que significa "texto muito longo"?

1. Não se podem fazer todas as substituições manualmente.
2. qualquer sequência dada de caracteres pode ocorrer nela.
3. o megabrain não pode utilizar sequências com um comprimento comparável ao comprimento do texto para substituição.

Falta algum carácter no texto do "arsenal" do editor de texto?

Não.

É possível fazer múltiplas alterações ao longo do texto?

Sim.

Algumas sequências podem ser ignoradas? Por exemplo, a substituição de "AA"->"BSAA" mudará a string "AAAAAL" para "BSAAAL" (ou seja, a 2ª sequência foi ignorada).

Não.

Podem ser utilizadas expressões regulares (ou as suas contrapartidas) ao substituir?

Não.

A solução do problema chocou-me pela sua imprevisibilidade (embora outras soluções sejam bastante possíveis). Comecei a resolvê-lo há um par de anos, após o que desapareci dos Jogos da Mente durante um ano e meio. Há uns dias voltei a olhar para ela, e há cerca de 24 horas enviei a solução a um moderador. Ainda não recebi uma resposta, mas estou 100% certo de que está correcta. O algoritmo é testado num conjunto de caracteres de teste, não foram encontrados erros.

Задачи, загадки, логические игры [Игры разума] икф
  • www.braingames.ru
Мегамозгу в очень длинном тексте требуется заменить все буквы «А» на буквы «Б», а все буквы «Б» - на буквы «А». Текстовый редактор позволяет заменить во всём тексте один произвольный набор символов на другой. Например, в результате замены «АА»->«БСАА» строка «АААААЛ» перейдёт в строку «БСААБСАААЛ». Как ему выполнить задачу?
 
Mathemat:

Um problema para os programadores (o peso do problema é 4):

Um megabrain num texto muito longo precisa de substituir todas as letras "A" por "B" e todas as letras "B" por "A". O editor de texto permite que um conjunto arbitrário de caracteres seja substituído por outro em todo o texto. Por exemplo, a substituição de "AA"->"BSAA" fará com que a corda "AAAAAL" se torne "BSAABSAAL". Como pode ele fazer a tarefa?

FAQ (a partir do sítio web):

A solução para o problema apenas me chocou com a sua imprevisibilidade (embora eu esteja bastante aberto a outras soluções). Comecei a resolvê-lo há um par de anos, após o que desapareci dos Jogos Mentais durante um ano e meio. Há uns dias voltei a olhar para ela, e há cerca de 24 horas enviei a solução a um moderador. Ainda não recebi uma resposta, mas estou 100% certo de que está correcta. O algoritmo é testado num conjunto de caracteres de teste, não foram encontrados erros.

Não pode A->A, B->B, AA->B, B->A?
 
Avals:
Não pode A->A, B->B, AA->B, B->A?


Pode, mas não pode.

Por exemplo, aqui está o texto "AAAAAAAAAAAAAABBBBBBBBB", resultando em

 
Mathemat:

Um problema para os programadores (o peso do problema é 4):

Um megabrain num texto muito longo precisa de substituir todas as letras "A" por "B" e todas as letras "B" por "A". O editor de texto permite que um conjunto arbitrário de caracteres seja substituído por outro em todo o texto. Por exemplo, a substituição de "AA"->"BSAA" fará com que a corda "AAAAAL" se torne "BSAABSAAL". Como é que resolve o problema?

FAQ (a partir do sítio web):

A solução para o problema apenas me chocou com a sua imprevisibilidade (embora eu esteja bastante aberto a outras soluções). Comecei a resolvê-lo há um par de anos, após o que desapareci dos Jogos da Mente durante um ano e meio. Há uns dias voltei a olhar para ela, e há cerca de 24 horas enviei a solução a um moderador. Ainda não recebi uma resposta, mas estou 100% certo de que está correcta. O algoritmo é testado num conjunto de caracteres de teste, não foram encontrados erros.

É resolvido em 4 substituições:

A -> AA

B -> BAB

AA -> B

BAB -> A

 
Contender:

Resolvido em 4 substituições:

A -> AA

B -> BAB

AA -> B

BAB -> A

Não verificou, mas esta solução é dada nos comentários para aqueles que resolveram. Aqui está a minha solução:

A -> AB
B -> AB
AB -> B
AB -> A

Nota: as duas primeiras substituições (mais precisamente, as suas partes direitas) são formalmente idênticas.

Qualquer pessoa pode fazê-lo em menos de 4 movimentos?

-----------------------------------------------------------------------------

E a propósito, o que dizer deste problema?

Задачи, загадки, логические игры [Игры разума] икф
  • www.braingames.ru
Перед вами на столе два тонкостенных непрозрачных сосуда кубической формы (без верхней грани) емкостью 4.096 и 8 литров. Как, имея неограниченный запас воды, быстро отмерить ровно 5 литров?
 
Mathemat:

À sua frente na mesa encontram-se dois recipientes em forma de cubo opaco de parede fina (sem borda superior) com capacidades de 4.096 e 8 litros. Com um abastecimento de água ilimitado, como se pode medir rapidamente exactamente 5 litros?

A tarefa está aqui. O peso do problema é 5.

FAQ:

- as paredes são muito finas, o seu volume é insignificante.

- 4.096 é quatro litros inteiros e noventa e seis milésimos, exactamente. Exactamente 5 litros são exactamente 5, não, digamos, 5.002 litros.

- Opacidade significa que não se pode, por exemplo, colocar um cubo mais pequeno num maior e deitar água no maior até às bordas do mais pequeno. Por causa da opacidade, não pode ser feito com precisão suficiente.

- rápido é realmente rápido, bastante rápido. A decisão das dez etapas não será tomada. É demasiado longo.

É complicado. Resolvi-o em três passos.

1) Colocar um cubo pequeno num cubo grande, e encher o cubo grande até às bordas. Agora incline-o para que a superfície da água toque a borda do pequeno cubo. (se acidentalmente derramou demasiada água - dê mais um pouco, é muito).


Agora derramámos exactamente um litro de água. (O comprimento do segmento AB=5 cm, é fácil de calcular a partir do tamanho dos lados dos cubos (20cm e 16cm respectivamente).

Retire cuidadosamente o cubo pequeno, deixando toda a água (7 litros) no cubo grande.

Agora inclinar o cubo grande até a água tocar a borda "diagonal" (oposta à borda através da qual a água é vertida), e verter a água para o cubo pequeno.

O cubo grande conterá exactamente metade do seu volume (4 litros); o cubo pequeno conterá 3 litros (= 7 litros - 4 litros).

Agora encha o cubo grande até à borda ou um pouco menos. Coloque cuidadosamente o cubo pequeno com três litros de água dentro. O seu volume é superior a 3 litros, pelo que não vai afundar completamente, mas apenas o suficiente para deslocar 3 litros de água do cubo grande. Agora retire o cubo pequeno. O cubo grande tem exactamente cinco litros (8L - 3L), o que era necessário.

 
Mathemat:

Não verificou, mas tal solução é dada nos comentários para aqueles que decidiram. Aqui está a minha solução:

Nota: As duas primeiras substituições são formalmente idênticas.

Qualquer pessoa pode fazê-lo em menos de 4 movimentos?

Em três substituições globais, a solução só é possível se houver um carácter adicional presente no alfabeto permitido, mas garantido ausente no texto, o que pela condição do problema não é possível.

Em determinadas condições, quatro movimentos são mínimos. Pode ser (mas tediosa e verbosamente) provado. :)

 
MetaDriver:

É um complicado, fi-lo em três passos.

1) Colocar o cubo pequeno no cubo grande, e encher o cubo grande até à borda. Agora incline-o para que a superfície da água toque a borda do pequeno cubo. (se acidentalmente derramou demasiada água - dê mais um pouco, é muito).


Agora derramámos exactamente um litro de água. (O comprimento do segmento AB=5 cm, é fácil de calcular a partir do tamanho dos lados dos cubos (20cm e 16cm respectivamente).

Retire cuidadosamente o cubo pequeno, deixando toda a água (7 litros) no cubo grande.

Agora inclinar o cubo grande até a água tocar a borda "diagonal" (oposta à borda através da qual a água é vertida), e verter a água para o cubo pequeno.

O cubo grande conterá exactamente metade do seu volume (4 litros); o pequeno conterá 3 litros (= 7L-4L).

Agora despeje o cubo grande até à borda ou um pouco menos. Coloque cuidadosamente o cubo pequeno com três litros de água. O seu volume é superior a 3 litros, pelo que não vai afundar completamente, mas apenas o suficiente para deslocar 3 litros de água do cubo grande. Agora retire o cubo pequeno. O cubo grande tem exactamente cinco litros (8L - 3L), o que era necessário.

por isso, na primeira etapa são vertidos 2 litros )

0.05*0.2*0.2=0.002 м3

 
sanyooooook:

por isso, no primeiro passo, são vertidos 2 litros)

0.05*0.2*0.2=0.002 м3

está a mentir novamente ;)

a área do triângulo ABC = (0,05*0,2) / 2

total: ((0,05*0,2) / 2) * 0,2 = 0,001 m^3

 
MetaDriver:

Um problema complicado, resolvi-o em três passos.

1) Colocar um cubo pequeno num grande, e encher o cubo grande até às bordas. Agora incline-o para que a superfície da água toque a borda do pequeno cubo. (se tiver derramado acidentalmente demasiada água, dê-lhe uma recarga, é muita).

Original, mas parece haver uma contradição na opacidade. E segurar o grande cubo inclinado sem qualquer apoio não é tão fácil, são necessárias duas pessoas.

Agora, inclinamos o cubo grande até a borda da água tocar a borda "diagonal" (oposta à borda através da qual a água escoa), e despejamos a água no cubo pequeno.

E há aqui tretas semelhantes, especialmente com o despejar de água no pequeno. Derramar água do grande para o pequeno através da borda do grande é difícil sem dispositivos especiais.

Em suma, existe uma solução mais simples e mais curta :)

MD: Para três substituições globais, a solução só é possível se houver um carácter adicional que esteja presente no alfabeto válido, mas garantido ausente no texto, o que, pelos termos do problema, não é o caso.

Nestas condições, quatro pinceladas são mínimas, podendo ser provadas (mas tediosamente e verbosamente). :)

Os moderadores afirmam que ainda ninguém nos Jogos Mentais forneceu uma solução mais curta do que 4 jogadas. (Eu não propus o problema abaixo, é apenas um autómato do motor do nosso site).

Задачи, загадки, логические игры [Игры разума] икф
  • www.braingames.ru
У Мегамозга нашли страшную болезнь. Доктор выписал ему всего 4 таблетки двух видов (по две каждого вида), совершенно не отличимых друг от друга, и предупредил, что, если выпить более одной таблетки одного вида — смерть, не выпить таблеток — смерть, выпить за раз меньше нормы — смерть. Таблетки надо принять за два приема: утром — 2 таблетки (по...