Темы --> Информатика --> Другое
    Разбор случаев(6 задач)
    Теория вероятностей(3 задач)
    Конструктив(21 задач)
    Формула(17 задач)
    Комбинаторика(9 задач)
---> 18 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: 1 2 3 4 >> Отображать по:
#601
Забор
  
Темы: [Формула]
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

Том Сойер получил важное задание по покраске забора. Забор состоит из n досок. Он когда-то был покрашен, однако с некоторых участков забора краска облупилась. Эти доски Тому и необходимо покрасить. Так как забор большой, пришлось подвезти к забору целую цистерну с краской. Цистерна была помещена у края забора и не может перемещаться. У Тома есть ведерко, набрав краски в которое, Том может покрасить \(k\) досок забора. При этом Том может в любой момент вернуться за краской к цистерне.

Изначально Том находится у цистерны. Соседние доски находятся на расстоянии 1 фута друг от друга, цистерна находится на расстоянии 1 фута от первой доски. По окончании работы Том должен положить кисточку и ведерко на свою исходную позицию рядом с цистерной.

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

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

Первая строка входного файла содержит количество досок в заборе \(n\) (1 ≤ \(n\) ≤ \(10^9\)) и вместимость ведерка \(k\) (1 ≤ \(k\) ≤ 100). Во второй строке содержится количество неокрашенных отрезков забора \(m\) (1 ≤ \(m\) ≤ 50). Далее следуют \(m\) строк, в каждой из которых описан один неокрашенный отрезок. Отрезок описывается своей левой границей \(l_i\) и правой границей \(r_i\) (1 ≤ \(l_i\) ≤ \(r_i\) ≤ \(n\)). Такое описание означает, что не покрашены \(l_i\)-я, (\(l_i\)+1)-я, …, (\(r_i\)–1)-я, \(r_i\)-я доски забора (доски нумеруются от 1 до \(n\)). Гарантируется, что неокрашенные отрезки, заданные во входном файле, не пересекаются.

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

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

Примеры
Входные данные
5 2
2
1 2
5 5
Выходные данные
12
#990
Праздники
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Нерабочими называются выходные, а также праздники: 23 февраля, 8 марта и K первых дней года. Праздник попавшие на выходные, переносятся. По заданному K требуется определить максимальное количество подряд идущих нерабочих дней.

Парламент некоторой страны принял новый закон о праздничных днях. Согласно этому закону первые K дней года, а также 23 февраля (День олимпиады по информатике) и 8 марта объявляются праздничными, а все остальные праздники отменяются. При этом все выходные (суббота и воскресенье), попавшие на праздничные дни, переносятся на следующие за этими праздниками рабочие дни.

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

Требуется определить, какое наибольшее количество нерабочих дней может идти подряд.

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

На вход подается единственное число K (1≤K≤50).

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

Требуется вывести единственное число — наибольшее количество нерабочих дней, идущих подряд.

Примеры
Входные данные
2
Выходные данные
4
Входные данные
10
Выходные данные
16
#1039
Магия Копперфильда
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Дана прямоугольная таблица. Фишка в таблице может перемещаться в любое место на K ходов. Требуется последовательно убрать все ячейки таблицы, кроме одной, задавая количество ходов, на которые должна сходить фишка, и координаты удаляемых клеток. Фишка должна оказаться в единственной оставшейся клетке.

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

1

2

…

N

N+1

N+2

…

2*N

:

:

…

:

N*(N–1)+1

N*(N–1)+2

…

N*N

Дэвид просит каждого зрителя поставить палец на левую верхнюю картинку (то есть в клетку номер 1), и Магия начинается: маг просит зрителей сдвинуть свой палец K1 раз в произвольном направлении (сдвигать палец разрешается только на соседнюю картинку по горизонтали или по вертикали, оставлять палец на месте запрещено, при этом если, допустим, Дэвид попросил сдвинуть палец 3 раза, то можно, например, сдвинуть палец на одну клетку вправо, затем — на одну клетку вниз, затем — на одну вверх). Затем со словами "Ваш палец не здесь" Дэвид убирает некоторые картинки, и — что удивительно, пальцы телезрителей действительно не указывают на те картинки, которые убирает Дэвид. Затем он просит сделать K2 ходов, и так далее (если Дэвид уже убрал какую-то картинку, то ходить через эту клетку нельзя). В конце, Дэвид убирает все картинки, кроме одной, и, улыбаясь, говорит: "Вы здесь" (аплодисменты).

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

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

Во входном файле записано одно число N — размер квадрата (2N100).

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

В выходной файл ваша программа должна печатать следующие строки чисел:

K1 X1,1 X1,2 … X1,m1

K2 X2,1 X2,2 … X2,m2

…

Ke Xe,1 Xe,2 … Xe,me

где Ki — это число ходов, которые должны сделать телезрители, а Xi,1 … Xi,mi — номера картинок, которые Дэвид должен убрать с экрана после этого. При этом все Ki должны удовлетворять условию 2NKi10000 и все Ki должны быть различны. Каждая картинка (кроме той, которая останется) должна убираться ровно один раз. После каждой просьбы зрителей сделать Ki ходов, Дэвид должен убирать хотя бы одну картинку. Каждое Ki должно печататься в начале новой строки. Ситуаций, когда телезритель остался на клетке, у которой нет соседних, а его просят куда-нибудь ходить, возникать не должно.

Примеры
Входные данные
3
Выходные данные
7 1 3 7 9
9 2 4 6 8
#1107
Лягушачьи игры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Имя входного файла: frogs.in
Имя выходного файла: frogs.out

В тридесятом царстве в новогодние праздники все лягушки собираются на самом большом болоте, чтобы поиграть в замечательную игру. Всего в этом царстве живет N зеленых лягушек и M коричневых. Для игры они выбирают на болоте N + M + 1 кочку, на первые N кочек слева садятся зеленые лягушки, а на последние M — коричневые (т. е. между ними находится одна кочка, на которой никто не сидит). Зеленые лягушки садятся лицом к коричневым лягушкам, а коричневые — к зеленым. Кочки настолько маленькие, что развернуться на них, не свалившись в болото, совершенно не возможно. Поэтому лягушки могут двигаться только вперед и не могут разворачиваться.

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

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

Поиграть в эту игру для случая N=M=3 можно по ссылке:

http://olympiads.ru/zaoch/2007/problems/frogs.swf

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

Во входном файле записаны два числа N и M (1≤N≤1000, 1≤M≤1000) – количество зеленых и коричневых лягушек соответственно.

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

Выведите последовательность прыжков лягушек для достижения поставленной цели. Каждый прыжок можно задать одним числом — номером прыгающей лягушки (поскольку свободная кочка всегда ровно одна). Пронумеруем всех лягушек в соответствии с их начальным положением. Зеленые лягушки будут пронумерованы числами от 1 до N, а коричневые — с N+1 до N+M в порядке слева направо.

В первую строку выходного файла выведите число K — количество прыжков. K не должно превышать 107. Далее выведите K чисел — номера лягушек.

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

Примеры
Входные данные
2 1
Выходные данные
5
2 3 2 1 3
#112032
Перемешивание
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Каждое утро капитан Ъ проводит занятия по строевой подготовке в возглавляемой им роте солдат. Всего в роте N солдат, каждый из которых носит форму определенного цвета. Различных цветов формы не более 26, так что для удобства солдаты обозначают цвета строчными латинскими буквами. Таким образом, каждому из \(N\) солдат соответствует буква от 'a' до 'z' — цвет его формы.

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

Но к 23 февраля солдаты решили удивить капитана и поменяться местами так, чтобы \(каждый\) солдат встал не на ту букву, которая соответствует цвету его формы. Так, солдат с цветом формы 'q' может встать на любую букву, кроме буквы 'q', иначе удивление капитана будет недостаточным.

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

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

В первой строке входного файла содержится единственное целое число \(N\) — количество солдат в роте \((1 \le N \le 100 000)\). Во второй строке содержится строка S, состоящая из \(N\) строчных латинских букв.

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

Единственная строка выходного файла должна содержать искомую строку \(T\), если задумка солдат осуществима, и «Impossible» в противном случае. Если верных ответов несколько, выведите любой из них.

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

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

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

1. Тесты 3—21. В тестах этой группы \(N \le 9\). Эта группа оценивается в 30 баллов.

2. Тесты 22—36. В тестах этой группы \(N \le 200\), а строка не может содержать никаких букв, кроме 'a', 'b' и 'c'. Эта группа оценивается в 30 баллов независимо от первой.

3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.

Примеры
Входные данные
9
olimpiada
Выходные данные
iapdialom
Входные данные
7
baaaaaa
Выходные данные
Impossible
Страница: 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест