Темы
    Информатика(2656 задач)
---> 167 задач <---
Источники --> Командные олимпиады --> Командные чемпионаты школьников Санкт-Петербурга по программированию
    1999(5 задач)
    2000(7 задач)
    2001(8 задач)
    2002(8 задач)
    2003(9 задач)
    2004(9 задач)
    2005(10 задач)
    2006(10 задач)
    2007(10 задач)
    2008(9 задач)
    2009(10 задач)
    2010(10 задач)
    2011(9 задач)
    2012(10 задач)
    2013(10 задач)
    2014(11 задач)
    2015(11 задач)
    2016(11 задач)
Страница: << 20 21 22 23 24 25 26 >> Отображать по:
#113624
Дюны
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Географ Григорий Георгиевич исследует образование песчаных дюн. Он выбрал очень длинную дюну и разбил его на огромное число участков, которые пронумеровал от \(1\) до \(10^9\).

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

Порыв ветра номер \(i\) имел силу \(x_i\) и действовал на участки с \(l_i\)-го по \(r_i\)-й. В результате этого порыва высота участка номер \(l_i\) увеличилась на \(x_i\), высота участка номер \(l_i \ + \ 1\) уменьшилась на \(x_i\), следующего — снова увеличилась на \(x_i\), и так далее до участка номер \(r_i\), включительно.

Зная всю информацию о всех \(n\) порывах ветра, Григорий Георгиевич хочет узнать установившуюся в итоге высоту некоторых интересующих его \(m\) участков. Помогите ему.

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

В первой строке входного файла содержатся два натуральных числа \(n\) и \(m\) (\(1 \le n, m \le 1000\)) — количество порывов ветра и количество участков, итоговая высота которых интересует Григория Георгиевича.

В каждой из следующих n строк содержится описание очередного порыва ветра — три целых числа \(l_i, \ r_i, \ x_i (1 \le l_i \le r_i \le 10^9; 1 \le x_i \le 1000\)).

В каждой из следующих \(m\) строк содержится целое число \(q_i\) (\(1 \le q_i \le 10^9\)) — номер участка, для которого требуется узнать его итоговую высоту. Номера участков приведены в возрастающем порядке.

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

Для каждого из \(m\) запросов выведите одно целое число — высоту соответствующего участка.

Примеры
Входные данные
2 6
1 6 7
3 7 2
1
2
3
6
7
8
Выходные данные
7
-7
9
-9
2
0
#113625
Игра
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Ребята выяснили, что Петя может закинуть кольцо на столбик только, если высота этого столбика не меньше \(l_1\) и не больше \(r_1\). На слишком высокий или слишком низкий столбик он закинуть кольцо не может. Зато, если столбик имеет подходящую высоту, бросок гарантированно заканчивается успехом. Аналогично, Вася может закинуть кольцо только на столбики с высотой не меньше \(l_2\) и не больше \(r_2\) и гарантированно закидывает кольцо на любой такой столбик.

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

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

В первой строке входного файла находятся два целых числа \(n\) и \(m\) — количество столбиков и колец, соответственно (\(1 \le m \le n \le 10^5\)). Следующие две строки содержат числа \(l_1, \ r_1 \ и \ l_2, \ r_2\) — минимальную и максимальную высоту столбиков, на которые могут кидать колечки Петя и Вася, соответственно (\(1 \le l_1 \le r_1 \le 10^9 , 1 \le l_2 \le r_2 \le 10^9\) ). В последней строке содержится \(n\) чисел, описывающих высоту столбиков, высота каждого столбика является целым положительным числом и не превышает \(10^9\).

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

В выходной файл выведите «Petya», если выиграет Петя, «Vasya», если выиграет Вася, или «Draw», если при оптимальной игре оба мальчика закинут на столбики равное число колец.

Пояснения к примерам

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

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

В третьем примере Петя первым ходом закидывает кольцо на один из двух доступных ему столбиков, а Вася вторым ходом закидывает кольцо на второй из этих столбиков. Теперь у Пети нет столбиков, на который он может закинуть кольцо, он кидает третье кольцо, но не попадает. Вася же закидывает последнее кольцо на любой из столбиков высоты 3 или 4.

