Разбор задач
муниципального этапа
ВСОШ РК 2018
Авторы легенд и части задач Н.О.Котелина, Н.К.Попова7-8 классы
A. Награды победителям
B. Сумма единиц
C. Только целые
D. Учет и контроль
E. Дружба-2
A. Награды победителям
В Республике Коми любят лыжный спорт. Школьники на уроках физкультуры тренируются перед соревнованиями Лыжня России. Сквер, в котором проходят тренировки, невелик по размеру и школьники бегают по небольшому кругу. Учитель обещал наградить тех, кто пройдет больше всех кругов, но не смог их определить
(сбился со счета). Чтобы никого не обидеть, он сказал, что победили все и все получат награду.
В тренировке участвовало N школьников. У учителя имеется M карамелек (2 <= N , M <= 32000). Он хочет разделить карамельки между школьниками поровну, во всяком случае, так, чтобы количество карамелек у школьников отличалось не больше, чем на одну. Учитель раздает карамельки школьникам по одной до тех пор, пока у него не останется карамелек меньше, чем школьников. Оставшиеся карамельки он тоже раздает школьникам. Сколько кому достанется карамелек?
Ввод
Две строки. В первой целое число N – количество школьников. Во второй строке целое число M – количество карамелек.
Вывод
Если карамельки удалось разделить поровну, то вывести количество карамелек, которое получил каждый школьник.
Если поделить поровну не удалось, то вывести четыре числа. Напечатать в одной строке через пробел, сколько школьников получили карамелек меньше, чем другие, и чему равно количество карамелек, которое каждый из них получил, затем, сколько школьников получили карамелек больше, чем другие, и чему равно количество карамелек, которое каждый из них получил.
Разбор
Условный оператор, целочисленное деление, принцип Дирихле. Задача
представлена в книге Льюиса Кэррола “Алиса в стране чудес”, там Алиса
награждает зверей, бежавших по кругу, чтобы согреться, цукатами.
– А кто же их будет раздавать? – спросили все хором.
– Она, конечно, – ответил Додо, ткнув пальцем в Алису.
Все окружили Алису и наперебой закричали:
– Награды! Награды! Раздавай награды!
Алиса растерялась. В замешательстве она сунула руку в карман – и вытащила оттуда пакетик цукатов.
Пусть N – количество участников, M – количество наград. Если остаток от деления M на N равен нулю (M mod N = 0), то наград всем достанется поровну (частное от деления M на N, то есть M div N). Пусть M mod N = r и не равно нулю. Тогда все участники получат M div N цукатов и еще r участников получат по одному цукату, то есть M div N + 1. А у N - r участников так и останется M div N цукатов.
B. Сумма единиц
На уроке английского в одной известной школе республики проходят числительные. Учительница спрашивает "What's one and one and one and one and one and one and one and one and one and one?" "I don't know,"отвечает Peter (Петя). "I lost count." (Я не знаю, я сбился со счета).
Вычислить сумму, названную учительницей.
Ввод
Последовательность из чередующихся слов one и and, разделенных одним пробелом, складывающихся в предложение для счета. Последовательность заканчивается точкой. Гарантируется правильный порядок слов.
Вывод
Число – сумма единиц.
РазборВычислить сумму, названную учительницей.
Ввод
Последовательность из чередующихся слов one и and, разделенных одним пробелом, складывающихся в предложение для счета. Последовательность заканчивается точкой. Гарантируется правильный порядок слов.
Вывод
Число – сумма единиц.
Последовательность символов, алгоритм суммирования, строки,
техника.Эта задача тоже из “Алисы в стране чудес”. Тот эпизод, где Алису
обвинили в неумении считать.
"Can you do addition?" the White Queen asked. "What's one and one and one and one and one and one and one and one and one and one?" "I don't know,"said Alice. "I lost count."
Очевидно сумма равна количеству слов one в предложении для счета. А количество слов one равно количеству символов ‘o’. Символ ‘n’ использовать нельзя, он встречается еще и в слове and. Осталось организовать чтение символов до точки с подсчетом количества буквы ‘o’.
C. Только целые
Ученик 8 класса одной известной школы республики Петя любит считать. Но не ворон за окном, а точки на листке тетради в клеточку. Он соединяет прямой линией две точки (пересечение линий) и считает, сколько точек лежит точно на прямой. Нарисовав достаточно много отрезков прямых, Петя догадывается, что можно предсказать количество точек с целочисленными координатами, и предлагает такую задачу.
На листке тетради в клеточку вводится обычная декартовая система координат с делением в одну клетку по оси x и по оси y. Концы отрезка задаются парой целых чисел - координатами. Надо определить, сколько всего точек с целочисленными координатами принадлежат отрезку по заданным координатам концов отрезка.
Ввод
Вводятся четыре целых числа – координаты концов отрезка (x1, y1) и (x2, y2).
Вывод
Выводится количество точек отрезка, имеющих целочисленные координаты.
Разбор
Алгоритм Евклида, геометрия
Задача имеет математическое содержание, требует “догадки”, но и дает подсказку. Если нарисовать достаточно много отрезков, можно заметить, что если отрезок вертикальный или горизонтальный, то для получения ответа необходимо вычесть координаты концов и добавить единицу. Интерес представляет случай, когда отрезок не является вертикальным или горизонтальным. В этом случае можно заметить, что если рассматривать отрезок как гипотенузу прямоугольного треугольника, то ответом будет число, равное наибольшему общему делителю длин катетов этого треугольника плюс единица. Доказывать этот факт от участника не требуется.
Сложность задачи оценивалась составителями как средняя.
Алгоритм Евклида
function gcd(a, b: integer): integer;
begin
while (a <> 0) and (b <> 0) do
if a > b then a := a mod b
else b := b mod a;
gcd := a + b
end;
D. Учет и контроль
Каждый уважающий себя склад ведет список имеющихся в наличии товаров и имеет список обязательного ассортимента. Регулярно происходит сравнение этих списков. Будем считать, что списки состоят из натуральных чисел - кодов товаров. Ваша задача - написать программу, которая сравнит
два списка и напечатает в порядке неубывания коды тех товаров, которые есть в обязательном ассортиментном списке, но которых нет в наличии.
Разбор
Циклы, массивы, сортировка, подсчет
Можно реализовать прямой подход. Отсортировать каждый массив и осуществить прямое сравнение, как в алгоритме слияния двух отсортированных массивов. Неэффективно и трудно технически. Но при имеющихся ограничениях работает.
Эффективное решение - подсчитать, сколько раз каждое число (числа по условию в диапазоне от 1 до 10) встречается в каждой из двух последовательностей. Для этого завести два массива, каждый из 10 элементов, и использовать элементы этих массивов как счетчики. Потом сравнить счетчики. Если во втором массиве нет элементов, которые учтены
в первом массиве, то их надо выводить.
E. Дружба-2
https://ipc.susu.ru/27440.html Эта задача, как и почти все задачи,
рассматриваемые далее, взята из муниципального этапа ВСОШ по информатике
2013 в г. Челябинске.На даче у семьи Пети печное отопление. Привезли дрова, уже распиленные на бревна, имеющие разную длину, и они не помещаются в печке. Придется Пете с отцом пилить. Разница длин чурбаков не должна превосходить некоторую величину L. Петя с отцом могут распилить бревно на любое количество чурбаков любой длины. Длину измеряют в пядях. Необязательно, чтобы длины всех чурбаков составляли целое число пядей и были одинаковы. Но после распила ничего не выбрасывается, все пойдет в топку. Так как использоваться будет ручная пила “Дружба-2”, хотелось бы минимизировать количество распилов.Напишите программу, которая подсчитает минимальное количество распилов для заданного набора бревен, при котором разница в длине между самым длинным и самым коротким чурбаком не будет превышать L.Разбор
Тема: математика, структуры данных (10-11 класс) или сортировка (7-9 класс и
частичное решение 10-11 класс). Сложность: средняяМинимальное количество распилов для доски получится, если доска будет распилена на части равной длины. Будем поддерживаем упорядоченный по длине частей список номеров досок и количества частей из этой доски. Пока разница между минимальной и максимальной длиной превышает D, мы должны увеличивать количество частей у доски, части которой имеют наибольшую длину. После изменения длины частей, доску перемещаем в упорядоченном списке.
Процесс гарантированно завершится, хотя бы когда длина всех частей станет меньше D. Для
распиливания досок на части меньше D, потребуется не более N*100000/D распилов.
Для ускорения работы программы для больших N можно использовать специальную структуру данных (кучу, мультисет). Общее время работы O(N*100000/D*log N). При этом для 7-9 классов для полного решения достаточно использовать квадратичную сортировку, а для 10-11 - нужна структура данных c возможностью извлечения максимального элемента за O(logN) (куча для максимума).
9-11 классы
A. Сказочная задача
B. Криминальная задача
C. Мечтательная задача
D. Forсчетная задача
E. Распилочная задача
A. Сказочная задача
Сложность задачи оценивалась составителями как средняя.
Алгоритм Евклида
function gcd(a, b: integer): integer;
begin
while (a <> 0) and (b <> 0) do
if a > b then a := a mod b
else b := b mod a;
gcd := a + b
end;
D. Учет и контроль
Каждый уважающий себя склад ведет список имеющихся в наличии товаров и имеет список обязательного ассортимента. Регулярно происходит сравнение этих списков. Будем считать, что списки состоят из натуральных чисел - кодов товаров. Ваша задача - написать программу, которая сравнит
два списка и напечатает в порядке неубывания коды тех товаров, которые есть в обязательном ассортиментном списке, но которых нет в наличии.
Разбор
Циклы, массивы, сортировка, подсчет
Можно реализовать прямой подход. Отсортировать каждый массив и осуществить прямое сравнение, как в алгоритме слияния двух отсортированных массивов. Неэффективно и трудно технически. Но при имеющихся ограничениях работает.
Эффективное решение - подсчитать, сколько раз каждое число (числа по условию в диапазоне от 1 до 10) встречается в каждой из двух последовательностей. Для этого завести два массива, каждый из 10 элементов, и использовать элементы этих массивов как счетчики. Потом сравнить счетчики. Если во втором массиве нет элементов, которые учтены
в первом массиве, то их надо выводить.
E. Дружба-2
https://ipc.susu.ru/27440.html Эта задача, как и почти все задачи,
рассматриваемые далее, взята из муниципального этапа ВСОШ по информатике
2013 в г. Челябинске.На даче у семьи Пети печное отопление. Привезли дрова, уже распиленные на бревна, имеющие разную длину, и они не помещаются в печке. Придется Пете с отцом пилить. Разница длин чурбаков не должна превосходить некоторую величину L. Петя с отцом могут распилить бревно на любое количество чурбаков любой длины. Длину измеряют в пядях. Необязательно, чтобы длины всех чурбаков составляли целое число пядей и были одинаковы. Но после распила ничего не выбрасывается, все пойдет в топку. Так как использоваться будет ручная пила “Дружба-2”, хотелось бы минимизировать количество распилов.Напишите программу, которая подсчитает минимальное количество распилов для заданного набора бревен, при котором разница в длине между самым длинным и самым коротким чурбаком не будет превышать L.Разбор
Тема: математика, структуры данных (10-11 класс) или сортировка (7-9 класс и
частичное решение 10-11 класс). Сложность: средняяМинимальное количество распилов для доски получится, если доска будет распилена на части равной длины. Будем поддерживаем упорядоченный по длине частей список номеров досок и количества частей из этой доски. Пока разница между минимальной и максимальной длиной превышает D, мы должны увеличивать количество частей у доски, части которой имеют наибольшую длину. После изменения длины частей, доску перемещаем в упорядоченном списке.
Процесс гарантированно завершится, хотя бы когда длина всех частей станет меньше D. Для
распиливания досок на части меньше D, потребуется не более N*100000/D распилов.
Для ускорения работы программы для больших N можно использовать специальную структуру данных (кучу, мультисет). Общее время работы O(N*100000/D*log N). При этом для 7-9 классов для полного решения достаточно использовать квадратичную сортировку, а для 10-11 - нужна структура данных c возможностью извлечения максимального элемента за O(logN) (куча для максимума).
9-11 классы
A. Сказочная задача
B. Криминальная задача
C. Мечтательная задача
D. Forсчетная задача
E. Распилочная задача
A. Сказочная задача
Вышел ворса из глухой тайги на трассу Сыктывкар - Воркута как раз возле дорожного знака. На знаке том написано: “До Ухты - X км, до Печоры - Y км, до Сыктывкара - ???“. Не может ворса разобрать, сколько до Сыктывкара, сердится, грозит. Успокойте ворсу, напишите программу и посчитайте расстояние от знака до Сыктывкара.
Ввод
В первой строке содержатся четыре целых числа, разделенные пробелами — расстояние от села Ухты до Сыктывкара A, расстояние от реки Печоры до Сыктывкара B (1 ≤ A < B ≤ 1114), расстояние от знака до Ухты X и расстояние от знака до реки Печоры Y (1 ≤ X, Y ≤ 1114). Гарантируется, что числа A, B, X, Y соответствуют какому-то возможному расположению знака на трассе.
Вывод
Вывести одно целое число — расстояние от дорожного знака, у которого вышел на трассу ворса, до Сыктывкара.
Разбор
Темы: условный оператор, геометрия. Сложность: простаяВвод
В первой строке содержатся четыре целых числа, разделенные пробелами — расстояние от села Ухты до Сыктывкара A, расстояние от реки Печоры до Сыктывкара B (1 ≤ A < B ≤ 1114), расстояние от знака до Ухты X и расстояние от знака до реки Печоры Y (1 ≤ X, Y ≤ 1114). Гарантируется, что числа A, B, X, Y соответствуют какому-то возможному расположению знака на трассе.
Вывод
Вывести одно целое число — расстояние от дорожного знака, у которого вышел на трассу ворса, до Сыктывкара.
Разбор
Возможны три случая:1) знак находится между Сыктывкаром и Ухтой (в этом случае B-A=Y-X, расстояние до Сыктывкара равно A-X); 2) знак находится между Ухтой и Печорой (в этом случае B-A=X+Y, расстояние до Сыктывкара равно A+X); 3) знак находится между Печорой и Воркутой (в этом случае B-A=X-Y, расстояние до Сыктывкара равно A+X).Пример реализации:var a,b,x,y:integer; begin read(a,b,x,y); if (b-a=x+y) or (b-a=x-y) then writeln(a+x) else writeln(a-x); end.B. Криминальная задача
Словарь Эллочки-людоедки составлял лишь 30 слов, но ими она могла выразить практически любую свою мысль. В словаре некоторых наших современников слов еще меньше. Рассказывают об одной группе ребят, которые, общаясь в Telegram, используют всего 6 слов — in, input, out, output, one, puton. Пишут они в одну строчку и без пробелов. Сотрудник службы безопасности наткнулся на переписку, очень напоминающую письмена
известной СБ группы. Необходимо понять, может ли это быть письменами группы, или же это чья-то шифровка, не имеющая к ней никакого отношения.
Разбор
Темы: рекурсия, конечные автоматы
Сложность: средняя.У нас есть словарь, состоящий из слов - in, input, out, output, one, puton. Нужно проверить, принадлежит ли он языку. Это задача с портала Timus Online Judge. Там она называется "странный диалог". Первое, что приходит в голову - смотреть в начало строки, если подстрока совпадает с любым элементом словаря - удаляем ее. Если мы смогли удалить все ‑ значит перед нами язык, если нет – значит, нет.Но тут возникает проблема, существуют коллизии. Например, нам дана строка "inputon". Если мы сначала удалим "input", то у нас останется "on", остаток мы удалить не сможем - выведем NO, но ведь in + puton вполне себе язык, а значит, мы должны вывести YES. Можно рассмотреть все варианты, запустить рекурсию, которая будет удалять "in" и рекурсивно рассматривать "puton" и удалять "input" и рассматривать "puton". Если хоть какая-то процедура придет к пустой строке - выводить YES, иначе - NO. И такое решение проходило на предложенных ограничениях.Но проще всего было смотреть диалог с конца, то есть, перевернуть все строки в условии и вводе задачи. В таком случае мы получаем набор ni, tupno, tuo, tuptuo, eno, notup, который НЕ СОДЕРЖИТ коллизий, и мы можем линейно удалять из перевернутого ввода, например "notupni" все подходящие варианты префиксов не задумываясь.Замечание. Префикс - подстрока строки, начинающаяся с ее первого символа. Префиксы abcde ‑ a, ab, abc, abcd, abcde.
Помечтаем? Великая тайга, бескрайняя тундра, старые горы… Для организации доступа к любой точке на территории Коми установлены стоянки с летающими такси (летками). Туристы, работники лесных хозяйств, нефтяники, просто местные жители в любой момент могут вызвать такси. Запрос всегда придет на ближайшую стоянку, а при равенстве расстояний — на стоянку с меньшим номером.Напишите программу, которая определит по координатам стоянок такси и клиентов, сколько
запросов пришло на каждую стоянку.Первая строка ввода содержит одно целое число N (2 ≤ N ≤ 10) – количество стоянок. Далее
следует N строк, содержащих по два целых чисел в диапазоне от 0 до 1000 — координаты стоянок.
Следующая строка ввода содержит одно целое число M (1 ≤ M ≤ 1000) – количество клиентов. Далее следует M строк, содержащих по два целых чисел в диапазоне от 0 до 1000 — координаты клиентов.
Вывести N строк, содержащих по одному целому числу. i-я строка содержит количество клиентов, выбравших i-ю стоянку такси.
Разбор
Тема: поиск минимума, сортировка подсчетом, циклы.
Сложность: простая
Пример реализации. Далее bx, by - координаты стоянок.for i:=1 to m do begin read(ax,ay); minr:=1000000000; minb:=0; for j:=1 to n do begin r:=sqr(ax-bx[j])+sqr(ay-by[j]); if r
D. Forсчетная задача
Чтобы узнать, насколько долго работает программа, необходимо рассмотреть имеющиеся в ней операторы цикла и число их повторений. Для вложенных операторов цикла число повторений перемножается, а для последовательных -- складывается.Напишите программу, вычисляющую общее число повторений для заданнойпоследовательности операторов for.
В первой строке ввода содержится одно целое число N (1 ≤ N ≤ 10) — число операторов for в программе. Далееследует 2⋅ N строк, содержащих информацию о циклах в исследуемой программе. Каждая строка содержит либостроку вида "for x", где x – целое число в диапазоне от 2 до 1000,- число повторений, либо строку "end",обозначающую конец цикла. Гарантируется, что каждый for будет иметь соответствующий ему end и наоборот.Вывести в первой строке одно целое число — общее число повторений для анализируемой программы.Гарантируется, что результат не будет превышать 10^18.
Разбор
Тема: использование стека или рекурсия. Сложность: ниже среднего
t:=0;readln(n);for i:=1 to 2*n do begin readln(s); if copy(s,1,3) = 'for' then begin inc(t); st[t]:=StrToInt(Copy(s,5,Length(s)-4)); { для накопления произведения } inc(t); st[t]:=0; { для накопления суммы } end else {end} begin if st[t]=0 then st[t]:=1; st[t-1]:=st[t-1]*st[t]; dec(t); st[t-1]:=st[t-1]+st[t]; dec(t); end; end;writeln(st[0]);
E. Распилочная задача
https://ipc.susu.ru/27440.html
● То же самое, что Дружба-2.
Но! Есть отличие в размере входных данных:
Для 7-8 классов
● количество бревен N (2 ⩽ N ⩽ 10)
Для 9-11 классов
● количество бревен N (2 ⩽ N ⩽ 1000)
Комментариев нет:
Отправить комментарий