Подразделы

Другие разделы

Дата и время

05/11/2024 18:46:54

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printЗадачи очного тура личного первенства 2011

printA. Суперпростые числа

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Назовем число из `n` цифр `a_1\ a_2\ …\ a_n` суперпростым, если числа `a_1\ a_2\ …\ a_k` являются простыми для всех `k` от 1 до `n` включительно.
Найдите все суперпростые числа, состоящие из `n` цифр.
Ввод содержит одно целое число `n` (`1\ ≤\ n\ ≤\ 9`).
Вывести все суперпростые числа из `n` цифр в порядке возрастания, по одному числу в строке. Если ни одного суперпростого числа из `n` цифр не найдено, то вывести сообщение "NO SOLUTION" (без кавычек).

Пример ввода

2

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

23
29
31
37
53
59
71
73
79

printB. Преобразования

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

С натуральным числом, записанном в десятичной системе счисления, разрешается делать следующие операции:
  • дописать в конце цифру 0;
  • дописать в конце цифру 4;
  • разделить на 2 (если число четное).
Напишите программу, которая находит способ получения с помощью этих операций из числа 2 заданного числа `N`.
Ввод содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 10^9`).
Вывести последовательность операций, в результате применения которых получается заданное число `N` (можно вывести любую последовательность, не обязательно кратчайшую, но количество операций не должно превышать 256). Если получить число `N` невозможно, то вывести сообщение "NO SOLUTION" (без кавычек).

Пример ввода

104

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

CAB

printC. Игра

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Есть `N` кучек камней. Двое играющих поочередно берут камни из кучек. Во время хода можно взять любое количество камней из не более чем `K` кучек, и по крайней мере один камень из какой-то кучки должен быть взят. Выигрывает тот, кто возьмет последний камень.
Напишите программу, которая для заданного распределения камней по кучкам определяет, может ли игрок, делающий первый ход, выиграть и какой ход он должен сделать, чтобы выиграть.
Первая строка ввода содержит два целых числа `N` и `K` (`1\ ≤\ K\ <\ N\ ≤\ 100`). Вторая строка содержит `N` целых чисел в диапазоне от 1 до 10000 – количество камней в кучках.
Вывести в первой строке сообщение "YES", если начинающий игрок может выиграть, иначе сообщение "NO". Во второй строке в случае положительного ответа вывести `N` целых чисел – сколько камней нужно взять из соответствующей кучки. Можно вывести любой вариант выигрышного хода.

Пример ввода 1

4 2
10 5 10 15

Пример вывода 1

YES
0 5 0 5

Пример ввода 2

2 1
10 10

Пример вывода 2

NO

printD. Наибольшее число

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Среди `n`-значных чисел, в десятичной записи которых нет цифры 0, найти число, для которого разность между самим числом и произведением его цифр максимальна.
Ввод содержит одно целое число `n` (`1\ ≤\ n\ ≤\ 10000`).
Вывести в первой строке найденное `n`-значное число с указанными свойствами. Если существует несколько таких чисел, то можно вывести любое из них.

Пример ввода

2

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

91

printE. Невидимость

Ограничения: время – 3s/6s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Земной флот должен подобраться незаметно к планете жукеров. Для этого на большом грузовом корабле был установлен генератор поля невидимости. Так как генератор потребляет энергию пропорционально кубу радиуса создаваемого поля, желательно разметить корабль с генератором в точке, где расход энергии на поддержание поля, скрывающего корабли флота, будет минимальным.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 100`) – количество кораблей. Далее следует `N` строк, каждая из которых содержит три целых числа `X_i`, `Y_i`, `Z_i` (`-1000\ ≤\ X_i,\ Y_i,\ Z_i\ ≤\ 1000`) – координаты `i`-го корабля в боевом порядке.
Вывести три вещественных числа `X`, `Y`, `Z` – координаты точки для размещения корабля с генератором с точностью `10^{-5}`.

Пример ввода

3
0 0 0
1 1 0
2 0 0

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

1.00000 0.00000 0.00000
Примечание: проверка будет выполняться по отличию радиуса генерируемого поля невидимости от оптимального значения.

printF. Поход

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Пете нужно подготовить маршрут для похода. У Пети есть карта, на которой для каждого участка местности указана сложность его преодоления. Во время похода можно двигаться только на юг или на восток, переходя с одного участка местности на другой. Петя хочет найти маршрут, сложность которого как можно ближе к заданной сложности `с`. Если есть два маршрута со сложностью `c-d` и `c+d`, то предпочтительнее маршрут меньшей сложности. Из двух маршрутов одинаковой сложности можно выбрать любой.
Первая строка ввода содержит три целых числа – размеры местности `n` и `m` (`2\ ≤\ n,\ m\ ≤\ 100`) и требуемая сложность похода `c` (`0\ ≤\ c\ ≤\ 1000`). Далее следует `n` строк, содержащих по `m` символов – цифры от '0' до '9'. Цифра означает сложность преодоления соответствующего участка местности. Начальная точка маршрута находится верхнем левом углу карты, а конечная – в правом нижнем углу.
Вывести в первой строке сложность найденного маршрута. Во второй строке вывести маршрут как последовательность из `(n+m-2)` букв 'S' (движение на клетку вниз) и 'E' (движение на клетку вправо).

Пример ввода

3 3 7
123
322
931

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

8
ESES

printG. Рассылка информации

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (3)

Староста группы должна сообщить всем студентам в группе некоторую информацию. Так как стоимость разговора у разных операторов сотовой связи различна и может отличаться в зависимости от направления вызова, то необходимо найти способ довести информацию до всех студентов, потратив минимальные средства. Кроме того не у каждого человека есть номера телефонов остальных студентов группы (т.е. `a` может позвонить `b`, а `b` может не знать номер телефона `a`).
Напишите программу, которая определит минимальные затраты на информирование студентов.
Первая строка ввода содержит два целых числа – количество студентов `N` (`1\ ≤\ N\ ≤\ 1000`) и количество каналов связи между студентами `M` (`1\ ≤\ M\ ≤\ 10000`). Далее следует `M` строк, содержащих по три целых числа `a`, `b` и `с` (`0\ ≤\ a,\ b\ ≤\ N-1`, `a\ ≠\ b`, `0\ ≤\ c\ ≤\ 1000`), означающие, что студент `a` может передать информацию студенту `b`, потратив `c` копеек. Номер 0 соответствует старосте группы. Пары студентов (`a`,`b`) в списке каналов связи не повторяются.
Вывести одно целое число – минимальные затраты на информирование. Если разослать информацию невозможно, то вывести сообщение "NO SOLUTION" (без кавычек).

Пример ввода 1

4 5
0 1 10
0 2 10
2 0 20
1 3 20
2 3 30

Пример вывода 1

40

Пример ввода 2

2 1
1 0 10

Пример вывода 2

NO SOLUTION

printH. Кротовые норы

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Петя хочет засыпать в саду несколько кротовых нор. Он сыпет в каждую нору грунт, пока уровень грунта не совпадет с уровнем земли в саду. Этот способ не позволяет засыпать горизонтальную часть норы полностью, так как грунт из вертикальной части норы будет сыпаться только до тех пор, пока не образуется склон с углом 45 градусов. Для упрощения расчетов будем рассматривать двумерную задачу.
15227.png
Напишите программу, которая по схеме кротовых нор вычислит объем грунта, необходимого для засыпания всех нор.
Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N,\ M\ ≤\ 100`) – размеры схемы. Далее следует `N` строк, содержащих по `M` символов '.' (нора) и '#' (земля) – схема кротовых нор. Верхняя граница схемы соответствует уровню земли. Предполагается, что за границами схемы ходов кротов нет.
Вывести одно вещественное число – объем грунта, необходимый для засыпания нор, с точностью `10^{-2}`.

Пример ввода 1

3 7
.####.#
......#
##...#.

Пример вывода 1

6.50

Пример ввода 2

2 3
.#.
...

Пример вывода 2

4.75

printI. Optical Reader

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Professor John decided to apply only multiple-choice tests to his students. In each test, each question will have five alternatives (A, B, C, D, and E), and the teacher will distribute one answer sheet for each student. At the end of the test, the answer sheets will be scanned and processed digitally to obtain the test score for each student. Initially, he asked a nephew, who knows computer programming, to write a program to extract the alternatives marked by the students in the answer sheets. The nephew wrote a good piece of software, but cannot finish it because he needs to study for the ICPC contest.
During processing, the answer sheets are scanned in gray levels between 0 (full black) and 255 (total white). After detecting the position for the five rectangles corresponding to each of the alternatives of a question, the software calculates the average pixel gray level for each rectangle, returning an integer value corresponding to each alternative. If the rectangle was filled properly the average value is zero (all black). If the rectangle was left blank the average value is 255 (white total). Thus, ideally, if the average values for each alternative of a question are (255, 0, 255, 255, 255), we know that the student has marked alternative B for that question. However, as answer sheets are processed individually, the average gray level for a completely filled rectangle is not necessarily 0 (may be higher), and the value for a rectangle not filled is not necessarily 255 (may be less). Professor John determined that rectangle average gray levels would be divided into two classes: those with values equal or lower to 127 are considered black and those with values higher than 127 will be considered white.
Obviously, not necessarily all questions of all sheets are marked correctly. It can happen that a student makes a mistake and marks more than one alternative for the same question, or does not mark any alternative. In such cases, the answer to the question should be disregarded.
Professor John now needs a volunteer to write one program that, given the average gray level values of the five rectangles corresponding to the alternatives of a question, determines which alternative was marked, or whether the answer to the question should be disregarded.
Input
The first line of a input contains an integer `N` indicating the number of questions in the answer sheet (`1\ ≤\ N\ ≤\ 255`).
Each of the `N` following lines describes the response to a question and contains five integers `A`, `B`, `C`, `D` and `E`, indicating the values of average gray levels for each alternative (`0\ ≤\ A,\ B,\ C,\ D,\ E\ ≤\ 255`).
Output
Your program must print `N` lines, each line corresponding to a question. If the answer to the question was correctly filled in the answer sheet, the line should contain the alternative selected ('A', 'B', 'C', 'D' or 'E'). Otherwise, the line should contain the character '*' (asterisk).

Sample Input

7
0 255 255 255 255
255 255 255 255 0
255 255 127 255 255
200 200 200 0 200
200 1 200 200 1
1 2 3 4 5
255 5 200 130 205

Sample Output

A
E
C
D
*
*
B

printJ. Just Prune The List

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

You are given two list of integers. You can remove any number of elements from any of them. You have to ensure that after removing some elements both of the list will contain same elements, but not necessarily in same order. For example consider the following two lists
List #1: 1 2 3 2 1
List #2: 1 2 5 2 3
After removing 1 from first list and 5 from second list, both lists will contain same elements. We will find the following lists after removing two elements.
List #1: 1 2 3 2
List #2: 1 2 2 3
What is the minimum number of elements to be removed to obtain two list having same elements?
Input
First line will contain two integers `N` (`1\ ≤\ N\ ≤\ 100000`), the number of element in the first list and `M` (`1\ ≤\ M\ ≤\ 100000`), the number of element in the second list. The next line will contain `N` integers representing the first list followed by another line having `M` elements representing the second list. Each integers in the input is 32 bit signed integer.
Output
Output a single line containing the number of elements to be removed.

Sample Input

5 5
1 2 3 2 1
1 2 5 2 3

Sample Output

2
loading