7866.png
ЧЕЛЯБИНСК,ЮУРГУ,ИЕТН

Назад

images/home.png Начало
images/balloon.gif Соревнования
2006
Задачи очного тура личного первенства

Подразделы

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

Дата и время

21/11/2024 16:55:56

Авторизация

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

printЗадачи очного тура личного первенства Южного Урала 2006

A. Одной цифрой

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

Найти наименьшее целое число `Y`, большее или равное заданному числу `X`, запись которого в некоторой системе счисления по основанию `B\ (2\ ≤\ B\ ≤\ 36)` состоит из одинаковых цифр. Например, для числа 1234 таким числом будет 1256, которое в 12-ричной системе можно записать, используя только одну цифру 8: `888_12`.
Ввод
В первой строке входного файла содержится целое `X\ (1\ ≤\ X\ ≤\ 10^9)` в десятичной системе счисления.
Вывод
В выходной файл вывести основание системы счисления `B` и через пробел запись искомого числа `Y` в этой системе счисления. Если существует несколько вариантов искомого `Y` в системах счисления с различными основаниями, то вывести результат, используя наименьшее из оснований. Для цифр от 10 до 35 использовать прописные латинские буквы A..Z соответственно.

Пример ввода

1234

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

12 888

B. Распаковка

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

Строка длиной не более `2*10^9` символов, состоящая из прописных латинских букв A..Z, была упакована по следующим правилам:
  • букве в исходной строке соответствует та же буква в упакованной строке
  • для последовательности из `N\ >\ 1` одинаковых букв в упакованной строке записывается число `N`, затем буква
  • для последовательности из `N\ >\ 1` одинаковых подстрок в упакованной строке записывается число `N`, затем в круглых скобках упакованная подстрока.
Напишите программу, определяющую по упакованной форме количество вхождений каждой из букв A..Z в исходную строку.
Ввод
В первой строке входного файле содержится упакованная строка длиной не более 256 символов.
Вывод
В выходной файл для каждой буквы A..Z, встречающейся в тексте, вывести строку, содержащую букву, затем пробел и количество вхождений этой буквы в исходную строку. Информация выводится в алфавитном порядке.

Пример ввода

10(5XH)X

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

H 10
X 51

C. Кривая пирамида

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

Археолог решил измерить длину ребер обнаруженной им странной формы пирамиды. Он выяснил, что основанием пирамиды служит правильный `N`-угольник с длиной стороны `A`, и определил с помощью лазерного дальномера расстояния от трех вершин у основания до верхушки пирамиды. Внезапно начавшаяся песчаная буря заставила археолога прервать измерения и спрятаться в палатке. Зайдя на форум сайта ipc.susu.ac.ru, археолог создал тему с просьбой о программе, которая поможет ему найти длину неизмеренных ребер пирамиды по уже известным данным и вернуться в город, не дожидаясь окончания бури.
Ввод
В первой строке входного файла содержатся 5 чисел, разделенных пробелами – количество вершин у основания `N\ (4\ ≤\ N\ ≤\ 10)`, длина стороны основания `A`, длины ребер пирамиды в порядке обхода соседних вершин основания по часовой стрелке `X,\ Y,\ Z` (значения `A,\ X,\ Y,\ Z` в диапазоне от 1 до 100).
Вывод
В выходной файл вывести `(N-3)` строки, в каждой строке по одному числу с 5 десятичными знаками – длины неизмеренных ребер пирамиды в порядке продолжения обхода вершин основания по часовой стрелке.

Пример ввода

4 4.0 5.0 3.0 5.0

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

6.40312

D. Составление числа

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

`N` карточек были пронумерованы числами от 0 до `N-1`. Несколько карточек положили в ряд, чтобы получилось число. Напишите программу, которая из оставшихся карточек составит такое же число.
Ввод
В первой строке входного файла содержатся два целых числа, разделенных пробелом – количество карточек `N\ (10\ ≤\ N\ ≤\ 1000)` и количество отобранных карточек `K\ (1\ ≤\ K\ ≤\ 10)`. Во второй строке входного указано `K` различных целых чисел в диапазоне от 0 до `N-1`, разделенных пробелами – номера на отобранных карточках.
Вывод
В выходной файл в первой строке вывести число M – количество карточек, взятых для составления такого же числа. Во второй строке вывести, разделяя пробелом, номера на этих карточках. Если существует несколько вариантов, можно вывести любой из них. Если составить такое же число невозможно, то в первой строке вывести число –1 .

Пример ввода

1000 3
11 45 99

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

2
114 599

E. Игра

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

Два игрока по очереди берут по одной карточке из общей кучи. На каждой карточке написано некоторое целое число, которое может быть как положительным, так и отрицательным. Игрок, взявший карточку, может либо забрать её себе, либо отдать сопернику. В начале игры карточек на руках ни у кого нет. Когда игроки разберут все карточки, игра заканчивается и игроки считают сумму чисел на своих карточках. Игроки стараются максимизировать разность между количеством своих очков и количеством очков соперника. Напишите программу, которая определит максимально возможную разность между очками первого игрока и его соперника, если оба игрока будут действовать оптимальным образом.
Ввод
В первой строке входного файла содержится целое число `N\ (1\ ≤\ N\ ≤\ 10000)` – количество различных чисел, записанных на карточках. Далее следует `N` строк, каждая из которых содержит два целых числа `A` и `B`, разделенных пробелом; число `B\ (1\ ≤\ B\ ≤\ 10^8)` означает количество карточек, на которых написано число `A\ (|A|\ ≤\ 10^8)`.
Вывод
Вывести единственную строку, содержащую целое число – разность между количеством очков первого и второго игроков, при оптимальной игре обоих.

Пример ввода

3
1 1
2 1
3 1

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

2

F. Максимальная расстановка

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

Задано прямоугольное поле размером `N` строк на `M` столбцов, клетки которого окрашены в черный или белый цвет. Требуется расставить максимальное количество шахматных коней на белые клетки поля таким образом, чтобы ни один конь не бил другого. В клетку можно поставить не более одного коня.
Ввод
В первой строке входного файла содержится два целых числа `N` и `M\ (1\ ≤\ N,\ M\ ≤\ 50)`, разделенных пробелом. Далее следуют `N` строк, содержащих `M` символов каждая, задающих поле. В строке `i`-ой на `j`-ой позиции содержится символ '.', если клетка белая, либо '#', если клетка черная.
Вывод
Вывести единственную строку, содержащую максимальное количество коней, которое можно расставить на заданном поле.

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

2 2
..
..

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

4

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

4 5
#...#
#.#.#
#....
..#..

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

7

G. Последовательности

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

Рассмотрим все `N`-элементные последовательности из целых чисел от 0 до `K-1`. Например, при `N=2` и `K=3` получаются последовательности (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1) и (2,2). Требуется определить количество последовательностей среди них, которые удовлетворяют `M` ограничениям, задаваемых тройкой чисел `(A,\ B,\ C)`: остаток от деления на `K` суммы элементов последовательности с `A`-го по `B`-ый равен `C`. Так как количество удовлетворяющих ограничениям последовательностей может быть очень большим, то нужно вывести только остаток от деления этого числа на 10000. Например, если `N=2,\ K=3` и сумма элементов с первого по второй равна 2, то удовлетворять условию будут последовательности: (0,2), (1,1) и (2,0), а если к этому добавить еще, что сумма элементов с первого по первый равна 1, то удовлетворять условиям будет только последовательность (1,1).
Ввод
В первой строке входного файла содержится три целых числа `N,\ K,\ M\ (1\ ≤\ N,\ K\ ≤\ 1000,\ 0\ ≤\ M\ ≤\ 1000)`. Далее следуют `M` строк, каждая из которых содержит описание одного из ограничений, т.е. тройка целых числа `A_i,\ B_i` и `C_i\ (1\ ≤\ A_i\ ≤\ B_i\ ≤\ N,\ 0\ ≤\ C_i\ ≤\ K-1`, `i` от 1 до `M`). Все числа в строках отделены друг от друга одним пробелом.
Вывод
Вывести единственное целое число, равное остатку от деления на 10000 количества удовлетворяющих ограничениям `N`-элементных последовательностей.

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

2 3 2
1 2 2
1 1 1

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

1

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

3 2 2
1 2 0
2 3 0

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

2

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

3 3 3
1 3 2
1 1 1
2 3 0

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

0

H. The Hotel with Infinite Rooms

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

The city of Binvolution has a strange hotel with infinite rooms. The groups that come to this hotel follow the following rules:
  • At the same time only members of one group can rent the hotel.
  • Each group comes in the morning of the check-in day and leaves the hotel in the evening of the check-out day.
  • Another group comes in the very next morning after the previous group has left the hotel.
  • A very important property of the incoming group is that it has in two times more members than its previous group unless it is the starting group. You will be given the number of members of the starting group.
  • A group with n members stays for n days in the hotel. For example, if a group of four members comes on 1st August in the morning, it will leave the hotel on 4th August in the evening and the next group of eight members will come on 5th August in the morning and stay for eight days and so on.
Given the initial group size you will have to find the group size staying in the hotel on a specified day.
Input
The input contains round numbers `S\ (1\ ≤\ S\ ≤\ 100)` and `D\ (1\ ≤\ D\ ≤\ 10^9)` in every line. `S` denotes the initial size of the group and `D` denotes that you will have to find the group size staying in the hotel on `D`th day (starting from 1). A group size `S` means that on the first day a group of `S` members come to the hotel and stays for `S` days then comes a group of 2*`S` members according to the previously described rules and so on.
Output
For each line of input, print on a single line the size of the group staying in the hotel on the `D`th day.

Sample Input

1 6
3 9
3 14

Sample Output

4
6
12
loading