Реализация программы рекордного образования гимназистов по информатике

Глава 4. Олимпиадные задачи, предлагаемые АСФ КемГУ.

Данные задачи размещены на сайте Анжеро-Судженского физиала Кемеровского Государственного университета.

1. Дан массив X(100) и Y(100). Записать алгоритм, меняющий последовательно местами значения элементов X(k) и Y(k) для этих таблиц, для k=1,2,...,100, не используя промежуточных величин.

2. Натуральное число N>1 представить в виде суммы натуральных чисел так, чтобы произведение этих слагаемых было максимально.

3. Сообщество роботов живет по следующим законам: один раз в начале года они объединяются в группы по 3 или 5 роботов; за год группа из 3 роботов собирает 5 новых, а группа из 5 роботов собирает 9 новых; роботы объединяются так, чтобы собрать за год наибольшее количество; каждый робот живет 3 года после сборки. Известно начальное количество роботов K и все они только что собраны. Сколько роботов будет через N лет?

4. Найти натуральные числа, не превосходящие заданного и делящиеся на каждую из своих цифр, отличных от нуля.

5. По кругу расположено N монет гербами вверх и M монет гербами вниз.Обходя круг по ходу часовой стрелки, переворачивают каждую S -тую монету. В первый раз счет начинается с герба. В каком порядке надо расставить монеты, чтобы после K ходов стало L монет, лежащих гербами вверх.

6. Имеется два массива X и Y. Массив X содержит пять элементов, расположенных по возрастанию, а массив Y содержит шесть различных элементов, расположенных по убыванию. Составить массив Z из элементов массивов X и Y упорядочивая их по возрастанию.

7. Найти все натуральные числа, не превосходящие заданного N и равные сумме кубов своих цифр.

8. N серых и M белых мышей сидят по кругу. Кошка ходит по кругу по часовой стрелке и съедает каждую S -тую мышку. В первый раз счет начинается с серой мышки. Составить алгоритм определяющий порядок в котором сидели мышки, если через некоторое время осталось K серых и L белых мышей.

9. Имеется таблица, содержащая N положительных целых чисел. Найти наименьшее положительное целое число, не содержащееся в этой таблице.

10. На длинной перфоленте записаны N попарно различных положительных целых чисел. Ваша ЭВМ может перематывать ленту на начало и считывать числа одно за другим. Внутренняя память машины может хранить только несколько целых чисел. Требуется найти наименьшее положительное целое число, которого нет на ленте. Опишите алгоритм, который сделает это за небольшое количество перемоток ленты.

11. На сельской улице живут в собственных домах только семьи Ивановых и Петровых. Они решили переселиться так, чтобы все Ивановы жили в начале улицы, а все Петровы - в конце. Известно общее количество домов на улице и кто живет в каждом доме. Составьте план переселения, при условии, что каждая семья должна переезжать не более одного раза, а в каждом обмене должны участвовать только две семьи.

12. На сельской улице живут в собственных домах только семьи Ивановых, Петровых и Сидоровых. Они решили переселиться так, чтобы все Ивановы жили в начале улицы, все Петровы в конце, а Сидоровы - в середине. Известно общее количество домов на улице и кто живет в каждом доме. Составьте план переселения, при условии, что каждая семья должна переезжать не более одного раза, а в каждом обмене должны участвовать не более, чем три семьи, и количество тройных обменов должно быть минимальным.

13. В правильном n-угольнике провели несколько диагоналей, причем никакие три не пересекаются в одной точке. На сколько частей диагонали разбили n-угольник? Диагонали заданы номерами вершин n-угольника, которые они соединяют, все вершины перенумерованы по порядку числами 1,...,n.

14. Заданы целочисленные координаты точек на плоскости X[19..89], Y[19..89], удовлетворяющие условиям: расстояние между соседними по нумерации точками равно I; 89-я точка совпадает с 19-й и никакие другие точки не совпадают. Написать алгоритм, который по заданным целым числам X0,Y0 определяет, находится ли точка (X0,Y0) внутри этого многоугольника.

15. Физический прибор состоит из восьми одинаковых кубов, с вертикальными или горизонтальными гранями, имеющих общую вершину. Четыре верхних куба занумерованы от 1 до 4 по часовой стрелке, под 1-м кубом - 5-й и т.д. Когда частица пролетает внутри куба, прибор дает его номер. Написать алгоритм, который по этим номерам: а) определяет, правильно ли сработал прибор; б) находит границы для угла между прямолинейной траекторией час тицы и вертикальной осью.

16. Имеется N банок с целочисленными объемами V1,...,VN литров, пустой сосуд и кран с водой. Можно ли с помощью этих банок отмерить и налить в сосуд ровно V литров воды. Входные данные: объем V>0, который нужно отмерить; количество банок N>0; объемы банок V1,...,VN>0.

17. Найти длину периода бесконечной степенной дроби по основанию Р, представляющей рациональное число N/M ( Для конечных дробей считать, что длина периода равна 1). M, N, P - целые числа.

18. Заданы количества монет (купюр) следующих достоинств: 1, 2, 3, 5, 10, 15, 25, 50, 100, 500, 1000, 2500, 5000, 10000. Можно ли набрать из этих монет заданную сумму. Если можно, то указать как это сделать.

19. Нижняя левая и верхняя правая вершины прямоугольника A имеют координаты (0,0) и (V,W) соответственно. Множество S из N точек задается парами координат (x[i],y[i]), 1<=i<=N. Найти такой прямоугольник G максимальной площади, что его стороны параллельны сторонам A, G полностью лежит в A (G и A могут иметь общие граничные точки) и ни одна точка из S не лежит внутри G (но может лежать на его стороне). Напечатать величину площади G и координаты нижней левой и верхней правой вершин этого прямоугольника. Если таких прямоугольников несколько, то вывести информацию по каждому. Замечание: в множестве S никакие две точки не лежат на одной прямой, параллельной стороне A.

20. Пусть слово - это последовательность от 1 до 8 символов, не включающая пробелов. Вводится n слов A1,...,An. Можно ли их переупорядочить так, чтобы получилась "цепочка", т.е. для каждого слова Aj его первая буква должна совпадать с последней буквой предыдущего слова, а последняя буква в Aj - с первой буквой последующего слова; соответственно последняя буква последнего слова должна совпадать с первой буквой первого слова. В цепочку входят все n слов без повторений. Дать ответ в виде "Можно"\"Нельзя". Если такое упорядочение возможно, то вывести какую-нибудь цепочку слов. Слова при выводе разделяются пробелами.

21. Вводится N - количество домов и К - количество дорог. Дома пронумерованы от 1 до N. Каждая дорога определяется тройкой чисел - двумя номерами домов - концов дороги и длиной дороги. В каждом доме живет по одному человеку. Найти точку - место встречи всех людей, от которой суммарное расстояние. до всех домов будет минимальным. Если точка лежит на доpоге, то указать номера домов - концов этой доpоги и расстояние от первого из этих домов. Если точка совпадает с домом, то указать номер этого дома. Примечание: длины дорог - положительные целые числа.

22. Получить разложение на простые множители числа n!=1*2*...*n, n-натуральное. n<=1000.

23. Совершенными числами называются числа, равные сумме своих делителей, включая 1 (6=1+2+3). Найти и вывести вместе со своими делителями совершенные числа из диапазона 4, 10000.

24. Заданы три числа А, В, С (число, месяц, год). Найти номер этого дня с начала года.

25. Дана таблица А(N, N), каждый элемент которой равен 0, 1, 5 или 7. Подсчитать количество четверок (квадратиков) А(i,j ), А(i+1, j), А(i, j+1), А(i+1, j+1), в каждой из которых все элементы различны.

26. Разработать программу, выводящую первые N элементов последовательности, которая описывается следующими аксиомами: 1) 1 является элементом последовательности; 2) если А-элемент последовательности, то 2*А, 3*А и 5*А тоже яв ляются элементами последовательности. 3) последовательности принадлежат только элементы, заданные акси омами 1 и 2.

27. Заданы прямоугольные координаты х1, y1; х2, y2; х3, y3; вершин треугольника и координаты х, y точки. Определить, находится ли точка в треугольнике.

28. Клетки шахматной доски занумерованы от 1 до 64 по строкам слева направо и снизу вверх. По заданному номеру клетки выдать номера всех клеток, имеющих с ней общую сторону.

29. Даны четыре коэффициента кубического уравнения. Найти его корни с точностью до 0.000001.

30. Написать программу дешифровки сообщения, закодированного по описанному ниже принципу. Шифр 432513, текст шифруется следующим образом:

НАСТОЯЩИЙ ВИНОВНИК КРАЖИ АЛМАЗОВ
4 3 2 5 1 3 4 3 2 5 1 3 4 3 2 5 1 3 4 3 2 5 1 3 4 3 2 5 1
СГУЧПВЭЛЛ ЗЙРТЕПНЛ НФГИН БОРГЙУГ

а именно, каждая буква алфавита заменяется на букву, номер которой равен номеру исходной буквы в алфавите + цифра, стоящая под ней, при этом буква с номером 33+N есть буква с номером N.

31. Написать программу, которая определяет, являются ли заданные три натуральных числа взаимно простыми.

32. Напишите программу, которая считывает натуральные числа N и M и находит частное N/M с точностью до 25 знаков(N и M не превосходят 1000).

33. Напишите программу, которая считывает арифметическое выражение без скобок, и определяет его правильность (имена переменных состоят только из одной буквы; константы запрещены). Написать алгоритм, который сдает сдачу минимальным количеством монет в английской денежной системе (12 пенсов = 1 шиллинг; 20 шиллингов = 1 фунт; 21 шиллинг = 1 гинея).

34. На двух прозрачных листах бумаги в клетку размером 20*20 нарисованы по одной геометрической фигуре путем закрашивания некоторых клеток в черный цвет. Описать алгоритм, определяющий, совпадут ли эти фигуры при совмещении.

35. Даны четыре точки на плоскости. Определить площадь их выпуклой оболочки (минимального выпуклого многоугольника, содержащего эти точки).

36. Даны два многочлена своими коэффициентами. Написать программу вычисления коэффициентов многочлена, являющегося их произведением.

37. Множество К строится следующим образом: Два натуральных числа A, B включены в множество К. Для любых х, у, входящих в К, число х+у+х*у включается в К. Других элементов в К нет. Составить алгоритм, определяющий, является ли z элементом множества К, если заданы числа A, B.

38. В русском тексте на 1000 букв в среднем приходится: а - 62; б - 14; в - 38; г - 13; д - 25; е,ё - 72; ж - 7; з - 16; и - 62; й - 10; к - 28; л - 35; м - 26; н - 53; о - 90; п - 23; р - 40; с - 45; т - 53; у - 21; ф - 2; х - 9; ц - 4; ч - 12; ш - 6; щ - 3; ъ,ь - 14; ы - 16; э - 3; ю - 6; я - 18. Придумать кодирование букв последовательностями из 0 и 1 (необязательно одинаковой длины) так, чтобы: - сообщение однозначно раскодировалось; имело минимальную длину.

39. Дана литерная строка, являющаяся арифметическим выражением без скобок. Все имена переменных состоят из одной буквы, константы отсутствуют. Вычислить значение этого выражения. Результат напечатать.

40. Цифры двух положительных двоичных чисел хранятся в двух линейных таблицах. Получить третью таблицу, хранящую их произведение. В двоичной системе счисления используются цифры 0 и 1, действия в двоичной системе определяются следующим образом: 0+0=0; 0*0=0; 0+1=1; 0*1=0; 1+0=1; 1*0=0; 1+1=10; 1*1=1.

41. На клетчатой бумаге нарисовали окружность целого радиуса R с центром на пересечении линий. Найти К - количество клеток, целиком лежащих внутри этой окружности.

42. Новобранцы выстроились в ряд и старшина скомандовал: "НАПРАВО", после чего каждый повернулся в произвольном направлении на 90, но увидев лицо соседа, тут же повернулся на 180. Перестанут ли они когда-нибудь вертеться? Результат обосновать.

43. Дана треугольная пирамида координатами своих вершин и точка М(х,у,z). Проверить, находится ли точка внутри пирамиды. Указание: уравнение плоскости, проходящей через три заданные точ ки, имеет вид: [(y2 - y1)(z3 - z1) - (y3 - y1)(z2 - z1)](x - x1) - [(x2 - x1)(z3 - z1) - (x3 - x1)(z2 - z1)](y - y1) + [(x2 - x1)(y3 - y1) - (x3 - x1)(y2 - y1)](z - z1) = 0

44. Трамвайные билеты имеют номера из шести цифр от 000000 до 999999. Билет называется "счастливым", если сумма 1-й, 3-й и 5-й цифр равна сумме 2-й, 4-й и 6-й цифр. Вычислить и напечатать количество "счастливых" билетов.

45. Дано положительное целое число К и К целых чисел А(1), ...,А(К). Вычислить наибольшее возможное значение суммы S(М,N)= А(М) +А (М+1)+...+А(N-1)+А(N), где 1<=М<=N<=К. Примечание. Число К столь велико, что числа А(1), А(2), ..., (К) занимают примерно одну пятую памяти, отводимой для хранения данных, а на выполнение К**2 даже простейших операций не хватает времени.

46. МОДИФИКАЦИЯ. Дано положительное целое число К и К целых чисел А(1),...,А(К), сумма которых равна 0. Числа были написаны по кругу. Вычислить максимальное значение суммы стоящих подряд чисел.

47. Устройства вывода вашей ЭВМ печатает на странице N строк, состоящих из М символов. Расстояние между центрами соседних символов равно: по горизонтали - Н единиц длины, по вертикали - V единиц. Начало координат находится в центре страницы. "Нарисовать" символом * две окружности с центрами в точках с координатами Х1, Y1, X2, Y2 и радиусами соответственно R1 и R2. Примечание. Если окружности не умещаются целиком на странице, то "рисовать" надо только те их части, которые умещаются.

48. Из листа клетчатой бумаги размером М*N клеток удалили некоторые клетки. На сколько кусков распадется оставшаяся часть листа? Пример. Если из шахматной доски удалить все клетки одного цвета,то оставшаяся часть распадется на 32 куска.

49. МОДИФИКАЦИЯ. То же, но перед удалением клеток лист склеили в цилиндр высотой N.

50. Имеется N карточек. На каждой стороне каждой карточки написано одно целое число. Известно, что каждое из чисел 1,...,N встречается на карточках дважды. Требуется узнать, можно ли карточки выложить так, чтобы каждое из чисел 1,...,N было на верхней стороне одной из карточек; если можно, то указать для каждой карточки, как ее класть.

51. Имеется N тетраэдров. На каждой грани каждого тетраэдра написано одно целое число. Известно, что каждое из чисел 1,...,N встречается на тетраэдрах четыре раза. Требуется узнать, можно ли поставить тетраэдры на стол так, чтобы каждое из чисел 1,...,N встречалось на верхних гранях трижды; если можно, то указать для каждого тетраэдра, как его ставить.

52. На клетчатой бумаге нарисовали окружность целого радиуса R с центром на пересечении линий. Найти К-количество клеток, целиком лежащих в этой окружности. Пример. Если R=5,то К=60.

53. 3-х мерное пространство разбито на кубики с ребром длины 1. Сколько из них помещается в сфере радиуса R, центр которой находится в вершине одного из кубиков? Пример. В сфере радиуса 3 помещается 56 кубиков.

54. Дана конечная последовательность состоящая из левых и правых круглых скобок. Узнать, можно ли добавить в нее цифры и знаки арифметических действий так, чтобы получилось правильное арифметическое выражение.

55. Дана конечная последовательность, состоящая из левых и правых круглых и квадратных скобок. Узнать, можно ли добавить в нее цифры и знаки арифметических действий так, чтобы получилось правильное арифметическое выражение.

56. На прямой окрасили N отрезков. Известны координата L[I] левого конца отрезка и координата R[I] правого конца I-го отрезка для I=1,...,N. Найти сумму длин всех окрашенных частей прямой. Примечание. Число N столь велико, что на выполнение N*N даже простейших операций не хватит времени.

57. МОДИФИКАЦИЯ. На окружности окрасили N дуг. Известны угловая координата L[I] начала и R[I] конца I-ой дуги (от начала к концу двигались, закрашивая дугу, против часовой стрелки). Какая доля окружности окрашена?

58. Дана последовательность из N целых чисел, среди которых нет двух одинаковых. Требуется вычеркнуть минимально возможное количество чисел так, чтобы ставшиеся шли в порядке возрастания. На печать следует выдать К - количество оставшихся чисел и их самих в порядке их следования. Примечание. Число N столь велико, что на выполнение N*N даже простейших операций не хватит времени.

59. МОДИФИКАЦИЯ. Даны N положительных целых чисел, которые не делятся ни на акие простые числа, кроме 2 и 3. Требуется выкинуть минимально возможное количество чисел так, чтобы из любых двух оставшихся одно делилось на другое.

60. На квадратном торте N свечей. Можно ли одним прямолинейным разрезом разделить его на две равные по площади части, одна из которых не содержала бы ни одной свечи? Свечи будем считать точками , у которых известны их целочисленные координаты Х[1], Y[1]; ...; Х[N], Y[N] (начало координат - в центре торта); разрез не может проходить через свечу.