Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 405 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(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 задач)
Страница: << 22 23 24 25 26 27 28 >> Отображать по:
#1102
Найдите прямую
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На плоскости дано N горизонтальных отрезков. Будем говорить, что прямая пересекает отрезок, если у этой прямой и этого отрезка есть хотя бы одна общая точка (в том числе прямая пересекает отрезок, если она проходит через один из его концов). Требуется найти прямую, пересекающую все отрезки, или установить, что такой нет.>

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

В первой строке входного файла находится единственное число N. В каждой из следующих N строк содержатся по три целых числа Pi, Qi, Ri, описывающих отрезки: соответствующий отрезок соединяет точки (Pi, Ri) и (Qi, Ri). Никакие два отрезка не лежат на одной прямой.

1≤N≤10000, Pi<Qi, все числа по модулю не превосходят 10000.

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

В случае, если искомая прямая существует, выведите в выходной файл коэффициенты ее уравнения (будем задавать прямую уравнением вида A∙x+B∙y+C=0, где x, y – координаты точек прямой, A, B, C – такие коэффициенты, что указанному уравнению удовлетворяют все точки прямой, и только они; соответственно, чтобы задать прямую, нужно задать три числа – A, B, C).

Коэффициенты уравнения должны быть целыми и не должны превосходить по модулю 109 (гарантируется, что при наличии решения такие A, B, C существуют).

Если прямой не существует, выведите в выходной файл сообщение “No solution” (без кавычек).

Примеры
Входные данные
3
0 1 0
0 1 1
0 1 2
Выходные данные
1 0 0
Входные данные
5
0 2 0
2 4 1
1 3 2
1 3 -1
1 3 -2
Выходные данные
3 -1 -5
Входные данные
3
0 1 0
1 2 1
-2 -1 2
Выходные данные
No solution
#1105
Игра с обменами
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Вася и Петя играют в увлекательную игру. Вася выписал подряд числа от 1 до N. А Петя выписал P пар чисел (Ai, Bi).

Теперь Вася преобразует имеющуюся последовательность чисел - он меняет местами числа в этой последовательности. Если некоторая пара чисел (Ai, Bi) выписана Петей, то Вася имеет право в любой момент взять числа из последовательности, стоящие на местах Ai и Bi и поменять их местами.

Например, если N=5. Тогда изначально Васей выписана последовательность

1 2 3 4 5

Пусть Петя написал две пары чисел: (1,2) и (2,5). Тогда Вася в любой момент может менять числа, стоящие на 1 и 2 местах, или же числа, стоящие на 2 и 5 местах.

Например, он может последовательно получить следующие последовательности:

2 1 3 4 5 (поменяв числа на 1 и 2 местах)

2 5 3 4 1 (поменяв числа на 2 и 5 местах)

5 2 3 4 1 (поменяв числа на 1 и 2 местах).

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

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

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

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

Сначала записано число N (1≤N≤100) – количество чисел в последовательности. Дальше идет N чисел – последовательность, полученная Васей (в последовательности каждое из чисел от 1 до N встречается ровно один раз).

Далее идет число P (0≤P≤10000) – количество пар чисел, выписанных Петей. Далее записано P пар чисел (каждое число пары – из диапазона от 1 до N).

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

В первую строку выходного файла выведите сообщение YES (если такая последовательность могла быть честно получена Васей) и NO (если такую последовательность Вася не мог получить, не нарушая правил игры).

В случае, если такая последовательность могла быть получена, далее выведите способ ее получения (если вариантов несколько, выведите любой из них). Сначала выведите число K – количество операций обмена (оно не должно превышать 100000), а затем K пар чисел, задающих номера мест, на которых стоят обмениваемые элементы (числа в паре могут быть выданы в любом порядке). Гарантируется, что если решение существует, то существует решение с числом обменов, не превышающим 100000.

Примеры
Входные данные
5
5 2 3 4 1
2
1 2
2 5
Выходные данные
YES
3
1 2
2 5
1 2
Входные данные
5
2 3 4 5 1
2
1 2
2 5
Выходные данные
NO
#1106
SMS
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

SMS-сообщения на мобильном телефоне марки MOBILO набираются только заглавными английскими буквами. Для набора буквы нужно нажать кнопку, на которой эта буква написана, при этом если эта буква написана первой, то кнопку нужно нажать один раз, если второй – то два раза и т.д. Устройство клавиатуры телефона приведено на рисунке.

Таким образом, чтобы набрать слово SMS, нужно нажать следующие кнопки:

<PQRS> <PQRS> <PQRS> <PQRS> <MNO> <PQRS> <PQRS> <PQRS> <PQRS>

Для набора двух букв, которые находятся на одной кнопке, при наборе нужно сделать паузу между их вводом. Например, чтобы набрать BA, нужно два раза нажать кнопку <ABC>, затем сделать паузу и затем нажать кнопку <ABC> еще раз.

