I Этап Всероссийской олимпиады школьников по информатике 2010-11 учебный год. Разбор задач.
День 1.
1.1. Решить неравенство 1
Для успешного решения задачи нужно прежде всего корректно определить самое левое целое число L и самое правое целое число R, удовлетворяющие неравенству. Если они известны и L ≤ R, то количество целых решений, удовлетворяющих исходному неравенству, будет равно: R − L + 1. В противном случае количество решений равно нулю.
При отыскания граничных значений возможны различные подходы. Один из них – воспользоваться формулами: L = ⌊ (A − C) / B ⌋ + 1, R = ⌈ (D − C) / B ⌉ − 1, где ⌊ ⌋ обозначает округление вниз, а ⌈ ⌉ – округление вверх. Например, ⌊ 5.5 ⌋ = 5, ⌊ −5.5 ⌋ = −6; ⌈ 5.5 ⌉ = 6, ⌈ −5.5 ⌉ = −5.
Важным условием полного решения задачи является правильный выбор используемых типов данных. Из формата входных данных следует, что нужно использовать тип данных int64, а вещественным типам данных не хватает точности.
1.2. Зарплата
Зарплата Васи есть ни что иное, как арифметическая прогрессия с первым членом A и шагом B. В задаче требуется найти сумму N первых членов арифметической прогрессии. Поскольку членов очень много, то очевидно, что суммирование в цикле не пройдет по времени для максимальных N. Поэтому необходимо воспользоваться формулой для нахождения суммы N первых членов арифметической прогрессии: SN = (2A + (N − 1) B) N / 2.
Очевидно, что при использовании формулы будет получено большое число, для вычисления которого нужно использовать тип данных int64.
1.3. Зверь-машина
Первым делом необходимо найти среднее арифметическое всех чисел. Далее в цикле проверить каждое из чисел, не забыв, что числа, совпадающие со средним арифметическим, заменять не надо.
Для того, чтобы избежать сравнения целого числа с вещественным, можно хранить сумму всех элементов и их количество. Тогда критерий сравнения можно представить в виде N Ai < sum.
Очевидно, что при подсчете суммы будет получено число, для хранения которого нужно использовать тип данных int64.
1.4. Статистика текста
Решение задачи подразумевает правильное понимание условия задачи и аккуратную программную реализацию. Важным для полного решения задачи является:
1. умение считать строку, содержащую пробелы;
2. понимание того факта, что пробел не является знаком препинания;
3. правильная формулировка правила выделения слова (например, “если текущий символ буква, а следующий за ним не буква или текущий символ буква и последний в строке, то мы нашли слово“).
День 2.
2.1. Решить неравенство 2
Для успешного решения задачи нужно прежде всего корректно определить самое левое целое число L и самое правое целое число R, удовлетворяющие неравенству. Если они известны и L ≤ R, то количество целых решений, удовлетворяющих исходному неравенству, будет равно: R − L + 1. В противном случае количество решений равно нулю.
При отыскания граничных значений возможны различные подходы. Один из них – воспользоваться формулами: L = ⌈ (A − C) / B ⌉, R = ⌈ (D − C) / B ⌉ − 1, где ⌈ ⌉ обозначает округление вверх. Например, ⌈ 5.5 ⌉ = 6, ⌈ −5.5 ⌉ = −5.
Важным условием полного решения задачи является правильный выбор используемых типов данных. Из формата входных данных следует, что нужно использовать тип данных int64, а вещественным типам данных не хватает точности.
2.2. Карты
В задаче требуется найти количество различных перестановок в наборе из N различных элементов. Для этого нужно вычислить факториал числа N по формуле: N! = 1 × 2 × … × (N − 1) × N.
При вычислении нужно аккуратно выбрать тип данных переменных, так как при умножении может быть получено большое число.
2.3. Уличная магия
Необходимо считать число во входном файле и подсчитать сумму цифр. Для этого можно считать число как строку, а затем перевести каждый символ в цифру и сложить. Нельзя забывать, что строка может содержать до 1 000 000 символов.
2.4. Ох уж эти ученые...
Решение задачи подразумевает правильное понимание условия задачи и аккуратную программную реализацию. Важным для полного решения задачи является:
1. умение считать строку, содержащую пробелы;
2. понимание того факта, что одиночный пробел или звездочка замене не подлежат;
3. умение выделить группу подряд идущих одинаковых символов с подсчетом их количества.
День 3.
3.1. Решить неравенство 3
Для успешного решения задачи нужно прежде всего корректно определить самое левое целое число L и самое правое целое число R, удовлетворяющие неравенству. Если они известны и L ≤ R, то количество целых решений, удовлетворяющих исходному неравенству, будет равно: R − L + 1. В противном случае количество решений равно нулю.
При отыскания граничных значений возможны различные подходы. Один из них – воспользоваться формулами: L = ⌊ (A − C) / B ⌋ + 1, R = ⌊ (D − C) / B ⌋, где ⌊ ⌋ обозначает округление вниз. Например, ⌊ 5.5 ⌋ = 5, ⌊ −5.5 ⌋ = −6.
Важным условием полного решения задачи является правильный выбор используемых типов данных. Из формата входных данных следует, что нужно использовать тип данных int64, а вещественным типам данных не хватает точности.
3.2. Сувениры
В задаче нужно найти, сколько есть различных способов выбрать два элемента из N. Количество способов определяется числом сочетаний, формула для которого после упрощения примет вид: N (N − 1) / 2.
При вычислении необходимо учесть тот факт, что при умножении может получиться большое число, а так же не нарушать порядок вычислений.
3.3. Дележка
В задаче нужно сделать то, что написано. Отдельно нужно рассмотреть случай, когда все купюры одинакового номинала.
3.4. Секретный отдел
Решение задачи подразумевает правильное понимание условия задачи и аккуратную программную реализацию. Важным для полного решения задачи является:
1. умение считать строку, содержащую пробелы;
2. понимание понятия “полезная часть шифровки”;
3. умение выделить слово в тексте.
День 4.
4.1. Решить неравенство 4
Для успешного решения задачи нужно прежде всего корректно определить самое левое целое число L и самое правое целое число R, удовлетворяющие неравенству. Если они известны и L ≤ R, то количество целых решений, удовлетворяющих исходному неравенству, будет равно: R − L + 1. В противном случае количество решений равно нулю.
При отыскания граничных значений возможны различные подходы. Один из них – воспользоваться формулами: L = ⌈ (A - C) / B ⌉, R = ⌊ (D - C) / B ⌋, где ⌊ ⌋ обозначает округление вниз, а ⌈ ⌉ – округление вверх. Например, ⌊ 5.5 ⌋ = 5, ⌊ -5.5 ⌋ = -6; ⌈ 5.5 ⌉ = 6, ⌈ -5.5 ⌉ = -5.
Важным условием полного решения задачи является правильный выбор используемых типов данных. Из формата входных данных следует, что нужно использовать тип данных int64, а вещественным типам данных не хватает точности.
4.2. Необычная зарплата
В этой задаче нужно всего лишь сделать то, что написано: по описанному алгоритму вычислить зарплату Васи в N-ом месяце.
Последовательность зарплат представляет собой ни что иное, как числа Фибоначчи, которые с увеличением N очень быстро растут. Поэтому при вычислении нужно использовать тип данных int64.
4.3. Обманщик
Для начала нужно отсортировать номиналы купюр эффективным алгоритмом (пузырек не укладывается по времени). Ответом на задачу будет элемент отсортированного массива с индексом ⌊ (N - 1) / 2 ⌋, если считать, что нумерация в массиве идет с нуля.
4.4. Палиндромы
Решение задачи подразумевает правильное понимание условия задачи и аккуратную программную реализацию. Важным для полного решения задачи является:
1. умение считать строку, содержащую пробелы;
2. понимание понятия “палиндром”;
3. умение выделить слово в тексте;
4. умение программно проверить, является ли последовательность символов палиндромом.