Подразделы

Другие разделы

Дата и время

24/02/2024 00:43:58

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printЗадачи 1 лиги областной олимпиады школьников по информатике 2002

print1. Числа Фибоначчи

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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 –10123456
`F_n` –8 5 –3 2 –1 10 112358
Во входном файле содержится три строки. В первой строке содержится целое число `d` (`0\ ≤\ d\ ≤\ 9`). Во второй строке содержится целое число `a`, а в третьей строке – целое число `b` (`-10^6\ ≤\ a\ ≤\ b\ ≤\ 10^6`).
В выходной файл вывести единственное целое число – количество чисел, оканчивающихся на заданную цифру `d`, среди чисел Фибоначчи с индексами в диапазоне от `a` до `b` включительно.

Пример ввода

1
-1
10

Пример вывода

4

print2. Кроссворд

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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.

print3. Дроби

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Любое рациональное число может быть представлено в виде периодической десятичной дроби: целая_часть , непериодическая_часть ( период ). Напишите программу для сложения двух периодических десятичных дробей.
Во входном файле содержатся две строки. В каждой строке содержится одна периодическая десятичная дробь в указанной выше форме, общее количество цифр в представлении дроби не превосходит 20.
В выходной файл вывести результат сложения также в виде периодической десятичной дроби.

Пример ввода

0,(3)
0,1(6)

Пример вывода

0,5(0)

print4. Число соответствий

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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

print5. Город-лабиринт

Ограничения: время – 500ms/1000ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В небольшом городе, имеющем квадратную форму, дорожные службы создали сложную сеть дорог и берут большие штрафы за нарушение правил движения. Путешественник хочет пересечь этот город, не нарушая правил движения. Для этого он купил на бензоколонке карту города и ввел ее в бортовой компьютер. Путешественник въезжает в город с запада по шоссе в северо-западный угол города и должен выехать по шоссе, ведущему на восток, из юго-восточного угла. Напишите программу, которая поможет путешественнику найти кратчайший путь в городе-лабиринте.
3488.gif
Во входном файле в первой строке содержится число `n` (`2\ ≤\ n\ ≤\ 20`) – размеры города. Далее следует `n` строк по n символов в каждой строке – информация о перекрестках. В городе существует всего три вида перекрестков. На перекрестке первого типа, обозначаемого во входном файле символом '+' (плюс), запрещены любые повороты, и необходимо продолжать движение в том же направлении. На перекрестке второго типа, обозначаемого символом '|' (вертикальная черта), при движении с запада на восток или с востока на запад нужно обязательно повернуть на север или на юг, а при движении с севера на юг или с юга на север – продолжить движение в том же направлении. На перекрестке третьего типа, обозначаемого символом '-' (минус), при движении с юга на север или с севера на юг нужно обязательно повернуть на запад или на восток, а при движении с востока на запад или с запада на восток – продолжить движение в том же направлении.
В выходной файл вывести кратчайший путь от первого перекрестка до выезда из города. Для каждого перекрестка, который встретится на пути путешественника, нужно указать направление дальнейшего движения – N (север), S (юг), W (запад) или E (восток). Если проехать через город без нарушения правил невозможно, то вывести сообщение "IMPOSSIBLE".

Пример ввода

3
-|+
|-|
-++

Вывод для примера

ESWSEEE
loading