Окружной этап всероссийской олимпиады школьников по информатике, 2015, i тур россия, самара, 14 ноября 2015 d. трамвайная остановка имя входного файла: стандартный ввод имя выходного файла: стандартный вывод ограничение по времени: 2 секунды ограничение по памяти: 256 мегабайт прохор решил подождать кешу на трамвайной остановке. дождь уже прекратился, но после него возле остановки образовалась огромная лужа, и теперь от каждой проезжающей машины разлета- ются брызги. прохор оглядел свое новенькое пальто, встал подальше от дороги и стал наблюдать за происходящим. когда прохор пришёл на остановку, на ней уже стояли n человек. для каждого из них известно расстояние от края тротуара s1, s2, . . , sn. среди этих расстояний можно выделить smin = min i=1..n {si} и smax = max i=1..n {si}. когда приходит новый потенциальный пассажир, он сразу обращает внимание на лужу, и встает от неё на расстоянии, равном (smin+smax)/2 (округление выполняется в меньшую сторону прохор заметил, что каждая машина (#j) характеризуется параметром dj — расстоянием от края тротуара, на которое долетают брызги. всех, кто стоит ближе dj , окатывает брызгами, после чего они, отряхиваясь и негромко произнося слова глубокой в адрес водителя, отходят на расстояние dj + 1 от края тротуара и ближе уже не подходят. разумеется, эти перемещения могут повлиять на значения smin и smax, и очередной потенциальный пассажир, пришедший после проезда очередной машины, будет определять для себя расстояние от края тротуара, исходя из этих новых значений. по данным о приходящих потенциальных пассажирах и проезжающих машинах определите для каждой машины, сколько людей, транспорт, удалось обрызгать её водителю. формат входных данных в первой строке содержатся целые положительные числа n и q (1 ⩽ (n+q) ⩽ 3·105 ) — начальное количество людей, транспорт, на остановке и количество сообщений о приходящих потенциальных пассажирах и проезжающих машинах. во второй строке содержится n целых чисел s1, s2, . . , sn (0 ⩽ sj ⩽ 109 ) — расстояния от края тротуара, на которых исходно стоят потенциальные пассажиры. в каждой из следующих q строк содержится сообщение одного из двух видов: — единственный символ p, обозначающий, что на остановку пришёл потенциальный пассажир; — символ c, обозначающий, что мимо остановки проехала машина, и целое число dj (0 ⩽ dj ⩽ 109 ) — расстояние от края тротуара, на которое долетают брызги от этой машины. гарантируется, что во входных данных есть информация о хотя бы одной проехавшей машине. формат выходных данных в единственной строке выведите z целых чисел y1, y2, . . , yz, где yj — количество людей, которых удалось обрызгать водителю машины #j (z — количество сообщений о проезжающих машинах).
Ответы
Не хорошо олимпиады с источников скатывать))0 Условия читал хоть?
Решение в прикрепленном файле.
1. "Школьное" решение
// PascalABC.Net 3.0, сборка 1066
var
s,s1:string;
i:integer;
a:char;
begin
Write('Введите натуральное число любой длины :'); Readln(s);
Write('Введите цифру, которую надо удалить: '); Readln(a);
s1:='';
for i:=1 to Length(s) do
if s[i]<>a then s1:=s1+s[i];
Writeln('Результат: ',s1)
end.
Тестовый прогон:
Введите натуральное число любой длины :3141592653589793
Введите цифру, которую надо удалить: 5
Результат: 3141926389793
2. Современное решение (так в школе почему-то не учат)
// PascalABC.Net 3.0, сборка 1066
begin
var s:=ReadString('Введите натуральное число любой длины :');
var a:=ReadChar('Введите цифру, которую надо удалить: ');
Write('Результат: ',s.Replace(a,''));
end.
// PascalABC.Net 3.0, сборка 1066
var
s,s1:string;
i:integer;
a:char;
begin
Write('Введите натуральное число любой длины :'); Readln(s);
Write('Введите цифру, которую надо удалить: '); Readln(a);
s1:='';
for i:=1 to Length(s) do
if s[i]<>a then s1:=s1+s[i];
Writeln('Результат: ',s1)
end.
Тестовый прогон:
Введите натуральное число любой длины :3141592653589793
Введите цифру, которую надо удалить: 5
Результат: 3141926389793
2. Современное решение (так в школе почему-то не учат)
// PascalABC.Net 3.0, сборка 1066
begin
var s:=ReadString('Введите натуральное число любой длины :');
var a:=ReadChar('Введите цифру, которую надо удалить: ');
Write('Результат: ',s.Replace(a,''));
end.
Проще всего складывать в столбик как обычные десятичные числа, но если в сумме число получится больше 8 (система восмиричная), то мы отнимаем 8, смотрим: меньше ли получившийся остаток 8, если нет, то снова отнимаем восемь и тогда записываем остаток, а в "ум" запишем число отнятых восьмерок
574+467=1263 (все числа в восьмиричной системе счисления)
так, складывая 4 и 7, получаем 11, что больше 8, поэтому отняв 8, получим цифру 3, которую и записываем как последнюю цифру числа (3 пишем, 1 в уме), далее складываем 6 и 7 и не забываем про 1, потому что в раз мы отняли всего одну восьмерку, получаем 14, но записываем только 6, а 1 в уме, затем 5, 4 и 1 - 2 пишем, 1 в уме, далее просто приписываем единицу, получаем 1263
P.S. несмотря на то, что кажется сложно, это немногим отличается от десятичной системы сложения в столбик
574+467=1263 (все числа в восьмиричной системе счисления)
так, складывая 4 и 7, получаем 11, что больше 8, поэтому отняв 8, получим цифру 3, которую и записываем как последнюю цифру числа (3 пишем, 1 в уме), далее складываем 6 и 7 и не забываем про 1, потому что в раз мы отняли всего одну восьмерку, получаем 14, но записываем только 6, а 1 в уме, затем 5, 4 и 1 - 2 пишем, 1 в уме, далее просто приписываем единицу, получаем 1263
P.S. несмотря на то, что кажется сложно, это немногим отличается от десятичной системы сложения в столбик
Ответить на вопрос
Поделитесь своими знаниями, ответьте на вопрос:
Популярные вопросы в разделе
Вывести целое число не более чем 10 разрядов и цифру. проверить что цифра входит в число
Автор: Romanovna-yana
Составить таблицу истинности для m= (a+¬b)*( ¬a +b)+ (¬a + ¬b + ¬c)
Автор: kirillboytsov403
Практическая в шараге кто может сам не шарю
Автор: spikahome