Если на кнопке написано три буквы, то как только эта кнопка нажата три раза подряд, последняя из написанных на ней букв сразу же добавляется в сообщение, а дальнейшие нажатия на эту кнопку воспринимаются как ввод следующей буквы. То же самое, если на кнопке написано 4 буквы. Таким образом, 4-х кратное нажатие на кнопку <ABC>, затем пауза, и затем нажатие на эту кнопку еще раз приведет к вводу текста CAA.

К сожалению, в силу произошедшего глюка, телефон стал иногда игнорировать паузы при вводе, а, иногда, наоборот, вести себя так, как будто была пауза тогда, когда паузы не было. Например, при вводе слова MOSCOW могло в итоге (как один из вариантов) получиться слово OMSCMNW.

Вы получили SMS-сообщение, набранное на этом телефоне. Известно, что изначально оно состояло из N символов. Напишите программу, которая определит количество вариантов исходных сообщений, которые при вводе могли превратиться в то, что вы получили (если вариантов окажется 0, то это будет означать, что у телефона сломалось что-то еще).

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

Сначала записана длина исходного сообщения N (1≤N≤80). Вторая строка содержит полученное SMS-сообщение – последовательность не более чем из 80 заглавных латинских букв.

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

Выведите одно число – количество вариантов исходного сообщения.

Примеры
Входные данные
4
MAMA
Выходные данные
1
Входные данные
2
WWW
Выходные данные
2
Входные данные
10
MAMA
Выходные данные
0
#1150
Таблица
  

Рассмотрим прямоугольную таблицу размером n m. Занумеруем строки таблицы числами от 1 до n, а столбцы – числами от 1 до m. Будем такую таблицу последовательно заполнять числами следующим образом.

Обозначим через aij число, стоящее на пересечении i-ой строки и j-ого столбца. Первая строка таблицы заполняется заданными числами – a11, a12, …, a1m. Затем заполняются строки с номерами от 2 до n. Число aij вычисляется как сумма всех чисел таблицы, находящихся в «треугольнике» над элементом aij. Все вычисления при этом выполняются по модулю r.






























 

 

ai,j

















Более точно, значение aij вычисляется по следующей формуле:

 

Например, если таблица состоит из трех строк и четырех столбцов, и первая строка состоит из чисел 2,3,4,5, а r = 40 то для этих исходных данных таблица будет выглядеть следующим образом (взятие по модулю показано только там, где оно приводит к изменению числа):

2

3

4

5

5 = 2 + 3

9 = 2 + 3 + 4

12 = 3 + 4 + 5

9 = 4 + 5

23 = 2 + 3 + 4 + 5 + 9

0 = (2 + 3 + 4 + 5 + 5 + 9 + 12) mod 40 = 40 mod 40

4 = (2 + 3 + 4 + 5 + 9 + 12 + 9) mod 40 = 44 mod 40

33 = 3 + 4 + 5 + 12 + 9

Требуется написать программу, которая по заданной первой строке таблицы (a11, a12, …, a1m), вычисляет последнюю строку, как описано выше.

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

Первая строка входного файла содержит числа n, m и r (2 ≤ n, m ≤ 2000, 2 ≤ r ≤ 109) – число строк и столбцов таблицы соответственно, а так же число, по модулю которого надо посчитать ответ. Следующая строка содержит m целых чисел – первую строку таблицы: a11, a12, …, a1m. Все a1i неотрицательны и не превосходят 109.

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

В первой строке выходного файла необходимо вывести m чисел – последнюю строку таблицы: an1, an2, …, anm.

Примеры
Входные данные
2 3 10
1 2 3
Выходные данные
3 6 5
Входные данные
3 3 10
1 1 1
Выходные данные
8 0 8
Входные данные
3 4 40
2 3 4 5
Выходные данные
23 0 4 33
#1151
Гомотетия
  

Гомотетией с центром O и коэффициентом k 0 называют преобразование плоскости, при котором точка O переходит сама в себя, а любая точка X O – в такую точку Y, что:

  • Y лежит на прямой OX;
  • OY = |k|OX;
  • при k >0 Y лежит на луче OX, при k <0 Y лежит на продолжении луча OX за точку O.

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

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

В первой строке входного файла содержится целое число n (3 ≤ n ≤ 1000) – количество вершин в каждом многоугольнике

В следующих n строках – по два целых числа x и y (-106 ≤ x,y ≤ 106) – координаты вершин первого многоугольника в порядке обхода против часовой стрелки.

В следующих n строках – по два целых числа x и y (-106 ≤ x,y ≤ 106) – координаты вершин второго многоугольника в порядке обхода против часовой стрелки.

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

Если существует гомотетия, которая переводит первый многоугольник во второй, то необходимо вывести в первой строке выходного файла слово «YES», а во второй строке – три вещественных числа – координаты центра гомотетии и ее коэффициент, которые вычисляются с точностью не менее 10-5. Если искомой гомотетии не существует, необходимо вывести в выходной файл слово «NO».

Примеры
Входные данные
3
-1 1
1 1
1 5
1 9
-3 1
1 1
Выходные данные
YES
1.0 1.0 2.0
Входные данные
3
-1 1
1 1
1 5
1 1
0 0
1 0
Выходные данные
NO
Страница: << 22 23 24 25 26 27 28 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест