Темы
    Информатика(2656 задач)
---> 13 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Региональный этап --> Московская областная олимпиада
    2007(7 задач)
    2008(6 задач)
Страница: << 1 2 3 >> Отображать по:
#1226
Игра с шашками
  

Поле для игры с шашками – длинная горизонтальная полоска, размеченная на клетки. Клетки пронумерованы от 1 до N (2 < N < 10000). На поле стоят две шашки. Позиция каждой из шашек определяется номером клетки, в которой она стоит.

Играют двое. Каждый игрок при своем ходе должен переместить любую шашку на одну, две или три клетки в сторону клетки 1 (сделать 1, 2 или 3 шага). Перепрыгивать через стоящую впереди шашку нельзя, но можно сдваивать шашки. На сдваивание шашек   тратится два шага из трех доступных игроку (то есть сдваивать можно либо шашки, стоящие  вплотную друг к другу, либо шашки, между которыми есть только одна пустая клетка). Если произошло сдваивание – ход передается другому игроку, который делает ход  одной шашкой , оставив другую на месте.

Выигрывает тот, кто сдвоит шашку на клетке с номером 1.

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

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

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

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

Выводится K строчек – ответ на каждую начальную позицию.

Если при заданной начальной позиции шашек в игре не достигается выигрыш (при правильной игре противника) выводится слово NO.

Если выигрыш достижим, то выводится первый ход начинающего игру, который приводит к его выигрышу независимо от того, как играет соперник. Ход описывается парой чисел  i, j через пробел, означающих, что выигрышный ход игрока – это перемещение шашки из клетки с номером i в клетку с номером  j. Например, «4 3» означает, что игрок двигает шашку, стоящую в клетке 4, на одну клетку в сторону клетки 1.

Примечание
Ответ на тест из примера:
NO
11 10
12 11
NO
15 12
12 10
Примеры
Входные данные
6
3 10
3 11
4 12
5 8
9 15
3 12
Выходные данные
YES
NO
#1227
Радио «Байтик»
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Как известно, при распространении радиоволн возникает интерференция, поэтому если рядом расположены две радиопередающие станции, вещающие на одной и той же частоте, то качество радиопередач резко снижается.

Радиостанция «Байтик» планирует транслировать свои программы в стране Флатландия. Министерство связи Флатландии выдало радиостанции лицензию на вещание на двух различных частотах.

Владельцы радиостанции имеют возможность транслировать свои радиопрограммы с использованием N радиовышек, расположенных в различных точках страны. Для осуществления трансляции на каждой радиовышке требуется установить специальный передатчик – трансмиттер. Каждый передатчик можно настроить на одну из двух частот, выделенных радиостанции. Кроме частоты вещания, передатчик характеризуется также своей мощностью. Чем мощнее передатчик, тем на большее расстояние он распространяет радиоволны. Для простоты, предположим, что передатчик мощности R распространяет радиоволны на расстояние, равное R километрам.

Все передатчики, установленные на вышках, должны, согласно инструкции министерства, иметь одну и ту же мощность. Чтобы программы радиостанции могли приниматься на как можно большей территории, мощность передатчиков должна быть как можно большей. С другой стороны, необходимо, чтобы прием передач был качественным на всей территории Флатландии. Прием передач считается качественным, если не существует такого участка ненулевой площади, на который радиоволны радиостанции «Байтик» приходят на одной частоте одновременно с двух вышек.

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

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

Первая строка содержит число N — количество вышек (3 ≤ N ≤ 1200). Последующие N строк содержат по два целых числа — координаты вышек. Координаты заданы в километрах и не превышают 104 по модулю. Все точки, в которых расположены вышки, различны. Все числа в строках разделены пробелом.

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

В первой строке выводится вещественное число — искомая мощность передатчиков. Во второй строке выводятся N чисел, где i-е число должно быть равно 1, если соответствующий передатчик должен вещать на первой частоте, и 2, если на второй. Ответ должен быть выведен с точностью, не меньшей 10–8.

Примеры
Входные данные
4
0 0
0 1
1 0
1 1
Выходные данные
0.707106781186548
1 2 2 1
#3139
Лицензионные ключи
  
Темы: [Строки]

Компания Macrohard выпустила в свет новую версию операционной системы «Frames» («Рамки») и теперь стремится внедрить ее на рынок информационных технологий. Каждая фирма, заказывающая новую версию «Рамок», получает лицензионные ключи от компании Macrohard по следующим правилам:

  • каждой копии присваивается уникальный 25-разрядный ключ, состоящий из цифр и заглавных букв латинского алфавита. Код разбивается на группы по 5 символов, которые разделяются между собой знаком «-»
  • по каждому ключу можно вычислить его контрольную сумму по следующему правилу: необходимо сложить веса значащих символов и взять остаток от деления этой суммы на некое число P, где вес символа есть
    • значение цифры, если символ является цифрой (то есть вес цифры 5 равен пяти)
    • порядковый номер буквы в латинском алфавите плюс 9 (то есть вес буквы F равен 15)
Например, для кода 12345-12345-12345-12345-12345 при P = 11 контрольная сумма равна (1+2+3+4+5)*5 mod 11 = 9
  • контрольная сумма является идентификатором фирмы, которая покупает операционные системы, следовательно, оно должно быть различным для разных юридических лиц.

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

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

В первой строке входного файла содержится два натуральных числа N и P (1 ≤ N ≤ 30000, 1 ≤ P ≤ 1000), где N – число уже использованных ключей, P – число, используемое для подсчета контрольной суммы. В следующих N строках следуют ключи, которые задаются в виде
XXXXX-XXXXX-XXXXX-XXXXX-XXXXX, где X – значащий символ (цифра или буква латинского алфавита).

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

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

Ввод
Вывод
3 5
23545-14978-59345-87926-52496     
67955-58818-19438-55659-02068    
99185-57241-15114-39158-36125
01389-28172-62843-79648-28129
5 3
BGPOV-D618J-FTN7L-4QWZJ-E6P8S     
7K3J3-I8076-58COS-0066F-9UAT4     
7S17C-YI099-1UC85-5S9PB-772LT     
TN2I4-TC1Z6-1OLI6-LT43G-9JMD3     
73OQ3-A9NBJ-N7UT7-AI349-XYJDT
1APMP-RSO53-G743I-F5TK6-R6487
5 4
7911L-5D41U-0N09C-34T16-5D0KI     
FRLAX-RE1Y1-WFVU0-88R56-C5D4V     
RUG51-IR00T-8L812-R6056-7OM59     
804F2-L7292-I12PX-14NDO-02LEW     
J3QQ4-H7H2V-2HCH4-M3HK8-6M8VW
Impossible
#3140
Феодальные отношения
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Для удобства замки феодалов занумерованы натуральными числами по порядку слева направо, начиная с единицы, и разбиты на улицы. Улица (i, j) представляет собой последовательность подряд идущих замков, начиная с замка под номером i и заканчивая замком с номером j (i ≤ j)

Однажды в город приехал новый феодал и пожелал выкупить там замок у одного из жителей. Также ему стало интересно узнать социальный статус соседей по улице, однако, город к тому времени так разросся, что феодал уже не мог сделать этого самостоятельно. Напишите программу, которая поможет ему!

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

Первая строка входного файла содержит число N (1 ≤ N ≤ 30000) — высота замка единственного главного феодала в городе, который никому не подчиняется. Далее, в следующих двух строках идут числа i и j (\(0 \leq i, j < 10^{10000}\)), задающие улицу (i, j), на которой хочет приобрести замок новый феодал (гарантируется, что замки с номерами i и j находятся в черте города, i ≤ j, j – i ≤ 105).

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

Примечание

Будут оцениваться и частичные решения задачи при малых N. Частичные решения для N<20 набирают до 40 баллов, а для N<50 набирают не более 70 баллов.

Ввод
Вывод
2
1
3
1 2 1
3
3
7
1 3 1 2 1
50
128873293
128873293
1
#3141
iCopter
  

В двухмерной игре для современных мобильных телефонов «iCopter» между Васей и Петей идет Bluetooth-сражение. Идет третий раунд. Он проходит с применением вертолётной техники в горном массиве.

Горный профиль в игре «iCopter» задается ломаной (x1, y1), (x2, y2), …, (xN, yN), координаты вершин которой удовлетворяют неравенствам x1 < x2 < … < xN. Начальные и конечные точки профиля расположены на уровне моря (y1 = yN = 0).

Над горами летают вертолет Васи и вертолет Пети. Вертолёт Васи находится в точке A с координатами (XA, YA), Пети — в точке B с координатами (XB, YB). Вертолет Васи производит выстрел снарядом с начальной скоростью, которая задается вектором с компонентами (VX , VY).

Полёт снаряда проходит по следующим законам движения (они определяют координаты снаряда в каждый момент времени до столкновения с горой t ≥ 0):

X = XA + VX * t

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

Требуется написать программу, которая по заданному рельефу, скорости снаряда и координатам вертолётов определяет точку попадания снаряда в гору и уничтожен ли при этом вертолёт Пети.

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

В первой строке входного файла задается семь целых чисел – радиус поражения R (0 ≤ R≤ 10 000, координаты точки A, координаты точки B, компоненты вектора скорости снаряда VX, VY ( -104 ≤ VX≤ 104, VX ≠ 0, 0 < VY≤ 104). Точки Aи B различны.

Во второй строке находится натуральное число N – количество вершин ломаной (2 ≤ N≤ 100 000), которая задает горный профиль. Последующие N строк содержат координаты вершин ломаной (x1, y1), (x2, y2), …, (xN, yN).

Координаты вершин ломаной, а также точек A и B, задаются парой целых чисел, не превосходящих по абсолютному значению 106. Гарантируется, что x1 < x2 < … < xN и y1 = yN = 0, а также то, что снаряд всегда попадает в заданный горный профиль и координата точки попадания xП по оси X лежит в пределах
x1 ≤ xП ≤ xN­­.

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

В первой строке выведите координаты точки взрыва с точностью не менее 3 знаков после запятой. Во второй строке выведите «YES», если вертолёт Пети будет поражен взрывом, и «NO» в противном случае.

Ввод
Вывод
4 6 6 0 6 -4 4
3
0 0
3 11
6 0
4.150749 6.780586
NO
4 6 6 1 6 -4 4
3
0 0
3 11
6 0
4.150749 6.780586
YES
Страница: << 1 2 3 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест