Прошел второй контест. Таблица результатов в конце отчета. Были задачи с простыми числами, алгоритм Евклида, одномерные массивы, поиск и сортировка, элементы комбинаторики. Задачи использовались из прошлых чемпионатов по программированию. Две ранее не пробовались в турнирах и одну из них пришлось снять. Вот список задач:
A. Свечи.
Дано N целых чисел. Требуется выбрать из них два таких числа, произведение которых максимально.
Ввод
Вводится сначала число N - количество чисел в последовательности (2 ≤ N ≤ 100). Далее записана сама последовательность: N целых чисел, по модулю не превышающих 1000.
Решение. Конечно, максимум может дать произведение двух отрицательных чисел и задача подразумевает исследование всех возможностей. Но если взглянуть на ограничения, то становится ясным, что пройдет полны перебор. Надо сравнить произведение каждого числа со всеми остальными и выбрать максимальное. Конечно, надо запоминать сомножители, дающие максимальное произведение.
C. Простые числа
Вывести все простые числа от M до N включительно.
Решение. Эта задача раньше не участвовала в турнирах. Я убрала тесты, вызывавшие Time limit (превышение времени), сведя задачу к простой проверке всех чисел в указанном диапазоне на простоту. На самом деле следовало использовать решето Эратосфена.
D. Ребус. Снята с контеста.
E. Книга настоящего программиста
G. Повторяем алгоритм Евклида
H. Сортировка
Сначала задаётся число N (1 ≤ N ≤ 100), а затем N целых чисел, по модулю не превышающих 1000.
Выведите N чисел в порядке неубывания.
Решение. Ограничения задачи таковы, что годится любой алгоритм сортировки.
J. Любопытство.
I. Strong Prime Power
A number which can be represented as pq, where p is a prime number and q is an integer greater than 0, is called a prime power. If q is larger than 1, we call the number a strong prime power. You are given an integer n. If n is a strong prime power, find p and q for it.
Input
The single line contains one integer n (2 ≤ n ≤ 1018). n will contain digits only ('0'-'9') without any leading zeros.
Output
If n is a strong prime power, output p and q in the single line separated by one space. If n is not a strong prime power, output 0 instead.
После дорешивания. Добавленные задачи отмечены красным.
A. Свечи.
Накануне восьмого марта Антон решил устроить Татьяне романтический вечер. Пригласил к себе, приготовил ужин и зажег N свечей разной высоты.
Таня пришла, а Антон решил сделать обстановку еще романтичнее, задувая свечи. Каждая свеча сгорает на сантиметр за минуту. Если свеча была задута, она прекращает уменьшаться в размерах. Если свечу попытались задуть, а она уже сгорела, то ее размер так и остается равным нулю.
После того, как гостья ушла домой, Антон решил узнать, сколько сантиметров свечей у него осталось в сумме.
В первой строке дано число N (1 <= N <= 1000) - количество свечей.
Во второй строке дано N чисел — высоты свечей hi (1 <= hi <= 1000).
В третье строке дано N чисел — время, когда была задута i-я свеча ti (0 <= ti <= 1000).
Решение. Нечего комментировать. Входные данные прочитать в массивы, аккуратно в цикле посчитать длины свечей и сумму длин.
B. Наибольшее произведениеДано N целых чисел. Требуется выбрать из них два таких числа, произведение которых максимально.
Ввод
Вводится сначала число N - количество чисел в последовательности (2 ≤ N ≤ 100). Далее записана сама последовательность: N целых чисел, по модулю не превышающих 1000.
Решение. Конечно, максимум может дать произведение двух отрицательных чисел и задача подразумевает исследование всех возможностей. Но если взглянуть на ограничения, то становится ясным, что пройдет полны перебор. Надо сравнить произведение каждого числа со всеми остальными и выбрать максимальное. Конечно, надо запоминать сомножители, дающие максимальное произведение.
C. Простые числа
Вывести все простые числа от M до N включительно.
Решение. Эта задача раньше не участвовала в турнирах. Я убрала тесты, вызывавшие Time limit (превышение времени), сведя задачу к простой проверке всех чисел в указанном диапазоне на простоту. На самом деле следовало использовать решето Эратосфена.
D. Ребус. Снята с контеста.
E. Книга настоящего программиста
Настоящий программист должен иметь на своей книжной полке хороший набор различных книг, которые помогут ему в его профессиональной карьере. Теоретические труды таких авторов как Д. Кнут, Т. Кормен, Н. Вирт, А. Ахо и других авторов и, конечно же, сборник задач Поповой Н.К. окажут существенную помощь студентам, желающим изучать программирование. К сожалению, не все студенты бережно относятся к своим книгам, и иногда в них заводится книжный червь, который очень любит кушать труды великих авторов. Один новоиспечённый студент купил хороший многотомник по программированию, приколотил к стене полку и выставил на нее вплотную все тома в порядке возрастания номеров слева направо. Однако бедный студент не знал, что внутри первого листа одного из томов притаился математический червяк, бесконечно маленький и очень прожорливый. Червяк стал прогрызать себе путь сквозь тома перпендикулярно плоскости листа. Остановился же он, лишь когда достиг последнего листа другого тома. На следующий день студент обнаружил повреждения и заинтересовался, сколько же миллиметров прогрыз червяк.
Формат входного файла
В первой строке через пробел записаны 4 целых числа — толщина каждого тома (без учета переплета), толщина переплета каждого тома, номер тома, с первого листа которого червяк начал свой путь, и номер тома, на последнем листе которого он остановился. Все числа положительные и не превосходят 100.
Формат выходного файла
Выведите единственное число — длину пути, прогрызенного червяком.
Решение. Простая задача, решение которой требует пространственного воображения. Как только вы правильно представите, как стоят книги на полке, задача тут же будет решена.
F. Вычисляем ПИ
Начиная с 1671 года, когда Джеймс Грегори открыл степенной ряд
arctg x=x-x3/3+x5/5-x7/7+...,
для вычисления числа Pi используется этот ряд. Например, при x=1 получим равенство
Pi/4=1-1/3+1/5-1/7+...+(-1)n/(2n+1)+... (1)
Требуется написать программу, которая по заданному N – количеству членов ряда (1) напечатает приближение к числу Pi с d знаками после десятичной точки.
Input: одна строка, содержащая два натуральных числа N (N ≤ 1000000) и d (d ≤ 8), напечатанные через пробел.
Output: одна строка, содержащая округлённое приближение к числу Pi.
Решение. С учетом подсказки, которая касается вывода ответа с указанным количеством знаков после десятичной точки, задача сводится к вычислению суммы. Заметьте только, что сумму надо увеличить в 4 раза.G. Повторяем алгоритм Евклида
Вася Хвостиков тренируется в исполнении алгоритма Евклида. Он вычисляет наибольший общий делитель (НОД) последовательности натуральных чисел. Сначала берет два натуральных числа из последовательности, вычисляет их НОД, потом берет следующее число из последовательности и вычисляет наибольший общий делитель для этого числа и ранее вычисленного НОД и так повторяет, пока числа не закончатся. Напишите программу, которая может проверить правильность результата для последовательности из N натуральных чисел.
Input: одна строка, содержащая число N, 2 ≤ N ≤ 20, количество натуральных чисел в последовательности и далее N строк, в каждой из которых содержится одно натуральное число, не превосходящее 65535.
Output: одно число – наибольший общий делитель данных N натуральных чисел.
Решение. Сначала читаем два числа и находим их НОД. Дальнейшие действия указаны в условии задачи,H. Сортировка
Сначала задаётся число N (1 ≤ N ≤ 100), а затем N целых чисел, по модулю не превышающих 1000.
Выведите N чисел в порядке неубывания.
Решение. Ограничения задачи таковы, что годится любой алгоритм сортировки.
J. Любопытство.
Межгалактический отдел звездных головоломок «МОЗГ» продолжает исследования на красной планете. В данный момент Curiosity находится находится в кратере потухшего вулкана и должен собрать по 40 образцов красного и синего камней (заумные названия оставим ученым). Сначала марсоход делает одно движение — берет камень и кладет его в отсек для красных камней, если все правильно — продолжаем набирать камни, если же взятый камень оказался синим, система предупреждает об этом, и марсоход делает — второе движение — перекладывает камень в отсек для синих камней, либо отбрасывает в сторону, если отсек заполнен (мы уже нашли 40 синих камней). Как только «красный» отсек заполнен — продолжаем все те же действия для синих камней. Спектральный анализ показал, что вокруг Curiosity лежит A красных камней и B синих.
Формат входного файла
В одной строке даны числа A, B (40 ≤ A, B ≤ 100).
Формат выходного файла
Вывести максимальное количество движений, которое может сделать робот в наихудшем случае, чтобы заполнить отсеки нужным количеством камней.
Решение. Аккуратные рассуждения о худшем случае. Логическая задача.I. Strong Prime Power
A number which can be represented as pq, where p is a prime number and q is an integer greater than 0, is called a prime power. If q is larger than 1, we call the number a strong prime power. You are given an integer n. If n is a strong prime power, find p and q for it.
Input
The single line contains one integer n (2 ≤ n ≤ 1018). n will contain digits only ('0'-'9') without any leading zeros.
Output
If n is a strong prime power, output p and q in the single line separated by one space. If n is not a strong prime power, output 0 instead.
Решение. Сначала перевод с английского. Потом становится ясно, что всего лишь надо проверить, можно ли представить данное число в виде степени (большей 1) некоторого простого числа. Перебор. И хорошо бы иметь список простых чисел.
А теперь результаты!
ЮНИОР
2. 06.07.2016
|
R
|
Участник
|
A
|
B
|
C
|
E
|
F
|
G
|
H
|
I
|
J
|
+
|
T
|
1
|
Алексей Д.
|
+
00:08 |
+
00:37 |
+
01:17 |
3
|
122
|
||||||
2
|
Никита Х.
|
+
00:16 |
+1
01:24 |
+
01:37 |
-1
01:52 |
3
|
217
|
|||||
3
|
Александр С.
|
+1
00:24 |
+
00:49 |
2
|
93
|
|||||||
4
|
Артур К.
|
+
00:35 |
-1
01:30 |
+
01:17 |
2
|
112
|
||||||
5
|
Руслан С.
|
+2
00:49 |
-3
01:11 |
+4
01:39 |
2
|
268
|
||||||
6
|
Алексей Л.
|
+2
00:25 |
1
|
65
|
||||||||
Максим И.
|
-4
01:29 |
-4
01:00 |
0
|
0
|
||||||||
Иван Т.
|
||||||||||||
Ростислав А.
|
||||||||||||
Попыток
|
10
|
5
|
2
|
6
|
2
|
6
|
8
|
1
|
0
|
|||
Из них зачтено
|
6
|
2
|
1
|
1
|
1
|
1
|
3
|
1
|
0
|
|||
Не зачтено
|
4
|
3
|
1
|
5
|
1
|
5
|
5
|
0
|
0
|
|||
|
R
|
Участник
|
A
|
B
|
C
|
E
|
F
|
G
|
H
|
I
|
J
|
+
|
T
|
|
1
|
Алексей Д.
|
+
00:08 |
+
00:37 |
+1
00:57 |
|
|
+
00:00 |
+
01:17 |
|
|
5
|
122
+ 77 |
|
2
|
Никита Х.
|
+
00:16 |
|
+
00:46 |
+2
01:26 |
+1
01:24 |
+
01:37 |
-1
01:52 |
|
|
5
|
217
+172 |
|
3
|
Артур К.
|
+
00:35 |
|
|
|
|
+6
00:34 |
+
01:17 |
|
|
3
|
112
+154 |
|
4
|
Руслан С.
|
+2
00:49 |
-3
01:11 |
+
00:27 |
+4
01:39 |
|
|
|
|
|
3
|
268
+27 |
|
5
|
Алексей Л.
|
+2
00:25 |
|
+1
00:02 |
|
|
|
|
|
|
2
|
65
+22 |
|
6
|
Александр С.
|
|
|
+1
00:24 |
|
|
|
|
+
00:49 |
|
2
|
93
|
|
7
|
Иван Т.
|
+
00:26 |
|
|
|
|
|
|
|
|
1
|
+26
|
|
Максим И.
|
|
|
|
|
|
-4
01:29 |
-4
01:00 |
|
|
0
|
0
|
|
|
|
Ростислав А.
|
|
|
|
|
|
|
|
|
|
|
|
|
Попыток
|
11
|
6
|
8
|
17
|
13
|
6
|
8
|
9
|
0
|
|||
|
Из них зачтено
|
6
|
2
|
5
|
5
|
2
|
1
|
3
|
1
|
0
|
|||
|
Не зачтено
|
4
|
3
|
1
|
5
|
1
|
5
|
5
|
0
|
0
|
|||
Комментариев нет:
Отправить комментарий