Дистанционная подготовка: Есть ли правильные ответы для задачи 617 на PascalABC?
Есть ли правильные ответы для задачи 617 на PascalABC?
от Анна Яценко - Пятница 7 Февраль 2014, 03:10
  Скажите, пожалуйста, есть ли правильные ответы для задачи 617 на PascalABC?

У вас в таблице указано количество правильных решений задач для различных языков, но PascalABC там нет.

Я пробовала использовать алгоритм, указанный Меньшиковым для этой задачи, пробовала этот алгоритм немного изменить, все равно с большими числами время выполнения не укладывается в 1 секунду.

Я помню, что решала эту задачу на TurboPascal, используя систему проверки с диска-приложения к книге, у меня все получалось.
Re: Есть ли правильные ответы для задачи 617 на PascalABC?
от Peter Cherepanov - Пятница 7 Февраль 2014, 11:04
  При таких ограничениях можно просто хранить таблицу простых чисел (их всего 78498) и находить ответ за микросекунды на любом языке. Достаточно найти положение начального и конечного числа в таблице и их вычесть.
Re: Есть ли правильные ответы для задачи 617 на PascalABC?
от Анна Яценко - Суббота 8 Февраль 2014, 00:02
  Вы имеете ввиду, что таблицу можно вычислить заранее с помощью другой программы и хранить во внешнем файле?

А потом этот файл читать с помощью программы для задачи 817?
Re: Есть ли правильные ответы для задачи 617 на PascalABC?
от Peter Cherepanov - Суббота 8 Февраль 2014, 00:11
  Нет, внешние файлы читать не получится. Можно использовать инициализированный массив.
Я не говорю, что это красивый способ решения задачи, но он самый быстро работающий.
Re: Есть ли правильные ответы для задачи 617 на PascalABC?
от Анна Яценко - Суббота 8 Февраль 2014, 00:13
  О, ужас, вы имеете ввиду, что массив надо инициализировать 78498 числами? :)
Re: Есть ли правильные ответы для задачи 617 на PascalABC?
от Анна Яценко - Суббота 8 Февраль 2014, 00:14
  А вообще для PascalABC статистика не собирается?
Re: Есть ли правильные ответы для задачи 617 на PascalABC?
от Peter Cherepanov - Суббота 8 Февраль 2014, 04:49
  Пишите генератор, или программирующую программу.
С Паскалем я знаком в основном по статье http://www.lysator.liu.se/c/bwk-on-pascal.html
и за его версиями не слежу.

P.S.
Верное решение на PascalABC есть -- 32-39995 Даниил Аникин. Бесхитростное решето Эратосфена вполне проходит по времени.
Re: Есть ли правильные ответы для задачи 617 на PascalABC?
от Анна Яценко - Суббота 8 Февраль 2014, 23:19
  Я уже и решето Эратосфена пробовала еще до того, как задать вопрос на форуме - все равно последний тест не проходит по времени.

А Вы не посмотрите мой код (32-42539), если мне нельзя посмотреть код того, кто решил это задачу с помощью решета Эратосфена?