Примеры
Входные данные
4 3
1 2
2 4
1 2 3 4
Выходные данные
Petya
Входные данные
4 4
1 4
1 4
1 2 3 4
Выходные данные
Draw
Входные данные
4 4
1 2
1 4
1 2 3 4
Выходные данные
Vasya
#113626
НОД и НОК
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Сережа очень любит математические задачи. Недавно на математическом кружке ему рассказали, что такое НОД и НОК.

НОД двух натуральных чисел \(a\) и \(b\) — это их наибольший общий делитель, то есть такое максимальное число \(x\), что \(a\) делится на \(x\) и \(b\) делится на \(x\). Например, НОД(24, 18) = 6. А НОК целых чисел \(a\) и \(b\) — это их наименьшее общее кратное, то есть такое минимальное число \(x\), что \(x\) делится на \(a\) и на \(b\). Например, НОК(24, 18) = 72.

Сережа сразу заметил, что может существовать несколько пар чисел с одинаковыми НОД и НОК. Теперь он заинтересовался вопросом: если заданы числа \(a\) и \(b\), насколько близко друг к другу могут быть два числа, у которых такие же НОД и НОК.

Помогите ему по заданным двум числам \(a\) и \(b\) найти такие числа \(x\) и \(y\), что \(НОД(a, \ b) \ = \ НОД(x, \ y), \ НОК(a, \ b) \ = \ НОК(x, \ y)\), а их разность \(y \ − \ x\) минимальна.

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

В первой строке входного файла находятся два натуральных числа \(a\) и \(b\) (\(1 \le a, \ b \le 10^9\) ).

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

Выведите два натуральных числа \(x\) и \(y\) (\(1 \le x \le y\)), таких, что \(НОД(a, \ b) \ = \ НОД(x, \ y), НОК(a, \ b) \ = \ НОК(x, \ y)\), а их разность \(y \ − \ x\) минимальна.

Примеры
Входные данные
3 4
Выходные данные
3 4
Входные данные
1 12
Выходные данные
3 4
#113627
Мерлин
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

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

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

В первой строке входного файла находится число \(n\) (\(2 \le n \le 10^5\) ) — количество сосудов. Во второй строке содержатся \(n\) чисел \(a_1, \ a_2, \dots, a_n \ (1 \le a_i \le 10^9\) ) — количество литров эликсира мудрости в каждом сосуде.

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

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

Пояснения к примерам

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

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

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

Примеры
Входные данные
3
2 3 2
Выходные данные
1
Входные данные
4
4 4 4 4
Выходные данные
0
Входные данные
5
1 2 3 4 5
Выходные данные
2
#113628
Регистрация на олимпиаду
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

  • для всех участников сначала написана фамилия, затем имя, а затем — отчество;
  • участники в таблице упорядочены лексикографически по фамилии.
Петя и Вася заметили, что фамилии у всех участников различны, а вот каждое имя встречается хотя бы два раза. При этом никакое имя не является ни фамилией, ни отчеством никакого из участников, аналогично никакие фамилия и отчество не совпадают.

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

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

В первой строке задано число \(n\) (\(2 \le n \le 1000\)) — общее число записей в электронной таблице. Далее, в \(n\) строках записано по три слова \(s_{1,i}, \ s_{2,i}, \ s_{3,i}\). Каждое из слов содержит от 1 до 20 латинских букв, первая буква является заглавной, а все остальные — строчными. Каждая строка соответствует одной из записей, сделанных Петей или Васей. Слова разделены одним пробелом.

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

Выведите n строк — электронную таблицу, в которой для каждого участника идет сначала фамилия, потом имя, потом отчество, причем все записи отсортированы лексикографически.

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

Примеры
Входные данные
4
Ivanov Ivan Ivanovich
Ivan Borisovich Petrov
Sergey Ivanovich Sidorov
Pavlov Sergey Borisovich
Выходные данные
Ivanov Ivan Ivanovich
Pavlov Sergey Borisovich
Petrov Ivan Borisovich
Sidorov Sergey Ivanovich
Страница: << 20 21 22 23 24 25 26 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест