Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 50 задач <---
Источники --> Командные олимпиады --> Командные чемпионаты школьников Санкт-Петербурга по программированию
    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 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#1755
Таможня
  
Для набора грузов известно время прихода каждого груза и время обработки груза аппаратом. Необходимо найти минимальное количество аппаратов, необходимых для того, чтобы грузы начинали обрабатываться сразу после прихода.

Идёт 2163 год. Мишу, который работает в отделении таможни при космодроме города Нью-Питер, вызвал в кабинет шеф.

Как оказалось, недавно Министерство Налогов и Сборов выделило отделению определённую сумму денег на установку новых аппаратов для автоматического досмотра грузов. Естественно, средства были выделены с таким расчётом, чтобы грузы теперь находились на таможне ровно столько времени, сколько требуется непосредственно на их досмотр.

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

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

На первой строке входного файла задано число \(N\) (0 ≤ \(N\) ≤ 50 000). На следующих \(N\) строках находится по 2 целых положительных числа \(T_i\) и \(L_i\) – время прибытия соответствующего груза и время, требуемое для его обработки (1 ≤ \(T_i\) ≤ \(10^6\), 1 ≤ \(L_i\) ≤ \(10^6\)).

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

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

Примеры
Входные данные
3
3 2
4 2
5 2
Выходные данные
2
Входные данные
5
13 4
15 1
11 5
12 3
10 3
Выходные данные
3
#1756
Динокод
  

Строки формируются по правилу: S1 = a, Si = Si-1 + chr(i) + Si-1. Необходимо по данной строке найти максимальное i, такое что данная строка является подстрокой Si

Учёные любят присваивать идентификаторы всему живому. Поэтому они обозначают динозавров I эпохи кодом `a'. Динозавры II эпохи, как произошедшие от динозавров I эпохи, именуются кодом `aba'. Ящеры III эпохи – `abacaba', и вообще если \(C\)(\(n\)) – код динозавров эпохи \(n\), то \(C\)(\(n\)+1)=\(C\)(\(n\))+\(S\)(\(n\)+1)+\(C\)(\(n\)) , где \(S\)(\(n\)+1) – символ очередной (\(n\)+1-ой) эпохи. Символ первой эпохи – `a' , символ второй эпохи – `b', затем `c', `d', …, `x', `y', `z'. После букв учёные почему-то перешли на цифры, и обозначили эпохи с XXVII по XXXVI соответственно `0', `1', …, `9' .

После XXXVI эпохи динозавры вымерли, и уже утверждённое название XXXVII эпохи (`α') отдали астрономам для нового кратера на Марсе.

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

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

На первой и единственной строке входного файла находится непустая строка, состоящая из символов `a', …, `z', `0', …, `9'. Длина строки не превосходит 100.

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

Выведите два числа – номер эпохи и смещение образца от начала кода. Если же статуя изображает неземного динозавра (или код инопланетян отличается от земного), выведите в выходной файл число 0.

Примеры
Входные данные
a
Выходные данные
1 0
Входные данные
bae
Выходные данные
5 13
#1757
Дракон Лун-Ян
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задан выпуклый многоугольник, составленный из проволоки. Требуется найти количество устойчивых положений многоугольника (когда он опирается на ось X двумя точками и центр масс многоугольника находится между ними)

Петя и его друг Андрейка только что познакомились с китайской мифологией. Особенно им понравились драконы. Поэтому мальчики решили сделать своих драконов из проволоки. Андрейка взял белую проволоку и согнул из неё дракона Лун-Инь: этот дракон спал, свернувшись клубком на столе. Тогда Петя взял чёрную проволоку и согнул дракона Лун-Ян. Этот дракон ничем не походил на Андрейкиного Лун-Иня. Его тело состояло из отрезков прямых, а когда он спал, то сворачивался в виде плоской замкнутой несамопересекающейся ломаной. Более того, Лун-Ян не ложился плашмя на стол для сна, а вставал перпендикулярно поверхности. Удержать равновесие дракон может только тогда, когда существуют две его различные точки, касающиеся стола, такие что центр масс дракона находится строго между ними.

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

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

В первой строке входного файла содержится число \(n\) (3 ≤ \(n\) ≤ 1000) – количество вершин ломаной и два целых числа \(x_c\) и \(y_c\) – координаты центра масс дракона (-1000 ≤ \(x_c\), \(y_c\) ≤ 1000). В следующих \(n\) строках содержится по два целых числа \(x_i\) и \(y_i\) (-1000 ≤ \(x_i\), \(y_i\) ≤ 1000) – координаты вершин ломаной в порядке обхода против часовой стрелки (ось \(O_X\) направлена вправо, а ось \(O_Y\) – вверх).

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

В первой строке выходного файла выведите число устойчивых положений дракона.

Примеры
Входные данные
12 1 2
3 4
2 4
2 3
1 3
1 4
0 4
0 0
1 0
1 1
2 1
2 0
3 0
Выходные данные
4
#1758
Увлекательная игра
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Загадывается число. Можно задавать вопросы с ответом Да или Нет (штраф за Да A конфет, за Нет B конфет). Требуется определить минимальное количество конфет, необходимое для отгадывания числа в худшем случае.

Петя и Маша играют в увлекательную игру. Маша загадывает число от 1 до \(n\), записывает его на чистый тетрадный лист, кладёт в конверт и запечатывает. После этого Петя пытается это число отгадать. Он может задавать любые вопросы про это число: "Верно ли, что это число равно трем?", "Верно ли, что это число – число Фибоначчи?", "Верно ли, что это число простое?" и так далее. Получив ответ "Да", Петя отдает Маше a конфет, а в случае ответа "Нет" – b конфет.

В какой-то момент Петя произносит сакраментальную фразу: "Я знаю, что это за число". После этого они распечатывают конверт в присутствии свидетелей, убеждаются в Петиной правоте, и, таким образом, Маша получает внушительную порцию конфет, а Петя – моральное удовлетворение.

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

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

Входной файл содержит три целых числа: \(n\) (1 ≤ \(n\) ≤ 1000), \(a\) и \(b\) (0 ≤ \(a\), \(b\) ≤ \(10^6\)).

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

Выведите одно число – минимальное количество конфет, которое должен иметь Петя, чтобы отгадать Машино число в худшем случае.

Примеры
Входные данные
8 1 1
Выходные данные
3
Входные данные
10 5 0
Выходные данные
5
Входные данные
7 0 2
Выходные данные
2
#1759
Единицы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задается число, состоящее из N единиц. Требуется вывести квадрат этого числа.

Найдите квадрат числа, десятичная запись которого состоит из \(n\) единиц.

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

Входной файл содержит единственное число \(n\) (1 ≤ \(n\) ≤ \(10^5\)).

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

Выведите искомый квадрат.

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