Всеукраинская 2007-2008

XXI Всеукраинская олимпиада по информатике

Первый тур

Гирлянда

Новогодняя елка украшена гирляндой бесконечной длины, которая состоит из последовательно соединенных лампочек. Когда гирлянду включают, загорается только первая лампочка, считая от выключателя, которая горит одну секунду. Далее гирлянда начинает мигать по следующему правилу. Каждую секунду для каждой лампочки проверяется условие: если ровно одна из ее соседних лампочек горит, то эта лампочка будет гореть на следующей секунде; иначе – не будет гореть. У первой лампочки только одна соседняя.

Задание

Напишите программу GARLAND, которая по номеру секунды находит количество лампочек гирлянды, которые будут гореть на протяжении этой секунды.

Входные данные

Единственная строка входного файла GARLAND.DAT содержит одно целое число N (1≤N≤10⁹) – номер секунды.

Выходные данные

Единственная строка выходного файла GARLAND.SOL должна содержать целое число – количество лампочек, которые будут гореть на секунде N.

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

Острова

Чтобы не отставать от современной мировой тенденции, правительство страны Олимпия планирует построить несколько островов для привлечения туристов. Карта островов уже подготовлена и представляет собой таблицу размером N´M клеток. Каждая клетка может быть водой или сушей. Набор клеток, которые представляют сушу, есть островом, когда из любой из них можно попасть в любую другую, перемещаясь по соседним по горизонтали или вертикали клеткам, и не существует других таких клеток вне набора.

Для удобства было решено построить мосты между некоторыми островами так, чтобы все острова стали связанными между собой. Мосты должны строиться только по вертикали или горизонтали, проходить только по клеткам с водой, начинаться и заканчиваться клетками с сушей. За стоимость строительства моста можно считать количество клеток воды, через которые он проходит. Требуется найти минимальную возможную общую стоимость строительства группы мостов, которые связывали бы между собой все острова. Другими словами, чтобы из каждой клетки суши можно было достичь любой другой, перемещаясь по соседним по вертикали и горизонтали клеткам суши, либо мостам. Два разных моста могут пересекаться между собой, т.е. проходить через одну и ту же самую клетку воды на разных уровнях.

Задание

Напишите программу ISLANDS, которая по карте островов находит минимальную стоимость строительства группы мостов, которые соединяют все острова.

Входные данные

Первая строка выходного файла ISLANDS.DAT содержит два целых числа N и M (1≤N, M≤500) – размеры карты островов. Каждая из последующих N строк содержит M символов 0 (вода) либо 1 (суша).

Выходные данные

Единственная строка выходного файла ISLANDS.SOL должна содержать одно целое число – найденную минимальную стоимость строительства мостов. Если соединить острова мостами невозможно, требуются вывести число -1.

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

Геном Ньютона

На планете Олимпия завершено изучение генома обитателей Олимпийской галактики. Оказалось, что расшифрованный геном может быть представлен в виде набора целых чисел, которые могут повторяться. В представлении генома талантливой личности содержится среди прочих единственное число, которое встречается нечетное количество раз и задает номер определенного генетически обусловленного таланта.

Разработанное оборудование получает представление генома в виде набора множеств чисел. Каждое множество задается четверкой чисел s, f, a, b. Такому множеству принадлежат a последовательных целых чисел начиная с s, следующие b чисел множеству не принадлежат, следующие a снова принадлежат, и т.д. Все числа множества не превышают f. Например, множество (s=1, f=10, a=2, b=1) содержит числа: 1, 2, 4, 5, 7, 8, 10, а множество (s=5, f=50 a=1, b=19) числа: 5, 25, 45.

Задание

Напишите программу GENOME, которая по представлению генома в виде набора множеств чисел установит, обладает ли его владелец каким-то генетически обусловленным талантом, и определит его номер.

Входные данные

Первая строка входного файла GENOME.DAT содержит количество множеств N (1≤N≤10 000) в наборе. Последующие N строк задают сами множества. Каждое множество задается четверкой чисел – s, f, a, b, (1≤s, f, a, b<10⁹; s≤f). Гарантируется, что представление генома содержит не больше одного числа, которое встречается нечетное количество раз.

Выходные данные

Единственная строка выходного файла GENOME.SOL должна содержать целое число, которое встречается нечетное количество раз в представлении генома, либо 0, если такого числа не существует.

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