2 / 2 / 1
Регистрация: 05.08.2017
Сообщений: 61
|
||||||
1 | ||||||
Сколько различных прямоугольников может на листочке нарисовать Вася, если рисовать он умеет только по линиям?09.10.2017, 13:11. Показов 5838. Ответов 16
Метки нет (Все метки)
У Васи есть листочек в клеточку, состоящий из N клеток по горизонтали и M клеток по вертикали, причем линии клеток листочка на краю также видны. Сколько различных прямоугольников может на этом листочке нарисовать Вася, если рисовать он умеет только по линиям?
Нашел решение, но не могу понять суть формулы. Может кто поможет подробно расписать, откуда получилась такая формула (сам процес получение формулы). Спасибо
0
|
09.10.2017, 13:11 | |
Ответы с готовыми решениями:
16
Сколько может быть дано различных сигналов, если каждый светофор имеет три состояния Сколько человек может говорить только по-французски и сколько может говорить на английском и французском языках? Найти интеграл методом прямоугольников по средним линиям Сколько бутылок воды выпьет Вася с друзьями, если бутылка воды стоит 20 коп |
Модератор
9871 / 5239 / 3306
Регистрация: 17.08.2012
Сообщений: 16,007
|
|
11.10.2017, 14:57 | 2 |
Элементарно, Ватсон.
Давайте перечислим все возможные прямоугольники, будем их сортировать, например, по ширине. Прямоугольников шириной 1 и высотой m будет 1n штук. Прямоугольников шириной 1 и высотой m-1 будет 2n штук. Прямоугольников шириной 1 и высотой m-2 будет 3n штук. ... Прямоугольников шириной 1 и высотой 1 будет mn штук. Всего шириной 1 будет 1n+2n+3n+...+mn=(1+2+3+...+m)n Прямоугольников шириной 2 и высотой m будет 1(n-1) штук. Прямоугольников шириной 2 и высотой m-1 будет 2(n-1) штук. Прямоугольников шириной 2 и высотой m-2 будет 3(n-1) штук. ... Прямоугольников шириной 2 и высотой 1 будет m(n-1) штук. Всего шириной 2 будет 1(n-1)+2(n-1)+3(n-1)+...+m(n-1)=(1+2+3+...+m)(n-1) ... ... ... Прямоугольников шириной n и высотой m будет 1∙1 штук. Прямоугольников шириной n и высотой m-1 будет 2∙1 штук. Прямоугольников шириной n и высотой m-2 будет 3∙1 штук. ... Прямоугольников шириной n и высотой 1 будет m∙1 штук. Всего шириной n будет 1∙1+2∙1+3∙1+...+m∙1=(1+2+3+...+m)∙1 Суммируем все получившиеся количества: (1+2+3+...+m)n+(1+2+3+...+m)(n-1)+...+(1+2+3+...+m)∙1=(1+2+3+...+m)(1+2+3+...+n) суммы в скобках есть ни что иное, как суммы арифметических прогрессий с первым членом, равным 1, и разностью прогрессии, также равной 1. Записываем то, что в скобках, как формулы для суммы соответствующей прогрессии: (m(m+1)/2)(n(n+1)/2) используются целые числа, одно из двух подряд идущих целых чисел обязательно чётное, вместо оператора деления на 2 можно применить операцию деления на 2 нацело: (n(n+1) div 2)(m(m+1) div 2) Voila!
0
|
Почетный модератор
64300 / 47595 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
|
|
11.10.2017, 15:14 | 3 |
Самое интересное в его условии это прочитать m,n 2 числа размером, как в условии указано до 1010000
0
|
Модератор
9871 / 5239 / 3306
Регистрация: 17.08.2012
Сообщений: 16,007
|
|
11.10.2017, 15:32 | 4 |
Читал-читал... Как отреагирует, я всех его Васей в одну тему солью...
0
|
41 / 74 / 15
Регистрация: 04.10.2017
Сообщений: 283
|
|
13.10.2017, 17:33 | 5 |
1
|
2386 / 1298 / 1492
Регистрация: 29.08.2014
Сообщений: 4,661
|
||||||
13.10.2017, 20:41 | 6 | |||||
особо не проверял (арифметику отсюда сдул: http://e-maxx.ru/algo/big_integer):
0
|
Модератор
9871 / 5239 / 3306
Регистрация: 17.08.2012
Сообщений: 16,007
|
|
15.10.2017, 09:04 | 7 |
tmpValue, спасибо, исправил в посте #2 "геометрических" на "арифметических".
0
|
Супер-модератор
|
||||||
15.10.2017, 12:08 | 8 | |||||
Зачем? Это ж FPC, тут свое есть:
1
|
Почетный модератор
64300 / 47595 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
|
|
15.10.2017, 12:25 | 9 |
volvo, А почему у меня просит gmp.dll? Модуль gmp есть.
0
|
Почетный модератор
64300 / 47595 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
|
|
15.10.2017, 12:34 | 11 |
Спасибо, уже разобрался.
Добавлено через 55 секунд Я скачал отсюда. http://ru.dll-ocx.com/download/gmp.dll/24618.html
0
|
41 / 74 / 15
Регистрация: 04.10.2017
Сообщений: 283
|
|
15.10.2017, 13:45 | 12 |
0
|
2 / 2 / 1
Регистрация: 05.08.2017
Сообщений: 61
|
|
16.10.2017, 18:37 [ТС] | 13 |
Скопировал и отправил решение на сайте e-olimp. Программа набрала 0%.
Добавлено через 1 минуту И этот вариант набрал 0%.
0
|
2386 / 1298 / 1492
Регистрация: 29.08.2014
Сообщений: 4,661
|
||||||
16.10.2017, 18:40 | 14 | |||||
а если убрать
0
|
2 / 2 / 1
Регистрация: 05.08.2017
Сообщений: 61
|
|
16.10.2017, 18:43 [ТС] | 15 |
тогда проходит на 40%, что и было до длинной арифметики.
После теста №9 пишет "Неверный ответ"
0
|
tmpValue
|
16.10.2017, 21:19
#16
|
Не по теме: Капинус, так, чисто ради любопытства, олимпиадное программирование подразумевает наличие программиста? Ну то есть кто здает задание, тот его и пишет.
0
|
2 / 2 / 1
Регистрация: 05.08.2017
Сообщений: 61
|
|
17.10.2017, 08:44 [ТС] | 17 |
0
|
17.10.2017, 08:44 | |
17.10.2017, 08:44 | |
Помогаю со студенческими работами здесь
17
Сколько различных протоколов может сформироваться? Сколько различных чисел может быть составлено? Сколько различных треугольников у него может получиться? Сколько различных последовательностей шаров может получиться? Сколько различных вариантов билетов может быть выписано? Сколько различных кодовых слов может использовать Игорь Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |