Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Конспекты / Олимпиадные задачи для начинающих 7-8 класс
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 26 апреля.

Подать заявку на курс
  • Информатика

Олимпиадные задачи для начинающих 7-8 класс

библиотека
материалов

Олимпиадные задачи для начинающих 7-8 класс

Оглавление


1. Целые числа

Задача 1A. Магазин канцелярских товаров

Данные вводятся из файла input.txt, выводятся в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Однажды, посетив магазин канцелярских товаров, Вася купил X карандашей, Y ручек и Z фломастеров. Известно, что цена ручки на 2 рубля больше цены карандаша и на 7 рублей меньше цены фломастера. Также известно, что стоимость карандаша составляет 3 рубля. Требуется определить общую стоимость покупки.

Входные данные

В единственной строке входного файла input.txt записаны три натуральных числа X, Y и Z через пробел, каждое из которых не превышает 109.

Выходные данные

В выходной файл output.txt выведите одно целое число – стоимость покупки в рублях.

Примеры

Входные данные

Выходные данные

1 1 1

20

Задача 1B. Строки в книге

Данные вводятся из файла input.txt, выводятся в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

В книге на одной странице помещается K строк. Таким образом, на 1-й странице печатаются строки с 1-й по K-ю, на второй — с (K+1)-й по (2∙K)-ю и т.д. Напишите программу, которая по номеру строки в тексте определяет номер страницы, на которой будет напечатана эта строка, и порядковый номер этой строки на странице.

Входные данные

Входной файл input.txt содержит число K – количество строк, которое печатается на странице, и число N – номер строки (1 ≤ K ≤ 200, 1 ≤ N ≤ 20000).

Выходные данные

В выходной файл output.txt выведите два числа – номер страницы, на которой будет напечатана эта строка и номер строки на странице.

Примеры

Входные данные

Выходные данные

50 1

1 1

20 25

2 5

15 43

3 13

Задача 1C. Точки и прямоугольники

Данные вводятся из файла input.txt, выводятся в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Введем на плоскости декартову прямоугольную систему координат и рассмотрим прямоугольник, один угол которого находится в начале координат, а противоположный ему – в точке (W, H). Рассмотрим второй прямоугольник, который находится строго внутри первого и вершины которого находятся в точках с целыми координатами, Обозначим ширину второго прямоугольника как w, высоту – как h. Стороны обоих прямоугольников параллельны осям координат.

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

Входные данные

Входной файл input.txt содержит четыре целых числа: W , H, w и h (3 ≤ W, H ≤ 109,1 ≤ w ≤ W−2, 1 ≤ h ≤ H−2).

Выходные данные

В выходной файл output.txt выведите целое число – ответ на задачу.

Примеры

Входные данные

Выходные данные

3 3 1 1

0

4 3 1 1

2

Задача 1D. Семья

Данные вводятся из файла input.txt, выводятся в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Известно, что отец старше сына на N лет, а сын моложе отца в M раз. Определите, сколько лет отцу и сколько лет сыну.

Входные данные

Входной файл input.txt содержит два натуральных числа N и M, разделенных пробелом (1 ≤ N, M ≤ 104). Входные данные таковы, что возраст отца и возраст сына являются целыми числами.

Выходные данные

В выходной файл output.txt выведите два числа, разделенные пробелом: возраст отца и возраст сына.

Примеры

Входные данные

Выходные данные

1 2

2 1

20 5

25 5

Задача 1Е. Прямоугольник

Данные вводятся из файла input.txt, выводятся в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Дан прямоугольник с размерами A х B мм. Сколько квадратов со стороной S мм можно отрезать от него?







Входные данные

Входной файл input.txt содержит три натуральных числа A, B и S, разделенных пробелом (1 ≤ A, B, S ≤ 109). Входные данные таковы, что стороны прямоугольника и квадрата являются целыми числами.

Выходные данные

В выходной файл output.txt выведите одно число: количество квадратов, которые можно отрезать от данного прямоугольника.

Примеры

Входные данные

Выходные данные

10 15 2

20

20 5 10

0

Задача 1F. Сокращаем перемены

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Требуется подсчитать, на сколько раньше будет заканчиваться k-й урок, если все перемены сократить на 5 минут.

Входные данные

Вводится одно натуральное число k, не превосходящее 7.

Выходные данные

Вывести одно натуральное число — время в минутах.

Примеры

Входные данные

Выходные данные

3

10

Задача 1G. Переезд

Данные вводятся из файла input.txt, выводятся в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

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

Входные данные

Во входном файле находится два целых числа N и M.(0M ≤109)

Выходные данные

В выходной файл. Выведите одно целое число – минимальное количество коробок, которое потребуется Васе.

Примеры

Входные данные

Выходные данные

15 20

1

40 15

3

60 15

4

1001 20

51

Задача 1H(№775). Последовательность

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.



Вася увлекается изобретением новых последовательностей и их исследованием. В этот раз он выписал на доске последовательность: 

1 2 3 2 3 4 3 4 5 4 5 6 5 6 7...

После этого Вася задался вопросом, на каком месте в ней впервые встретится число k?

Напишите программу, которая ответит на его вопрос.

Формат входных данных

Вводится натуральное число k (1 ≤ k ≤ 100).

Формат выходных данных

Выведите одно число – искомую позицию, на которой первый раз встретилось число k. Члены последовательности нумеруются с единицы.

Примеры

Входные данные

Выходные данные

1

1

2

2

4

6

2. Условный оператор

Задача 2A. Карточки

Данные вводятся из файла input.txt, выводятся в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Вася выложил в ряд слева направо 100 карточек, на которых написаны числа 1, 2, 3, …, 100 соответственно (числами вниз). После этого он поменял местами карточки, на которых написаны числа i и j. Петя открывает карточки по очереди слева направо. Какое минимальное количество карточек ему придется открыть, чтобы точно выяснить, какие карточки поменял местами Вася?

Входные данные

Вводятся два числа i и j. Числа записаны через пробел.

Выходные данные

Требуется вывести одно число – минимальное количество карточек, которое достаточно открыть Пете.

Ограничения

Во всех тестовых примерах натуральные числа i и j различны и лежат от 1 до 100.

Задача 2B. Квартиры

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

В доме несколько подъездов. В каждом подъезде одинаковое количество квартир. Квартиры нумеруются подряд, начиная с единицы. Может ли в некотором подъезде первая квартира иметь номер x, а последняя – номер y?

Входные данные

Вводятся два натуральных числа x и y (x  y), не превышающие 10 000.

Выходные данные

Выведите слово YES (заглавными латинскими буквами), если такое возможно,
и
 NO в противном случае.

Примеры

Входные данные

Выходные данные

11 15

YES 

2 10

NO 

Задача 2C. Турнир

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

:: Результаты :: Вопросы :: Посылки :: Разбор :: Добавить темы :: Темы :: Лучшие решения :: Источники

Темы: [Условный оператор (if)]

Командные олимпиады, Турнир Архимеда, 2008, Задача F

В однокруговом турнире без ничьих участвовало N команд (каждая сыграла с каждой по одному матчу). Победителями считаются все команды, которые выиграли не меньше партий, чем остальные. Какое наибольшее количество победителей может быть в таком турнире?

Формат входных данных

Вводится одно натуральное число, не превосходящее 1000 – количество команд.

Формат выходных данных

Выведите одно число – наибольшее возможное количество победителей в таком турнире.

Примеры

Входные данные

Выходные данные

2

1

Задача 2D. От перестановки что-то меняется ...

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Всем известно, что «от перестановки слагаемых сумма не изменяется». Однако, случается и так, что перестановка двух чисел приводит к более интересным последствиям.

Пусть, например, заданы три числа: a1, a2, a3. Рассмотрим равенство a1+ a2= a3. Оно может быть неверным (например, если a1= 1, a2= 4, a3= 3), однако может стать верным, если поменять некоторые числа местами (например, если поменять местами a2 и a3, оно обратится в равенство 1 + 3 = 4).

Ваша задача – по заданным трем числам определить: можно ли их переставить так, чтобы сумма первых двух равнялась третьему.

Входные данные

Входной файл input.txt содержит три целых числа: a1, a2, a3 (−108 ≤ a1, a2, a3 ≤ 108).

Выходные данные

В выходной файл output.txt выведите слово «YES», если заданные числа можно переставить так, чтобы сумма первых двух равнялась третьему. В противном случае выведите в выходной файл слово «NO».

Примеры

input.txt

output.txt

1

3 5 2

YES

2

2 2 5

NO

3

2 2 4

YES

Задача 2E. Конь

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.



На доске размером K x N клеток (K строк, N столбцов) в j-й строке и i-м столбце стоит шахматный конь. Может ли он за один или несколько ходов попасть в клетку в m-й строке и s-м столбце?

Формат входных данных

Вводятся 6 натуральных чисел: K, N, j, i, m, s (1 ≤ K  N ≤ 100). Клетки (i, j) и (s, m) не совпадают.

Формат выходных данных

Выведите слово YES, если такое возможно, и NO в противном случае.

Пример

Входные данные

Выходные данные

8 8 1 2 7 8  

YES 

Задача 2F. Теннис

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.



Вася, Петя и Коля играли в теннис навылет (проигравший пропускал следующую партию, уступая свое место третьему). Вася утверждает, что сыграл x партий, Петя – что сыграл y партий, Коля – z партий. Определите, могло ли такое быть.

Формат входных данных

Вводятся три целых неотрицательных числа x, y, z, не превосходящих 1 000.

Формат выходных данных

Выведите YES (заглавными буквами), если такое могло быть, и NO в противном случае.

Примеры

Входные данные

Выходные данные

3 1 2

YES 

1 1 1

NO 

Задача 2G. Пирожки

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Петя очень любит пирожки с различной начинкой, причем не так важно с какой именно. Однажды, пребывая в голодном состоянии, Петя зашел в буфет и увидел, что в продаже присутствуют пирожки с картошкой, капустой и рисом. Петя желает купить как можно больше пирожков, но проблема в том, что количество пирожков в продаже ограничено так же, как и количество денег у Пети. Помогите Пете определить максимально возможное количество пирожков, которые он может купить.

Входные данные

Первая строка входного файла input.txt содержит числа P1, P2 и P3 – стоимость пирожков с картошкой, капустой и рисом соответственно. Во второй строке определены значения N1, N2 и N3 – количество соответствующих пирожков в продаже. В третьей строке записано число R – количество денег у Пети. Все числа во входных данных целые неотрицательные, не превосходящие 1018.

Выходные данные

В выходной файл output.txt выведите одно целое число - ответ на задачу.

Примеры

Входные данные

Выходные данные

1

5 3 8
2 6 4
23

7

2

15 18 20
1 4 100
1000000

105

Задача 2H. Кольцевая

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Два автомобиля движутся по кольцевой дороге длины L в противоположных направлениях. Они начинают движение из одной точки и едут с постоянными скоростями v1 и v2 соответственно. Требуется определить, на каком расстоянии друг от друга они окажутся в момент времени T.

Формат входных данных

На вход подаются 4 натуральных числа L, v1, v2, T, разделенных пробелом. Все числа не превосходят 100.

Формат выходных данных

Выведите расстояние между автомобилями в момент времени T – длину кратчайшей из двух дуг дороги между автомобилями.

Примеры

Входные данные

Выходные данные

10 1 2 1

3

10 2 3 2

0

Задача 2I. Паркет - 2

Данные вводятся из файла input.txt, выводятся в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Вhello_html_m56e5f0d5.pngаша задача – определить, можно ли замостить бесконечную плоскость правильными многоугольниками без пробелов и перекрытий. Все многоугольники должны иметь равное количество вершин и размеры. Например, лист тетради в клетку – пример замощения плоскости квадратами. Напоминание: правильный многоугольник – это выпуклый многоугольник, у которого все стороны равны между собой и все углы равны между собой.

Входные данные

Входной файл input.txt содержит целое число N – количество вершин в правильном многоугольнике (3 ≤ N ≤ 1000).

Выходные данные

В выходной файл OUTPUT.TXT выведите «YES», если плоскость можно замостить и «NO» в противном случае.

Примеры

Входные данные

Выходные данные

4

YES

5

NO

Задача 2J. СтатГрад

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

В Москве установили счетчики системы СтатГрад для учета и контроля над силой града. Каждый счетчик системы учитывает количество попаданий в него градин за сутки. Если в него попадает меньше a градин, то он передает сигнал NO GRAD. Если попадает не меньше a градин, но меньше b градин, то он передает сигнал GRAD. Если больше либо равно b градин – то он ломается, и не передает никакого сигнала.

Даны числа a и b (a < b), а также количество попавших в счетчик градин. Требуется определить, какой сигнал нужно передать.

Входные данные

Вводятся три натуральных числа, не превосходящих 1000: a, b и количество градин. Числа разделены пробелом.

Выходные данные

Выведите либо NO GRAD, либо GRAD, либо не выводите ничего.

Входные данные

Выходные данные

10 20 15

GRAD

10 20 5

NO GRAD

10 20 30




Задача 2K. Точки на окружности

Данные вводятся из файла input.txt, выводятся в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

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

Формат входных данных:

В первой строке входного файла содержится число целое число N — количество точек на окружности (3 ≤ N ≤ 1000).

Формат выходных данных:

В выходной файл необходимо записать одно целое число — количество непомеченных точек.

Пример файлов входных и выходных данных:

Входные данные

Выходные данные

3

0

Задача 2L. Часы

Вы — член команды, которая создает прикладную программу, обучающую маленьких детей определять время по часам. Часть программы, рисующая на экране часы, уже написана вашими товарищами. Часы представляются кругом с числами от 1 до 12. Эта программа позволяет пользователям переставлять стрелки на часах. Ваша задача — с точностью до 5 минут определить время по положению стрелок, используя те числа на циферблате, которые наиболее близки к стрелкам.

Правила определения времени следующие. Если минутная стрелка находится ближе всего к числам 1, 2, 3, …, 11, то она определяет соответственно 5, 10, 15, …, 55 минут. Если же она находится наиболее близко к числу 12, то считается, что она задает 0 минут. Если минутная стрелка наиболее близко подошла к числам 12, 1, 2, 3, 4 или 5, то считается, что часы определяется тем числом, к которому наиболее близка часовая стрелка. Однако, если же минутная стрелка ближе всего к числам 6, 7, 8, 9, 10 или 11, то часы задаются числом, предшествующим тому числу, к которому наиболее близко подошла в данный момент часовая стрелка.

Входные данные

Во входном файле записано через пробел два целых числа, принимающие значения от 1 до 12, первое из которых — то число на циферблате, к которому подошла наиболее близко часовая стрелка, а второе — ближайшее к минутной стрелке.

Выходные данные

В выходной файл нужно вывести значение времени, заданного во входном файле. Время выводить в формате h:mm, где h — одна или две цифры, если требуется, обозначающие текущее значение часов, а mm — минуты, всегда две цифры.

Пример файлов входных и выходных данных:

Входные данные

Выходные данные

7 3

7:15

1 10

12:50

10 6

9:30

10 12

10:00

Задача 2M. Красная шапочка

Данные вводятся из файла input.txt, выводятся в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Красная Шапочка часто навещает свою бабушку. Но она очень боится, что рано или поздно ее бабушку опять навестит волк. Поэтому она решила договориться с Лесничим об охране бабушки. Лесничий согласился охранять бабушку за 10 пирожков.
Узнав об этом, волк сказал Красной Шапочке, что ей совершенно незачем тратить пирожки на Лесничего. За половину тех пирожков, которые Красная Шапочка несет бабушке, Волк пообещал не трогать ее. Сегодня (26 ноября)
 в России отмечается день матери. Мама испекла несколько пирожков, и попросила Красную Шапочку отнести их бабушке. Требуется определить, сколько пирожков Красная Шапочка сможет донести до бабушки.

Входные данные

Вводится одно четное число - количество пирожков, которые испекла мама.

Выходные данные

Программа должна вывести  одно число - количество пирожков, которые Красная Шапочка сможет донести до бабушки.

Примеры

Входные данные

Выходные данные

Комментарий

 12

6

Если мама испекла 12 пирожков, то выгоднее отдать половину пирожков (6 штук) волку, чем 10 пирожков Лесничему. В этом случае Красная Шапочка сможет донести до бабушки 12-6=6 пирожков.

100

90

Если мама испекла 100 пирожков, то выгоднее отдать 10 пирожков Лесничему, чем половину (50 пирожков) волку. До бабушки в этом случае Красная Шапочка донесет 100-10=90 пирожков.

20

10

Если испечено 20 пирожков, то в любом случае (и если отдать половину пирожков Волку, и если отдать 10 пирожков Лесничему) бабушке останется 10 пирожков.

Ограничения

Решение задачи будет проверяться на тестовых примерах, в которых число испеченных мамой пирожков - натуральное число, не превосходящее 100.

Задача 2N. Счастливый билет

Данные вводятся из файла input.txt, выводятся в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Вы пользуетесь общественным транспортом? Вероятно, вы расплачивались за проезд и получали билет с номером. Счастливым билетом называют такой билет с шестизначным номером, где сумма первых трех цифр равна сумме последних трех. Т.е. билет с номером 385916 – счастливый, т.к. 3+8+5=9+1+6. Вам требуется написать программу, которая проверяет счастливость билета.

Входные данные

В единственной строке входного файла input.txt записано одно целое число N
(0 ≤ N < 106).

Выходные данные

В выходной файл output.txt нужно вывести «YES», если билет с номером N счастливый и «NO» в противном случае.

Примеры

Входные данные

Выходные данные

385916

YES

123456

NO

Задача 2O.(№1178) Оплата интернета

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.


Витя подключен к интернет по следующему тарифному плану. Ежемесячная абонентская плата составляет A рублей, и в эту абонентскую плату включено B мегабайт трафика. Неизрасходованные мегабайты в конце месяца «сгорают». Если трафик превышает B мегабайт, то каждый мегабайт трафика сверх предоплаченных стоит C рублей. Известно, что за прошлый месяц Витя израсходовал D мегабайт трафика. Определите, во сколько обошелся ему доступ в интернет в прошлом месяце (считая, в том числе и абонентскую плату)?

Входные данные

Вводятся четыре натуральных числа A, B, C, D. Все числа не превышают 100.

Выходные данные

Выведите одно число — сумму (в рублях), которую Витя должен заплатить за интернет.

Примеры

Входные данные

Выходные данные

100 10 12 15

160

100 10 12 1

100

3. Циклы

Задача 3A. (№1934) Офис

Данные вводятся из файла input.txt, выводятся в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.



Помимо составления последовательностей, летом Вася очень любил смотреть в окно. Напротив его дома расположился офис строительной фирмы. В течение всего месяца Вася наблюдал за его служащими. Про каждый из 31 дня месяца он знает, сколько сотрудников пришло на работу. Ему также известно, что каждый из служащих берет ровно по 4 выходных в месяц. Теперь он ломает голову над загадкой – сколько всего сотрудников работает в этом офисе. Напишите программу, которая ответит Васе на этот вопрос.

Формат входных данных

Вводится 31 целое неотрицательное число. Эти числа описывают количество работников, пришедших в офис в соответствующие дни месяца. Гарантируется, что входные данные корректны.

Формат выходных данных

Выведите единственное число – общее количество работников офиса. Гарантируется, что ответ не превышает 100.

Примеры

Входные данные

Выходные данные

10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0

10

Задача 3B. Оттепель

Данные вводятся из файла input.txt, выводятся в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Уставшие от необычно теплой зимы, москвичи решили узнать, действительно ли это самая длинная оттепель за всю историю наблюдений за погодой. Они обратились к синоптикам, а те, в свою очередь, занялись исследованиями статистики за прошлые годы. Их интересует, сколько дней длилась самая длинная оттепель.

Оттепелью они называют период, в который среднесуточная температура ежедневно превышала 0 градусов Цельсия. Напишите программу, помогающую синоптикам в работе.

Формат входных данных

Сначала вводится число N общее количество рассматриваемых дней (1 ≤ N ≤ 100). В следующей строке задается N целых чисел, разделенных пробелами. Каждое число – среднесуточная температура в соответствующий день. Температуры – целые числа, принадлежащие  диапазону от –50 до 50.

Формат выходных данных

Требуется вывести одно число – длину самой продолжительной оттепели, то есть наибольшее количество последовательных дней, на протяжении которых среднесуточная температура превышала 0 градусов. Если температура в каждый из дней была неположительной, выведите 0.

Примеры

Входные данные

Выходные данные

Комментарий

6
-20 30 -40 50 10 -10

2

Рассматриваются 6 дней. Самая продолжительная оттепель была на 4-й и 5-й день (50 и 10 градусов соответственно)

8
10 20 30 1 -10 1 2 3

4

Самая продолжительная оттепель была в первые 4 дня

5
-10 0 -10 0 -10

0

Дней с положительной температурой не было

Задача 3С. Деление с остатком

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Вася учится делить с остатком. Он взял некоторое число, разделил его на 2 и отбросил остаток. То, что получилось, разделил на 3 и опять отбросил остаток. Полученное число он разделил на 4, отбросил остаток и получил число K. Какое число мог выбрать Вася изначально?

Формат входных данных

Вводится натуральное число K, не превосходящее 1 000.

Формат выходных данных

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

Примеры

Входные данные

Выходные данные

1

24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

Задача 3D.№3903. Количество чисел

Данные вводятся из файла input.txt, выводятся в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.


Сколько всего натуральных чисел состоят из не менее чем а цифр и не более, чем b цифр?

Входные данные

Вводятся два произвольных натуральных числа а и b через пробел. Каждое не превышает 10 000.

Выходные данные

Выведите одно число: количество чисел, обладающих указанным свойством.


Примеры

Входные данные

Выходные данные

1 2

99

1 1

9

Задача 3E. Деление без остатка(ЗАДАЧА 3)

Данные вводятся из файла input.txt, выводятся в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Дано натуральное число n (n <=1000). Составить программу для проверки делится ли целое число на каждую из его цифр без остатка. Напечатать такие числа в интервале от 10 до n.

Входные данные

Вводится одно натуральное число не превосходящее 1 000.

Выходные данные

Программа должна вывести все числа, которые делятся на каждую из цифр без остатка, в порядке возрастания, через пробел.

Примеры

Вход Выход

40 11 12 15 22 24 33 36

Задача 3F. Загадка

Петя и Катя – брат и сестра. Петя – студент, а Катя – школьница. Петя помогает Кате по математике. Он задумывает два натуральных числа X и Y (X,Y≤1000), а Катя должна их отгадать. Для этого Петя делает две подсказки. Он называет сумму этих чисел S и их произведение P. Помогите Кате отгадать задуманные Петей числа.

Входные данные

Входной файл INPUT.TXT содержит два натуральных числа S и P, разделенных пробелом.

Выходные данные

В выходной файл OUTPUT.TXT выведите два числа Х и Y, загаданные Петей. Числа следует вывести в порядке неубывания своих значений, разделенные пробелом.

Примеры

INPUT.TXT

OUTPUT.TXT

1

4 4

2 2

2

5 6

2 3

4. Строки

Задача 4A. «У моего папы больше денег»

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Двое играют в такую игру. Первый называет число, затем второй называет число. Если число второго больше, то он выиграл, в противном случае (даже если числа равны), выиграл первый. Помогите второму игроку – напишите программу, которая будет за него успешно играть в эту игру.

Формат входных данных

Вводится натуральное число A, которое назвал первый игрок (в числе А не больше 100 цифр).

Формат выходных данных

Выведите одно натуральное число – какой-нибудь (любой!) выигрышный ход второго игрока.

Примеры

Входные данные

Выходные данные

1

5

1000000000000000

1000000000000001

Задача 4B. Светофор

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

А Вы знаете, как работает светофор? Пожалуй, что каждый школьник знаком с этим устройством, но не каждый точно может описать алгоритм его работы. Если сомневаетесь, то спросите себя: «Сколько раз мигает зеленый сигнал светофора?».

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

  1. горит только зеленый сигнал;

  2. зеленый сигнал мигает;

  3. гаснет зеленый, загорается желтый;

  4. гаснет желтый, загорается красный;

  5. загорается желтый и горит вместе с красным;

  6. гаснут желтый и красный и все повторяется с пункта 1.

Еще следует не забывать о том, что светофор может работать в режиме нерегулируемого перекрестка, когда присутствует только желтый мигающий сигнал.

По текущей индикации сигналов светофора следует определить его следующее состояние, в которое он должен перейти, либо определить, что светофор неисправен.

Входные данные

Входной файл input.txt содержит в трех строках описание текущего состояния светофора. Первая строка описывает верхнюю секцию, вторая – среднюю, третья – нижнюю. Состояние каждой из секций определяется ее цветом: black (черный), red (красный), yellow(желтый) и green(зеленый). Если некоторый цвет мигает, то он описывается в верхнем регистре, иначе – в нижнем.

Выходные данные

В выходной файл output.txt выведите ответ на задачу в том же формате, если светофор исправен. В случае неисправности светофора выведите «error».

Примеры

Входные данные

Выходные данные

1

black
black
green

black
black
GREEN

2

black
YELLOW
black

black
YELLOW
black

3

red
yellow
green

error

Задача 4C. Трудная задача

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Витя пригласил своего друга Сергея в гости, но не сказал ему код от цифрового замка своего подьезда, а послал следующее SMS-сообщение: В последовательности цифр 3182 все цифры больше 5 разделить на 2 (при необходимости отбросив остаток), а затем удалить из полученной последовательности все четные цифры. Какой код получил Сергей, выполнив указанные в сообщении действия?

Формат входных данных

Вводятся 4 цифры в одной строке без пробелов – последовательность, содержащаяся в SMS-сообщении.

Формат выходных данных

Выведите код цифрового замка без пробелов.

Примеры

Входные данные

Выходные данные

0586

53

Задача 4D. Шашки - 2

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

На доске стоит белая шашка. Требуется определить, может ли она попасть в заданную клетку, делая ходы по правилам (не превращаясь в дамку).

Входные данные

В единственной строке входного файла input.txt записаны клетка, где стоит шашка, в шахматной нотации, а затем, через пробел, клетка, куда шашка должна попасть. Начальная и конечная клетки не совпадают.

Выходные данные

В единственную строку выходного файла output.txt нужно вывести слово YES (заглавными буквами), если шашка может попасть из начальной клетки в конечную, и NO в противном случае.

Примеры

input.txt

output.txt

Комментарии

a1 b2

YES

Для выполнения указанного перемещения шашка должна сделать один ход вперед и вправо

b2 a1

NO

Назад шашка ходить не может

a1 h7

NO

a1 и h7 - клетки разного цвета

a1 h8

YES

7 ходов вправо вверх

Пояснение

Доска имеет размер 8x8, вертикали нумеруются маленькими латинскими буквами от a до h, горизонтали - числами от 1 до 8. Белая шашка ходит по чёрным полям по диагонали вверх.

Задача 4E. Сжатие бинарных последовательностей

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Последовательность из символов «0» и «1» называется бинарной. Они широко применяются в информатике и других науках. Одно из неудобств бинарных последовательностей – их трудно запоминать. Для решения этой проблемы были предложены разные способы их сжатия. Программист Слава использует следующий способ: просматривая последовательность слева направо, он заменяет «1» на «a», «01» на «b», «001» на «c», …, «00000000000000000000000001» на «z». Напишите программу, которая поможет Славе автоматизировать этот способ сжатия.

Входные данные

Входной файл input.txt содержит бинарную последовательность – строку из символов «0» и «1» длиной не более 255 символов. Гарантируется, что к ней применим указанный способ сжатия.

Выходные данные

В выходной файл output.txt выведите одну строку из латинских строчных букв от «a» до «z» – сжатие заданной бинарной последовательности.

Примеры

input.txt

output.txt

1

101

ab

2

101001

abc

3

0000000000000000000000001

y

Задача 4F. Число

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Вводится натуральное число. Требуется разделить запятыми тройки его цифр (считая справа).

Формат входных данных

Вводится одно натуральное число, не превышающее 10100.

Формат выходных данных

Вывести то же число, разделяя тройки цифр запятыми.

Примеры 

Входные данные

Выходные данные

1000

1,000

12345678

12,345,678

999

999

Задача 4G (№509). Количество слов

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.




На вход программы поступает строка текста, в которой могут встречаться:

  1. прописные и строчные (т.е. большие и маленькие) латинские буквы;

  2. пробелы;

  3. знаки препинания: точка, запятая, восклицательный и вопросительный знак;

  4. символ –, обозначающий в некоторых случаях тире, а в некоторых — дефис.

Слово — это последовательность подряд идущих латинских букв и знаков дефис, ограниченная с обоих концов. В качестве ограничителей могут выступать начало строки, конец строки, пробел, знак препинания, тире. Тире отличается от дефиса тем, что слева и справа от знака дефис пишутся буквы, а хотя бы с одной стороны от тире идет либо начало строки, либо конец строки, либо пробел, либо какой-либо знак препинания, либо еще одно тире.

Напишите программу, определяющую, сколько слов в данной строке текста.

Формат входных данных

Вводится строка длиной не более 200 символов.

Формат выходных данных

Выведите одно число — количество слов, которые содержатся в исходной строке.

Примеры

Входные данные

Выходные данные

Hello , world!

2

www.olympiads.ru

3

Gyro-compass - this is a ...

4


Задача 4H. Нули

Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц.

Входные данные

В единственной строке входного файла INPUT.TXT записана последовательность нулей и единиц (без пробелов). Суммарное количество цифр не превышает 100.

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести искомую длину цепочки нулей.

Пример

Входные данные

Выходные данные

1

00101110000110

4

5. Массивы

Задача 5A. Бег по эскалатору

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Пусть N человек бегут вниз по эскалатору, причем i-ый пробегает одну ступеньку за ti секунд. По технике безопасности бега по эскалатору, на эскалаторе запрещены «обгоны», то есть если человек A в процессе бега догнал человека B, который бежит с более низкой скоростью, то далее, до конца эскалатора, человек A бежит со скоростью человека B. Однако ступени эскалатора таковы, что на них может помещаться несколько человек одновременно.

Ваша задача написать программу, которая поможет работникам станции рассчитать, когда закончит свой бег по эскалатору каждый бегущий человек.

Входные данные

В первой строке входного файла INPUT.TXT записано число N (1 ≤ N ≤ 105). В следующих N строках перечислены пары чисел ti, wi (1 ≤ ti, wi ≤ 106) – время пробега одной ступени и количество ступеней до конца эскалатора для i-го человека. Гарантируется, что изначально всем людям осталось бежать различное число ступеней.

Выходные данные

В i-ой строке выходного файла OUTPUT.TXT выведите время в секундах, через которое i-ый человек сойдет с эскалатора.

Пример

Входные данные

Выходные данные

1

3
2 10
3 11
1 12

20
33
33


Задача 5B. Азартный Шрэк

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Как-то раз Шрек решил посетить казино. Не будучи заядлым любителем азартных игр, Шрек обнаружил, что он не знает правил ни одной из игр, доступных в казино. Недолго думая, Шрек решил все-таки поиграть. Его взор привлекла игра с довольно незамысловатыми правилами.

На игровом столе лежат N карточек. На каждой карточке написано целое положительное число. Игра проходит между игроком и крупье. Карточки лежат на столе числами вниз. Игра заключается в том, что игрок открывает ровно N/2 карточек. Сумма всех чисел, написанных на карточках открытых игроком, называется “суммой игрока”. Следующим ходом крупье открывает оставшиеся N/2 карточек. Сумма всех чисел, написанных на карточках открытых крупье, называется “суммой крупье”. Выигрыш игрока определяется разностью чисел между “суммой игрока” и “суммой крупье”. Очевидно, что полученная разность может быть отрицательным числом. Это свидетельствует о том, что игрок проиграл и должен казино соответствующую сумму. Все бы ничего, но Шрек обладает способностью видеть надписи сквозь бумагу любой плотности. Ваша задача определить максимальную сумму выигрыша, которую может получить Шрек с учетом того, что он видит все числа, написанные на карточках.

Входные данные

Первая строка входного файла input.txt содержит одно четное натуральное число N (2 ≤ N ≤ 100). Вторая строка входного файла содержит ровно N чисел Ai(1 ≤ Ai ≤ 106) – числа, написанные на игральных карточках. Все числа в строке разделяются одиночными пробелами, Ai – число, написанное на i-й карточке. Карточки нумеруются последовательно, начиная с единицы.

Выходные данные

Единственная строка выходного файла output.txt должна содержать ровно одно целое число – максимальный выигрыш, который может получить Шрек с учетом своей уникальной способности видеть числа, написанные на карточках.

Примеры

Входные данные

Выходные данные

2
1 3

2

4
3 1 8 100

104

Задача 5С. Лестница (Пример #1)

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Определить, сколькими различными способами можно подняться на 10-ю ступеньку лестницы, если за один шаг можно подниматься на следующую ступеньку или через одну.

Входные данные

В первой строке входного файла INPUT.TXT записано число ступеней лестницы
N (1 ≤ N ≤ 10).

Выходные данные

В выходной файл OUTPUT.TXT выведите число различных способов, которыми можно подняться на 10-ю ступеньку лестницы.

Примеры

Входные данные

Выходные данные

2

2

3

3

4

5

Задача 5Е. Считалочка

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

Дети решили поиграть в догонялки, и, чтобы выбрать водящего, встали в круг и стали считаться. Для этого они использовали считалочку. Показывая пальцем по очереди на каждого стоящего в кругу, считающий произносит одно слово, и тот, на кого придется последнее слово, и будет водить. Требуется по данной считалочке определить, кто же будет водить.

Формат входных данных

В первой строке вводится считалочка. Она состоит из слов, записанных латинскими буквами. Слова разделены одним пробелом. Знаков препинания нет, строка начинается и заканчивается буквой. В считалочке не менее двух слов, а длина строки не превосходит 100.

Во второй строке в том же формате вводится список имен школьников в том порядке, в котором они стоят по кругу. Считать начинают с первого школьника. Детей не менее двух, а длина строки не превосходит 100.

Формат выходных данных

Выведите имя школьника, которому предстоит водить.

Примеры

Входные данные

Выходные данные

To be or not to be 
John Mary Ann Kate

Mary

Na zolotom kryltse sideli 
Vasya Vasya Vasya

Vasya

Разбор олимпиадных задач 7-8 класс

1. Целые числа

Задача 1A. Магазин канцелярских товаров

Разбор

Из условия задачи понятно, что карандаш стоит 3 рубля, ручка – 5 рублей, а фломастер – 12 рублей. Для нахождения общей стоимости умножим количество на стоимость и сложим получившиеся числа.

Подводным камнем задачи является ограничение до 109 , то есть общая стоимость может превысить максимально допустимое значение типа Longint или int . Поэтому следует использовать 64-битный тип данных (int64).

Решение

{ Программа № 1A. Магазин канцелярских товаров }

{ -------------------------------------------------- }

{ Однажды, посетив магазин канцелярских товаров, Вася }

{ купил X карандашей, Y ручек и Z фломастеров. }

{ Известно, что цена ручки на 2 рубля больше цены }

{ карандаша и на 7 рублей меньше цены фломастера. }

{ Также известно, что стоимость карандаша составляет }

{ 3 рубля. Требуется определить стоимость покупки }

{ Тема: [Целые числа] }

{ Источник: Школьная олимпиада по Красноярскому краю, }

{ 7-8 классы, Задача А, 2013/2014 }

{ --------------------------------------------------- }

program task_1a;

var x, y, z : int64;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(x, y, z);

write(3*x + 5*y + 12*z);

end.



Задача 1B. Строки в книге

Разбор

Для большего удобства будем нумеровать страницы и строки в книге, начиная с нуля. То есть на нулевой странице будут строки с 0 до K−1 , на первой – с K до 2*K−1 и так далее. Тогда номер страницы легко узнать делением на K , а номер строки на этой странице равен остатку от деления. Действительно, если номер строки делится на K , то это будет нулевая строка на одной из страниц, а следующие за ней будут иметь соответствующий остаток.

Решение

{ Программа № 1B. Строки в книге }

{ --------------------------------------------------- }

{ В книге на одной странице помещается K строк. }

{ Напишите программу, которая по номеру строки }

{ в тексте определяет номер страницы, на которой }

{ находится эта строка, и порядковый номер этой строки}

{ Темы: [Целые числа] }

{ Источник: Школьная олимпиада по Красноярскому краю, }

{ 7-8 классы, Задача B, 2013/2014 }

{ -------------------------------------------------- }

program task_1b;

var k, n : Longint;

begin

assign(input, 'input.txt'); reset(input);

assign(output, 'output.txt'); rewrite(output);

read(k, n);

dec(n);

write(n div k + 1,' ', n mod k + 1);

end.



Задача 1C. Точки и прямоугольники

Разбор

Внутри первого прямоугольника находится (W−1)(H−1) точек с целыми координатами. А второй прямоугольник содержит ровно (w+1)(h+1) таких точек. Значит, результатом будет разность этих произведений.

В этой задаче важно обратить внимание на ограничения. Все числа могут быть до миллиарда, а это значит, что произведение двух из них будет порядка 1018 . Поэтому следует использовать 64-битный тип данных (Int64 ).

Решение на языке Паскаль

{ Программа № 1C. Точки и прямоугольники }

{ --------------------------------------------------- }

{ Рассмотрим прямоугольник, один угол которого }

{ находится в начале координат, а противоположный ему }

{ – в точке (W, H). Рассмотрим второй прямоугольник, }

{ который находится строго внутри первого и вершины }

{ которого находятся в точках с целыми координатами, }

{ Обозначим ширину второго прямоугольника как w, }

{ высоту – как h. Стороны обоих прямоугольников }

{ параллельны осям координат. Необходимо найти }

{ количество точек с целыми координатами, которые }

{ находятся строго внутри первого прямоугольника }

{ и строго снаружи второго. }

{ Темы: [Целые числа] }

{ Источник: "Муниципальный этап Всероссийской }

{ олимпиады школьников Красноярского края по }

{ информатике, 7-8 классы" }

{ --------------------------------------------------- }

Program task_1c;

var

w1,h1,w2,h2: Int64;

begin

assign(input, 'input.txt'); reset(input);

assign(output, 'output.txt'); rewrite(output);

read(w1,h1,w2,h2);

write((w1-1)*(h1-1)-(w2+1)*(h2+1));

end.



Задача 1D. Семья

Разбор

Составим и решим систему уравнений:

xhello_html_m4a4bb36.gif+N = y, отсюда: xM = x+N,

xM = y; выразим: x= N / (M1), y= MN / (M1)

Решение

{ Программа № 1D. Семья }

{ --------------------------------------------------- }

{ Известно, что отец старше сына на N лет, а сын }

{ моложе отца в M раз. Определите, сколько лет отцу }

{ и сколько лет сыну. }

{ Темы: [Целые числа] }

{ Источник: Полуфинал XIV Всероссийской командной }

{ олимпиады школьников по программированию }

{(Восточно-Сибирский регион)" , Задача А }

{ --------------------------------------------------- }

Program task_1d;

var n, m, t: Longint;

begin

assign(input, 'input.txt'); reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(n, m);

WriteLn(n*m div (m-1),' ',n div (m-1));

end.

Задача 1Е. Прямоугольник

Разбор

Количество целых квадратов, которые возможно отрезать по длине прямоугольника можно определить разделив a div s, а по высоте прямоугольника - b div s. Результат получаем умножением полученных целых чисел: x:=(a div s)*(b div s)

Решение

{ Программа № 1Е. Прямоугольник }

{ --------------------------------------------------- }

{ Дан прямоугольник с размерами A х B мм. Сколько }

{ квадратов со стороной S мм можно отрезать от него? }

{ Темы: [Целые числа] }

{ Источник: Задачи по программированию. Под редакцией }

{ С.М. Окулова. М: БИНОМ, 2006 }

{ --------------------------------------------------- }

program task_1E;

var

a, b, s, x: int64;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(a,b,s);

x:=(a div s)*(b div s);

writeln(x)

end.

Задача 1F.(№2837) Сокращаем перемены

Разбор

Ответом будет (k-1)*5

Решение

{ Программа № 1Е. Сокращаем перемены }

{ --------------------------------------------------- }

{ Требуется подсчитать, на сколько раньше будет }

{ заканчиваться k-й урок, если все перемены сократить }

{ на 5 минут. }

{ Тема: [Целые числа] [Условный оператор (if)] }

{ Источник: Личные олимпиадыШкольная личная }

{ олимпиада ФМШ №2007 г. Москвы20108 кл, Задача A }

{ --------------------------------------------------- }

program task_1f;

var

k: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(k);

writeln((k-1)*5);

end.

Задача 1G. Переезд

Решение

{ Программа № 1G. Переезд. }

{ --------------------------------------------------- }

{ Вася купил себе новую квартиру и теперь занимается }

{ переездом. У него есть N книг, Вася хочет перевезти }

{ их отдельно от остальных вещей. Для транспортировки }

{ он может использовать коробки, которые вмещают }

{ M книг каждая. Помогите посчитать Васе, какое }

{ количество коробок ему понадобиться для перевозки }

{ всех книг за один раз. }

{ Темы: [Целые числа] }

{ Источник: Задачи по программированию. }

{ Под редакцией С.М. Окулова. М: БИНОМ, 2006 }

{ --------------------------------------------------- }

program task_1g;

var m, n, res: int64;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(n, m);

res:=(n + m - 1) div m;

writeln(res);

end.



Задача 1H(№775). Последовательность

Разбор

Если k =1,2, то ответ равен k.

Если k >2, первый раз число k встретиться в тройке: (k-2), (k-1), k, это будет (k -2) – ая тройка в последовательности. Следовательно, искомая позиция равна 3* k – 6.

Решение

{ Программа № 1H. Последовательность }

{ --------------------------------------------------- }

{ Дана последовательность: 1 2 3 2 3 4 3 4 5 4 5 6... }

{ Напишите программу, которая ответит на вопрос }

{ на каком месте в ней впервые встретится число k? }

{ Тема: [Арифметические алгоритмы] }

{ Источник: IV Открытая олимпиада школьников }

{ по программированию, 2009/2010, Задача А }

{ --------------------------------------------------- }

program task_1h;

var k, p: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(k);

if k > 2 then p:= 3*k - 6

else p:= k;

writeln(p);

end.

2. Условный оператор

Задача 2A. Карточки

Разбор

Так как карточки открываются слева направо, достаточно открыть первую по порядку из переставленных карточек, то есть взять минимум из i и j. Однако есть случай, когда количество действий можно сократить: если переставлены последние 2 карточки, то, перевернув 3-ю с конца, мы уже будем знать ответ.

Решение

{ Программа № 2A. Карточки }

{ --------------------------------------------------- }

{ Вася выложил в ряд слева направо 100 карточек, на }

{ которых написаны числа 1, 2, 3, …, 100  }

{ соответственно (числами вниз). После этого он }

{ поменял местами карточки, на которых написаны }

{ числа i и j. Петя открывает карточки по очереди }

{ слева направо. Какое минимальное количество }

{ карточек ему придется открыть, чтобы точно выяснить}

{ какие карточки поменял местами Вася? }

{ Тема: [Условный оператор (if)] }

{ Источник: http://informatics.mccme.ru/ }

[ Турнир Архимеда, 2007, Задача I] }

{ --------------------------------------------------- }

program task_2a;

var i, j: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(i,j);

if i < j then writeln(i)

else writeln(j)

end.



Задача 2B. Квартиры

Разбор

Посчитаем число квартир в подъезде - вычтем x из y и прибавим k этому числу 1. Если y делится на число квартир без остатка, выводим YES, иначе - NO.

Решение

{ Программа № 2B. Квартиры }

{ --------------------------------------------------- }

{ В доме несколько подъездов. В каждом подъезде }

{ одинаковое количество квартир. Квартиры нумеруются }

{ подряд, начиная с единицы. Может ли в некотором }

{ подъезде первая квартира иметь номер x, }

{ а последняя – номер y? }

{ Тема: [Условный оператор (if)] }

{ Источник: http://informatics.mccme.ru/ }

{ Командные олимпиадыТурнир Архимеда,2008, Задача A }

{ --------------------------------------------------- }

program task_2b;

var

x,y,k: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(x,y);

k := y - x + 1;

if y mod k =0 then writeln('YES')

else writeln ('NO')

end.



Задача 2C. Турнир

Разбор

Для начала нужно догадаться, что ответ зависит от общего количества матчей между командами. Пример:

количество команд(n) - количество матчей(m)

2-1, 3-3, 4-6, 5-10, 6-15, 7-21 и т.д. m = n*(n-1)/2

Также приведу таблицу ответов: (вход. дан. - ответ) 2-1, 3-3, 4-3, 5-5, 6-5, 7-7 и т.д. Можно заметить, что если количество матчей нацело делится на количество команд, то ответ n, иначе n-1.

Решение

{ Программа № 2C. Турнир }

{ --------------------------------------------------- }

{ В однокруговом турнире без ничьих участвовало  }

{ N команд (каждая сыграла с каждой по одному матчу) }

{ Победителями считаются все команды, которые выиграли}

{ не меньше партий, чем остальные. Какое наибольшее }

{ количество победителей может быть в таком турнире? }

{ Тема: [Условный оператор (if)] }

{ Источник: http://informatics.mccme.ru/ }

{ Командные олимпиадыТурнир Архимеда2008, Задача E}

{ --------------------------------------------------- }

program task_2c;

var n, m: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(n);

m:= n*(n-1) div 2;

if m mod n = 0 then writeln(n) else writeln(n-1)

end.



Задача 2D. От перестановки что-то меняется ...

Разбор

Для решения этой задачи надо было проверить на истинность три равенства – равно ли число сумме двух других.

Решение

{ Программа № 2D. От перестановки что-то меняется }

{ --------------------------------------------------- }

{ Пусть, например, заданы три числа: a1, a2, a3. }

{ Рассмотрим равенство a1+ a2= a3. Оно может быть }

{ неверным (например, если a1=1, a2=4, a3=3), однако }

{ может стать верным, если поменять некоторые числа }

{ местами (например, если поменять местами a2 и a3, }

{ оно обратится в равенство 1 + 3 = 4). }

{ Ваша задача – по заданным трем числам определить, }

{ можно ли их переставить так, чтобы сумма }

{ первых двух равнялась третьему. }

{ Тема: [Условный оператор (if)] }

{ Источник:[Школьная олимпиада по Красноярскому краю, }

{ 9-11 класс, 2013, Задача A] }

{ --------------------------------------------------- }

program task_2d;

var a, b, c: Longint;

begin

assign(input, 'input.txt'); reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(a,b,c);

if (a=b+c) or (b=a+c) or (c=a+b) then Write('YES')

else Write('NO');

end.



Задача 2E. Конь

Разбор

Задача всегда имеет решение, если меньшая из сторон не меньше 3, если обе стороны равны 3, то решения не будет только в случае если координаты одной из клеток (2,2). Если меньшая сторона равна 1, то решения не будет, остается рассмотреть вариант при К (N) равной 2. В таком случае надо учитывать в одной строке (столбце) находятся клетки или нет. Если клетки расположены в одной строке (столбце), то разница координат по столбцу (строке) должна делиться на 4 без остатка, или если в разных строках (столбцах), и остаток от деления разницы координат на 4 равен 2. то решение есть, а иначе решения нет.

Решение

{ Программа № 2E. Конь }

{ --------------------------------------------------- }

{ На доске размером K x N клеток(K строк, N столбцов) }

{ в j-й строке и i-м столбце стоит шахматный конь. }

{ Может ли он за один или несколько ходов попасть }

{ в клетку в m-й строке и s-м столбце? }

{ Тема: [Условный оператор (if)] }

{ Источник: http://informatics.mccme.ru/ }

{Командные олимпиадыТурнир Архимеда2008, Задача D }

{ --------------------------------------------------- }

program task_2e;

var k,n,i,j,m,s,min: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(k,n,i,j,m,s);

if k < n then min:=k

else min:=n;

if min>=3 then writeln('YES')

else if (k=3) and (n=3) then

if (i=2) and (j=2) or (m=2) and (s=2) then writeln('NO')

else writeln('YES')

else if min=1 then writeln('NO');

if (k=2) then

if (s-j) mod 4 = 0 then writeln('YES')

else if (s-j) mod 4 = 2 then writeln('YES')

else writeln ('NO')

if (n=2) then

if (m-i) mod 4 = 0 then writeln('YES')

else if (m-i) mod 4 = 2 then writeln('YES')

else writeln ('NO')

end.



Задача 2F. Теннис

Решение:

{ Программа № 2F. Теннис }

{ --------------------------------------------------- }

{ Вася, Петя и Коля играли в теннис навылет }

{ (проигравший пропускал следующую партию, уступая }

{ свое место третьему). Вася утверждает, что сыграл x}

{ партий, Петя – что сыграл y партий, Коля – z партий}

{ Определите, могло ли такое быть. }

{ Тема: [Условный оператор (if)] }

{ Источник: http://informatics.mccme.ru/ }

{ Командные олимпиады, Турнир Архимеда,2008, Задача E }

{ --------------------------------------------------- }

program task_2f;

var x, y, z: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(x,y,z);

if (x+y+z>1)and((x+y=z)or(y+z=x)or(x+z=y)) then writeln(‘YES’)

else writeln(‘NO’)

end.



Задача 2G. Пирожки

Разбор

Так как нашему герою надо максимизировать количество купленных пирожков, то логично начинать покупки с самого дешёвого из них. Поэтому сначала поменяем местами введённые данные так, чтобы стоимости не убывали. Тогда пирожков первого типа Петя может купить [ s/c1 ] (где [a] – целая часть от a ), но не более, чем их есть в продаже (то есть не более n1 ). Готовая формула получается min {n1, [ s/c1 ]}.

Аналогично рассчитываются покупки пирожков других типов (с учётом того, что часть денег уже потрачена). Подводным камнем в этой задаче является наличие нулей во входных данных (даже в цене пирожка). Поэтому каждую операцию деления следует обработать в условии.

Решение

{ Программа № 2G. Пирожки }

{ --------------------------------------------------- }

{ Однажды Петя зашел в буфет и увидел, что в продаже }

{ присутствуют пирожки с картошкой, капустой и рисом. }

{ Петя желает купить как можно больше пирожков, но }

{ количество пирожков в продаже ограничено так же, }

{ как и количество денег у Пети. Помогите Пете }

{ определить максимально возможное количество }

{ пирожков, которые он может купить }

{ Тема: [Условный оператор (if)] }

{ Источник: "Муниципальный этап Всероссийской }

{ олимпиады школьников Красноярского края }

{ по информатике, 7-8 классы" 2013, Задача С }

{ --------------------------------------------------- }

program task_2g;

uses math;

var

c1, c2, c3, n1, n2, n3, s, t, r, tmp : Int64;

begin

assign(input, 'input.txt'); reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(c1, c2, c3, n1, n2, n3, s);

if c1 > c2 then begin

t := c1; c1 := c2; c2 := t;

t := n1; n1 := n2; n2 := t;

end;

if c2 > c3 then begin

t := c2; c2 := c3; c3 := t;

t := n2; n2 := n3; n3 := t;

end;

if c1 > c2 then begin

t := c1; c1 := c2; c2 := t;

t := n1; n1 := n2; n2 := t;

end;

if c1 <> 0 then tmp := s div c1

else tmp := n1;

r := min(n1, tmp);

dec(s, r*c1);

if c2 <> 0 then tmp := s div c2

else tmp := n2;

t := min(n2, tmp);

dec(s, t*c2);

inc(r, t);

if c3 <> 0 then tmp := s div c3

else tmp := n3;

inc(r, min(n3, tmp));

Write(r);

end.



Задача 2H. Кольцевая

Разбор

Посчитаем сколько проехали автомобили, сложим и возьмем по модулю L - это одна из дуг. Вычитаем ее длину из L и получаем вторую дугу. Ответ - минимум из двух дуг.

Решение

{ Программа № 2H. Кольцевая }

{ --------------------------------------------------- }

{ Два автомобиля движутся по кольцевой дороге длины L }

{ в противоположных направлениях. Они начинают }

{ движение из одной точки и едут с постоянными }

{ скоростями  v1 и v2 соответственно. }

{ Требуется определить, на каком расстоянии друг от }

{ друга они окажутся в момент времени T. }

{ Тема: [Условный оператор (if)] }

{ Источник: http://informatics.mccme.ru/ }

{ Командные олимпиадыТурнир Архимеда2008,Задача G}

{ --------------------------------------------------- }

program task_2h;

var

L,T,v1,v2,s1,s2: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(L,v1,v2,T);

s1:=(v1*T + v2*T) mod L;

s2:= L - s1;

if s1 < s2 then writeln(s1)

else writeln(s2);

end.



Задача 2I. Паркет - 2

Разбор

Из школьного курса математики известно, что сумма углов в n-угольнике равна 180(n−2) градусов, тогда один угол в правильном n-угольнике равен 180(n−2)/n градусов. Если замостить всю плоскость, то будут вершины, в которых сходятся углы n-угольников. А это значит, что угол в 360 градусов будет состоять из нескольких углов n-угольника. Другими словами 360 должно делиться на 180(n−2)/n , после упрощения получаем, что 2n должно делиться на n−2. Либо можно было заметить, что это выполняется лишь для n=3 , n=4 и n=6 .

Решение

{ Программа № 2I. Паркет-2 }

{ --------------------------------------------------- }

{ Определить, можно ли замостить бесконечную }

{ плоскость правильными многоугольниками без пробелов }

{ и перекрытий. Все многоугольники должны иметь }

{ равное количество вершин и размеры. Например, лист }

{ тетради в клетку – пример замощения плоскости }

{ квадратами. Дано целое число N – количество вершин }

{ в правильном многоугольнике. Выведите «YES», если }

{ плоскость можно замостить и «NO» в противном случае }

{ Тема: [Условный оператор (if)] }

{ Источник: Полуфинал XIV Всероссийской командной }

{ олимпиады школьников по программированию }

{ (Восточно-Сибирский регион)", Задача B. }

{ --------------------------------------------------- }

Program task_2i;

var n, t : int64;

begin

assign(input, 'input.txt'); reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(n);

if 2*n mod (n-2) = 0 then WriteLn('YES')

else WriteLn('NO');

end.



Задача 2J.№845. СтатГрад

Разбор

Если с=a and c

Решение

{ Программа № 2j. СтатГрад }

{ --------------------------------------------------- }

{ В Москве установили счетчики системы СтатГрад для }

{ учета и контроля над силой града. Каждый счетчик }

{ системы учитывает количество попаданий в него }

{ градин за сутки. Если в него попадает меньше }

{ a градин, то он передает сигнал NO GRAD. Если }

{ попадает не меньше a градин, но меньше b градин, }

{ то он передает сигнал GRAD. Если больше либо равно }

{ b градин – то он ломается, и не передает никакого }

{ сигнала. Даны числа a и b (a < b), а также }

{ количество попавших в счетчик градин. }

{ Требуется определить, какой сигнал нужно передать. }

{ Тема:  }

{ Источник: }

{ , , , Задача A }

{ --------------------------------------------------- }

program task_2j;

var

a,b,c: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(a,b,c);

if c < a then writeln(NO GRAD)

else if c < b then writeln(GRAD);

end.



Задача 2K. Точки на окружности

Разбор

Если количество точек нечетное, то помечены будут все точки. В случае нечетного количества точек, непомеченных точек будет ровно половина.

Решение

{ Программа № 2K. Точки на окружности }

{ --------------------------------------------------- }

{ На окружности на равном расстоянии друг от друга }

{ расположены N точек. Мы произвольно выбираем одну }

{ из этих точек и помечаем ее красным крестиком. }

{ Двигаясь по часовой стрелке вдоль окружности, }

{ помечаем каждую вторую встретившуюся точку. Так }

{ будем делать до тех пор, пока не дойдем до }

{ помеченной точки. В результате, некоторые из точек }

{ будут помечены, а какие-то нет. Ваша задача }

{ определить количество непомеченных точек. }

{ Тема: [Арифметические алгоритмы][Условный оператор] }

{ Источник: Тестовая олимпиада школьников }

{ по информатике 24.09.2009, Задача 6 }

{ --------------------------------------------------- }

program task_2k;

var

k,n: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(n);

if n mod 2 = 0 then

k:=n div 2

else k:=0;

writeln(k);

end.


Задача 2L. Часы

Решение

{ Задача 2L. Часы }

{ --------------------------------------------------- }

{ Часы представляются кругом с числами от 1 до 12. }

{ Ваша задача — с точностью до 5 минут определить }

{ время по положению стрелок, используя те числа на }

{ циферблате, которые наиболее близки к стрелкам. }

{ Правила определения времени следующие. }

{ Если минутная стрелка находится ближе всего }

{ к числам 1, 2, 3, …, 11, то она определяет }

{ соответственно 5, 10, 15, …, 55 минут. Если же она }

{ находится наиболее близко к числу 12, то считается, }

{ что она задает 0 минут. Если минутная стрелка }

{ наиболее близко подошла к числам 12, 1, 2, 3, 4 }

{ или 5, то считается, что часы определяется тем }

{ числом, к которому наиболее близка часовая стрелка.}

{ Однако, если же минутная стрелка ближе всего }

{ к числам 6, 7, 8, 9, 10 или 11, то часы задаются }

{ числом, предшествующим тому числу, к которому }

{ наиболее близко подошла часовая стрелка. }

{ Источник: Школьная олимпиада по информатике 2012 г. }

{ 5-7 класс, Задача 1.

{ --------------------------------------------------- }

program task_2l;

var h, m,h1,m1: byte;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(h,m);

if (m>=1) and (m<=11) then m1:=m*5

else m1:=0;

if (m>=6) and (m<=11) then h1:=h-1

else h1:=h;

if h1=0 then h1:=12;

if m1<10 then writeln(h1,':0',m1)

else writeln(h1,':',m1);

end.



Задача 2M. Красная шапочка

Разбор

Сначала делим количество пирожков пополам. Если их больше либо равно 10, то тогда выгоднее отдать 10 пирожков лесничему, а иначе просто отдать половину имеющихся волку.

Решение

{ Программа № 2М. Красная шапочка }

{ --------------------------------------------------- }

{ Красная Шапочка часто навещает свою бабушку. Но она }

{ очень боится волка. Поэтому она решила договориться }

{ с Лесничим об охране бабушки. Лесничий согласился }

{ охранять бабушку за 10 пирожков. Узнав об этом, }

{ волк сказал Красной Шапочке, что ей незачем тратить }

{ пирожки на Лесничего. За половину тех пирожков, }

{ которые Красная Шапочка несет бабушке, Волк }

{ пообещал не трогать ее. Мама испекла несколько }

{ пирожков и попросила Красную Шапочку отнести их. }

{ бабушке. Требуется определить, сколько пирожков }

{ Красная Шапочка сможет донести до бабушки }

{ Источник: Школьная командная олимпиада ФМШ № 2007 }

{ г. Москвы, 10-11 классы, 2006-2007, Задача A }

{ --------------------------------------------------- }

program task_2m;

var k,p: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(k);

p:= k div 2;

if p > 9 then writeln(k-10)

else writeln(p)

end.



Задача 2N. Счастливый билет

Разбор

Эта простая классическая задача имеет не единственное решение. Рассмотрим два решения.

Решение 1.

Считаем счастливый билет в целочисленную переменную x и разобьем это число по цифрам так, чтобы первая цифра оказалась в переменной x1, вторая в x2 и т.д. до x6. После чего для того, чтобы убедиться в том, что билет счастливый достаточно сравнить значения x1+x2+x3 и x4+x5+x6. Но как так разбить число на цифры? Для этого можно воспользоваться целочисленным делением и остатком от деления. Например, последняя цифра целого числа x всегда равна x%10 (остатку от деления x на 10), а первая цифра шестизначного числа x всегда равна x/100000 (целочисленному делению х на 100000). Подумайте - почему? С помощью целочисленного деления мы можем от целого числа отбросить любое количество цифр (n цифр), разделив его на 10n целочисленно, а с помощью остатка от деления на 10 мы получаем последнюю цифру. Например, в нашем случае x3=x/1000%10.

Решение 2.

Можно счастливый билет считать в строковую переменную и полагая, что в нем ровно 6 цифр работать с ними как с массивом символов. Билет будет счастливым, если сумма ASCII-кодов первых трех символов равна сумме ASCII-кодов последних трех. На самом деле вовсе не обязательно осуществлять перевод в реальные цифры. На языке Си даже не придется для этого использовать специальную функцию (как ord в паскале).

Решение 1

{ Программа № 2N. Счастливый билет }

{ --------------------------------------------------- }

{ Счастливым билетом называют такой билет }

{ с шестизначным номером, где сумма первых трех цифр }

{ равна сумме последних трех. Требуется написать }

{ программу, которая проверяет счастливость билета }

{ Тема:[ Условный оператор ] }

{ Источник: , }

{ Курс олимпиадника: Решение 1 }

{ --------------------------------------------------- }

program task_2n;

var

n,x1,x2,x3,x4,x5,x6: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(n);

x1:= n div 100000;

x2:= n div 10000 mod 10;

x3:= n div 1000 mod 10;

x4:= n div 100 mod 10;

x5:= n div 10 mod 10;

x6:= n mod 10;

if x1 + x2 + x3 = x4 + x5 + x6

then writeln('YES')

else writeln('NO');

end.

Решение 2

{ Программа № 2N. Счастливый билет }

{ --------------------------------------------------- }

{ Счастливым билетом называют такой билет }

{ с шестизначным номером, где сумма первых трех цифр }

{ равна сумме последних трех. Требуется написать }

{ программу, которая проверяет счастливость билета }

{ Тема:[ Условный оператор ] }

{ Источник: , }

{ Курс олимпиадника: Решение 2 }

{ --------------------------------------------------- }

program task_2n;

var

s: string;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(s);

if ord(s[1])+ord(s[2])+ord(s[3])=ord(s[4])+ord(s[5])+ord(s[6])

then writeln('YES')

else writeln('NO');

end.



Задача 2O.(№1178) Оплата интернета

Разбор

Если Dhello_html_m2b5484ea.pngB, то есть Витя не израсходовал «лишних» мегабайт трафика, выводим A, в противном случае число «лишних» мегабайт составляет DB, следовательно, ответом будет число A+C*(DB).

Решение

{ Задача № 2O. Оплата интернета }

{ --------------------------------------------------- }

{ Ежемесячная абонентская плата составляет A рублей, }

{ и в эту абонентскую плату включено B мегабайт }

{ трафика. Неизрасходованные мегабайты в конце месяца }

{ «сгорают». Если трафик превышает B мегабайт, }

{ то каждый мегабайт трафика сверх предоплаченных }

{стоит C рублей. Известно, что за прошлый месяц Витя }

{ израсходовал D мегабайт трафика. Определите, }

{ во сколько обошелся ему доступ в интернет в прошлом }

{ месяце (считая в том числе и абонентскую плату) }

{ Тема:   }

{ Источник: }

{ , }

{ , , , Задача A }

{ --------------------------------------------------- }

program task_2o;

var a, b, c, d: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(a,b,c,d);

if d <= b then writeln(a)

else writeln(a + c*(d-b))

end.

3. Циклы

Задача 3A. (№1934) Офис

Разбор

Сумма всех чисел во входном файле равна суммарному количеству посещений офиса всеми его работниками в течение месяца. Эта сумма равна числу сотрудников умноженному на 27, так каждый из них посетил офис 27 раз. Получаем формулу: х = s div 27.

Решение

{ Программа № 3A. Офис }

{ --------------------------------------------------- }

{ Вася очень любил смотреть в окно. Напротив его дома }

{ расположился офис некоторой строительной фирмы. }

{ В течение всего месяца Вася наблюдал за его }

{ служащими. Про каждый из 31 дня месяца он знает, }

{ сколько сотрудников пришло на работу. Ему также }

{ известно, что каждый из служащих берет ровно по }

{ 4 выходных в месяц. Напишите программу, которая }

{ определит, сколько всего служащих работает в офисе }

{ Тема: [Арифметические алгоритмы] [Цикл]] }

{ Источник: IV по }

{ программированию, , , Задача B }

{ --------------------------------------------------- }

program task_3a;

var

i, k, s: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

s:=0;

for i:=1 to 31 do begin

read(k); s:=s + k;

end;

writeln(s div 27);

end.


Задача 3B. (№512) Оттепель

Разбор

В цикле проверяем условие temp>0. Пока температура положительна, увеличиваем d – длину текущей на данной момент оттепели, по ее окончанию запоминаем эту длину. Затем сравниваем ее с максимальной длиной и, если надо, изменяем максимальную длину оттепели. Выводим ответ.

Решение

{ Задача № 3b. Оттепель }

{ --------------------------------------------------- }

{ Требуется вывести одно число – длину самой }

{ продолжительной оттепели, то есть наибольшее }

{ количество последовательных дней, на протяжении }

{ которых среднесуточная температура превышала 0 }

{ Темы:   }

{ Источник: }

{ , ,  }

, , Задача B }

{ --------------------------------------------------- }

program task_3b;

var

d, i, k, n, max, temp: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(n);

k:=0; d:=0; max:=0;

for i:=1 to n do begin

read(temp);

if temp > 0 then d:=d + 1

else begin

k:=d;

d:=0;

end;

if k > max then max:=k;

end;

writeln(max);

end.



Задача 3С. Деление с остатком

Разбор


Рассмотрим условия на математическом языке:

Вначале об остатках. Числа могут давать остатки 0 и 1, при делении на 2.

0, 1 и 2 при делении на 3.

0, 1, 2 и 3 при делении на 4. И так далее...

Ну пускай у нас было число n изначально.

Тогда оно могло давать остатки либо 0 либо 1, при делении на 2. Запишем какие действия мог сделать Вася:

1.(n-0)/2 когда n дает остаток 0 при делении на 2.

2.(n-1)/2 когда n дает остаток 1 при делении на 2.

Дальше аналогично действуем и с тройкой, только теперь у нас не одно n как было вначале, а два числа которые мы будем рассматривать, это (n-0)/2 и (n-1)/2.

Рассмотрим эти числа, они могут давать остатки 0, 1 или 2, при делении на 3.

Рассмотрим вначале (n-0)/2

1.((n-0)/2-0)/3 когда (n-0)/2 дает остаток 0 при делении на 3.

2.((n-0)/2-1)/3 когда (n-0)/2 дает остаток 1 при делении на 3.

3.((n-0)/2-2)/3 когда (n-0)/2 дает остаток 2 при делении на 3.

Теперь рассмотрим второе выражение: (n-1)/2

1.((n-1)/2-0)/3 когда (n-1)/2 дает остаток 0 при делении на 3.

2.((n-1)/2-1)/3 когда (n-1)/2 дает остаток 1 при делении на 3.

3.((n-1)/2-2)/3 когда (n-1)/2 дает остаток 2 при делении на 3.

Теперь осталось аналогичным способом эти 6 выражений поделить на 4.

И сразу заметим, что после того как мы разделим эти выражения на 4, то мы получим 25 вариантов числа K, я сразу буду писать получившееся выражение и равно K.

Ну начнем сверху:

1.((n-0)/2-0)/3

1. (((n-0)/2-0)/3-0)/4=K когда ((n-0)/2-0)/3 дает остаток 0 при делении на 4

2. (((n-0)/2-0)/3-1)/4=K когда ((n-0)/2-0)/3 дает остаток 1 при делении на 4

3. (((n-0)/2-0)/3-2)/4=K когда ((n-0)/2-0)/3 дает остаток 2 при делении на 4

4. (((n-0)/2-0)/3-3)/4=K когда ((n-0)/2-0)/3 дает остаток 3 при делении на 4

Потом:

2.((n-0)/2-1)/3

1. (((n-0)/2-1)/3-0)/4=K когда ((n-0)/2-1)/3 дает остаток 0 при делении на 4

2. (((n-0)/2-1)/3-1)/4=K когда ((n-0)/2-1)/3 дает остаток 1 при делении на 4

3. (((n-0)/2-1)/3-2)/4=K когда ((n-0)/2-1)/3 дает остаток 2 при делении на 4

4. (((n-0)/2-1)/3-3)/4=K когда ((n-0)/2-1)/3 дает остаток 3 при делении на 4

Потом:

3.((n-0)/2-2)/3

1. (((n-0)/2-2)/3-0)/4=K когда ((n-0)/2-2)/3 дает остаток 0 при делении на 4

2. (((n-0)/2-2)/3-1)/4=K когда ((n-0)/2-2)/3 дает остаток 1 при делении на 4

3. (((n-0)/2-2)/3-2)/4=K когда ((n-0)/2-2)/3 дает остаток 2 при делении на 4

4. (((n-0)/2-2)/3-3)/4=K когда ((n-0)/2-2)/3 дает остаток 3 при делении на 4

и так далее и получим всего 24 выражения.

Теперь перенесем числа в одну сторону, n останется в другой(ведь K тоже число)

Получим 24 выражения:

1.n=24K+0

2.n=24K+1

3.n=24K+2

4.n=24K+3

5.n=24K+4

6.n=24K+5

7.n=24K+6

8.n=24K+7

9.n=24K+8

10.n=24K+9

11.n=24K+10

12.n=24K+11

13.n=24K+12

14.n=24K+13

15.n=24K+14

16.n=24K+15

17.n=24K+16

18.n=24K+17

19.n=24K+18

20.n=24K+19

21.n=24K+20

22.n=24K+21

23.n=24K+22

24.n=24K+23

Получается что n может быть равно всем вот этим 24 вариантам.

А ведь n это начальное число.

Выведем эти 24 варианта на экран.

Решение

{ Программа № 3С. Деление с остатком }

{ --------------------------------------------------- }

{ Вася учится делить с остатком. Он взял некоторое }

{ число, разделил его на 2 и отбросил остаток. }

{ То, что получилось, разделил на 3 и опять отбросил }

{ остаток. Полученное число разделил на 4, отбросил }

{ остаток и получил число K. Какое число мог выбрать }

{ Вася изначально? }

{ Темы:  }

{ Источник: Школьная олимпиада по Красноярскому краю,}

{7-8 классы, Задача A, 2013/2014 }

{ --------------------------------------------------- }

program task_3С;

var i, k, n: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(k);

for i:=0 to 23 do

write(24*k+i);

end.



Задача 3D.№3903. Количество чисел

Разбор

Автор И.А. Шуйкова

Составим модель задачи

Входные данные: a, b – натуральные числа, не превышающие 10 000 (тип данных integer).

Выходные данные: количество натуральных чисел, состоящих из не менее, чем а цифр и не более, чем b цифр.

Решение задачи

Перед решением задачи необходимо вспомнить все математические определения и термины, которые используются в тексте задачи. Напомним, что натуральные числа – это числа, использующиеся при счете предметов, то есть числа 1, 2, 3 и т.д.

Для решения любой задачи и ее понимания полезно сразу разобрать примеры, приведенные в задаче. Согласно первому примеру при а=1 и b=2, количество натуральных чисел равно 99. Действительно, это числа 1, 2, 3, 4, 5, 6, 7, 8, 9 (они состоят из одной цифры),10,11,…,99 (они состоят из двух цифр). Всего получается 99 чисел.

Согласно второму примеру при а=1 и b=1, количество натуральных чисел равно 9. Действительно, это числа 1, 2, 3, 4, 5, 6, 7, 8, 9 (они состоят из одной цифры).

Когда вы разобрали примеры, приведенные в задаче, и поняли их, полезно будет привести свой пример и разобрать его.

Пример. а=2 и b=2, количество натуральных чисел равно всем двузначным числам: 10,11,12,…,99. Всего получается 99-10+1=90 чисел.

Как видим, в ответах разобранных примеров встречаются только лишь нули и девятки. Если рассмотреть другие примеры, то ответы также будет содержать нули и девятки.

Проанализировав различные ситуации входных данных, можно сделать вывод:

1. При а=b в ответе будет число, состоящее из одной девятки и нулей, количество которых равно (a-1).

2. При ав ответе будет число, состоящее из b цифр. В конце числа (a-1) нулей, а в начале числа – девятки. Количество девяток, таким образом, (b - a+1).

3. При a>b в ответе будет 0 (таких чисел нет).

Таким образом, для решения этой задачи нет необходимости делать какие-либо вычисления. Фрагмент кода задачи приведен ниже и содержит только печать нужного количества девяток и нулей.

for i := a to b do write(9);

for i := 1 to a - 1 do write(0);

Обратите внимание, что предварительно составленная модель задачи позволяет в ряде случаев обойтись без сложных вычислений. Во многих олимпиадных задачах есть «изюминка», увидев которую, вы решите задачу легко и красиво.



Решение

{ Программа № 3D. Количество чисел }

{ --------------------------------------------------- }

{ Сколько всего натуральных чисел состоят из не менее }

{ чем а цифр и не более, чем b цифр?

{ Темы:  }

{ Источник: }

{ , ,, Задача C }

{ --------------------------------------------------- }

program task_3d;

var

a, b, i: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(a, b);

if a > b then write(0)

else begin

for i := a to b do write(9);

for i := 1 to a - 1 do write(0);

end

end.



Задача 3E. Деление без остатка(ЗАДАЧА 3)

Решение

{ Программа 3E. Деление без остатка }

{ --------------------------------------------------- }

{ Дано натуральное число n (n <=1000). Составить }

{ программу для проверки делится ли целое число }

{ на каждую из его цифр без остатка. Напечатать }

{ такие числа в интервале от 10 до n. }

{ Тема: [ Цикл while ] }

{ --------------------------------------------------- }

program task_3e;

var

i,k,n,x: integer;

flag: boolean;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(n);

for i:= 10 to n do begin

flag:=true;

k:=i;

while k > 0 do begin

x:=k mod 10;

if x <> 0 then begin

if (i mod x) <> 0 then flag:=false

end

else flag:=false;

k:=k div 10;

end;

if flag then write(i:5);

end

end.



Задача 3F. Загадка

(Время: 1 сек. Память: 16 Мб Сложность: 18%)

Разбор

Эту задачу можно решить, составив систему из двух уравнений и двух неизвестных:

X+Y=S

X*Y=P

Выразив Х из первого уравнения и подставив во второе, мы получим квадратное уравнение, из которого получим Х, а значит и Y. Но это решение не самое быстрое для реализации. Здесь можно использовать то, что компьютер способен выполнять миллионы простых операций в секунду. Поэтому можно реализовать полный перебор всех вариантов значений X и Y (очевидно, всевозможных значений получится не более миллиона). Причем, для удобства можно сразу положить что X<=Y. Таким образом, мы сократим перебор вариантов вдвое и сможем найти однозначное решение, которое без проблем возможно вывести в порядке неубывания. Следующий алгоритм реализует вышеописанные рассуждения:

read(s,p);

for x=1..1000{

for y=x..1000{

if(x+y==s и x*y==p) write(x,' ',y);

}

}

Необходимо уметь оценивать временную сложность задачи. Несмотря на то, что ЭВМ способна на многое, далеко не любая задача в случае неэффективного ее решения сможет уложиться в требуемые временные ограничения. Например, если бы дипазон чисел Х и Y был в диапазоне до 30000, то такое решение с полным перебором привело бы к провалу, т.к. в этом случае возможно потребовалось бы выполнение порядка миллиарда операций, что вполне сомнительно для ограничений в 1 секунду. Но и в этом случае перебор был бы возможен. Действительно, когда значение X определено, то не обязательно перебирать всевозможные значения Y, т.к. Y=S-X. Поэтому более короткий и быстрый алгоритм решения этой задачи может выглядеть следующим образом:

read(s,p);

for x=1..30000{

y=s-x;

if(x<=y и x*y==p) write(x,' ',y);

}

Решение (вариант 1)

{ Программа 3F. Загадка Вариант 1 }

{ --------------------------------------------------- }

{ Петя и Катя – брат и сестра. Петя – студент, а }

{ Катя – школьница. Петя помогает Кате по математике. }

{ Он задумывает два натуральных числа X и Y(X,Y≤1000) }

{ а Катя должна их отгадать. Для этого Петя делает }

{ две подсказки. Он называет сумму этих чисел S }

{ и их произведение P. }

{ Помогите Кате отгадать задуманные Петей числа. }

{ Тема: [ Цикл for] }

{ --------------------------------------------------- }

program task_3f_v1;

var

s, p, x, y: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(s, p);

for x:= 1 to 1000 do

for y:= x to 1000 do

if (x + y = s) and (x * y = p) then

writeln(x,' ',y)

end.

Решение (вариант 2)

{ Программа 3F. Загадка Вариант 2 }

{ --------------------------------------------------- }

{ Петя и Катя – брат и сестра. Петя – студент, а }

{ Катя – школьница. Петя помогает Кате по математике. }

{ Он задумывает два натуральных числа X и Y(X,Y≤1000) }

{ а Катя должна их отгадать. Для этого Петя делает }

{ две подсказки. Он называет сумму этих чисел S }

{ и их произведение P. }

{ Помогите Кате отгадать задуманные Петей числа. }

{ Тема: [ Цикл for] }

{ --------------------------------------------------- }

program task_3f_v2;

var

s, p, x, y: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(s, p);

for x:= 1 to 30000 do begin

y:= s - x;

if (x <= y) and (x * y = p) then

writeln(x,' ',y)

end

end.

4. Строки

Задача 4A. «У моего папы больше денег»

Разбор

Считываем число строкой. Выводим эту строку и еще одну любую цифру

Решение

{ Программа № 4A. У моего папы больше денег }

{ --------------------------------------------------- }

{ Двое играют в такую игру. Первый называет число, }

{ затем второй называет число. Если число второго }

{ больше, то он выиграл, в противном случае }

{ (даже если числа равны), выиграл первый. Помогите }

{ второму игроку – напишите программу, которая будет }

{ за него успешно играть в эту игру. }

{ Темы:  }

{ Источник: }

{ , ,, Задача C }

{ --------------------------------------------------- }

program task_4a;

var s: string;

n: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(s);

n:=random(5)+1;

writeln(s,n);

end.



Задача 4B. Светофор

Разбор

Так как количество состояний светофора невелико, то можно просто все их перебрать с

помощью составных условий и для каждого варианта вывести правильный ответ.

Приведённый ниже код не требует пояснений.

Решение

{ Программа № 4B. Светофор }

{ --------------------------------------------------- }

{ Рассмотрим обычный автомобильный светофор, }

{ состоящий из трех секций красного, желтого и }

{ зеленого сигналов. Каждая секция может отражать два}

{ цвета: соответствующий ей цвет во включенном }

{ состоянии и черный цвет в выключенном состоянии. }

{ Когда светофор исправен, то ему доступно }

{ 6 возможных состояний. В обычном рабочем режиме }

{ имеем следующий алгоритм работы: }

{ 1.горит только зеленый сигнал; }

{ 2.зеленый сигнал мигает; }

{ 3.гаснет зеленый, загорается желтый; }

{ 4.гаснет желтый, загорается красный; }

{ 5.загорается желтый и горит вместе с красным; }

{ 6.гаснут желтый и красный и повторяем с пункта 1. }

{ Светофор также может работать в режиме }

{ нерегулируемого перекрестка, когда присутствует }

{ только желтый мигающий сигнал }

{ По текущей индикации сигналов светофора следует }

{ определить его следующее состояние, в которое он }

{ должен перейти, либо, что светофор неисправен. }

{ Темы:  }

{ Источник: "Муниципальный этап Всероссийской }

{ олимпиады школьников Красноярского края }

{ по информатике, 7-8 классы" Задача B, 2013 год }

{ --------------------------------------------------- }

program task_4b;

var s1, s2, s3 : String;

begin

assign(input, 'input.txt'); reset(input);

assign(output, 'output.txt'); rewrite(output);

ReadLn(s1); ReadLn(s2); ReadLn(s3);

if (s1='black')and(s2='black')and(s3='green') then begin

WriteLn(s1); WriteLn(s2); WriteLn('GREEN');

end else

if (s1='black')and(s2='black')and(s3='GREEN') then begin

WriteLn(s1); WriteLn('yellow'); WriteLn(s1);

end else

if (s1='black')and(s2='yellow')and(s3='black') then begin

WriteLn('red'); WriteLn(s1); WriteLn(s1);

end else

if (s1='red')and(s2='black')and (s3='black') then begin

WriteLn(s1); WriteLn('yellow'); WriteLn(s3);

end else

if (s1='red')and(s2='yellow')and(s3='black') then begin

WriteLn(s3); WriteLn(s3); WriteLn('green');

end else

if (s1='black')and(s2='YELLOW')and(s3='black') then begin

WriteLn(s1); WriteLn(s2); WriteLn(s3);

end

else WriteLn('error');

end.

Задача 4C. Трудная задача

Разбор

Удобнее всего будет считать число строкой, а затем просто пробежаться циклом по строке и занести каждую цифру в массив (целочисленный!). При этом проверяем, если элемент массива больше пяти, то целочисленно делим его на 2. При выводе массива на экран, выводим только нечетные числа.

Решение

{ Программа № 4C. Трудная задача }

{ --------------------------------------------------- }

{ Витя пригласил своего друга Сергея в гости, но не }

{ сказал ему код от цифрового замка своего подьезда, }

{ а послал следующее SMS-сообщение: }

{ В последовательности цифр 3182 все цифры больше 5 }

{ разделить на 2 (при необходимости отбросив остаток) }

{ а затем удалить из полученной последовательности }

{ все четные цифры. Какой код получил Сергей, }

{ выполнив указанные в сообщении действия? }

{ Темы:  }

{ Источник: }

{ , , , Задача D

{ --------------------------------------------------- }

program task_4c;

var a: array[1..4] of integer;

s: string; i,k,n: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(s); n:=length(s);

for i:=1 to n do begin

val(copy(s,i,1),a[i],k);

if a[i] mod 2 = 0 then a[i]:=a[i] div 2;

if a[i] mod 2 <> 0 then write(a[i]);

end;

end.



Задача 4D. Шашки - 2

Разбор

Данную задачу можно решить моделированием ходов шашки. Заведём массив 8х8 и поставим единичку в исходную позицию шашки. А затем пройдём циклами по всему массиву и проверим в какие клетки можно попасть. Это можно сделать, если хотя бы одна из соседних по диагонали снизу клеток равна единице. Если массив проходить внизу вверх, то, при рассмотрении ряда, все достижимые клетки нижнего ряда будут известны и это позволит найти все достижимые клетки текущего ряда. Но эта задача подразумевает ответ YES или NO, поэтому на ней можно набрать много баллов, не имея правильного решения. Самый простой вариант – всегда выводить слово YES. Можно добавить проверку второго значения в координате шашки и отловить варианты, когда подразумевается ход назад. А также можно добавить проверку на цвет клетки. Цвет клетки зависит от чётности суммы номеров строки и столбца. Такое частичное решение набирает уже почти полный балл.

Решение

{ Программа № 4D. Шашки-2 }

{ --------------------------------------------------- }

{ На доске стоит белая шашка. Требуется определить, }

{ может ли она попасть в заданную клетку, делая ходы }

{ по правилам (не превращаясь в дамку). }

{ Доска имеет размер 8 x 8, вертикали нумеруются }

{ маленькими латинскими буквами от a до h, }

{ горизонтали - числами от 1 до 8. Белая шашка }

{ ходит по чёрным полям по диагонали вверх. }

{ Темы:  }

{ Источник: Школьная олимпиада по Красноярскому краю,}

{ 7-8 классы, Задача D, 2013/2014 }

{ --------------------------------------------------- }

program task_4d;

var i,i1,i2: Longint;

j,j1,j2: Char;

mm: array [1..8,'a'..'h'] of Longint;

s: string;

begin

assign(input, 'input.txt'); reset(input);

assign(output, 'output.txt'); rewrite(output);

read(s);

j1:=s[1];

i1:=ord(s[2])-48;

j2:=s[4];

i2:=ord(s[5])-48;

mm[i1][j1] := 1;

for i:=i1+1 to 8 do

for j:='a' to 'h' do

if (j>'a') and (mm[i-1][chr(ord(j)-1)]>0) or

(j<'h') and (mm[i-1][chr(ord(j)+1)]>0) then

mm[i][j] := 1;

if mm[i2][j2]>0 then Write('YES')

else Write('NO');

end.

Задача 4E. Сжатие бинарных последовательностей

Разбор

В этой задаче надо понимать, что все буквы тоже имеют свой числовой код (ASCII-код). Например буква «a» имеет код 97. А также к ним тоже можно прибавлять целые числа, получая другие символы. Например, если к «a» прибавить один, то получим «b». В С++ это можно так и писать, а в Паскале всё приходится делать с помощью функций ord и chr . Одним проходом по строке будем считать количество подряд идущих нулей, а когда встречаем единицу, то сразу выводить полученную букву.

Решение

{ Программа № 4E. Сжатие бинарных последовательностей }

{ --------------------------------------------------- }

{ Последовательность из символов «0» и «1» называется }

{ бинарной. Они широко применяются в информатике. }

{ Одно из неудобств бинарных последовательностей – их }

{ трудно запоминать. Для решения этой проблемы были }

{ предложены разные способы их сжатия. Программист }

{ Слава использует следующий способ: просматривая }

{ последовательность слева направо, он заменяет }

{ «1» на «a», «01» на «b», «001» на «c», …, }

{ «00000000000000000000000001» на «z». Напишите }

{ программу, которая поможет автоматизировать процесс }

{ Темы:  }

{ Источник: "Муниципальный этап Всероссийской }

{ олимпиады школьников Красноярского края }

{ по информатике, 7-8 классы" Задача D, 2013 год }

{ --------------------------------------------------- }

program task_4e;

var s: String;

i,c: Longint;

begin

assign(input, 'input.txt'); reset(input);

assign(output, 'output.txt'); rewrite(output);

ReadLn(s);

for i:=1 to length(s) do

if s[i] = '1' then begin

Write(chr(97+c));

c := 0;

end else inc(c);

end.



Задача 4F. Число

Решение

{ Программа № 4F. Число }

{ --------------------------------------------------- }

{ Вводится натуральное число. Требуется разделить }

{ запятыми тройки его цифр (считая справа). }

{ Темы: [Условный оператор(if), Строки] }

{ Источник: }

{ , ,, Задача C }

{ --------------------------------------------------- }

program task_4f;

var s: string;

i,n: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(s);

n:=length(s);

for i:=1 to n do begin

write(s[i]);

if ((n-i) mod 3 = 0) and (i<>n) then write(',');

end;

end.


Задача 4G (№509). Количество слов

Разбор


Вместо того чтобы считать буквы слов можно считать только их первые буквы. Какая буква является первой буквой слова? Любая, слева от которой стоит не буква. Исключение составляет буква, слева от которой стоит символ “-“, а перед ним - буква. Мы вводим строку s и перед ней ставим два символа “!!”:

s = “!!” + s;

После этого циклом пробегаем по массиву строк с счетчиком i где первоначально I = 3 и это выглядит таким образом

for i:=3 to length(s) do

Теперь зададим несколько условий:

Если s[i] в [‘a’..’z’, ‘A’..’Z’] {s[i] - буква} и

не (s[i-1] в [’a’..’z’, ’A’..’Z’]) {s[i-1] – не буква} и

не ((s[i-1]=’-‘) и (s[i-2] в [‘a’..’z’,’A’..’Z’])) {s[i-1] – не дефис} то тогда k := k + 1;

Теперь решение этой задачи находиться в переменной k, но не забудьте что k первоначально равна 0).

Решение

{ Программа № 4G. Количество слов }

{ --------------------------------------------------- }

{ Напишите программу, определяющую, сколько слов }

{ в данной строке текста. }

{ Темы: [Строки] [Условный оператор(if)] }

{ Источник: }

{ , , , }

{ [Задача D] }

{ --------------------------------------------------- }

program task_4g;

var s: string;

i, k, n: integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(s);

s:='!!' + s;

n:=length(s);

k:=0;

for i:=3 to n do

if (s[i] in ['A'..'Z', 'a'..'z']) and

not (s[i-1] in ['A'..'Z','a'..'z']) and

not((s[i-1]='-') and (s[i-2] in ['A'..'Z','a'..'z']))

then inc(k);

writeln(k);

end.


Задача 4H. Нули

Разбор

Решение №1

Здесь можно определить некоторую переменную-счетчик, в которой хранить текущее количество непрерывно идущих нулей при просмотре последовательности слева направо (можно и справа налево). При этом, если встречается единица, то нужно сбросить значение счетчика на ноль. Просматривая список нужно сверять значение счетчика с максимальным ранее найденным и таким образом запоминать максимальное. Считывать данные можно как в одну строку, обрабатывая нули и единицы как элементы массива, либо читать посимвольно до окончания потока данных.

c=max=0;

while(not EOF){

read(x);

if(x=='0') c=c+1;

else c=0;

if(c>max) max=c;

}

write(max);

Решение №2

Можно использовать другой подход к решению этой задачи. Проверить наличие подпоследовательности из k нулей в исходной строке можно с помощью функции pos в Паскале. Используя это можно создать некоторую строку с нулем, которую последовательно удлинять на один ноль и каждый раз проверять имеется ли такая подстрока в исходной до тех пор, пока такая подстрока существует. Длина последней существующей подстроки нулей и будет ответом.

p='0';

read(s);

while(p содержится в s) p=p+'0';

write(len(p)-1);

Решение

{ Программа № 4H. Нули }

{ --------------------------------------------------- }

{ Требуется найти самую длинную непрерывную цепочку }

{ нулей в последовательности нулей и единиц. }

{ Темы: [Строки] [Условный оператор(if)] }

{ --------------------------------------------------- }

program task_4h;

var

p,s: string;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

p:='0'; {создадим некоторую строку с нулем}

read(s);

while (pos(p,s)>0) do {пока(p содержится в s) }

p:= p + '0'; {удлиняем p на один ноль}

writeln(length(p)-1);

end.

5. Массивы

Задача 5A. Бег по эскалатору

Разбор

Так как на эскалаторе нельзя обгонять, то расположим всех людей в порядке увеличения стартовой ступеньки. Это можно сделать с помощью алгоритма сортировки. Количество людей достаточно велико, поэтому квадратичные алгоритмы не подходят для этой задачи. В С++ можно воспользоваться стандартной библиотекой шаблонов и применить процедуру sort. В Паскале же придётся написать быструю сортировку Хоара (или любой другой алгоритм сортировки с асимптотикой времени работы не хуже O(NlogN ) самостоятельно.

Заметим, что нет необходимости сортировать сами данные. Можно завести ещё один массив с номерами людей и сортировать его. То есть расположить номера людей в порядке возрастания стартовой ступеньки (такой вариант реализован в решении на Паскале).

Если бы на эскалаторе был только i -ый человек, то его время прибытия было равно tiwi . Но у него есть помеха – тот, кто идёт перед ним. Тогда итоговое время будет Ti=max {T i1 ,tiwi }. И рассматривать людей следует снизу вверх.

Осталось дело за малым – вести полученные результаты в нужном порядке. В решении на Паскале (так как менялись номера людей, а не сами данные) всё выводится по порядку.

Решение

{ Программа № 5А. Бег по эскалатору }

{ --------------------------------------------------- }

{ Пусть N человек бегут вниз по эскалатору, причем }

{ i-ый пробегает одну ступеньку за ti секунд. }

{ По технике безопасности бега по эскалатору, }

{ на эскалаторе запрещены «обгоны», то есть если }

{ человек A в процессе бега догнал человека B, }

{ который бежит с более низкой скоростью, то до конца }

{ эскалатора, человек A бежит со скоростью человека B }

{ Однако ступени эскалатора таковы, что на них может }

{ помещаться несколько человек одновременно. }

{ Написать программу, которая поможет рассчитать, }

{ когда закончит бег по эскалатору каждый человек }

{ Темы:  }

{ Источник: "Муниципальный этап Всероссийской }

{ олимпиады школьников Красноярского края }

{ по информатике, 7-8 классы" Задача D, 2013 год }

{ --------------------------------------------------- }

program task_5a;

{uses math;}

var n, i : Longint;

mm: array [0..100500,0..1] of Longint;

tmp: Longint;

res: array [0..100500] of Longint;

m: array [0..100500] of Longint;

procedure qs(l, r : Longint);

var i, j, x, t : Longint;

begin

i:= l;

j:= r;

x:= mm[m[l + random(r-l)], 1];

repeat

while mm[m[i], 1] < x do inc(i);

while mm[m[j], 1] > x do dec(j);

if i <= j then begin

t := m[i];

m[i] := m[j];

m[j] := t;

inc(i);

dec(j);

end;

until i>j;

if l < j then qs(l, j);

if r > i then qs(i, r);

end;

begin

randomize;

assign(input, 'input.txt'); reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(n);

tmp:= 1;

for i:=0 to n-1 do begin

Read(mm[i, 0], mm[i, 1]);

m[i] := i;

res[i] := tmp * mm[i, 0] * mm[i, 1];

end;

qs(0, n-1);

for i:=1 to n-1 do

res[m[i]] := max(res[m[i]], res[m[i-1]]);

for i:=0 to n-1 do WriteLn(res[i]);

end.



Задача 5B. Азартный Шрэк

Разбор

Так как надо найти наибольший выигрыш, значит, Шрэк должен взять карточки с самыми большими числами, а крупье достанутся все остальные. Для решения этой задачи можно воспользоваться одним из алгоритмов сортировки. После того как числа в массиве станут упорядочены по возрастанию, достаточно сложить числа второй половины массива и вычесть числа из первой. Ниже в решении приведён пример сортировки.

Решение

{ Программа № 5B. Азартный Шрек }

{ --------------------------------------------------- }

{ На игровом столе лежат N карточек. На каждой }

{ карточке написано целое положительное число. Игра }

{ проходит между игроком и крупье. Карточки лежат на }

{ столе числами вниз. Игра заключается в том, что }

{ игрок открывает ровно N/2 карточек. Сумма всех }

{ чисел, написанных на карточках открытых игроком, }

{ называется “суммой игрока”. Следующим ходом крупье }

{ открывает оставшиеся N/2 карточек. Сумма всех чисел }

{ написанных на карточках открытых крупье, называется }

{ “суммой крупье”. Выигрыш игрока определяется }

{ разностью между “суммой игрока” и “суммой крупье”. }

{ Полученная разность может быть отрицательным числом }

{ Это свидетельствует о том, что игрок проиграл и }

{ должен казино соответствующую сумму. Шрек обладает }

{ способностью видеть надписи сквозь бумагу любой }

{ плотности. Вам нужно определить максимальную сумму }

{ выигрыша, которую может получить Шрек с учетом того }

{ что он видит все числа, написанные на карточках. }

{ Темы:  }

{ Источник: Школьная олимпиада по Красноярскому краю, }

{7-8 классы, Задача С, 2013/2014 }

{ --------------------------------------------------- }

program task_5b;

var n, i, a, r : Longint;

m : array [0..105] of Longint;

begin

assign(input, 'input.txt'); reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(n);

for i:=0 to n-1 do Read(m[i]);

i := 0;

while i < n-1 do

if m[i] > m[i+1] then begin

a := m[i];

m[i] := m[i+1];

m[i+1] := a;

if i > 0 then dec(i);

end

else inc(i);

for i:=0 to n-1 do

if i < n div 2 then dec(r, m[i])

else inc(r, m[i]);

Write(r);

end.

Задача 5С. Лестница (Пример #1)

Разбор

Пусть K(10) -количество способов подъема на 10 ступеньку. Определим подзадачу K(i) нашей задачи как количество способов подъема на i-ю ступеньку.

Исходя из условия задачи, на 10 ступеньку можно подняться непосредственно с 8-й и 9-й ступенек. Поэтому, если мы знаем количество способов подъема K(8) и K(9) на 8 и 9 ступеньки соответственно, то количество способов подъема на 10 ступеньку может быть определено как K(10) = K(8) + K(9).

Такое соотношение получается потому, что любой способ подъема на 8-ю ступеньку превращается в способ подъема на 10-ю ступеньку добавлением перешагивания через 9-ю ступеньку, а любой способ подъема на 9-ю ступеньку превращается в способ подъема на 10-ю ступеньку добавлением подъема с 9 на 10-ю ступеньку. Все эти способы различны. Аналогичное соотношение справедливо для любой ступеньки i, начиная с третьей, т.е.

K(i) = K(i - 2) + K(i - 1).

Осталось определить значения K(1) и K(2), которые равны: K(1) = 1, K(2) = 2.

Следовательно, для решения задачи достаточно одномерной таблицы с 10 - ю элементами, для которой необходимо последовательно вычислить значения элементов таблицы согласно приведенным выше рекуррентным соотношениям. Для одномерной таблицы таким способом обычно является последовательное вычисление элементов, начиная с первого.

K[1]: = 1;

K[2]: = 2;

For i:=3 to 10 do

K[i]: = K[i - 1] + K[i - 2]

Таким образом, размерность таблицы, достаточная для реализации рекуррентных соотношений, определяется количеством аргументов у функций, соответствующих подзадачам. Количество же элементов по каждой размерности (количество элементов в строках, столбцах) определяется количеством возможных значений соответствующего аргумента.

Решение

{ Программа № 5С. Лестница }

{ --------------------------------------------------- }

{ Определить, сколькими различными способами можно }

{ подняться на 10-ю ступеньку лестницы, если за }

{ один шаг можно подниматься на следующую ступеньку }

{ или через одну. }

{ Темы: [ Динамическое программирование ] }

{ --------------------------------------------------- }

program task_5c;

var

n, i: integer;

k : array [0..10] of integer;

begin

assign(input, 'input.txt'); reset(input);

assign(output, 'output.txt'); rewrite(output);

Readln(n);

K[1]:= 1;

K[2]:= 2;

For i:=3 to n do

K[i]:= K[i-1] + K[i-2];

writeln(K[n])

end.



Задача 5Е. Считалочка

Разбор

Сначала необходимо посчитать количество слов в считалочке. Это можно сделать например так: изначально счетчик равен 1. Пробегаемся по строке и видя пробел увеличиваем на 1 счетчик. Далее запоминаем массив строк, - каждая строка имя участника. Вычисляем водящего и выводим строку с нужным номером.

Решение

{ Программа № 5E. Считалочка }

{ --------------------------------------------------- }

{ Дети решили поиграть в догонялки, и, чтобы выбрать }

{ водящего, встали в круг и стали считаться. }

{ Для этого они использовали считалочку. Показывая }

{ по очереди на каждого стоящего в кругу, считающий }

{ произносит одно слово, и тот, на кого придется }

{ последнее слово, и будет водить. Требуется по }

{ данной считалочке определить, кто же будет водить. }

{ Темы: [ Массивы ] [Условный оператор (if)] }

{ Источник: }

{ , ,, Задача E }

{ --------------------------------------------------- }

program task_5e;

const m=100;

var c,k,i,j,n: integer;

s: string;

a: array[1..m] of string;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(s);

n:=length(s);

{считаем количество слов в считалочке}

k:=1;

for i:=1 to n-1 do

if (copy(s,i,1)=' ')and(copy(s,i+1,1)<>' ') then k:=k+1;

{Разбираем строку со списком имен, поместив каждое имя в ячейку массива}

c:=0;

readln(s);

n:=length(s);

for i:=1 to n do

if copy(s,i,1)=' ' then c:=c+1;

c:=c+1; j:=1;

for i:=1 to n do

if copy(s,i,1)=' ' then j:=j+1

else a[j]:= a[j]+ copy(s,i,1);

if (k < c) or (k mod c = 0) then writeln(a[k])

else writeln(a[k mod c]);

end.



Краткое описание документа:

Сборник олимпиадных задач для учащихся 7-8 классов, начинающих изучение языка программирования Pascal и имеющих некоторые знания в области программирования на уровне понимания синтаксиса языка и простейших алгоритмов. Содержит  набор задач, сложность которых растет от темы к теме. Для многих рассматриваемых задач приведен разбор их решений, а также один из возможных вариантов решения на языке Pascal. Но мы рекомендуем Вам сначала попытаться их решить самостоятельно, и лишь в том случае, когда это сделать не получается, прибегать к просмотру их решения. Для составления сборника были использованы задания Всероссийской олимпиады школьников по информатике, а также региональных, муниципальных и школьных олимпиад прошлых лет. 

Автор
Дата добавления 02.11.2014
Раздел Информатика
Подраздел Конспекты
Просмотров4001
Номер материала 106845
Получить свидетельство о публикации

"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ


Идёт приём заявок на международный конкурс по математике "Весенний марафон" для учеников 1-11 классов и дошкольников

Уникальность конкурса в преимуществах для учителей и учеников:

1. Задания подходят для учеников с любым уровнем знаний;
2. Бесплатные наградные документы для учителей;
3. Невероятно низкий орг.взнос - всего 38 рублей;
4. Публикация рейтинга классов по итогам конкурса;
и многое другое...

Подайте заявку сейчас - https://urokimatematiki.ru

Похожие материалы

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