Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(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 задач)
Страница: << 16 17 18 19 20 21 22 >> Отображать по:
#3202
Магия числа 23
  

По заданному числу \(N\) найдите натуральное число \(K\), такое что:

  • число \(\overline{KK}\) (повторённая два раза десятичная запись \(K\)) является точным квадратом некоторого натурального числа (см. примеры),
  • \(K\) при записи в десятичной системе счисления имеет длину от \(N\) до \(N+23\) (включительно).

Так, для \(N=1\) условию удовлетворяет, например, число \(K=13223140496\), т.к. оно имеет длину 11, что укладывается в диапазон от 1 до 24, а также число \(1322314049613223140496\) является точным квадратом натурального числа.

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

Вводится одно натуральное число \(N\) (\(1 \le N \le 2323\)).

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

Выведите искомое число \(K\). Если чисел, удовлетворяющих условию, несколько, выведите любое из них. Если таких чисел не существует, выведите 0.

Примечания

Тесты состоят из четырёх групп. В этой задаче нет off-line групп. Баллы за каждую группу начисляются только при прохождении всех тестов этой группы.

  1. Тесты 1--4, из условия, оцениваются в 0 баллов.
  2. Тест 5, \(N = 13\), оценивается в 30 баллов.
  3. Тесты 6--14. В них \(N \le 80\). Группа оценивается в 30 баллов.
  4. Тесты 15--29. Полные ограничения, оценивается в 40 баллов.
Примеры
Входные данные
1
Выходные данные
13223140496
Входные данные
11
Выходные данные
13223140496
Входные данные
10
Выходные данные
13223140496
Входные данные
39
Выходные данные
1322314049586776859504132231404958677685950413223140496
#3203
Вася и его друзья
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В новой игре "Closed Loops 7" игрокам предлагается клетчатая таблица \(N\) на \(M\) клеток. Ход состоит в том, что очередной игрок рисует цикл - замкнутую линию без самопересечений, идущую только по сторонам клеток. Каждый цикл можно нарисовать только один раз за всю игру (при этом, конечно, не запрещается рисовать циклы, пересекающиеся с уже нарисованными). Игроки ходят по очереди. Выигрывает тот, кто рисует последний возможный цикл. К примеру, если \(N=2\), \(M=1\), то циклов всего три и игрок, делающий третий ход, выигрывает.

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

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

Даны три целых числа: \(N, M\) - размеры таблицы (\(1 \le N \le 100, 1 \le M \le 8\)) и \(K\) - количество игроков (\(1 < K \le 10^9\)).

Выходные данные
Выведите одно число от 1 до \(K\) - каким по счету игроком должен быть Вася, чтобы выиграть.

Примечания

Тесты состоят из трёх групп. В этой задаче нет off-line групп.

  1. Тесты 1 и 2, из условия, оцениваются в 0 баллов.
  2. Тесты 3--15. \(N \cdot M \le 24\). Эта группа оценивается в 40 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. Тесты 16--42. Полные ограничения, группа оценивается в 60 баллов. Баллы начисляются только при прохождении всех тестов группы.
Примеры
Входные данные
2 1 2
Выходные данные
1
Входные данные
1 8 8064
Выходные данные
36
#3204
Отрезки на прямой возвращаются
  

На прямой задано \(N\) попарно различных отрезков \([a_i, b_i]\) (\(i = 1, 2, \dots, N\), \(a_i < b_i\)). Будем говорить, что отрезок номер \(i\) непосредственно содержится в отрезке номер \(j\) (\(i \ne j\)), если:

  • он полностью принадлежит \(j\)-му (то есть \(a_j \le a_i\) и \(b_i \le b_j\)),
  • среди заданных \(N\) отрезков не найдётся такого отрезка (с номером \(k\)), что \(i\)-й отрезок принадлежит \(k\)-му и \(k\)-й принадлежит \(j\)-му (здесь \(i\), \(j\) и \(k\) - различные числа).

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

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

Сначала вводится целое число \(N\) (\(1 \le N \le 100\,000\)). Далее идут \(N\) пар целых чисел \(a_i\), \(b_i\) (\(-10^9 \le a_i < b_i \le 10^9\)).

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

Выведите \(N\) чисел. Число номер \(i\) должно быть равно номеру отрезка, в котором непосредственно содержится отрезок номер \(i\), либо 0 - если такого не существует.

Если существует несколько решений, выведите любое.

Примечания

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

  1. Тест 1, из условия, оценивается в 0 баллов.
  2. Тесты 2--11. В них \(N \le 100\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. Тесты 12--27. В них \(N \le 10\,000\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. Тесты 28--35. Off-line группа, полные ограничения. Каждый тест оценивается в 5 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.
Примеры
Входные данные
4
2 3
0 4
1 6
0 5
Выходные данные
3 4 0 0
#3205
Отрезки на прямой возвращаются--2
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

При написании программы, проверяющей ответ участника для задачи 3204 "Отрезки на прямой возвращаются" (ссылка на задачу) (прочитайте её условие!), жюри столкнулось с трудностями, превосходящими сложность самой задачи. С мыслью "почему бы и нет" написание такой программы было решено также включить в комплект задач.

Проверяющей программе доступно три блока информации:

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

Ваша задача - написать программу, которая по этим данным определит, правильно ли программа абстрактного участника посчитала ответ.

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

Вход состоит из трёх частей. Первая часть - число \(N\) (\(1 \le N \le 100\,000\)) и следом \(N\) пар \(a_i\), \(b_i\) (\(-10^9 \le a_i \lt b_i \le 10^9\)). Далее идут \(N\) чисел, каждое из которых от 0 до \(N\), \(i\)-е равно номеру отрезка, являющегося одним из непосредственно содержащих \(i\)-й, либо нулю - по мнению абстрактного участника. Далее идут ещё \(N\) чисел в том же формате - ответ жюри на эту задачу.

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

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

Выведите \(N\) строк. В \(i\)-й строке должен быть вердикт для \(i\)-го отрезка. Выведите OK, если ответ абстрактного участника правильный, и WA - иначе.

Примечания

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

  1. Тест 1, из условия, оценивается в 0 баллов.
  2. Тесты 2--11. В них \(N \le 100\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. Тесты 12--27. В них \(N \le 10\,000\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. Тесты 28--35. Полные ограничения. Каждый тест оценивается в 5 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.
Примеры
Входные данные
4
2 3
0 4
1 6
0 5
2 2 1 0
3 4 0 0
Выходные данные
OK
WA
WA
OK
#3330
Футболки
  
Array

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

Один из типов футболок Петя любит больше остальных, отчасти из-за того, что количество футболок этого типа позволяет носить только их. Но однажды Пете сказали, что он одевается не “по моде”, на что Петя обиделся и поспорил, что он сможет \(N\) дней одеваться модно. По моде, принятой в их школе, нельзя ходить два дня подряд в однотипной футболке и нельзя прийти в футболке того же типа ровно через неделю, после того как ты ее надел (например, два понедельника подряд). Школьная мода распространяется и на те дни, когда в школу ходить не надо.

Петя хочет знать, может ли он выиграть спор и, если может, то в каком порядке ему нужно надевать футболки в течении этих \(N\) дней. Он просит вас ему помочь.

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

Во входном файле содержатся пять целых чисел \(N, W, B. C\) и \(K\), разделенных пробелами — число дней, которые Петя должен носить футболки “по моде”, количество белых, черных и цветных футболок, имеющихся у него соответственно, и количество грязных однотипных футболок, которое согласится стирать мама. Гарантируется, что хотя бы одно из чисел \(W, B, C\) не меньше \(K\). \(1 \le N \le 1000, 1 \le K \le 1000, 0 \le W \le 1000, 0 \le B \le 1000, 0 \le C \le 1000\).

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

В первой строке выходного файла выведите единственное слово YES или N0 — ответ на вопрос задачи. Если ответ YES, то во второй строке выведите \(N\) символов, где \(i\)-ый символ означает цвет футболки, которую Петя будет носить в \(i\)-ый день. Символ “W” означает белый цвет, “В” — черный, “С” — цветной.

Примечание

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

Тесты 1-3, из условия, оцениваются в 0 баллов.

1. В тестах этой группы среди чисел \(W, B\) и \(C\) хотя бы одно равно нулю. Эта группа оценивается в 50 баллов, при этом баллы начисляются только при прохождении всех тестов группы (при этом прохождения всех тестов из условия не требуется).

2. Баллы за тесты этой группы начисляются только при прохождении всех тестов 1 группы. Некоторые тесты этой группы объединяются в подгруппы, баллы за каждую подгруппу ставятся только при прохождении всех тестов подгруппы

Примеры
Входные данные
2 5 0 4 1
Выходные данные
YES
WC
Входные данные
4 3 4 5 3
Выходные данные
YES
CWCW
Входные данные
10 3 2 1 3
Выходные данные
NO
Страница: << 16 17 18 19 20 21 22 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест