олимпиада УПИ...[школьная]
Здравствуйте!
Дело в том, что мне завтра нужно сдать задания упийской олимпиады по информатике для зачисления в их компьютерную школу, но в силу ряда обстоятельств сделал толко несколько....
Помогите, пожалуста, решить следующие задания исходными кодами паскаля(быть может кто
-то такие уже решал...), прошу писать название задачи.
1)Палиндромы
Входной файл input.txt
Выходной файл output.txt
Известно, что палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Например, палиндромами являются строки «A», «ABA», «ABBA», а строки «AB», «AAB», «ABAB» палиндромами не являются.
Рассмотрим некоторую строку S, состоящую только из латинских букв A и B. Назовем запрещенными все строки длины n, которые состоят также только из букв A и B и содержат S в качестве подстроки. Например, если S = «AB» и n =3, то существует четыре запрещенных строки— «AAB», «ABA», «ABB» и «BAB». Остальные строки будет называть допустимыми.
Требуется написать программу, которая для заданной строки S длиной не более пяти символов и заданного числа n определяет количество допустимых строк длины n, которые являются палиндромами.
Ввод
Первая строка входного файла содержит строку S. Длина строки S не превосходит пяти. Вторая строка содержит число n (1 ≤ n ≤ 100).
Вывод
Выведите в выходной файл одно число — количество строк длины n, которые являются палиндромами и не содержат S в качестве подстрок.
пример:
ввод:
AB
3
выход:
2
----
2)Лестница
Входной файл: input.txt
Выходной файл: output.txt
Археологи раскопали Древний Храм, ко входу в который ведет лестница, шириной в 1 (один) метр, из М ступенек различной длины и высоты. Лестница построена из каменных блоков 1×1×1 метр. Археологи хотят для удобства туристов, чтобы лестница состояла из меньшего количества ступенек N. Для этого они могут также устанавливать каменные блоки 1×1×1.
Какое минимальное количество блоков необходимо, чтобы сделать лестницу в N ступенек, если известны начальная длина и высота каждой ступеньки. Высоты и длины ступенек новой лестницы могут различаться.
Ввод
В первой строке через пробел заданы два целых числа M и N (1 ≤ N < M ≤ 100). Далее идут M строк, содержащих пару целых чисел Li и Hi – длина и высота i-ой ступеньки соответственно (1 ≤ Li, Hi ≤ 101). Ступеньки нумеруются снизу вверх.
Вывод
В выходной файл выведите единственное число – ответ на задачу.
пример ввода и вывода:
http://bos.pp.ru/upi/3.gif (4.5 Kb)
---------
3)Симметричная последовательность
Входной файл: b.in
Выходной файл: b.out
Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:
1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1
Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество, и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.
Ввод
Во входном файле записано сначала число N — количество элементов исходной последовательности. Далее записано N чисел — элементы этой последовательности. 1≤N≤100, элементы последовательности — натуральные числа от 1 до 9.
Вывод
В выходной файл выведите сначала число M — минимальное количество элементов, которое надо дописать к последовательности, а потом M чисел (каждое — от 1 до 9) — числа, которые надо дописать к последовательности.
пример ввода и вывода:
http://bos.pp.ru/upi/4.gif (2.5 Kb)
------------
Бракованная ханойская башня
Входной файл: input.txt
Выходной файл: output.txt
Васе на день рождения друзья подарили набор для игры «Ханойская башня». Набор состоит из трех стержней (A, B и C). На стержень A нанизаны по порядку N дисков
диаметра 1,2,3,…,N так, что диск диаметра 1 находится вверху. Требуется переместить эту башню на стержень C, при этом за один ход разрешается переложить диск с одного стержня на другой. И диск меньшего диаметра нельзя класть на диск большего диаметра.
Вот только по роковой случайности диск диаметра K оказался бракованным - его нельзя положить на стержень B. Но это нисколько не огорчило Васю, а наоборот, он даже был в восторге! Помогите ему подсчитать, за какое наименьшее количество перекладываний можно переместить башню со стержня A на стержень C.
Ввод
Во входном файле даны два целых числа N – количество дисков (1 . N . 1000) и K - диаметр бракованного диска (1 . К . N).
Вывод
Выходной файл должен содержать единственное число – ответ на задачу, либо фразу «Impossible», если диски переместить невозможно.
пример:
ввод:
2 1
вывод
5
------------
Найди прямую
Входной файл: input.txt
Выходной файл: output.txt
На плоскости дано множество отрезков. Требуется найти прямую, которая пересекла бы наибольшее возможное количество из данных отрезков и при этом проходила бы как минимум через две точки с целочисленными координатами.
Считается, что прямая пересекает отрезок, если она имеет с ним хотя бы одну общую точку (т.е. она может проходить через конец отрезка, внутреннюю точку отрезка, либо содержать весь отрезок).
Ввод
Во входном файле записано сначала число N — количество отрезков (1≤N≤1000). Далее идет N четверок чисел Xi1, Yi1, Xi2, Yi2 задающих координаты концов отрезков. Все эти числа целые, по модулю не превосходящие 10000.
Заданные отрезки могут пересекаться, иметь общие части, один из них может полностью содержаться внутри другого. Отрезки имеют ненулевую длину.
Вывод
В выходной файл выведите координаты каких-нибудь двух точек, через которые проходит прямая, пересекающая наибольшее количество отрезков. Координаты точек должны быть целыми
и не должны по
модулю превышать 10^7.
пример:
http://bos.pp.ru/upi/7.gif (3.8)
-----
Представление чисел
Входной файл: c.in
Выходной файл: c.out
Дано натуральное число N. Требуется представить его в виде суммы двух натуральных чисел A и B таких, что НОД (наибольший общий делитель) чисел A и B — максимален.
Ввод
Во входном файле записано натуральное число N (2≤N≤109).
Вывод
В выходной файл выведите два искомых числа A и B. Если решений несколько, выведите любое из них.
example:
вход: 15
вывод: 5 10
Дело в том, что мне завтра нужно сдать задания упийской олимпиады по информатике для зачисления в их компьютерную школу, но в силу ряда обстоятельств сделал толко несколько....
Помогите, пожалуста, решить следующие задания исходными кодами паскаля(быть может кто
-то такие уже решал...), прошу писать название задачи.
1)Палиндромы
Входной файл input.txt
Выходной файл output.txt
Известно, что палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Например, палиндромами являются строки «A», «ABA», «ABBA», а строки «AB», «AAB», «ABAB» палиндромами не являются.
Рассмотрим некоторую строку S, состоящую только из латинских букв A и B. Назовем запрещенными все строки длины n, которые состоят также только из букв A и B и содержат S в качестве подстроки. Например, если S = «AB» и n =3, то существует четыре запрещенных строки— «AAB», «ABA», «ABB» и «BAB». Остальные строки будет называть допустимыми.
Требуется написать программу, которая для заданной строки S длиной не более пяти символов и заданного числа n определяет количество допустимых строк длины n, которые являются палиндромами.
Ввод
Первая строка входного файла содержит строку S. Длина строки S не превосходит пяти. Вторая строка содержит число n (1 ≤ n ≤ 100).
Вывод
Выведите в выходной файл одно число — количество строк длины n, которые являются палиндромами и не содержат S в качестве подстрок.
пример:
ввод:
AB
3
выход:
2
----
2)Лестница
Входной файл: input.txt
Выходной файл: output.txt
Археологи раскопали Древний Храм, ко входу в который ведет лестница, шириной в 1 (один) метр, из М ступенек различной длины и высоты. Лестница построена из каменных блоков 1×1×1 метр. Археологи хотят для удобства туристов, чтобы лестница состояла из меньшего количества ступенек N. Для этого они могут также устанавливать каменные блоки 1×1×1.
Какое минимальное количество блоков необходимо, чтобы сделать лестницу в N ступенек, если известны начальная длина и высота каждой ступеньки. Высоты и длины ступенек новой лестницы могут различаться.
Ввод
В первой строке через пробел заданы два целых числа M и N (1 ≤ N < M ≤ 100). Далее идут M строк, содержащих пару целых чисел Li и Hi – длина и высота i-ой ступеньки соответственно (1 ≤ Li, Hi ≤ 101). Ступеньки нумеруются снизу вверх.
Вывод
В выходной файл выведите единственное число – ответ на задачу.
пример ввода и вывода:
http://bos.pp.ru/upi/3.gif (4.5 Kb)
---------
3)Симметричная последовательность
Входной файл: b.in
Выходной файл: b.out
Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:
1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1
Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество, и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.
Ввод
Во входном файле записано сначала число N — количество элементов исходной последовательности. Далее записано N чисел — элементы этой последовательности. 1≤N≤100, элементы последовательности — натуральные числа от 1 до 9.
Вывод
В выходной файл выведите сначала число M — минимальное количество элементов, которое надо дописать к последовательности, а потом M чисел (каждое — от 1 до 9) — числа, которые надо дописать к последовательности.
пример ввода и вывода:
http://bos.pp.ru/upi/4.gif (2.5 Kb)
------------
Бракованная ханойская башня
Входной файл: input.txt
Выходной файл: output.txt
Васе на день рождения друзья подарили набор для игры «Ханойская башня». Набор состоит из трех стержней (A, B и C). На стержень A нанизаны по порядку N дисков
диаметра 1,2,3,…,N так, что диск диаметра 1 находится вверху. Требуется переместить эту башню на стержень C, при этом за один ход разрешается переложить диск с одного стержня на другой. И диск меньшего диаметра нельзя класть на диск большего диаметра.
Вот только по роковой случайности диск диаметра K оказался бракованным - его нельзя положить на стержень B. Но это нисколько не огорчило Васю, а наоборот, он даже был в восторге! Помогите ему подсчитать, за какое наименьшее количество перекладываний можно переместить башню со стержня A на стержень C.
Ввод
Во входном файле даны два целых числа N – количество дисков (1 . N . 1000) и K - диаметр бракованного диска (1 . К . N).
Вывод
Выходной файл должен содержать единственное число – ответ на задачу, либо фразу «Impossible», если диски переместить невозможно.
пример:
ввод:
2 1
вывод
5
------------
Найди прямую
Входной файл: input.txt
Выходной файл: output.txt
На плоскости дано множество отрезков. Требуется найти прямую, которая пересекла бы наибольшее возможное количество из данных отрезков и при этом проходила бы как минимум через две точки с целочисленными координатами.
Считается, что прямая пересекает отрезок, если она имеет с ним хотя бы одну общую точку (т.е. она может проходить через конец отрезка, внутреннюю точку отрезка, либо содержать весь отрезок).
Ввод
Во входном файле записано сначала число N — количество отрезков (1≤N≤1000). Далее идет N четверок чисел Xi1, Yi1, Xi2, Yi2 задающих координаты концов отрезков. Все эти числа целые, по модулю не превосходящие 10000.
Заданные отрезки могут пересекаться, иметь общие части, один из них может полностью содержаться внутри другого. Отрезки имеют ненулевую длину.
Вывод
В выходной файл выведите координаты каких-нибудь двух точек, через которые проходит прямая, пересекающая наибольшее количество отрезков. Координаты точек должны быть целыми
и не должны по
модулю превышать 10^7.
пример:
http://bos.pp.ru/upi/7.gif (3.8)
-----
Представление чисел
Входной файл: c.in
Выходной файл: c.out
Дано натуральное число N. Требуется представить его в виде суммы двух натуральных чисел A и B таких, что НОД (наибольший общий делитель) чисел A и B — максимален.
Ввод
Во входном файле записано натуральное число N (2≤N≤109).
Вывод
В выходной файл выведите два искомых числа A и B. Если решений несколько, выведите любое из них.
example:
вход: 15
вывод: 5 10
Помогу за 5 wmz за задачку ;)
