Задачи 7-8 класс. Олимпиада 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
Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти: 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

 

 

 

 

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

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

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

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

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

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

Если решение не существует, вывести 0.

Если решение есть, то в первой строке выходной файл должен содержать количество плиток, которое должно быть использовано. Далее выходной файл должен содержать еще 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
Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти: 64 мегабайта
Максимальная оценка: 100 баллов

 

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

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

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

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

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

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

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

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

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

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

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

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

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

input.txt output.txt
6 3

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 расположена в стране Я или наоборот. Выводим любое из них.

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

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

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