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

Назад

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

Подразделы

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

Дата и время

16/11/2024 15:20:23

Авторизация

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

printЗадачи Южно-Уральского командного чемпионата 2009

A. Калейдоскоп

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

Фирма "Amusing Caleidoscopic Matrices" устанавливает в офисах калейдоскопические матрицы, представляющие собой квадраты из `N\ times\ N` элементов, окрашенных в разные цвета. Через некоторый интервал времени на калейдоскопе меняются местами случайно выбранные строки или столбцы матрицы и образуется новый узор. Стоимость калейдоскопа тем выше, чем больше различных узоров он может сгенерировать, и чем меньше среди них некрасивых. Узор считается некрасивым, если в нем есть квадрат `2\ times\ 2`, в котором цвета всех элементов одинаковы или, наоборот, попарно различны. Два узора считаются одинаковыми, если они совпадают при повороте на угол, кратный 90 градусов.
Напишите программу, определяющую для заданной калейдоскопической матрицы количество различных узоров, которые могут получиться на ней, и количество некрасивых узоров среди них.
Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 6`) – размеры матрицы калейдоскопа. Далее следует `N` строк, содержащих по `N` целых чисел в диапазоне от 1 до 9 – номера цветов элементов матрицы.
Вывести два целых числа – количество различных узоров, которые могут получиться на заданной матрице, и количество некрасивых узоров среди них.

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

2
1 2
2 3

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

1 0

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

2
1 2
3 4

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

2 2

B. Forth

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

Вася Пупкин нашел старую программу на языке Forth и хочет перевести ее на язык С++. Чтобы избежать ошибок, неизбежных при переводе вручную, Вася обратился за помощью в написании транслятора к вашей команде.
Язык Forth использовался для программирования встраиваемых микрокомпьютеров и мог оперировать только целыми числами в диапазоне от –32768 до 32767. В основе вычислительной модели языка Forth лежит стековая машина и все вычисления записываются в обратной польской записи. В обнаруженной программе были только команды арифметических действий, загрузки целых констант и обращения к переменным. Команды +, -, *, /, MOD заменяют два верхних элемента стека результатом соответствующего арифметического действия. Имя переменной в Forth рассматривается как команда, которая должна загрузить на стек адрес ячейки памяти. Команда @ заменяет адрес на вершине стека значением из ячейки памяти по этому адресу. Для сохранения результата вычислений в ячейке памяти используется команда !, которая снимает со стека два верхних элемента и по адресу, заданному первым элементом, записывает второе снятое значение. Целое число в программе означает, что это число нужно загрузить на вершину стека.
Программа "X @ 1 - 2 * Y !" после перевода на язык С++ будет выглядеть так: "Y=(X-1)*2;". Команде MOD в языке C++ соответствует операция %.
Напишите программу, выполняющую перевод найденной программы на язык С++.
В первой строке ввода содержится программа на языке Forth. Длина строки не превышает 1000 символов. Команды в строке разделены пробелами. Имена переменных состоят только из прописных латинских букв и цифр и начинаются с буквы. Длина имен не превышает 31 символа. Программа корректна, перед выполнением программы и после ее завершения стек пустой, при выполнении всех команд в стеке достаточно элементов, арифметические операции выполняются только над числами, при выполнении команд ! и @ в верхнем элементе стека содержится адрес ячейки памяти, а вторым элементом стека при выполнении команды ! является число.
Вывести несколько строк на языке С++. Каждая строка должна содержать один оператор присваивания, оканчивающийся символом ';'. Порядок операторов должен соответствовать порядку выполнения команд ! в программе на Forth. Нельзя производить никаких оптимизаций вычислений, менять порядок операндов или выполнения действий. Если порядок выполнения действий в программе на языке Forth не соответствует приоритету или ассоциативности этих операций на языке С++, то нужно использовать скобки. Последовательность символов "--" в C++ является специальной операцией, поэтому, чтобы не было ошибок при компиляции, между двумя знаками минус нужно поставить один пробел, других пробелов в выводимых операторах не должно быть.

Пример ввода

4 2 -1 - * X ! 9 1 X @ 2 * + Y ! X !

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

X=4*(2- -1);
Y=1+X*2;
X=9;
Пояснения: В программе на Forth не производится изменения переменных после загрузки их значений в стек, т.е. такой последовательности команд (или аналогичной) не встречается: 5 X ! X @ 6 X ! Y !
Приоритет: Операции * / % имеют приоритет выше, чем + -, поэтому "1 2 3 * +" `→` "1+2*3", а "1 2 3 + *" `→` "1*(2+3)".
Ассоциативность: Операции с одинаковым приоритетом выполняются слева направо, поэтому "1 2 - 3 -" `→` "1-2-3" (скобки не нужны), но "1 2 3 - -" `→` "1-(2-3)". Аналогично "1 2 + 3 +" `→` "1+2+3", а "1 2 3 + +" `→` "1+(2+3)".

C. Сокращение штатов

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

В связи с кризисом Билл Виндоуз решил закрыть или продать не приносящие доходы подразделения и уволить некоторую часть сотрудников таким образом, чтобы его прибыль стала максимальна. При этом структура сложившихся иерархических отношений в компании должна сохраниться. Можно уволить в том числе главных менеджеров компании и оставить от компании наиболее доходную часть, продав менее доходные подразделения.
Напишите программу, которая определит персонал обновленной компании.
В первой строке ввода содержатся одно целое число `N` (`1\ ≤\ N\ ≤\ 100 000`) – количество сотрудников в компании. Далее следует `N` строк, содержащих по два целых числа – доход от работы сотрудника `p_i` (`-10 000\ ≤\ p_i\ ≤\ 10 000`) и номер сотрудника `c_i` (`0\ ≤\ c_i\ ≤\ N`), который является его начальником (для топ-менеджера компании `c_i=0`). В первой строке вывести одно целое число `M` (`M\ ≥\ 0`) – количество оставшихся в компании сотрудников после сокращения, при котором доход компании становится максимальным. Во второй строке вывести `M` чисел через пробел — номера сотрудников в порядке возрастания. Если существует несколько вариантов решения, нужно вывести один (любой) из них.

Пример ввода

7
10 3
5 3
-3 6
-10 6
7 4
-1 0
-1 3

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

3
1 2 3

D. Космическая станция

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

Астронавту необходимо попасть как можно быстрее из одного отсека космической станции в другой. К несчастью в тот момент, когда он отправился в путь, из технологических ниш появились роботы и принялись за уборку коридоров станции. Роботы движутся в несколько раз медленнее человека. Астронавт может идти вслед за роботом с той же скоростью, но не может обойти его в коридоре, так как робот занимает всю ширину коридора. Отсеки достаточно большие, чтобы роботы и астронавт могли пройти мимо друг друга, но время на переход из одного коридора в другой считается равным 0. Если астронавт попадает в некоторый отсек одновременно с роботом, то астронавт не может обогнать робота и попасть в коридор, который робот будет убирать следующим, или успеть выйти из этого коридора. Каждый коридор станции убирается только одним из роботов ровно один раз.
Напишите программу, которая поможет астронавту найти минимальный по времени путь из отсека 1 в отсек `N` с учетом передвижений роботов.
Ввод содержит в первой строке три целых числа – количество отсеков `N` (`1\ <\ N\ ≤\ 1000`), количество роботов `M` (`1\ ≤\ M\ ≤\ N`) и отношение скорости астронавта к скорости робота `S` (`2\ ≤\ S\ ≤\ 10`). Далее следует `M` строк, каждая строка начинается с количества убираемых роботом коридоров `k_i`, далее следует номер начального отсека пути робота, далее следует `k_i` пар целых чисел – длина коридора (целое от 1 до 1000) и номер отсека, в который ведет очередной коридор на пути робота. Между двумя отсеками не более одного коридора, общее количество коридоров не превышает `10*N`. Из любого отсека можно попасть по коридорам в любой другой.
В первой строке вывести одно целое число `K` – количество коридоров в минимальном по времени пути из отсека 1 в отсек `N`. Во второй строке вывести `K+1` число – номера отсеков, по которым проходит минимальный путь. Если существует несколько вариантов решения, нужно вывести один (любой) из них.

Пример ввода

3 1 10
3 3 1 1 4 2 5 3

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

2
1 2 3

E. Взлом кода

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

Для входа в секретную лабораторию необходимо набрать код из `n` цифр. Путем анализа внутренней структуры замка было установлено, что для введенного кода вычисляется следующая хэш-функция:
`h_0=0`
`h_i=(h_{i-1}*a+c_i)\ mod\ b` для `i=1…n`
где `c_i` – цифры вводимого кода от 0 до 9
Если значение `h_n` совпадает с заданным при настройке замка значением `g`, то замок открывается. Удалось выяснить значения `a`, `b` и `g`. Необходимо определить код, который откроет замок.
Первая строка ввода содержит четыре целых числа – длина кода `n` (`2\ ≤\ n\ ≤\ 12`) и значения `a`, `b`, `g` (`10\ ≤\ a,\ b\ ≤\ 10^15`, `0\ ≤\ g\ <\ b`). Хотя бы один код, соответствующий входным данным, существует.
В первой строке вывести последовательность из `n` цифр – код замка. Если существует несколько вариантов решения, нужно вывести один (любой) из них.

Пример ввода

3 11 1000 146

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

123

F. Стратегия для игры

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

В одной из книг Вася Пупкин обнаружил описание следующей игры. Игра начинается с ввода человеком последовательности прописных латинских букв – начального слова. Компьютер может выбрать, кто будет ходить первым: человек или компьютер. Затем игроки ходят по очереди. На каждом ходе игрок должен выбрать одно из слов, получившихся на предыдущем шаге и заменить одну из его букв на пробел. Пробелами заменяются также все остальные буквы в слове, совпадающие с выбранной. В результате слово может либо исчезнуть совсем, либо разбиться появившимися пробелами на несколько слов. Если игрок не может сделать свой очередной ход (не осталось слов), он проигрывает.
Вася решил написать программу для этой игры, и даже реализовал интерфейс, но он не смог придумать беспроигрышную стратегию для компьютера и обратился за помощью к вашей команде. Вы должны написать подпрограмму с именем game, которой передается строка `s` с начальным словом, заданным человеком.
void game(char *s); // С/С++
procedure game(var s:string); // Pascal
Для выполнения хода ваша подпрограмма должна вызывать подпрограмму robot с номером слова (нумерация слов начинается с 1) и выбранной буквой в этом слове.
void robot(int w, char c); // С/С++
procedure robot(w:integer; c:char); // Pascal
Эта подпрограмма делает все необходимые изменения в строке `s`, вводит ход человека и опять изменяет строку. После возврата из подпрограммы строка `s` будет изменена по результатам двух ходов. Если человек не может сделать ход, подпрограмма robot завершает выполнение программы. В случае, если компьютер не может сделать ход, вы должны выйти из подпрограммы game. Если первый ход должен сделать человек, а не компьютер, то для выполнения хода человеком нужно вызвать подпрограмму human без параметров.
void human(); // С/С++
procedure human; // Pascal
Длина начального слова не превышает 100 букв. Пересылаемое на проверку решение должно содержать только подпрограмму game, вспомогательные функции, команды #include (в C/C++) и глобальные переменные. В подпрограммах не должен выполняться ввод или вывод.
Пример подпрограммы на C/C++
void game(char *s)
{ int i=0;
  if(rand()%2)
    human();
  while(s[i])
  {
    if(s[i]!=' ')
      robot(1,s[i]);
    ++i;
  }
}
Пример подпрограммы на Pascal
procedure game(var s:string);
var i:integer;
begin
  if length(s) mod 2=0 then
    human;
  i:=1;
  while i<=length(s) do
    if s[i]=' ' then
      inc(i)
    else
      robot(1,s[i]);
end;

G. Скульптура

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

На набережной Петрозаводска установлено множество абстрактных скульптур. Одна из скульптур так понравилась Васе Пупкину, что он решил сделать ее копию и установить в своем саду. Скульптура представляет собой `N` стальных прутьев, торчащих из общего центра. Вася измерил углы между 1-м и 2-м прутьями, 2-м и 3-м прутьями, …, `N`-м и 1-м прутьями. Также он измерил расстояния между вершинами этих прутьев. Вернувшись домой, Вася понял, что этих данных для создания точной копии скульптуры недостаточно. Тогда он решил сделать скульптуру, у которой будут такие же углы и расстояния между вершинами прутьев. Подобрать нужную длину прутьев оказалось сложной задачей, и Вася обратился за помощью к вашей команде. Вася не уверен, что все измерения были записаны верно, поэтому программа должна проверять возможность создания скульптуры с заданными параметрами.
Напишите программу, которая вычислит длину прутьев в скульптуре.
В первой строке ввода содержится одно целое число `N` (`3\ ≤\ N\ ≤\ 15`) – количество прутьев. Во второй строке содержится `N` вещественных чисел, разделенных пробелами, в диапазоне от 1 до 100 – углы между прутьями в градусах. В третьей строке содержится `N` вещественных чисел, разделенных пробелами, в диапазоне от 1 до 100 – расстояния между вершинами прутьев.
В первой строке вывести YES, если удалось найти длину прутьев, или NO, если сделать скульптуру с заданными параметрами не удастся. Во второй строке в случае положительного ответа вывести `N` вещественных чисел, разделенных пробелами – длину прутьев с точностью `10^{-6}`. Если существует несколько вариантов решения, нужно вывести один (любой) из них.

Пример ввода

3
30.0 60.0 30.0
10.0 20.0 10.0

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

YES
17.320508 20.000000 20.000000

H. Основание системы счисления

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

Основанием системы счисления может служить не только число 10. В этой задаче основание может быть в диапазоне от 2 до 36. Для записи цифр в системах счисления с основанием от 11 до 36 дополнительно используются латинские буквы от A до Z (A=10, …, Z=35). Регистр букв в записи числа может быть произвольным.
Напишите программу, определяющую основание системы счисления, в которой записано некоторое неотрицательное целое число.
В первой строке ввода содержится запись одного целого числа в неизвестной системе счисления. В записи числа не более 30 букв и цифр.
Вывести в первой строке минимальное из возможных основание системы счисления, в которой может быть записано заданное число. Основание выводится в десятичной системе счисления.

Пример ввода

2A

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

11

I. Primary Arithmetic

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

Children are taught to add multi-digit numbers from right-to-left one digit at a time. Many find the "carry" operation – in which a 1 is carried from one digit position to be added to the next – to be a significant challenge. Your job is to count the number of carry operations for each of a set of addition problems so that educators may assess their difficulty.
Each line of input contains two unsigned integers less than 10 digits. The last line of input contains 0 0.
For each line of input except the last you should compute and print the number of carry operations that would result from adding the two numbers, in the format shown below.

Sample Input

123 456
555 555
123 594
0 0

Sample Output

No carry operation.
3 carry operations.
1 carry operation.
Source: Waterloo U local contest, 2000

J. JR;;P. EPT;F

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

8059.jpg
A common typing error is to place the hands on the keyboard one row to the right of the correct position. So "Q" is typed as "W" and "J" is typed as "K" and so on. You are to decode a message typed in this manner.
Input consists of several lines of text. Each line may contain digits, spaces, upper case letters (except Q, A, Z), or punctuation shown above (except back-quote ` ). Keys labelled with words (Tab, BackSp, Control, etc.) are not represented in the input. You are to replace each symbol by the one immediately to its left on the QWERTY keyboard shown above. Spaces in the input should be echoed in the output.

Sample Input

JR;;P. EPT;F

Sample Output

HELLO, WORLD
Source: Waterloo U local contest, 2001
loading