Начало
Соревнования
Задачи 1 лиги областной олимпиады школьников по информатике 2002
1. Числа Фибоначчи
Модулярная арифметикаОлимпиадные задачи на русском языке
| 09/01/2002 | Областная олимпиада школьников по информатике (2 лига) (1) |
| 09/01/2002 | Областная олимпиада школьников по информатике (1 лига) (1) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Последовательность чисел Фибоначчи определяется следующим образом: `F_0=0`, `F_1=1`,
`F_n\ =\ F_{n-1}\ +\ F_{n-2}` для `n>1`. Последовательность можно
определить и для отрицательных индексов `n`. Вот ближайшие к нулю
числа Фибоначчи:
| `n` | … | –6 | –5 | –4 | –3 | –2 | –1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | … |
| `F_n` | … | –8 | 5 | –3 | 2 | –1 | 1 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | … |
Во входном файле содержится три строки. В первой строке содержится
целое число `d` (`0\ ≤\ d\ ≤\ 9`). Во второй строке содержится целое
число `a`, а в третьей строке – целое число `b` (`-10^6\ ≤\ a\ ≤\ b\ ≤\ 10^6`).
В выходной файл вывести единственное целое число – количество чисел, оканчивающихся на
заданную цифру `d`, среди чисел Фибоначчи с индексами
в диапазоне от `a` до `b` включительно.
Пример ввода
1 -1 10
Пример вывода
4
2. Кроссворд
Рекурсивный переборОлимпиадные задачи на русском языке
| 09/01/2002 | Областная олимпиада школьников по информатике (1 лига) (2) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Кроссворд является сформированным правильно, если
- все слова в нем состоят не менее чем из 2 букв,
- если две буквы находятся в соседних клетках, то они являются частью какого-либо слова,
- слова, читаемые по горизонтали, начинаются только с клеток, у которых нет слева клетки с буквой, а слова, читаемые по вертикали, начинаются с клеток, у которых нет выше клетки с буквой.
Каждая буква в правильном кроссворде была заменена некоторым целым числом.
При этом каждой букве соответствует свое число, а каждому числу
соответствует одна буква. Известны все слова, использованные в кроссворде.
Требуется расставить слова в сетке кроссворда (восстановить кроссворд).
Во входном файле в первой строке содержатся два целых числа `n` и `m` (`1\ ≤\ n\ ≤\ 20`, `1\ ≤\ m\ ≤\ 20`) – размеры
кроссворда, далее следует `n` строк, содержащих по `m` целых чисел (от 0 до 26) в строке. Число 0 соответствует незаполненной (черной) клетке кроссворда.
Далее следуют все слова, используемые в кроссворде, по одному слову в каждой строке. Слова содержат только прописные латинские буквы. Длина всех слов кроссворда – от 2 до 20 символов.
В выходной файл вывести заполненный кроссворд.
Если возможно несколько вариантов заполнения, то нужно вывести любой (один) из них. Для обозначения незаполненных клеток используйте символ '.' (точка).
Пример ввода
3 4 7 1 2 5 0 4 0 14 14 5 8 0 ICE ET TEA FILE
Пример вывода
FILE .C.T TEA.
3. Дроби
Периодические последовательностиОлимпиадные задачи на русском языке
| 09/01/2002 | Областная олимпиада школьников по информатике (1 лига) (3) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Любое рациональное число может быть представлено в виде
периодической десятичной дроби: целая_часть , непериодическая_часть ( период ). Напишите программу для сложения двух периодических десятичных дробей.
Во входном файле содержатся две строки. В каждой строке содержится одна периодическая десятичная дробь в указанной выше форме, общее количество цифр в представлении дроби не превосходит 20.
В выходной файл вывести результат сложения также в виде периодической десятичной дроби.
Пример ввода
0,(3) 0,1(6)
Пример вывода
0,5(0)
4. Число соответствий
Поразрядная сортировка и сортировка подсчетомОлимпиадные задачи на русском языке
| 09/01/2002 | Областная олимпиада школьников по информатике (1 лига) (4) |
| 01/10/2010 | Занятие 4 (G) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Числом соответствий для двух строк `a` и `b` будем называть максимально
возможное количество пар `(a_i,\ b_j)`, образованных из `i`-го символа строки `a` и `j`-го символа строки `b`, таких, что `a_i=b_j`, и каждый символ из строк `a` или `b` входит не более чем в одну пару.
Числом точных соответствий для двух строк `a` и `b` будем называть максимально возможное количество пар `(a_i,\ b_j)`, таких, что `a_i=b_j` и `i=j`. Числом неточных соответствий для двух строк `a` и `b` будем называть разницу между числом соответствий и числом точных соответствий.
Во входном файле содержатся две строки одинаковой длины, состоящие только из прописных латинских букв. Длина строк не превосходит 10000 символов.
В выходной файл вывести два числа, по одному числу в строке – число точных и число неточных соответствий между строками.
Пример ввода
ABCBBE BADDBA
Пример вывода
1 2
5. Город-лабиринт
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 09/01/2002 | Областная олимпиада школьников по информатике (1 лига) (5) |
| 09/01/2002 | Областная олимпиада школьников по информатике (2 лига) (5) |
| 14/11/2007 | Занятие 10 (F) |
| 17/11/2012 | Занятие 10 (D) |
Ограничения: время – 500ms/1000ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В небольшом городе, имеющем квадратную форму, дорожные службы создали сложную сеть дорог и берут большие штрафы за нарушение правил движения. Путешественник хочет пересечь этот город, не нарушая правил движения. Для этого он купил на бензоколонке карту города и ввел ее в бортовой компьютер. Путешественник въезжает в город с запада по шоссе в северо-западный угол города и должен выехать по шоссе, ведущему на восток, из юго-восточного угла. Напишите программу, которая поможет путешественнику найти кратчайший путь в городе-лабиринте.
Во входном файле в первой строке содержится число `n` (`2\ ≤\ n\ ≤\ 20`) – размеры города. Далее следует `n` строк по n символов в каждой строке – информация о перекрестках. В городе существует всего три вида перекрестков. На перекрестке первого типа, обозначаемого во входном файле символом '+' (плюс), запрещены любые повороты, и необходимо продолжать движение в том же направлении. На перекрестке второго типа, обозначаемого символом '|' (вертикальная черта), при движении с запада на восток или с востока на запад нужно обязательно повернуть на север или на юг, а при движении с севера на юг или с юга на север – продолжить движение в том же направлении. На перекрестке третьего типа, обозначаемого символом '-' (минус), при движении с юга на север или с севера на юг нужно обязательно повернуть на запад или на восток, а при движении с востока на запад или с запада на восток – продолжить движение в том же направлении.
В выходной файл вывести кратчайший путь от первого перекрестка до выезда из города. Для каждого перекрестка, который встретится на пути путешественника, нужно указать направление дальнейшего движения – N (север), S (юг), W (запад) или E (восток). Если проехать через город без нарушения правил невозможно, то вывести сообщение "IMPOSSIBLE".
Пример ввода
3 -|+ |-| -++
Вывод для примера
ESWSEEE
