|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
25.07.2020, 15:33 | #91 |
Пользователь
Регистрация: 08.02.2020
Сообщений: 78
|
Спасибо, проверил, всё подошло)
Кстати это ешё одно задание к которому у меня нету своего варианта: Как известно, в разные годы дежурят и развозят подарки разные Деды Морозы. Но все они суеверны - развозят подарки на протяжении всего года, кроме дней, когда на календаре Деда Мороза "Пятница 13". Сколько дней Дед Мороз не развозил подарки во время своего дежурства? Входные данные В первой строке задано количество смен k дежурства Деда Мороза. Далее в k строках указаны года a и b (1920 ≤ a ≤ b ≤ 2050 по григорианскому календарю), попадающие на очередную смену. Выходные данные Вывести количество дней, когда Дед Мороз не будет развозить подарки. Нужно ли знать календарь для этой задачи? |
25.07.2020, 16:31 | #92 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,302
|
Благодаря питону знать календарь не надо.
Код:
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
26.07.2020, 12:20 | #93 |
Пользователь
Регистрация: 08.02.2020
Сообщений: 78
|
Я уже перешёл к олимпиадным задачам, по этому к большинству у меня нету своего варианта:
1)Посчитать сумму двух натуральных чисел A и B, записанных в римской системе счисления. Ответ также записать в римской системе счисления. M = 1000, D = 500, C = 100, L = 50, X = 10, V = 5, I = 1. Все числа – не превышают 2000. Входные данные В строке записано два числа в римской системе счисления, между которыми стоит знак + . Выходные данные Единственное число – сумма чисел, записанное также в римской системе счисления. Числа в римской системе счисления записаны большими латинскими буквами. Не смог выполнить, дошёл до сюда: Код:
Найти наибольшее количество зернышек, которое может собрать мышка на своем пути. Входные данные Первая строка содержит числа n и m – размеры пола (1 ≤ n, m ≤ 500). Далее идет n строк, начиная сверху, в каждой из которых размещено m чисел – количества зернышек на соответствующей плитке. Выходные данные Одно число – наибольшее количество зернышек, которое может собрать мышка на своем пути. 3)Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости N квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами – сами спички. Напишите программу, которая по количеству квадратов N, которое необходимо составить, находит минимальное необходимое для этого количество спичек. Входные данные Одно целое число N (1 ≤ N ≤ 10^18). Выходные данные Вывести минимальное количество спичек, требуемых для составления N квадратов. |
26.07.2020, 21:00 | #94 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,310
|
Рассуждения по 2-ой задаче (про мышку).
Мышка двигается от нижнего левого угла к правому верхнему. Если положить, что результат известен, то при обратном движении, от верхнего правого угла к нижнему левому, у мышки будет всегда выбор двух направлений: вперёд/вниз. На первом шаге заполняем массив. Выбираем ячейку прямо и пишем в ней сумму собранных зёрен. Продолжаем процесс до конца, а затем вниз до левого нижнего угла. Аналогично можно посчитать число собираемых зёрен и при движении только вниз, а затем только влево. Используем этот алгоритм для заполнения всех ячеек. Теперь можно указать путь мышки и наибольшее количество собранных зёрнышек. PS: Поскольку в данную ячейку, при движении справа налево, можно попасть двумя путями, то в саму ячейку пишем максимальную сумму из двух: сумма значения в ячейке с суммой из ячейки выше и суммой из ячейки справа. По поводу 3-й задачи. Для выкладывания первого квадрата нужны 4-е спички. Для минимизации числа спичек следующие квадраты используют уже выложенные спички. Можно показать, что для выкладывания прямоугольника с числом квадратов m*n потребуется: K = 2*m*n + m + n спичек. Пусть мы выкладываем вначале квадрат из квадратиков (1), а затем из оставшихся спичек достраиваем квадратики до заданного N (2). (1) В квадрате из квадратиков m = n. Нам требуется 2*m^2 + 2*m спичек. Получим m как ближайшее целое к корню квадратному из N. (2) Нам необходимо выложить ещё z = N - m^2 квадратиков. Число этих квадратиков не превышает z <= m*k, где k - число рядов квадратиков, дополняющих наш квадрат до N квадратиков. Понятно, что [z / m] - это число рядов квадратиков, которые надо доложить (берём целую часть от деления). Теперь посчитаем число построенных квадратиков: m * (m + k). Для их построения нам нужно известное число спичек, см. формулу выше (n = m + k). Возможно, что нам потребуется достроить ещё несколько квадратиков в последнем ряду: p = N - m * (m + k) Для их построения потребуется ещё 2*p + 1 спичка. Собственно всё. Осталась самая малость - реализовать на ЯВУ.
Как-то так, ...
Последний раз редактировалось ViktorR; 26.07.2020 в 22:18. |
26.07.2020, 23:00 | #95 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,310
|
Моё решение задачи о спичках:
Код:
Собственно почему изначально выбираем квадрат из квадратиков, а затем расширяем (достраиваем) до прямоугольника и, наконец, достраиваем последний ряд. Обоснование: Так как фигура, которую мы строим состоит из квадратиков, то для минимизации площади, занимаемой этими квадратиками нам необходимо строить квадрат. После построения квадрата вновь пристраиваемые квадратики должны использовать границы уже построенной фигуры, поскольку при этом минимизируется число используемых спичек. PSS: k - пристраиваемое число рядов. Если k чётное, то ряды можно пристраивать и снизу и справа. Т.е. форма будет оставаться "квадратной", но без части квадратов в нижнем правом углу ... Нас интересует не форма фигуры и каким способом мы пристраиваем оставшиеся квадратики - не важно. Код:
Как-то так, ...
Последний раз редактировалось ViktorR; 26.07.2020 в 23:29. |
28.07.2020, 21:33 | #96 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,310
|
Вот реализация алгоритма для поиска числа зёрен, собранных мышкой.
1. Этот алгоритм был описан в одной из книг. Мне удалось найти в Сети книгу: В. Потопахин, Turbo Pascal, Решение сложных задач, 2006 В ней описан алгоритм "Поиск пути с наибольшим весом" и дан пример на Паскале. К сожалению и описание алгоритма и его реализация грешат ошибками. Видимо спешили для издания (это последняя часть книги). Хотя находил много ошибок и в других главах. Но это не важно. Важно, что алгоритм рабочий. Его реализацию на Python и привожу. 2. Поскольку пол храма - это двумерный массив, то для его описания выбрал библиотеку Numpy. В этом случае обращение к элементам массива как и в Pascal. 3. При заполнении вспомогательного массива использован следующий алгоритм: а) двигаемся по столбцам справа налево, а по строкам сверху вниз. б) Заполняем первую строку и последний столбец суммой чисел предыдущего и текущего элементов. в) Для остальных элементов выполняется заполнение по принципу: суммируем значение текущего элемента с большим из двух (верхнего или правого). Пример: Код:
Размер пола и число зёрен задаём в тексте скрипта после комментария # ---- Main ----- Код:
Как-то так, ...
|
28.07.2020, 21:41 | #97 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,310
|
К предыдущему посту.
Примеры работы скрипта: Число зёрен 0 - 20. Размер пола 3, 7 Код:
Размер пола 4, 4 Код:
Размер пола 4, 4 Код:
Как-то так, ...
|
09.08.2020, 12:27 | #98 |
Пользователь
Регистрация: 08.02.2020
Сообщений: 78
|
3 задания, которые не смог выполнить:
1)Задано два натуральных числа A и B. Найти количество таких пар чисел (P, Q), что для них A является НОД(P, Q), а B – НОК(P, Q). Входные данные В единственной строке два натуральных числа A и B (A < 105, B ≤ 106). Выходные данные Единственное число – искомое количество пар. Мой вариант(не работает): Код:
Входные данные Первая строка содержит количество чисел n (1 < n < 101). Во второй строке через пробел заданы n натуральных чисел, каждое из которых не превышает 30000. Выходные данные НОД заданных чисел. Мой вариант(выводит ошибку): Код:
Входные данные В одной строке заданы координаты последовательных вершин четырёхугольника. Все числа целые, не превышающие по модулю 100. Выходные данные Вывести площадь четырёхугольника, округленную до целых. Мой вариант (выводит ошибку): Код:
|
09.08.2020, 13:44 | #99 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,310
|
Сходу по 3-ей:
Четырёхугольник может быть и не прямоугольником и не параллелограммом. Многоугольник лучше разбивать на треугольники и считать их площади по формуле Герона.
Как-то так, ...
|
10.08.2020, 21:14 | #100 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,310
|
По поводу второй - найти НОД
Код:
Если i - НОД, то остатки должны быть нулевыми для обоих чисел. С другой стороны, думаю, что было бы быстрее, если начать искать НОД от меньшего из чисел и в сторону убывания последнего. Т.е. проверяем какое меньшее. Пытаемся делить большее на меньшее, если делится, то хорошо. Ищем первый делитель для меньшего числа (делим на 2, 3, ... и если находим делитель, то выбираем больший и проверяем на остальных числах. Добавлено: Так получилось у меня. Но не проверял на выборке. Код:
Как-то так, ...
Последний раз редактировалось ViktorR; 10.08.2020 в 23:47. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
готовлюсь к олимпиаде по информатике | salauat | Паскаль, Turbo Pascal, PascalABC.NET | 25 | 01.12.2013 21:32 |
Подготовиться к олимпиаде за лето | UaKot | Свободное общение | 20 | 10.05.2013 18:53 |
Подготовка к региональной олимпиаде | New man | Помощь студентам | 20 | 14.12.2012 21:01 |
Задачи по олимпиаде | Darick | Помощь студентам | 7 | 23.12.2011 15:45 |
Как подготовиться к олимпиаде? | Kn793 | Помощь студентам | 16 | 26.07.2008 12:22 |