Задания 4-го (Real-Time) тура Всеукраинской Интернтет-олимпиады NetOI-2010
12 февраля 2011 года
Задача Painting
Васе Пупкину, герою NetOI, в день рождения подарили набор цветных карандашей (все карандаши в наборе разных цветов). Вася начертил прямоугольную таблицу, содержащую m строк клеточек по n клеточек в каждой строке, и стал закрашивать клеточки таблицы цветными карандашами – каждую клеточку каким-то одним цветом. Когда все клеточки были закрашены, оказалось, что:
- для закрашивания клеточек любой из m строк использовались все имеющиеся в наборе карандаши, каждый по одному разу;
- среди m строк не было двух, закрашенных одинаково (две строки считаются закрашенными одинаково, если все клеточки с одинаковыми номерами этих строк закрашены одинаковыми цветами);
- если бы число строк было на 1 больше (то есть, m+1), то обязательно нашлись бы две строки, закрашенных одинаково.
Зная, что каждый из карандашей Вася использовал ровно m раз, найдите количество карандашей в наборе.
Технические условия. Программа Painting обязательно читает с клавиатуры натуральное число k - количество цифр числа m (1 ≤ k <1000), а далее - k цифр числа m, записанных через пробел (цифры записаны слева направо, начиная со старшего разряда). Программа выводит на экран единственное число – количество карандашей в наборе.
Пример
Ввод: 2 2 4
Вывод: 4
Задача Crystal
Юный химик Лиза выращивает кристаллы. На прямоугольную пластину с питательной средой она капает зародышевыми кристаллами, которые вскоре растут и заполняют всю пластину. В связи с постоянным недосыпанием и микроскопическими размерами пластины её вкрапления получаются разбросанными случайно по пластине и иногда кристаллы разрастаются достаточно долго. Лизе необходимо определить время, за которое пластина полностью покроется кристаллами, если известны ее размеры и места вкрапления. Из учебника по координационной химии известно, что за 1 минуту кристалл разрастается на соседние клеточки, с которыми он имеет общее ребро.
Технические условия. Программа Crystal читает с клавиатуры числа H и W – количество строк и столбиков пластины, далее - число K – количество вкраплений, которые сделала Лиза, после чего K пар чисел R и C – соответственно строка и столбик вкрапления. Все числа целые, разделены пробелами и удовлетворяют ограничениям: 1 <= H, W <= 500; 0 <= K <= 50; 1 <= R <= H; 1 <= C <= W.
Программа выводит на экран единственное целое число - минимальное количество минут, после которого вся пластина будет покрыта кристаллами, а если этого никогда не случится, то вывести -1.
|
Пример 1 |
|
Пример 2 |
|
|
Ввод |
Вывод |
Ввод |
Вывод |
|
7 7 2 3 3 7 5 |
6 |
40 20 3 2 8 1 18 27 5 |
28 |
Задача ABACABA
Абацабовский язык состоит из всех тех последовательностей букв A, B, C (разумеется, латиницей), в которых одна и та же буква повторяется не больше двух раз подряд. Все эти слова пронумерованы по правилам: сначала все однобуквенные, затем все двухбуквенные и т. д., а среди слов с одинаковым количеством букв — в словарном порядке, то есть сначала сравниваются первые буквы; если они одинаковы, то сравниваются вторые, и т. д. В частности, словами абацабовского языка с 1‑го по 47‑е являются A, B, C, AA, AB, AC, BA, BB, BC, CA, CB, CC, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC, BBA, BBC, BCA, BCB, BCC, CAA, CAB, CAC, CBA, CBB, CBC, CCA, CCB, AABA, AABB, AABC, AACA, AACB, AACC, ABAA, ABAB, ABAC, ABBA, ABBC. Напишите программу, выполняющую преобразование между буквенным и порядковым представлением слов абацабовского языка.
Технические условия. Программа ABACABA читает с клавиатуры либо целое строго положительное число, либо последовательность букв, образующих слово абацабовского языка. Программа должна вывести в первом случае слово абацабовского языка, имеющего такой номер, а во втором — порядковый номер введенного слова. Достаточно, чтобы программа умела работать со словами, номера которых не превосходят 1018.
Программа должна выводить только ответ, без каких-либо лишних символов, в т. ч. и пробелов. Числа должны начинаться с ненулевой цифры.
|
Пример 1 |
Пример 2 |
|
Ввод AACC Вывод 42 |
Ввод 935 Вывод ABACABA |
Задача Oddsum
Дана прямоугольная таблица размером N строк на M столбцов; в каждой клетке записано целое число. По ней нужно пройти сверху вниз, начав путь в какой-нибудь клетке верхней строки, далее каждый раз переходя в одну из «нижне-соседних» клеток (иными словами, из клетки с номером (i, j) можно перейти либо в (i+1, j–1), либо в (i+1, j), либо в (i+1, j+1); в случае j=M возможны только 1-й и 2-й из трех перечисленных вариантов, в случае j=1 — только 2-й и 3-й) и закончив путь в какой-нибудь клетке нижней строки. Напишите программу, находящую максимально возможную нечетную сумму значений пройденных клеток (среди всех допустимых путей).
При этом отдельные числа могут быть четными; нечетной должна получиться окончательная сумма.
Технические условия Программа Oddsum читает с клавиатуры N и M — количество строк и количество столбцов (2≤M≤500, 2≤N≤500), а далее - N строк из M разделенных пробелами целых чисел (каждое не превосходит по модулю 1 000 000) — значения клеток таблицы. Программа выводит на экран единственное целое число — найденную максимально возможную нечетную сумму. Если сформировать нечетную сумму вообще невозможно, программа должна вместо ответа вывести -2.
Пример
|
Ввод |
Вывод |
|
4 3 1 15 2 9 7 5 9 2 4 6 9 –1 |
39 |
Примечание к примеру
Наилучший (з суммой 39) допустимый путь проходит через клетки со значениями 15, 9, 9, 6. Путь, проходящий через клетки со значениями 15, 9, 9, 9, имеет еще большую сумму 42, но для данной задачи он не допустимый, так как сумма 42 четна.
Задача Efractions
Математики древнего Египта не знали дробей в современном понимании, но умели представлять нецелые числа как сумму дробей вида 1/k, причем все k в этой сумме должны быть различными. Например, современное понятие 2/5 выражалось как «одна треть и одна пятнадцатая» (в самом деле, 1/3 + 1/15 = 5/15 + 1/15 = 6/15 = 2/5).
Математики Нового времени доказали, что любую правильную обыкновенную дробь можно записать в египетском представлении (как сумму дробей вида 1/k), причем это представление не единственное. Напишите программу, преобразующую правильную обыкновенную дробь в египетское представление с минимальным количеством слагаемых. Если существуют разные египетские представления с одинаковым минимальным количеством слагаемых, программа должна находить любое из них.
Технические условия. Программа Efractions читает с клавиатуры два натуральных числа n и m (1≤n<m≤1000) — числитель и знаменатель правильной обыкновенной дроби. Программа выводит на экран последовательность различных натуральных чисел, разделенных пробелами — совокупность знаменателей в египетском представлении этой дроби.
Пример 1
Ввод
2 5
Вывод
3 15
Пример 2
Ввод
732 733
Вывод
2 5 8 9 16 65970 105552
Задание подготовили В.Боднарь, Б.Дибров, Г.Непомнящий, Ю.Пасихов, С.Петров, И.Порублёв