Информативный заголовок: разминка
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Информативный заголовок: разминка - 2010-05-14 18:23:20.240000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
выбрав наугад два числа такие, что 2 <= x <= y <= 99, мы сообщаем человеку A их сумму, а человеку B - их произведение; обоим даётся задача найти исходные числа x и y. далее между ними происходит следующий диалог:
B: я не знаю чисел
A: я знаю, что ты не знаешь. я тоже не знаю
B: теперь я знаю числа
A: теперь я тоже их знаю
человек A и человек B - люди умные, и всего за четыре отвлечённых фразы они справляются с заданием. задача: написать и выложить в комментариях программу, которая найдёт загаданные числа, воспользовавшись приведённым диалогом. язык реализации - произвольный
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 18:29:22.220000
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
Потуплю немного. Программа должна найти ту пару чисел, которая привела А и В к результату?
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 18:32:40.790000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Родригес
Потуплю немного. Программа должна найти ту пару чисел, которая привела А и В к результату?
программа должна найти числа x и y. в качестве исходных данных A знал их сумму x + y, а B знал их произведение x * y
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 18:40:52.343333
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
Ясно.
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 18:51:17.860000
|
|
|
furiousangel
Сообщений: 1116
Оценки: 0
Присоединился: 2005-05-28 06:31:47
|
Если я правильно понял условие, то на php это должно выглядеть как-то так (код еще не проверял)
quote:
<?php
$sum = $argv[1];
$mul = $argv[2];
for ($a=2; $a<=99;$a++)
for ($b=$a; $b<=99;$b++)
{
if (($mul==$a*$b) && ($sum==$a+$b))
die("x=$a,y=$b");
}
Это брутфорсный вариант. Арифметический приводить думаю нет смысла:))
?>
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 18:51:28.806666
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Числа целые?
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:00:37.123333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: _SaZ_
Числа целые?
да
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:01:53.263333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: furiousangel
это должно выглядеть как-то так
нет, не так
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:03:04.900000
|
|
|
furiousangel
Сообщений: 1116
Оценки: 0
Присоединился: 2005-05-28 06:31:47
|
чего не так? Было проверено. Работает.
UPD: Точно не так). невнимательно прочитал условие. исправил в том же посте
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:17:24.026666
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: furiousangel
исправил в том же посте
приведённый диалог - существенная часть условия. может, в третий раз прочитаешь внимательно?
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:17:32.290000
|
|
|
Parano1d
Сообщений: 423
Оценки: 0
Присоединился: 2008-05-21 13:40:17.093333
|
furiousangel, в твоём примере известны $sum и $mul сразу. по условию они известны разным людям. по-моему брутфорс не является решением этой задачи
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:21:59.066666
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Вы в 7-й класс не ходили в школе или я не совсем понял, в чём фишка "диалога".
C#
using System;
namespace Denaturat_01
{
class Program
{
static void Main( string[] args )
{
try
{
const int A = 8;
const int B = 15;
Console.WriteLine( "Input: A = {0}; B = {1};", A, B );
int d = Convert.ToInt32( Math.Sqrt( A * A - 4 * B ) );
int x = ( A - d ) / 2; // 3
int y = ( A + d ) / 2; // 5
Console.WriteLine( "Output: x = {0}; y = {1};", x, y );
}
catch ( Exception )
{
Console.WriteLine( "Answer not found" );
}
finally
{
Console.ReadKey();
}
}
}
}
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:22:09.560000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Parano1d
по условию они известны разным людям
верно. так, человек А знает сумму чисел и ответы человека B; человек B знает произведение чисел и ответы человека A
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:24:24.130000
|
|
|
furiousangel
Сообщений: 1116
Оценки: 0
Присоединился: 2005-05-28 06:31:47
|
quote:
ORIGINAL: Denaturat
quote:
ORIGINAL: furiousangel
исправил в том же посте
приведённый диалог - существенная часть условия. может, в третий раз прочитаешь внимательно?
Эм…. может….
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:26:42.643333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: _SaZ_
Вы в 7-й класс не ходили в школе или я не совсем понял, в чём фишка "диалога".
второе. каждый знает только свою часть информации, и ничем кроме приведённых фраз они не обменивались: ни человек A, ни человек B не знают одновременно суммы и произведения чисел, у них есть только своя информация и её достаточно для нахождения решения
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:27:17.546666
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Ладно, это не для меня. Я не знаю, откуда начать копать в этом диалоге.
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:31:23.406666
|
|
|
Parano1d
Сообщений: 423
Оценки: 0
Присоединился: 2008-05-21 13:40:17.093333
|
quote:
Ладно, это не для меня. Я не знаю, откуда начать копать в этом диалоге.
у меня единственное предположение, что с длины строк… но вряд ли)
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:32:55.006666
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Если числа произвольные - то их невозможно связать с этим диалогом.
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:34:53.366666
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: _SaZ_
Если числа произвольные - то их невозможно связать с этим диалогом.
ещё как возможно. спокойно оцени все данные которыми располагают A и B в каждый момент времени
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:37:24.200000
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
quote:
ORIGINAL: _SaZ_
Если числа произвольные - то их невозможно связать с этим диалогом.
Нет, числа не произвольные. Вышеописанный диалог с последующим ответом возможен только при одной паре чисел. Вот их и должна найти программа.
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:37:57.570000
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
quote:
ORIGINAL: Denaturat
ни человек A, ни человек B не знают одновременно суммы и произведения чисел, у них есть только своя информация и её достаточно для нахождения решения
Думаю очевидно, что в данном случае будет 98*98 = 9604 решений. Осталось привязать каждое из них к диалогу :)
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:44:42.790000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
Я предлагаю перефразировать условие, чтобы оно стало яснее.
Загадочный человек X выбрав наугад два числа такие, что 2 <= x <= y <= 99, сообщил (шёпотом, на ушко) человеку A их сумму, а человеку B - их произведение (тоже шёпотом). После чего X скрылся в неизвестном направлении.
Далее мы наблюдаем диалог:
B: я не знаю чисел
A: я знаю, что ты не знаешь. я тоже не знаю
B: теперь я знаю числа
A: теперь я тоже их знаю
человек A и человек B - люди умные, и всего за четыре отвлечённых фразы они справляются с заданием. задача: написать и выложить в комментариях программу, которая найдёт загаданные числа, воспользовавшись приведённым диалогом. язык реализации - произвольный
Итого, нам неизвестны никакие числа. Но тем не менее, зная диалог, мы можем их восстановить.
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:44:54.773333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Родригес
Вышеописанный диалог с последующим ответом возможен только при одной паре чисел
вообще говоря, пара может быть и не единственной, хотя в данном случае это несущественно. усложнённый вариант данной задачи - определить корреляцию между размером диапазона и количеством решений; однако это уже нетривиально, потому не предлагаю
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:46:40.570000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: rgo
Я предлагаю перефразировать условие, чтобы оно стало яснее.
благодарю
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 19:58:29.276666
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: _SaZ_
Ладно, это не для меня. Я не знаю, откуда начать копать в этом диалоге.
Я могу дать изначальное направление. Помнишь задачки про мудрецов/математиков с абсолютно логичным мышлением, прокачивающих все варианты за считанные секунды? Вот это задачка того типа.
Если задачка денатурата непонятна, начни с такой:
Пока три мудреца спали в лесу, злодей измазал им лица сажей. Мудрецы проснулись утром одновременно и одновременно посмотрели друг на друга. Увидев лица спутников измазанные сажей они все трое начали ржать. Но через две секунды, они вдруг прекратили ржать. Вопрос: почему мудрецы прекратили ржать?
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 20:18:21.216666
|
|
|
furiousangel
Сообщений: 1116
Оценки: 0
Присоединился: 2005-05-28 06:31:47
|
Интересная задача. ПРоснувшись они увидели измазанные лица друг друга и начали смеяться. Но вспомнив, что костра они не разжигали и предположив, что на их лицах фекалии, стало несмешно %)
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-14 22:01:47.356666
|
|
|
Genco
Сообщений: 1662
Оценки: 90
Присоединился: 2007-12-16 23:11:22.003333
|
Закралась мысль,что фишка в том, КАКИЕ сумму и произведение им сообщили. Из разговора можно предположить,что они таковы, что произведение может получаться из чисел диапазона [2,98] совсем небольшим числом способов,специфическое такое…причем такой способ из этих,чтобы ещё и сумма оставалась неясной реально один. Ergo, надо подумать о простых числах и набросать программочку с грамотным перебором их произведений…. Мб если ещё подумаю - осмыслю проблему получше….
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-15 00:10:57.156666
|
|
|
SmanxX1
Сообщений: 208
Оценки: 0
Присоединился: 2007-07-31 14:33:56.650000
|
Это больше не задачка, а загадка, причем старая.
Ответ один. =)
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-15 00:36:41.320000
|
|
|
Lost_boy
Сообщений: 327
Оценки: 0
Присоединился: 2009-03-25 11:07:27.910000
|
Человек А и человек В знают только свои числа или они еще знают о том, что были проведены операции перед тем, как они получили числа?
З.Ы. rgo, каждый из них перестал смеяться потому, что понял, что измазаны не только его соседи, но и он сам?
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-15 00:48:44.456666
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Lost_boy
Человек А и человек В знают только свои числа или они еще знают о том, что были проведены операции перед тем, как они получили числа?
в смысле? человек A знает, что ему сказали сумму искомых чисел; человек B знает, что ему сказали их произведение
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-15 00:50:52.083333
|
|
|
Lost_boy
Сообщений: 327
Оценки: 0
Присоединился: 2009-03-25 11:07:27.910000
|
Все теперь ясно. А то я подумал что они не знают что это сумма и произведение соответственно, тогда задача показалась за гранью фантастики)
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-15 00:51:01.660000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: SmanxX1
Это больше не задачка, а загадка, причем старая.
Ответ один. =)
ну так разгадай загадку - а лучше научи это делать компьютер, всё быстрее будет
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-15 01:32:05.080000
|
|
|
S00pY
Сообщений: 785
Оценки: 0
Присоединился: 2007-04-14 20:44:05.376666
|
Первый говорит тот что знает произведение чисел… и он говорит что он не знает,значит типо у него произведение не двух простых,так?
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-15 01:45:11.630000
|
|
|
Genco
Сообщений: 1662
Оценки: 90
Присоединился: 2007-12-16 23:11:22.003333
|
Но,зная сумму,его осеняет. Значит,произведение как-то просто раскладывается….блин, всегда бесила олимпиадная математика((.
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-15 03:12:22.823333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: S00pY
так?
зачем спрашивать у меня, если можно проверить самостоятельно?
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-15 03:14:25.406666
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Genco
всегда бесила олимпиадная математика((.
никакой сложной математики здесь нет - исключительно умение извлекать максимум информации из минимума доступных данных
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-15 03:36:52.236666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Ну подкину и я пару мыслей по теме.
1) у B не могло быть число, которое однозначно раскладывается на сомножители, например, у него не могло быть числа 14, т.к. у него есть всего одно разложение на простые сомножители (2 и 7), но могло быть число 18, т.к. его можно разложить более чем одним способом (2 и 9, 3 и 6).
2) А узнал об этом только исходя из суммы своих чисел. следовательно, он разложил своё число на все возможные комбинации и просчитал, что произведения любой из этих пар может быть разложено более, чем одним способом. иначе, могла бы быть пара чисел, произведение которых раскладывалось бы на сомножители однозначно и B его сразу же определил бы. к примеру, предположим, что у A было число 11, возможные варианты слогаемых, их произведений и возможных разложений:
слог. произв. возм. сомнож.
сумма: 11
2 + 9 => 18 => 2 и 9, 3 и 6 - подходит (неоднозначное разложение)
3 + 8 => 24 => 2 и 12, 3 и 8, 4 и 6 - подходит
4 + 7 => 28 => 2 и 14, 4 и 7 - подходит
5 + 6 => 30 => 2 и 15, 3 и 10, 5 и 6 - подходит
с другой стороны, если бы у А было число 20:
сумма 20:
2 + 18 => 36 => 2 и 18, 3 и 12, 4 и 9, 6 и 6 - подходит
3 + 17 => 51 => 3 и 17 - не подходит (число 51 однозначно раскладывается на 3 и 17)
То есть у А могло быть число 11, но не могло быть число 20.
3) Если у А было число 11, то у B могли быть числа 18, 24, 28 и 30 (см. выше). Предположим, что у него было число 18. Возможные варианты разложения: 2 и 9, 3 и 6. Следовательно, у А могут быть числа 2 + 9 = 11 (что полностью подпадает под логические выводы из первых двух фрах) и 3 + 6 = 9. Проделаем с числом 9 ту же процедуру, что делали с числом 11:
сумма: 9
2 + 7 => 14 - не подходит, однозначное разложение.
То есть, если у B число 18, то он может высчитать, что у A либо 9, либо 11, при этом зная логику А, он понимает, что если бы у А было число 9, то он бы не сказал "я знаю [что ты не можешь высчитать число]", следовательно, у А число 11, а исходные числа - 2 и 9.
4) после того, как B узнал свои числа и сказал об этом, А пытается узнать, из какого числа (18, 24, 28 или 30) B мог сделать такой вывод. Если числа 24, 28 и 30 отпадут (проверять уже не стану), то бинго! А может сделать вывод, что у B число 18, и следовательно x и y равны 9 и 2.
В принципе, всё это можно формализовать и записать в виде алгоритма, на вход которого подавать одно из чисел - сумму или произведение, но получится дико замутно и жутко некрасиво, а поскольку всё гениальное просто, должен быть другой, простой и элегантный способ. Есть такое подозрение, что способ этот будет начинаться с канонического разложения всех произведений числа B и анализом коэффициентов при слогаемых. Дальнейшие действия на время оставляю на произвол публики и возвращаюсь к более земным и насущным проблемам.
(надеюсь, когда вернусь, кто-нибудь придумает что-нибудь не такое замутное)
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-15 03:40:40.953333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Да, и, насколько я понимаю, ни число человека А, ни число человека В основной программе не будет известно? В таком случае, необходимо просто перебрать все возможные значения B с неоднозначным разложением (по моим расчётам, их всего навсего 1343 :))
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-15 13:39:53.690000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: kreol
В принципе, всё это можно формализовать и записать в виде алгоритма, на вход которого подавать одно из чисел - сумму или произведение
а можно не подавать ничего, кроме имеющихся фактов, и получить ответ
|
|
|
|
|
RE: Информативный заголовок: разминка - 2010-05-15 15:32:03.310000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: Denaturat
а можно не подавать ничего, кроме имеющихся фактов, и получить ответ
Как я и сказал, если есть отработанный алгоритм проверки, можно прогнать все числа и посмотреть результат. Прогонять придётся около 2-3 тысяч пар чисел, что вполне терпимо. Если есть отработанный алгоритм.
|
|
|
|
|
|
