Темы --> Информатика --> Алгоритмы --> Перебор
    Комбинаторные структуры(59 задач)
    Перебор с отсечением(22 задач)
    Простые задачи на перебор(43 задач)
    Гамильтонов цикл(2 задач)
---> 37 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(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 задач)
Страница: << 2 3 4 5 6 7 8 >> Отображать по:
#111858
Простой квадрат
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

У Пети имеется игровое поле размером \(3\times3\), заполненное числами от 1 до 9. В начале игры он может поставить фишку в любую клетку поля. На каждом шаге игры разрешается перемещать фишку в любую соседнюю по стороне клетку, но не разрешается посещать одну и ту же клетку дважды. Петя внимательно ведет протокол игры, записывая в него цифры в том порядке, в котором фишка посещала клетки. Пете стало интересно, какое максимальное число он может получить в протоколе. Помогите ему ответить на этот вопрос.

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

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

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

Выведите одно целое число — максимальное число, которое могло получиться в протоколе при игре на данном поле.

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

Пример

Ввод Вывод 
1 2 3
4 5 6
7 8 9
 
987456321
#111991
Волшебный квадрат
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

На день рождения Егору подарили волшебный квадрат.

Волшебный квадрат — это таблица 3 × 3, в каждой из ячеек которой находятся числа от 0 до 9. Егор придумал следующую игру с волшебным квадратом: он загадывает число N и пытается так поставить числа в каждую ячейку квадрата, чтобы сумма чисел в каждой строке и каждом столбце была равна в точности N.

Пусть расстановка — это волшебный квадрат, заполненный числами. Тогда расстановки A и B считаются различными, если хотя бы для каких-то строки x и столбца y выполняется неравенство Ax, y ≠ Bx, y, где Ax, y и Bx, y — это числа, находящиеся в строке x и столбце y в расстановках A и B соответственно.

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

Напишите программу, которая поможет ответить на вопрос Егора.

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

Единственная строка входных данных содержит целое число N (0 ≤ N ≤ 109).

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

Требуется вывести одно число — искомое количество расстановок.

Примеры тестов

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

Примечание

В примере из условия существует всего одна допустимая расстановка — это таблица 3 × 3, состоящая из нулей. Очевидно, что сумма элементов в любой строке или столбце в такой расстановке равна 0.

#112090
Турист Петр
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

На отдыхе в Теплой Стране Вера познакомилась с симпатичным волейболистом- трактористом Петром. Турист Петр, кстати, собирается после отличного отдыха в Теплой Стране отправиться в путешествие по городам Европы. Как известно, Европа обладает развитой транспортной системой: в Европе есть \(V\) интересующих Петра городов и \(E\) маршрутов ночных поездов. Каждый маршрут соединяет два различных города, время в пути составляет одну ночь. Поезда по маршруту ходят в обоих направлениях.

Основной целью поездки Петра является осмотр местных достопримечательностей. По- скольку Петр — невероятно занятой человек, то он решил, что все путешествие должно занимать не более четырех дней. Петр уже многое повидал, поэтому на осмотр достопримечательностей в каждом городе Петр тратит ровно один день. Он хочет составить наиболее практичный тур: каждый день он будет тратить на осмотр города, а каждую ночь — на переезд ночным поездом между городами. Разумеется, Петр не имеет ни малейшего желания посещать один город несколько раз.

Но на этом прагматичность Петра не заканчивается: Петр, как настоящий турист, хочет посмотреть на самые красивые европейские достопримечательности. Он долго изучал справочники и для каждого города оценил свою ожидаемую радость от его посещения \(p_i\). Теперь он хочет найти маршрут, при котором его радость будет наибольшей. Помогите Петру найти такой маршрут.

Формат входного файла

В первой строке входных данных заданы два целых числа \(V\) и \(E\) (1 ≤ \(V\); \(E \le 3*10^5\)) — количество городов и маршрутов поездов, соответственно. В следующей строке заданы V целых чисел \(p_i\) (1 ≤ \(p_i\) ≤ \(10^8\)), где \(p_i\) обозначает ожидаемую радость от посещения го- рода с номером \(i\). В следующих \(E\) строках заданы описания маршрутов поездов. Каждое описание состоит из пары различных чисел \(a_i\) и \(b_i\) (1 ≤ \(a_i\); \(b_i\) ≤ V\( \)) — номеров городов, между которыми курсирует этот маршрут поезда. Гарантируется, что между каждой парой городов существует не более одного маршрута поезда.

Формат выходного файла

В первой строке выходных данных выведите число K (1 ≤ K ≤ 4) — количество городов в оптимальном маршруте туриста Петра. В следующей строке выведите номера этих городов в порядке посещения. Города нумеруются начиная с единицы. Если оптимальных маршрутов несколько, выведите любой из них.

Система оценивания

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

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

1. Тесты 3–16. В тестах этой группы \(V\); \(E\) ≤ 100. Эта группа оценивается в 20 баллов

2. Тесты 17–32. В тестах этой группы \(V\); \(E\) ≤ 1 000. Эта группа оценивается в 20 баллов.

3. Тесты 33–53. В тестах этой группы \(V\) ≤ 3 000, \(E\) ≤ 60 000. Эта группа оценивается в 30 баллов.

4. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 30 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура.

Примеры
Входные данные
5 4
4 2 3 1 5
1 2
2 3
3 4
4 5
Выходные данные
4
2 3 4 5
Входные данные
4 3
1 2 3 4
1 2
1 3
1 4
Выходные данные
3
4 1 3
#112101
Паровозик из Морошково (BC)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

В первой строке через пробел вводятся два натуральных числа: количество часов в одних сутках ( H ) и минут в одном часу ( M ) на Пандоре ( 1 ≤ H , M ≤ 500 ).

Следующая строка содержит четыре целых числа, описывающих время начала ( H s , M s ) и конца ( H f , M f ) светового дня ( 0 ≤ H s , H f < H ; 0 ≤ M s , M f < M ). При этом либо H s < H f , либо H s = H f и M s < M f (гарантируется, что день начинается раньше, чем заканчивается). Если паровозик проезжает мимо водопада ровно в H s часов M s минут или ровно в H f часов M f минут, то считается, что он проехал мимо водопада днём.

Третья строка содержит одно натуральное число N — количество водопадов, рядом с которыми проезжает паровозик ( 1 ≤ N ≤ 100 000 ).

В следующих N - 1 строках вводятся по 2 целых числа H i и M i , описывающих продолжительность временных интервалов для проезда между соседними водопадами: H 1 , M 1 — время в пути между первым и вторым водопадами, H 2 , M 2 — между вторым и третьим и так далее. Гарантируется, что время, затрачиваемое на дорогу между любыми двумя соседними водопадами, строго положительно, не превосходит одних пандорианских суток и записано корректно: 0 ≤ H i ≤ H , 0 ≤ M i < M .

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

Если составить подходящее расписание невозможно, то в качестве ответа выведите одно слово « Impossible » (без кавычек). Иначе выведите два числа H 0 и M 0 , разделённые пробелом, описывающие любое подходящее время проезда паровозика рядом с первым водопадом.

Примечание

Тесты к этой задаче состоят из четырех групп.

  • Тесты 1–2. Тесты из условия, оцениваемые в ноль баллов.

  • Тесты 3–17. В тестах этой группы H = 24 , M = 60 и N ≤ 1000 . Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

  • Тесты 18–38. В тестах этой группы H ≤ 80 , M ≤ 100 , N ≤ 100000 . Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

  • В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура. Тесты в этой группе оцениваются независимо.

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

Примеры
Входные данные
24 60
8 0 22 0
6
6 0
21 0
19 0
12 0
10 0
Выходные данные
12 0
Входные данные
24 60
8 17 20 10
2
11 59
Выходные данные
Impossible
#112776
Урок физкультуры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

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

Всего на урок пришло \(N\) детей, изначально построившихся таким образом, что рост стоящего на позиции \(i\) равен \(h_i\) (используется нумерация c \(1\)). Можно считать, что все числа \(h_i\) различны и лежат в диапазоне от 1 до \(N\). Шеренга считается упорядоченной, если на первой позиции стоит школьник ростом один, на второй позиции стоит школьник ростом два и так далее.

Феоктист Всеволодович получает большое удовольствие от процесса упорядочивания школьников, поэтому он всегда выбирает наиболее длинную последовательность обменов. С другой стороны, он не хочет чтобы ученики догадались о том, что он умышленно затягивает построение, поэтому никогда не делает заведомо бессмысленных обменов. А именно, преподаватель никогда не меняет местами школьников на позициях \(i\) и \(j\), если \(h_i < h_j\) . Очевидно, что данное ограничение делает процесс сортировки шеренги по росту конечным.

Староста Саша очень любит играть в волейбол и прекрасно понимает, что чем дольше преподаватель будет расставлять всех по местам, тем меньше времени останется для игры. Ученики уже построились некоторым образом, а Феоктист Всеволодович вышел поговорить по телефону, так что Саша может успеть поменять местами ровно двух школьников, необязательно стоящих рядом в шеренге. Разумеется, он хочет сделать это таким образом, чтобы преподаватель как можно быстрее закончил упорядочивать шеренгу (Саша давно уже раскусил, как именно действует Феоктист Всеволодович). С информатикой у старосты всегда были определённые проблемы, поэтому ему требуется ваша помощь.

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

В первой строке ввода содержится единственное число N — количество школьников на уроке (\(1 \le N \le 1 000 000\)).

Во второй строке записано \(N\) различных целых чисел \(h_i\) (\(1 \le h_i \le N\)). \(i\)-е число соответствует росту школьника стоящего на \(i\)-й позиции

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

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

Замечание

В первом примере из условия после Сашиной перестановки, получится последовательность {2, 1, 3, 5, 4}, и тренер сможет сделать всего два обмена, перед тем как последовательность станет упорядоченной (например, он может поменять местами 1-го и 2-го школьника, а затем 4-го и 5-го). Если Саша поменяет местами двух других школьников, тренер затем сможет сделать три или более обменов.

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

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

Примеры
Входные данные
5
2 4 3 5 1
Выходные данные
2 5
Входные данные
4
1 2 3 4
Выходные данные
-1 -1
Входные данные
10
2 3 7 1 5 10 4 6 9 8
Выходные данные
3 7
Страница: << 2 3 4 5 6 7 8 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест