Задачи 9-11 класс. Олимпиада 2013

Автор: admin Опубликовано: Дек 10, 2013 В рубрике: Олимпиада

 

Задача 1. Выигрышный билет.

Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти: 64 мегабайта
Максимальная оценка: 100 баллов

Петя и Витя сделали автомат для игры в билеты. Игра состоит в том, что каждый из игроков тянет за ручку автомата и получает билет. Номера билетов представляют собой набор из шести цифр от 0 до 9, причем разные билеты содержат одинаковые наборы цифр, но позиции этих цифр могут быть разные для разных билетов. Выигрывает тот игрок, у которого номер билета больше. Например, если Пете выпал билет с номером 081211, а Вите 101218, то Витя победил.

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

Требуется написать программу, которая поможет Вите выяснить какой билет с наибольшим номером может ему выпасть, если известен номер билета Пети.

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

Входной файл состоит из одной строки, которая содержит шестизначный номер билета Пети без пробелов.

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

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

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

input.txt output.txt
081211 821110
111111 111111

 

Задача 2. Пол.

Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта
Максимальная оценка: 100 баллов

 

Борису Борисовичу необходимо покрыть пол плитками. В его распоряжении есть плитки двух типов 1×2 и 1×3. Пол представляет собой квадратное поле размера N×N, плитки, при этом можно класть горизонтально или вертикально.

Для N=5 это можно сделать, например, так, как показано на рисунке. Плитки занумерованы от 1 до 9, и каждая плитка размера 1×2 представлена двумя своими номерами на рисунке, а каждая плитка размера 1×3 представлена тремя номерами.

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

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

Входной файл содержит целое число N (2 £ N £100).

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

В первой строке выходной файл содержит количество плиток, которое должно быть использовано. Далее выходной файл содержит еще N строк по N чисел в каждой. Числа в строках разделены пробелами. Эти строки описывают таблицу, пример которой изображен на рисунке выше. В этой таблице j-е число в i-й строке указывает номер плитки, которой занята клетка пола в i-й строке и j-ом столбце.

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

input.txt output.txt
5 9

1 2 3 6 6

1 2 3 9 8

1 2 3 9 8

5 5 5 9 8

7 7 4 4 4

2 2

1 1

2 2

 

Задача 3. Заграничные перелеты

Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта
Максимальная оценка: 100 баллов

Капитан Пронин получил в свое распоряжение информацию о перелетах между странами А и Я. Эти страны являются потенциальными противниками нашей страны, и поэтому капитан Пронин решил очень внимательно отнестись к этой информации.

1 2 3 6 6
1 2 3 9 8
1 2 3 9 8
5 5 5 9 8
7 7 4 4 4

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

Требуется написать программу, которая проведет анализ и составит список аэродромов страны А и список аэродромов страны Я.

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

Первая строка входного файла содержит два целых числа N (2 £ N £100) и M (2 £ M £1000). Число N указывает количество аэродромов, а M – количество рейсов в списке капитана Пронина.

Далее идут M строк, каждая из которых содержит описание одного рейса. Рейс описывается двумя числами. Каждое слово представляет код одного из аэродромов и находится в диапазоне от 1 до N. Числа в одной строке разделены ровно одним пробелом.

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

Если правильного решения нет, то нужно вывести число 0.

Если правильное решение есть, то выходной файл должен содержать два целых числа: F – количество аэродромов в стране А, и S – количество аэродромов в стране Я. Между этими числами должен быть ровно один пробел.

Во второй строке должны быть представлены F чисел, описывающих коды аэродромов, находящихся в стране А. Числа должны быть упорядочены по возрастанию. Все числа в строке должны быть разделены одиночными пробелами.

В третьей строке должны быть представлены S чисел, описывающих коды аэродромов, находящихся в стране А. Числа должны быть упорядочены по возрастанию. Все числа в строке должны быть разделены одиночными пробелами.

Если правильное решение не единственно, то можно вывести любое.

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

input.txt output.txt
4 2

1 2

3 4

5 6

3 3

1 4 5

2 3 6

4 4

1 2

1 4

3 2

3 4

2 2

1 3

2 4

 

Пояснения к примеру 2. Аэродром 1 никак не может быть в одной стране с аэродромами 2 и 4, т.к между ними есть рейс, а по условию задачи рейсы есть только для аэродромов разных стран. Значит, аэродром 1 может быть в одной стране только с аэродромом 3. Аналогично рассуждаем в отношении трех других аэродромов. В итоге получаем, что 1 должен быть с 3, а 2 должен быть вместе с 4 в одной стране. Получаем два решения: пара 1, 3 принадлежит стране А, а пара 2, 4 расположена в стране Я или наоборот. Выводим любое из них.

Задача 4. Торт

Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта
Максимальная оценка: 100 баллов

 

Гена принес торт на день рождения Чебурашки. Торт был квадратной формы и Гена воткнул в него свечи в N рядов по N штук в каждой. Причем сделал он это очень аккуратно, так что между соседними свечами получилось одинаковое расстояние, как в горизонтальных рядах, так и в вертикальных столбцах.

Как Вы догадались, Чебурашке исполнилось N2 лет, но он все равно очень любит поиграться с едой. Чебурашка решил вырезать из торта кусок треугольной формы такой, что каждая вершина этого треугольника будет свечкой. Главный вопрос, который теперь волнует Чебурашку: сколько свечек будет на его треугольном куске торта?

Требуется написать программу, которая поможет Чебурашке определить, сколько свечек будет на его треугольном куске торта.

Примечание: все свечки, попавшие на разрез, Чебурашка оставляет на своем куске торта.

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

Первая строка входного файла содержит целое число N (2 £ N £40000) – количество свечек в любом ряду и столбце торта.

Вторая строка содержит числа R1, C1, R2, C2, R3, C3 (2 £ R1C1R2C2R3C3 £ N) разделенные пробелами (один пробел между каждой парой соседей). Числа R1, C1 – номера ряда  и столбца первой свечки, R2, C2 – номера ряда и столбца второй свечки, R3, C3 – номера ряда и столбца третьей свечки. Эти три свечки являются вершинами куска торта, отрезанного Чебурашкой. Гарантируется, что пары координат попарно различны, т.е. треугольник, описывающий Чебурашкин кусок торта, не содержит угла в 180º.

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

Выходной файл содержит целое число, которое означает число свечек в куске торта Чебурашки (включая свечки, попавшие на границу).

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

input.txt output.txt
5

1 1 3 1 2 3

5
10

2 2 3 4 4 3

4

 

Вы можете обсудить этот пост комментариях или в нашем чате, который находится в верхнем правом углу сайта. Если вы не знаете как общаться в чате, то скорее жмите СЮДА! Приятного Вам общения :)

Прокомментировать

Copyright © 2018 Урок информатики All rights reserved.
Тема доработана интернет студией SMOpro, специализация которой реклама в блогах.