27 октября 2023 Сириус олимпиада по информатике ответы для 5, 6, 7, 8, 9, 10, 11 классов школьный этап 2023 ВСОШ
Ответы и решения для олимпиады по информатике Сириус для 5, 6, 7, 8, 9, 10, 11 класса школьного этапа 2023 всероссийской олимпиады школьников ВСОШ 4 группы регионов 27 октября.
Все ответы и решения: скачать
Ответы и решения для 5-6 класса
Задание 1: конференция
На конференции сказочных существ выступали Колобок, Золушка, Бармалей и Пятачок. Когда их спросили о порядке выступления, каждый из них сделал два заявления, один раз сказав правду и один раз —— неправду.
Колобок сказал:
- Я выступал первым;
- Золушка выступила сразу после Пятачка.
Золушка сказала:
- Я выступала первой;
- Пятачок выступал вторым.
Бармалей сказал:
- Я выступал третьим;
- Пятачок выступал последним.
Пятачок сказал:
- Я выступал вторым;
- Колобок был вторым.
Определите порядок выступления героев на конференции.
За полностью правильный ответ вы получите 100баллов, в противном случае —— по 20 баллов за каждое верное имя на нужной позиции.
Колобок
Пятачок
Золушка
Бармалей
Задание 2: пирамида
В 2023 году до нашей эры древнеегипетские строители получили заказ от фараона на постройку пирамиды. Пирамиду с основанием n×n строят следующим образом: сначала выкладывают из кубических блоков основание в виде квадрата n×n. Затем сверху по центру укладывают квадрат (n−2)×(n−2) затем ещё выше по центру —— квадрат (n−4)×(n−4) и так далее до самого верха.
Некоторые блоки такой пирамиды со всех сторон окружены другими блоками, некоторые блоки имеют две грани, которые видны снаружи, некоторые —— три видимых грани, и, если n нечётно, то верхний блок имеет пять граней, видимых снаружи. Фараон хочет, чтобы блоки, у которых видно ровно две грани, были украшены египетскими иероглифами по обеим граням.
На рисунке для примера представлена пирамида с основанием 5×5 блоков. Интересующие нас блоки выделены зелёным. Для этой пирамиды количество блоков, у которых видно ровно две грани, равно 16, и, соответственно, украсить иероглифами в этом примере потребуется 32 грани.
Для пирамиды с основанием 6×6 аналогичным образом можно заметить, что число блоков, у которых видно две грани, равно 24, и, значит, иероглифами нужно украсить 48 граней.
Фараон ещё не решил, какое основание будет у его пирамиды. Для начала он хочет увидеть проекты для пирамид с основаниями 7×7, 10×10,18×18 и 23×23 блока. Запишите в таблицу количество граней, которое потребуется украсить иероглифами в каждом из этих случаев. За каждый правильно найденный ответ вам будет начислено по 25 баллов.
Задание 3: кубики
Распределите в три столбика по два кубика одного (любого) цвета. Сделайте это, затратив как можно меньше ходов. За один ход можно переместить только один кубик. Разрешено брать только верхний кубик из столбика и перемещать его на любое свободное место в другом столбике. Максимально в один столбик помещается не более четырёх кубиков. Начальное положение кубиков приведено на рисунке.
Запишите порядок перемещений кубиков в следующем формате: «номер столбика, откуда берётся верхний кубик; пробел; номер столбика, в который кладётся этот кубик».
Команды записываются по одной в строке. Например, следующая последовательность команд
2 3 1 3 означает, что сначала из второго столбика верхний кубик переносится в третий столбик (на нижнюю позицию), а затем из первого столбика верхний кубик переносится в третий столбик (на вторую снизу позицию).
Оцениваться будут только решения, которые приводят к поставленной цели. Чем меньше шагов окажется в вашем алгоритме, тем больше баллов вы получите. За самый короткий алгоритм вы получите 100 баллов. Решения, в которых обнаружится некорректная команда (попытка взять кубик из пустого столбика или попытка положить кубик в полный столбик), оцениваются в 0 баллов.
Задание 4: орнамент
Тимофей любит украшать свою тетрадь по математике различными орнаментами. В этот раз он нарисовал узор из квадратов с попарно общими сторонами (см. рисунок). По количеству квадратов n определите длину всех нарисованных линий. Считайте, что длина стороны квадрата равна единице.
Ответом на эту задачу является некоторое выражение, которое может содержать целые числа и переменную n, операции сложения (обозначаются +), вычитания (обозначаются − ), умножения (обозначаются *) и круглые скобки. Запись вида 2n для обозначения произведения числа 2 и переменной n некорректна, нужно писать 2 * n.
Ваше выражение должно давать правильный ответ для любого натурального значения n. Например, для приведённых на рисунке n=4 значение выражения должно быть равно 13, а при n=5 значение выражения должно быть равно 16. Пример правильной формы записи ответа: 4 * n−2 * (n+5).
Задание 5: сегодняшнее число
Сегодня 27 октября 2023 года или 27.10.2023 —— кому как удобнее. Важно то, что для записи даты используются две цифры 0, одна цифра 1, три цифры 2, одна цифра 3 и одна цифра 7.
1) Сколько в этом году дат (включая сегодняшнюю), в записи которых используется такой же набор цифр? Во всех датах необходимо использовать ведущие нули, если они нужны. Две первые цифры определяют число месяца, две следующие —— номер месяца, четыре последних —— номер года (2023).
2) Составьте из всех этих цифр «наибольшую» корректную дату. Запишите только цифры, при этом необходимы ведущие нули в записях дней и месяцев, например, 07022321.
3) Используя шесть цифр из этих восьми, составьте наибольшее время, которое может быть корректной записью в 24‑часовом формате ЧЧ:ММ:СС (часы, минуты и секунды) на индикаторе электронных часов. Запишите только цифры, при этом необходимы ведущие нули в записях часов, минут и секунд, например, 070223.
4) Составьте из этих цифр наибольшее число‑палиндром (не обязательно использовать все цифры). Напомним, что палиндром читается одинаково как слева направо, так и справа налево. Например, такие числа, как 0, 7, 22, 818, 6226, являются палиндромами, а 10 или 1024 —— не являются.
5) Составьте из этих 8 цифр два четырёхзначных числа, таких, чтобы разность между большим и меньшим из них была минимальной. Чему она будет равна?
Например, если бы сегодня было 31 декабря 2012 года, то ответы на вопросы были бы такие:
1) 32) 101132223) 2322114) 213125) 7
В первом задании подходящими датами являются 23 ноября 2012, 13 декабря 2012 и 31 декабря 2012.
Во втором задании ответ соответствует дате 10 ноября 3222 года.
В третьем задании ответ соответствует времени 23:22:11.
В пятом задании разность 7 будет достигнута, например, для чисел 2120 и 2113.
Если вы не можете ответить на какой‑то вопрос, то запишите в соответствующем поле любое положительное число. За каждый правильный ответ вам будет начислено по 20 баллов.
Ответы и решения для 7-8 класса
Задание 1: Василисы Премудрые
На слёт юных Василис по обмену премудростями прилетело 5 Василис из разных княжеств: Новгородского, Смоленского, Ростовского, Казанского и Московского. Традиционно каждое княжество отвечало за свою науку: грамоту, строительство, арифметику, кораблестроение и звездознание. У каждого княжества знамя определенного цвета: белое, синее, зелёное, жёлтое и красное.
Известно, что:
1. Новгородцы обычно носят одежду в цвет знамени, и она белая. Они не любят ни читать, ни считать.
2. Казанское княжество в ответе за звездознание. Знамя у них ни красное, ни зелёное.
3. Ростовчане ничего не смогут нам рассказать ни о кораблях, ни о цифрах. Знамя у них синего цвета.
4. Смоленск считается самым грамотным, а знамя у них ни красное, ни жёлтое. Определите науки и цвета знамён княжеств.
Задание 2: Львы и тигры
В цирке выступают 3 льва и 6 тигров. Перед выходом на арену их требуется выстроить в некотором порядке. При этом необходимо учитывать, что никакой лев не переносит, когда непосредственно перед ним выбегает другой лев, а тигры, наоборот, чувствуют себя уверенно, когда спереди или сзади следует другой тигр. Если у тигра и спереди, и сзади есть сородич, он тоже доволен.
Произвольного льва обозначим буквой L, произвольного тигра обозначим буквой T. Львов между собой и тигров между собой различать не будем.
При этих условиях некоторый порядок их выхода можно задать последовательностью из трёх букв L и шести букв T. Например, последовательность LTLLTTTTTбудет нарушать упомянутые условия: в ней есть два льва, следующие друг за другом, и тигр, у которого нет соседа‑тигра.
Ваша задача —— вывести все правильные способы построения зверей перед выходом на арену.
Чем больше различных правильных ответов вы приведёте, тем больше баллов получите. Каждый способ построения зверей следует указывать в отдельном поле, добавляя их при необходимости. Вы можете вводить свои ответы в произвольном порядке. Буквы внутри одного ответа выводите без пробелов и других разделителей.
За каждый неверный способ построения зверей с точки зрения условия итоговый балл уменьшается на 10, но он не может стать меньше 0.
Если строки в ответе повторяются, то это никак не влияет на итоговый балл.
Задание 3: Кубики
Распределите в три столбика по два кубика одного (любого) цвета. Сделайте это, затратив как можно меньше ходов.
За один ход можно переместить только один кубик. Разрешено брать только верхний кубик из столбика и перемещать его на любое свободное место в другом столбике. Максимально в один столбик помещается не более трёх кубиков.
Начальное положение кубиков приведено на рисунке.
Запишите порядок перемещений кубиков в следующем формате: «номер столбика, откуда берётся верхний кубик; пробел; номер столбика, в который кладётся этот кубик».
Команды записываются по одной в строке. Например, следующая последовательность команд
23
13
означает, что сначала из второго столбика верхний кубик переносится в третий столбик (на нижнюю позицию), а затем из первого столбика верхний кубик переносится в третий столбик (на вторую снизу позицию).
Оцениваться будут только решения, которые приводят к поставленной цели. Чем меньше шагов окажется в вашем алгоритме, тем больше баллов вы получите. За самый короткий алгоритм вы получите 100 баллов. Решения, в которых обнаружится некорректная команда (попытка взять кубик из пустого столбика или попытка положить кубик в полный столбик), оцениваются в 0 баллов.
Задание 4: Крэги Уйлера
Уйлер разводит крэгов. Крэги —— удивительные существа, которые могут иметь, а могут и не иметь нос, глаз и ухо (но хотя бы один из органов есть у каждого, ведь надо же им всем как‑то ориентироваться в пространстве). При этом периодически рождаются везучие особи, у которых присутствуют сразу два органа, а иногда даже все три!
Уйлер ведёт строгий учёт всех своих крэгов. Он посчитал, сколько из них имеют
- нос;
- ухо;
- глаз;
- нос и ухо;
- нос и глаз;
- ухо и глаз;
- нос, ухо и глаз,
и получил 7 целых неотрицательных чисел. К сожалению, Уйлер не посчитал общее число своих крэгов и к тому же забыл, какое число чему соответствует. Помогите ему понять, сколько всего у него крэгов. Например, если бы Уйлер имел набор чисел 3,1,4,1,5,3,2, то у него могло бы быть
- 0 крэгов только с носом;
- 2 крэга только с ухом;
- 1 крэг только с глазом;
- 0 крэгов в точности с носом и ухом;
- 1 крэг в точности с ухом и глазом;
- 2 крэга в точности с носом и глазом;
- 1 крэг с носом, ухом и глазом,
то есть всего 7 крэгов. На рисунке три больших круга обозначают множества крэгов с ухом/носом/глазом, а в пересечении кругов лежат крэги, обладающие сразу несколькими органами; числами обозначено количество крэгов, лежащих строго в этой области. Несложно проверить, что в этом случае его подсчёты дали бы последовательность чисел (в том же порядке, какой указан в самом начале задачи) «3,4,5,1,3,2,1», что совпадает с исходным набором.
Можно доказать, что в этом случае другого суммарного количества быть не может, поэтому ответом для набора «3,1,4,1,5,3,2» является число 7. Решите теперь задачу самостоятельно для других пяти наборов чисел.
1.2,2,0,0,0,0,02.5,0,5,0,5,0,53.1,1,3,3,0,0,04.1,6,2,8,8,4,55.7,2,4,8,4,3,1
Каждый верно найденный ответ оценивается в 20 баллов, и при этом гарантируется, что в каждом из подпунктов существует ровно одно возможное суммарное число крэгов у Уйлера.
Задания по программированию.
Задание 1: Прямые и окружности
Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Окончив чертёж и подписав все цифры,Александров со спокойной отчетливостьюназвал все линии и все размеры, спряталмелок в карман и по‑строевому вытянулся,глядя в холодные глаза полковника.Александр Куприн, «Юнкера».Дополнительное задание, полученное Алексеем от строгого учителя, было следующим: требовалось выбрать на плоскости точку и провести через неё n различных прямых. После этого нужно было построить m различных окружностей с центром в отмеченной точке. На сколько частей все линии делят плоскость?
Формат входных данных
Две строки входных данных содержат два неотрицательных целых числа n и m (0 ≤ n, m ≤ 108).
Формат выходных данных
Выведите одно натуральное число —— ответ на вопрос задачи.
Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64‑битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java.
Система оценки
Решения, правильно работающие при n=0, будут оцениваться в 20 баллов.
Решения, правильно работающие при m=0, будут оцениваться в 20 баллов.
Замечание
В первом примере ни одной линии не проведено, плоскость на части не разделилась.
Во втором примере проведено две прямые и три окружности. Плоскость разделилась на 16 частей, как показано на рисунке.
Задание 2: Братья и сёстры
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Рославлев‑младший. Вот неожиданныйгость! Это брат мой!Александр Грибоедов, «Кто брат, кто сестра,или Обман за обманом».У Ани братьев в a раз больше, чем сестёр, а у её брата Бори братьев в b раз больше, чем сестёр. Сколько мальчиков и девочек в этой семье?
Формат входных данных
Две строки входных данных содержат два натуральных числа a и b (1 ≤ a, b ≤ 109). В этой задаче —— никакого обмана, гарантируется непротиворечивость входных данных.
Формат выходных данных
Выведите в двух строках два натуральных числа —— ответ на вопрос задачи. Первое число —— количество мальчиков, второе —— девочек.
Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 6464‑битный тип данных, например, long long в C++, int6464 в Free Pascal, long в Java.
Система оценки
Решения, верно работающие при a, b ≤ 100, получат не менее 50 баллов.
Замечание
В примере у Ани братьев в 5 раз больше, чем сестёр, а у её брата Бори братьев в 2 раза больше, чем сестёр. В семье 5 мальчиков и 2 девочки. Проверим: у Ани 1 сестра и 5 братьев (в 5 раз больше), а у Бори 2 сестры и 4 брата (в 2 раза больше).
Задание 3: Шестёрки
Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт —— Скажи нам, Сколько шестью шесть?—— Вы погодите, Дайте сесть! Я сразу не соображу! Я посижу, тогда скажу Эмма Мошковская, «Таблица умножения». Шестиклассница Эмма в последнее время увлеклась восточной культурой. Дома она носит ханьфу, старательно выводит кисточкой иероглифы и очень любит цифру шесть, которая в Китае символизирует гармонию и баланс. Сегодня, сидя за обедом, Эмма задумалась о том, что получится, если число, состоящее из одних шестёрок, возвести в квадрат. Помогите ей перемножить эти числа. Поскольку результат может оказаться очень большим, выведите только одну цифру на интересующей девочку позиции.
Формат входных данных
Две строки входных данных содержат два натуральных числа: n —— длина числа, состоящего из одних шестёрок, и k —— интересующая Эмму позиция в квадрате числа (1 ≤ n ≤ 109, 1 ≤ k ≤ 2×n).
Формат выходных данных
Выведите одну десятичную цифру —— ответ на вопрос задачи.
Система оценки
Решения, верно работающие при n ≤9, получат не менее 50 баллов.
Замечание
В первом примере n=1, в квадрат возводится число, состоящее из одной шестёрки, то есть 6. k=1, девочка хочет узнать первую цифру квадрата этого числа. 62=36, на первой позиции цифра 3. Во втором примере n=2 и k=3. 662=4356, на третьей позиции результата цифра 5.
Ответы и решения для 9-11 класса
Задание 1: Прямые и окружности
Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Окончив чертёж и подписав все цифры, Александров со спокойной отчетливостью назвал все линии и все размеры, спрятал мелок в карман и по‑строевому вытянулся, глядя в холодные глаза полковника. Александр Куприн, «Юнкера». Дополнительное задание, полученное Алексеем от строгого учителя, было следующим: требовалось выбрать на плоскости точку и провести через неё n различных прямых. После этого нужно было построить m различных окружностей с центром в отмеченной точке. На сколько частей все линии делят плоскость?
Формат входных данных
Две строки входных данных содержат два неотрицательных целых числа n и m (0 ≤ n, m ≤108).
Формат выходных данных
Выведите одно натуральное число —— ответ на вопрос задачи.
Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64‑битный тип данных, например, long в C++, int64 в Free Pascal, long в Java.
Система оценки
Решения, правильно работающие при n=0, будут оцениваться в 20 баллов.
Решения, правильно работающие при m=0, будут оцениваться в 20 баллов.
Замечание
В первом примере ни одной линии не проведено, плоскость на части не разделилась. Во втором примере проведено две прямые и три окружности. Плоскость разделилась на 16 частей, как показано на рисунке.
Задание 2: Братья и сёстры
Рославлев‑младший. Вот неожиданный гость! Это брат мой! Александр Грибоедов, «Кто брат, кто сестра, или Обман за обманом». У Ани братьев в a раз больше, чем сестёр, а у её брата Бори братьев в b раз больше, чем сестёр. Сколько мальчиков и девочек в этой семье?
Формат входных данных
Две строки входных данных содержат два натуральных числа a и b (1≤ a, b ≤109). В этой задаче —— никакого обмана, гарантируется непротиворечивость входных данных.
Формат выходных данных
Выведите в двух строках два натуральных числа —— ответ на вопрос задачи. Первое число —— количество мальчиков, второе —— девочек.
Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64‑битный тип данных, например, long в C++, int64 в Free Pascal, long в Java.
Система оценки
Решения, верно работающие при a, b ≤ 100, получат не менее 50 баллов.
Замечание
В примере у Ани братьев в 5 раз больше, чем сестёр, а у её брата Бори братьев в 2 раза больше, чем сестёр. В семье 5 мальчиков и 2 девочки. Проверим: у Ани 1 сестра и 5 братьев (в 5 раз больше), а у Бори 2 сестры и 4 брата (в 2 раза больше).
Задание 3: Шестёрки
Скажи нам, Сколько шестью шесть? Вы погодите, Дайте сесть! Я сразу не соображу! Я посижу, тогда скажу Эмма Мошковская, «Таблица умножения». Шестиклассница Эмма в последнее время увлеклась восточной культурой. Дома она носит ханьфу, старательно выводит кисточкой иероглифы и очень любит цифру шесть, которая в Китае символизирует гармонию и баланс.
Сегодня, сидя за обедом, Эмма задумалась о том, что получится, если число, состоящее из одних шестёрок, возвести в квадрат. Помогите ей перемножить эти числа. Поскольку результат может оказаться очень большим, выведите только одну цифру на интересующей девочку позиции.
Формат входных данных
Две строки входных данных содержат два натуральных числа: n —— длина числа, состоящего из одних шестёрок, и k —— интересующая Эмму позиция в квадрате числа (1 ≤ n ≤109, 1 ≤ k ≤ 2×n).
Формат выходных данных
Выведите одну десятичную цифру —— ответ на вопрос задачи.
Система оценки
Решения, верно работающие при n ≤9, получат не менее 50 баллов.
Замечание
В первом примере n=1, в квадрат возводится число, состоящее из одной шестёрки, то есть 6. k=1, девочка хочет узнать первую цифру квадрата этого числа. 62=36, на первой позиции цифра 3. Во втором примере n=2 и k=3. 662=4356, на третьей позиции результата цифра 5.
Задание 4: Награждение участников олимпиады
—— Мы все третье место заняли: и я,и Мишка, и Толька, и Кимка, все‑все.Вовка —— первое, рыжий лягушонок ——второе, а мы, остальные восемнадцать человек, мы заняли третье.Так инструктор сказал!Виктор Драгунский, «Третье местов стиле баттерфляй».
Жюри подводит итоги очередной олимпиады по информатике. В этот раз получилось так, что многие участники набрали одинаковое число баллов. Согласно окончательной таблице результатов, первое место заняли a1 участников, второе место —— a2 участников, …, заключительное n‑е место заняли an участников.
Согласно регламенту соревнования, требуется каждого участника наградить призом. Суммарно на все призы в смете олимпиады заложена сумма в P денежных единиц. Жюри хочет, чтобы при покупке призов выполнялись следующие условия:
1)1) Всем участникам, занявшим одно и то же место, достанутся одинаковые призы;
2)2) Всем участникам, занявшим заключительное n‑е место, достанутся призы стоимостью в 1 денежную единицу;
3)3) Разница d между призом участника на i‑м месте и призом участника на i+1‑м месте должна быть одинакова для всех i от 1 до n−1, в том числе может быть и так, что d=0, то есть все участники могут получить одинаковые призы независимо от занятого ими места.
Необходимо определить, какую максимальную разницу d жюри может запланировать при этих условиях, не выходя за пределы заложенной в смету суммы P.
Формат входных данных
В первой строке входных данных содержится одно натуральное число n —— количество различных мест, которые заняли участники олимпиады (2≤n≤105). В следующих n строках, по одному в строке, находятся натуральные числа ai —— количество участников, занявших i‑е место (i от 1 до n). Общее количество участников a1+a2+…+an не превосходит 1018, любое ai не менее 1. В последней строке находится натуральное число P —— сумма, заложенная в смете на призы (P≤1018). Гарантируется, что P>a1+a2+…+an, то есть для каждого участника можно купить приз стоимостью как минимум в одну денежную единицу.
Формат выходных данных
Выведите одно неотрицательное целое число —— максимальную разницу d, которую можно запланировать, не выходя за пределы суммы P.
Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64‑битный тип данных, например, long в C++, int64 в Free Pascal, long в Java.
Система оценки
Решения, правильно работающие для случаев, в которых P/n не превосходит 106, получат не менее 60 баллов.
Замечание
В примере участники распределились следующим образом:
1 место —— 2 участника,
2 место —— 1 участник,
3 место —— 3 участника,
4 место —— 4 участника,
5 место —— 2 участника.
Если заложить разницу между призами в 4 денежных единицы, то распределение стоимостей призов будет следующим:
5 место —— 2 приза по 1 денежной единице,
4 место —— 4 приза по 5 денежных единиц,
3 место —— 3 приза по 9 денежных единиц,
2 место —— 1 приз по 13 денежных единиц,
1 место —— 2 приза по 17 денежных единиц.
Суммарно на призы будет потрачено 2⋅1+4⋅5+3⋅9+1⋅13+2⋅17=96 денежных единиц, что укладывается в смету в 100100 денежных единиц.
Если же заложить разницу между призами в 55 денежных единиц, то потребуется 2⋅1+4⋅6+3⋅11+1⋅16+2⋅21=117 денежных единиц, что превышает сумму, указанную в смете.
Задание 5: Фермер Джон и древний камень
И редко кто бы мог увидеть Его ночной и тайный путь, Но берегись его обидеть, Случайно как‑нибудь толкнуть. Он скроет жгучую обиду, Глухое бешенство угроз, Он промолчит и будет с виду Недвижен, как простой утес. Николай Гумилёв, «Камень». Фермер Джон получил в наследство поле, на котором с незапамятных времен находится один большой и древний камень. По непонятной для самого себя причине Джон боится приближаться к камню, не говоря уже о том, чтобы сдвинуть или избавиться от него.
Фермер разбил всё свое поле, которое представляет собой прямоугольник n×m метров, сеткой на квадраты со стороной один метр. Камень занимает ровно один такой единичный квадрат. Камень находится в строке номер x и столбце номер y.
Техника Джона может обработать только прямоугольный участок земли, стороны которого имеют целочисленные значения в метрах и на котором не располагается этот камень. Теперь Джон хочет узнать, сколькими способами он может засеять прямоугольник с расположенными на сетке сторонами, такой, что внутри этого прямоугольника не содержится древний камень.
Формат входных данных
На вход подаются четыре натуральных числа n, m, x, y, каждое в отдельной строке. 1≤n, m≤31622, 1≤x≤n1, 1≤y≤m1.
Формат выходных данных
Выведите одно неотрицательное целое число —— количество способов выделить на поле один прямоугольный участок земли со сторонами, расположенными на сетке, и не содержащий внутри квадрат с камнем. Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64‑битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java.
Система оценки
Решения, верно работающие при n, m≤30, получат не менее 20 баллов.
Решения, верно работающие при n, m≤300, получат не менее 40 баллов.
Решения, верно работающие при n, m≤3000, получат не менее 60 баллов.