Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 115 задач <---
Источники --> Личные олимпиады --> Открытая олимпиада школьников
    2002(9 задач)
    2003(10 задач)
    2004(13 задач)
    2005(12 задач)
    2006(12 задач)
    2007(11 задач)
    2008-2009(19 задач)
    2009-2010(23 задач)
    2010-2011(19 задач)
    2011-2012(8 задач)
    2012-2013(21 задач)
    2013-2014(8 задач)
    2014-2015(8 задач)
Страница: << 15 16 17 18 19 20 21 >> Отображать по:
#1984
Кодировка
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Вот уже три года майор Пронин ведёт борьбу с подпольной группой по производству контрафактной продукции. Недавно его коллега, внедрившийся под прикрытием в эту организацию, передал ему важнейший документ, описывающий местонахождение главной фабрики преступников. К несчастью, сразу после этого он был раскрыт.

Майор понимал, что у него совсем немного времени до того, как придут и за ним. Поэтому он выбрал некоторый кусок документа и переслал Вам, своему ближайшему соратнику по борьбе со злом (майор боялся, что не хватит времени отправить документ целиком). Сразу после этого к нему ворвались злоумышленники и схватили Пронина. Чтобы не вызывать никаких подозрений, преступники решили не удалять документ, а просто закодировать его некоторым образом. Известно лишь, что каждый символ был заменён ровно на один символ, при этом разные символы перешли в разные, одинаковые – в одинаковые. Известно, что и до, и после перекодировки документ состоял только из символов с ASCII-кодами от 32 до 255 включительно.

Получив часть документа S, Вы немедленно отправились выручать Пронина из беды, но его дом оказался пуст. На его компьютере остался закодированный документ. Ни майор, ни его коллега на связь не выходят. Вы поняли, что единственный способ отыскать их – проникнуть на главную фабрику организации. Для этого необходимо раскодировать весь документ. Прежде чем передать его лингвистам, нужно произвести техническую обработку.

Возможно, что в тексте есть несколько фрагментов, которые могут являться кодом имеющегося у вас фрагмента S. Вы наудачу предположили, что имеющийся у вас фрагмент S в закодированном тексте является самым первым из фрагментов, в которые он мог быть закодирован.

Ваша задача – вычислить, какие символы документа могут быть определены однозначно исходя из приведённых соображений.

Входные данные

В первой строке записан перекодированный документ, во второй – часть документа S, оказавшаяся у вас. Обе строки имеют длину не более 106 символов и состоят только из символов с ASCII-кодами от 32 до 255 включительно. Длина S меньше длины документа.

Выходные данные

Если на каком-то этапе произошла ошибка и входные данные некорректны, выведите Impossible. Иначе запишите в первой строку Possible, а во вторую – результат раскодировки. Символы, которые невозможно определить однозначно, замените на ?.

Система оценки

Подзадача 0 (0 баллов) тесты из условия.

Подзадача 1 (30 баллов) Обе строки состоят только из латинских маленьких букв. Длина каждой строки не превосходит 100. Балл за группу начисляется при прохождении всех тестов группы.

Подзадача 2 (30 баллов) Длина каждой строки не превосходит 1000. Балл за группу начисляется при прохождении всех тестов группы.

Подзадача 3 (40 баллов) Без дополнительных ограничений. В подгруппе 8 тестов каждый из которых оценивается в 5 баллов.

Примеры
Входные данные
ababc
ab
Выходные данные
Possible
abab?
Входные данные
fadacabba
bcc
Выходные данные
Possible
?b?b?bccb
Входные данные
abcdef
ee
Выходные данные
Impossible
Входные данные
cdcd
ab
Выходные данные
Possible
abab
#3196
Контрольная работа
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Параллель восьмых классов написала контрольную работу. В результате ровно A% учащихся получили 5, ровно B% — 4, ровно C% — 3, а остальные D% написали её на 2. Какое минимальное количество школьников должно быть в параллели восьмых классов для того, чтобы могли получиться такие результаты?

Входные данные

Вводятся 4 целых числа от 0 до 100 — A, B, C, D (A + B + C + D = 100).

Выходные данные

Выведите единственное целое положительное число — минимальное возможное количество учащихся в параллели.

Примеры
Входные данные
40 50 5 5
Выходные данные
20
#3198
Числовые промежутки
  

Сегодня в школе Васе рассказывали про числовые промежутки. Каждый из них задаётся парой чисел — своими началом и концом, и информацией о том, включается ли в него каждый из концов. Таким образом, существует четыре типа промежутков:

  • Интервал. Обозначается (x, y), включает в себя все числа z: x < z < y.
  • Полуинервалы. Обозначаются [x, y) и (x, y], включают в себя все такие z, что x ≤ z < y и x < z ≤ y соответственно.
  • Отрезок. Обозначается [x, y] и включает в себя все числа z: x ≤ z ≤ y.
В качестве домашней работы Васе досталось посчитать количество целых чисел в каждом из данных промежутков. Поскольку они ещё не проходили вещественных чисел, \(x\) и \(y\) рациональные: \(x\) = \(a \over b\) , \(y\) = \(c \over d\) (\(a\) и \(c\) целые, \(b\) и \(d\) целые положительные)

Рассмотрим пример: [\(3 \over 2\), 4) В данном случае \(d\) = 1, поэтому вместо \(4 \over 1\) пишут просто 4. В этом множестве содержится два целых числа: 2 и 3, а число 4 не содержится.

Помогите Васе с домашней работой — напишите программу, которая по заданному числовому промежутку посчитает количество целых чисел, содержащихся в нём.

Входные данные

Первым символом идёт открывающаяся квадратная или круглая скобка. Далее записано число x в формате \(a \over b\) либо a, где |a| ≤ 109, 0 < b ≤ 109. После следует запятая и пробел. Потом — число y в таком же формате. Далее — закрывающаяся квадратная или круглая скобка. После неё идёт перевод строки и конец файла.

Гарантируется, что данный числовой промежуток не является пустым (то есть содержит в себе хотя бы одно число, не обязательно целое).

Выходные данные

По заданному числовому промежутку выведите единственное число — количество целых чисел в нём.

Примеры
Входные данные
[3/2, 4)
Выходные данные
2
Входные данные
[-2/4, 5/3]
Выходные данные
2
Входные данные
[-1000, 1000]
Выходные данные
2001
Входные данные
[-2, 4/3]
Выходные данные
4
#3199
Делёж яблок
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Этим летом у бабушки был большой урожай яблок. Она собрала яблоки в корзину и отдала своим \(K\) внукам.

Первый внук взял из корзины половину всех яблок и еще \(a_1\) яблоко (если количество яблок не делилось на два, то результат деления на два он мог округлить как в большую сторону, так и в меньшую). К примеру, если в корзине было 7 яблок и \(a_1 = 1\), то он мог взять либо 4, либо 5, а если было 6 яблок и \(a_1 = 1\), то он взял ровно 4.

Второй внук взял половину от всех оставшихся яблок и ещё \(a_2\) (если яблок было нечетное количество, то он также мог округлить половину как в большую, так и в меньшую сторону). И так далее, \(K\)-ый внук взял половину яблок, оставшихся после \(K - 1\) внука, и ещё \(a_k\). В итоге в корзине ничего не осталось.

Теперь они задумались, насколько же большой урожай был у бабушки. Ни один из них не помнит, делилось ли количество яблок на 2 нацело при его выборе, а если нет, то в какую сторону он округлил половину яблок. Внуков интересует минимальное и максимальное изначальное количество яблок в корзине, при которых могли произойти описанные события.

Входные данные

Сначала вводится целое положительное число \(K\) (\(1 \le K \le 1\,000\)). Далее записано \(K\) целых неотрицательных чисел \(a_1, \dots , a_K\) (\(0 \le a_i \le 1\,000\)).

Выходные данные

Выведите два неотрицательных целых числа без ведущих нулей, каждое в новой строке - минимальное и максимальное возможное количество яблок в корзине соответственно.

Примеры
Входные данные
1
1
Выходные данные
1
3
Входные данные
2
0 1
Выходные данные
1
7
#3201
Студентам --- бесплатно!
  

Зал Большого галактического театра состоит из \(S\) рядов, по \(S\) мест в каждом ряду.Продажа билетов на каждый спектакль происходит по следующему принципу: первые \(S^2 - N\) ценителей прекрасного приобретают билеты на любые места по их вкусу, а оставшиеся \(N\) кресел администрация бесплатно выделяет студентам, отдавая дань сложившимся традициям.

Во избежание обвинений в дискриминации по половому признаку, рассаживать студентов по этим \(N\) местам необходимо таким образом, чтобы:

  • в каждом ряду количество девушек-студенток и количество юношей-студентов различалось бы не более чем на 1;
  • на каждой "вертикали мест" (т. е. местах, имеющих один и тот же номер, но расположенных в разных рядах) количество девушек-студенток и количество юношей-студентов также различалось бы не более чем на 1.
Таким образом, после продажи билетов ценителям прекрасного билетёры должны распределить оставшиеся \(N\) кресел на женские и мужские с соблюдением этих правил.

Каждое место в зале определяется двумя числами от 1 до \(S\) - номером ряда и номером самого места в этом ряду. Студенческое кресло номер \(i\) расположено в \(a_i\)-м ряду и имеет в нём номер \(b_i\). Поскольку ценители прекрасного могли занять совершенно любые места, числа \(a_i\) и \(b_i\) могут принимать любые значения от 1 до \(S\). В частности, может оказаться так, что в каком-нибудь ряду не будет ни одного студенческого места.

Ради упрощения работы билетёров администрация обращается к вам с заданием написать программу, которая автоматизирует процесс распределения студенческих мест на мужские и женские.

Входные данные

Сначала вводятся два целых числа \(S\) и \(N\) (\(1 \le S \le 100\,000\), \(1 \le N \le \min\{100\,000, S^2\}\)). Далее расположены \(N\) пар натуральных чисел \((a_i, b_i)\), не превосходящих \(S\). Гарантируется, что все места различные.

Выходные данные

Если искомого способа не существует, выведите Impossible.Иначе выведите единственную строку из \(N\) символов ‘M’ (мужское) и ‘W’ (женское). Символ на \(i\)-й позиции соответствует статусу \(i\)-го места в той же нумерации, в которой они были перечислены во входных данных.

Примечания

Тесты состоят из четырёх групп.

  1. Тесты 1 и 2. Тесты из условия, оцениваются в 0 баллов.
  2. Тесты 3--19. В них \(S \le 1\,000\), \(N \le 30\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. Тесты 20--30. В них \(S \le 1\,000\), \(N \le 1\,000\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. Тесты 31--34. Off-line группа, полные ограничения. Каждый тест оценивается в 10 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.

Примеры
Входные данные
2 2
2 1
1 2
Выходные данные
MW
Входные данные
3 5
1 2
2 3
1 3
2 1
1 1
Выходные данные
WMWWM
Страница: << 15 16 17 18 19 20 21 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест