Электрик Вася целый день паяет платы, а если точнее, то делает разводку платы — прокладывает дорожки по ней. Частенько Васе попадается работа по проводке двух дорожек из углов платы к углам на противоположной стороне. Плату можно представить как n рядов по m участков в каждом, где некоторые участки уже содержат в себе элементы и через них дорожку проводить нельзя. Стартовые участки дорожек находятся в участках (1, 1) и (n, 1), а противоположные углы — в (1, m) и (n, m). Нельзя допускать пересечения двух дорожек, то есть проводить дорожки через один и тот же участок. И также, по специфике обработки платы, при прокладывании путь не может отдаляться от целевой стороны. Это значит, что если последний участок пути дорожки находится в координате (r, c), то следующий участок дорожки должен быть в (r + 1, c), (r - 1, c) или (r, c + 1). Теперь Васе вдруг стало интересно, а сколькими способами он может проложить дорожки? Два способа считаются различными, если последовательность пути хотя бы одной из дорожек отличается.
Помогите Васе, найдите количество способов.
В первой строке задается три целых числа n, m и k — размеры платы и количество уже занятых участков на ней.
В следующих k строках задается по два целых числа ri и ci — координаты i-го занятого участка. Все координаты занятых участков различны и не находятся в углах платы.
В единственной строке выведите количество возможных способов провести две дорожки с вышеописанными условиями. Ответ требуется выводить по модулю 109 + 7.
4 3 1
3 2
5
5 4 2
1 2
4 3
39
Отдыхая после занятий в университете Леша и Дима решили как-то развлечься и придумали следующую игру:
Один человек загадывает неотрицательное целое число a, а другой, задавая некоторые вопросы, должен отгадать его. Вопрос состоит из одного целого неотрицательного числа b. В ответ на вопрос игрок получает количество единичных бит в битовой записи числа a + b.
Леша и Дима уже научились быстро отгадывать число, теперь им интересно как вы справитесь с этой задачей!
Вы можете задать не более 30 вопросов (не включая операцию для вывода загаданного числа).
Для того, чтобы задать вопрос вы должны вывести вопросительный знак «?», и после него через пробел целое число b. Обязательно требуется вывести перевод строки и сделать операцию flush.
Если вы решите, что уже знаете загаданное число, вы можете в любой момент вывести его в отдельной строке, сделать операцию flush и завершить программу.
Для сброса буфера вывода (то есть для операции flush) сразу после перевода строки нужно сделать:
- fflush(stdout) в языке C++
- System.out.flush() в Java
- stdout.flush() в Python
- flush(output) в Pascal
? 3
? 40
42
4
3
В этой задаче вы должны помочь Юре справиться с домашним заданием по арифметике.
Давайте назовем выражением набор переменных, цифр и других не пустых выражений заключенных в круглые скобки с расставленными между ними знаками вычитания и сложения. Обратите внимание, что выражение не может начинаться с лидирующего знака вычитания или сложения. Примеры правильных выражений: «2+2», «(b-((a)+7))», «(a-4)+(7+a)-f-3». Примеры неправильных: «(2+2», «-a+b», «-(2+a)», «()».
К сожалению Юра не помнит точных значений переменных, но зато он знает для каждой переменной отрезок на котором она могла принимать значения. Юра уверен, что если он назначит переменным значения так, что значение выражения будет максимальным возможным, то его домашнюю работу примут.
Первая строка содержит два целых числа n и m — длина выражения и количество различных переменных в выражении.
Вторая строка содержит строку a длины n — выражение из домашнего задания Юры. Выражение будет состоять только из цифр и переменных (строчных букв латинского алфавита) описанных далее, а также операций сложения («+»), вычитания («-») и круглых скобок («(» и «)»). Все числа в выражении однозначные.
Следующие m строк будут в следующем формате: "ci li ri", где ci — название переменной, а li и ri — левая и правая граница возможных принимаемых значений переменной ci. Все названия переменных различные и являются строчными латинскими буквами.
Выведите единственное целое число — максимальное возможное значение выражения.
3 2
a-b
a 2 3
b -5 5
8
19 3
y+((y+z)+(y-x))+(z)
x 0 7
y 0 8
z 0 9
42
Как вы знаете, в БГУИР есть две формы обучения: платная и бюджетная. В 2042 году, после появления сверхточного экзамена ИГЭ (который между прочим вычисляет IQ абитуриента с точностью до 6-го знака после запятой, при чем для любых двух абитуриентов их результат на ИГЭ не может совпадать), было решено разбивать абитуриентов на две части минимизируя максимальное различие в IQ в одной части.
В 2042 году, кроме Влада, в БГУИР поступило еще n студентов (вам известен их IQ). Влад настолько умен, что может обмануть ИГЭ и получить на нем любой результат, но не более одной тысячи. Подскажите, какое значение IQ Владу нужно показать на экзамене, чтобы после оптимального разбиения на бюджетников и платников всех абитуриентов, максимальная разница между IQ двух студентов, попавших на одну форму обучения, была бы как можно меньше. Если в группе меньше двух студентов, то считать максимальную разницу для группы равной нулю.
В первой строке входного файла содержится одно целое число n — количество студентов. В следующих n строках содержатся вещественные числа iqi — результат на экзамене i-го студента с ровно 6-ю знаками после запятой. Все iqi — различны.
Если ответов существует несколько, то выведите любой. Ответ должен быть в промежутке [0, 1000] и иметь ровно 6 знаков после запятой, а так же не встречаться среди iqi.
3
100.000041
100.000043
100.000044
100.000042
В недалеком будущем, для поступления в университет межгалатических отношений на факультет космического десанта потребуется сдавать экзамен по прохождению экстремальной трассы испытаний. На одном из этапов трассы нужно уничтожить все мишени при помощи оружия BFG9000. Можно считать, что мишени расположены в двухмерной плоскости. Оружие BFG9000 за один выстрел уничтожает все мишени, которые попали в квадрат размером s × s (чем мощнее BFG9000, тем больше квадрат), но только если в квадрате находится как минимум три мишени (BFG9000 не разменивается по мелочам) и стороны квадрата параллельны осям координат (выстрел должен быть ровным). Чтобы не возиться с повторным размещением мишеней, они сконструированы таким образом, что после уничтожения сразу воспроизводятся (т. е. они снова будут учитываться при попадании), при этом такие мишени уже будут считаться уничтоженными. Фактически, нужно стрелять по мишеням и попасть в каждую как минимум один раз и тогда этап будет считаться пройденным.
Юра уже давно занимается изучением всей полосы, и на момент поступления ему известно, в каких координатах будут располагаться мишени при стрельбе. Конечно, он мог взять самую мощную BFG9000 которая есть в его распоряжении, но чем мощнее оружие, тем оно тяжелее и тем менее комфортно с ним бегать. Поэтому Юра задался целью определить минимальную мощность BFG9000, которую он может взять с собой, чтобы он смог пройти этап стрельбы. Помогите Юре.
В первой строке задается одно целое число n — количество мишеней на этапе стрельбы.
В следующих n строках задается по два целых числа xi и yi — координаты мишеней.
В единственной строке выведите минимальный размер стороны квадрата, которую должна покрывать BFG9000, чтобы была возможность попасть во все мишени.
4
1 1
1 2
2 2
3 5
3
3
1 1
11 1
1 43
42
Вова нашел две пустые бутылки. Одна могла вместить в себя n литров воды, а другая — m литров. Вова может выполнять следующие действия:
- Полностью наполнить одну из бутылок водой;
- Вылить из одной из бутылок всю воду;
- Перелить воду из одной бутылки в другую, пока одна из них не наполнится или другая опустошится.
Вова интересуется, а за какое минимальное количество таких действий он сможет получить ровно k литров воды в одной из бутылок?
В первой строке задано одно целое число t — количество тестовых примеров.
В следующих t строках задано по три целых числа n, m и k — емкости бутылок и количество воды, которое нужно получить, соответственно.
Для каждого тестового примера в отдельной строке выведите одно целое число — минимальное количество действий или -1, если необходимое количество воды невозможно получить.
2
30 37 10
6 8 13
42
-1
Ваня и Вова решили сыграть в одну игру. У них на столе неожиданно оказался чистый листок белой бумаги. Ваня взял карандаш и с помощью линейки нарисовал n вертикальных и n горизонтальных линий на расстоянии в 1 сантиметр. Затем он взял ручку и поставил точки в местах пересечений линий, а сами линии стер. В результате на листке бумаги получилось n × n точек. Теперь им предстоит сыграть в увлекательную игру.
Ваня и Вова по очереди соединяют соседние точки — точки, находящиеся на расстоянии в 1 сантиметр. Если в результате образовался квадрат 1 × 1 сантиметр, то к счету игрока совершившего ход прибавляется одно очко (или несколько, если образовалось сразу несколько квадратов). В конце, когда никто уже не может сделать ход (когда все пары соседних точек соединены) подсчитываются набранные очки каждого игрока. Если количество очков у второго игрока строго больше чем у первого, то побеждает второй игрок. В противном случае побеждает первый.
Определите победителя, если каждый игрок придерживается оптимальной стратегии и первым всегда ходит Вова.
В первой строке задано одно целое число n — колиество вертикальных и горизонатльных линий.
Выведите "Vanya", если победил Ваня, в противном случае выведите "Vova".
1
Vova
2
Vanya
12 апреля 2042 года у Леши произошла трагедия: ему сообщили, что номер его мобильного телефона не делится на 42! Он не стал проверять это и тут же побежал в салон связи исправлять эту ситуацию.
В 2042 году номер телефона Леши выглядит как число n записанное подряд k раз. К примеру, при n = 903 и k = 3, номер телефона: 903903903.
Леше разрешили ровно один раз выбрать непустое подмножество цифр из {0, 1, 2, ..., 9} и одну дополнительную цифру, которое не входит в это подмножество, и заменить в своем номере все цифры из множества на дополнительную цифру.
Найдите, сколькими способами Леша может изменить свой номер телефона по указанному выше правилу, чтобы он делился на 42. Два способа считаются различными, если после изменения получились разные номера.
В единственной строке входного файла содержатся два целых числа n и k.
Обратите внимание, что номер телефона может содержать ведущие нули, однако гарантируется, что в исходном номере ведущих нулей нет.
В единственной строке выведите одно целое число — количество способов изменить номер телефона так, чтобы он делился на 42.
543 2
9
18111198 3
42
В первом примере подходят следующие числа: 540540, 546546, 522522, 588588, 444444, 000000, 222222, 666666 и 888888.
Влад и Даша решили переехать в Казань. Метро в Казани выглядит как n станций соединенных n - 1 переездами так, что от каждой станции можно добраться до каждой. Для каждой станции i известна ее глубина под землей depthi.
Влад выбирает местоположение квартиры, а Даша — местоположение дачи (их выборы могут совпасть). Пусть Влад выбрал станцию i, а Даша станцию j. Назовем непохожестью пары станций количество различных битов в двоичных представлениях depthi и depthj. Ребята не поругаются, если четность непохожести станций i и j не будет совпадать с четностью длины кратчайшего пути по переездам от станции i к станции j (длина пути — количество переездов, по которым требуется проехать).
Найдите количество различных пар местоположений, которые могут быть выбраны так, что Влад и Даша не поругаются друг с другом.
В первой строке входного файла содержится одно целое число n — количество станций в метрополитене.
В следующей n - 1 строке содержится по 2 целых числа a и b — описание переездов между станциями.
В последней строке входного файла содержатся n целых чисел depthi — глубина станции i.
В единственной строке выведите одно целое число — ответ на задачу.
3
1 2
1 3
1 2 3
2
За последние 42 года Ваня успел совершить n кругосветных путешествий. В каждом путешествии он посещал некоторые города, а первые буквы названий записывал в порядке их посещения в своей записной книжке. И вот, в 2042 году Ваня решил вспомнить все свои путешествия. Однако он столкнулся с одной проблемой — городов, у которых совпадают первые буквы, очень много. А это значит, что точно восстановить каждое путешествие у него не удастся. Ваня не сильно расстроился, ведь все-равно он может извлечь из этого полезную информацию. Например, он может определить минимальное количество городов, которые он мог посетить за все n путешествий и подобрать названия для каждого из этих городов так, чтобы записи в его книжке были непротиворечивы.
Помогите Ване определить минимальное количество городов k, которые он мог посетить за последние 42 года совершив n кругосветных путешествий и подберите для каждого города некоторое название (возможно несуществующее). Так как Ваня и сам может придумать названия для городов, он просит каждому из городов сопоставить уникальное целое число из промежутка [1, k]. Также не забудьте определить для каждого путешествия номера городов, которые он мог посетить. В одном путешествии город может быть посещен несколько раз, но посещать город из самого себя нельзя.
В первой строке задано одно целое число n — количество кругосветных путешествий совершенных Ваней за последние 42 года.
Далее идет n строк si состоящих только из строчных букв латинского алфавита — первые буквы посещенных в кругосветном путешествии городов, записанные в порядке их посещения.
В первой строке выведите одно целое число k — минимальное количество городов.
В следующих n строках выведите по |si| целых чисел — номера городов, которые Ваня мог посетить в i-м кругосветном путешествии в порядке их посещения.
3
abc
acb
bcd
4
1 2 3
1 3 2
2 3 4
1
aa
2
1 2
Одной темной ночью n волков вышли на охоту на m овец. Овцы располагаются в целочисленных точках декартовой системы координат, где i-я овца находится в точке (xi, yi).
Для каждого волка известна область охоты — прямоугольник x1, y1, x2, y2, в котором он сможет поймать любую овцу (даже овцу на границе прямоугольника). За границы этого прямоугольника волк не выходит.
Два волка принадлежат одной стае, если множество овец, которых сможет поймать первый, совпадает с множеством овец, которых сможет поймать второй.
Продемонстрируйте познания в зоологии и по полученным данным определите количество стай волков!
В первой строке входного файла содержатся два целых числа n и m — количество волков и количество овец соответсвенно.
В следующих n строках содержатся по четыре целых числа x1, y1, x2, y2 — область охоты i-го волка.
В следующих m строках содержатся по два целых числа xi и yi — координаты i-й овцы.
В единственной строке выведите одно целое число — количество стай волков.
2 1
1 1 1 1
1 1 1 2
1 1
1
2 1
1 1 1 1
1 2 1 2
1 1
2