Правила решения задач можно прочитать тут.

Правила решения задач можно прочитать тут.

Правила решения задач можно прочитать тут.

О компьютерах

Ограничения
Временное ограничение: 5 сек.

Условия
В одном университете жили-были веселые студенты и злобные лаборанты. Веселые студенты любили играть в Quake по сети. Чтобы помешать студентам играть в Quake, злобные лаборанты отсоединили все компьютеры от сети, поставили на длинный стол в ряд и прибили их к столу девятидюймовыми гвоздями. Но веселые студенты не сдались. Они решили соединить компьютеры проводами (коаксиальным кабелем) так, чтобы каждый компьютер был соединен хотя бы с одним соседним. Один метр провода стоит 1 о.у.е. (о.у.е. - очень условная единица). Студенты измерили расстояния между соседними компьютерами в метрах и поместили их в файл input.txt. Все расстояния оказались целочисленными. Требуется написать программу, которая по данным расстояниям между компьютерами определяет минимальную сумму длин проводов, необходимых для требуемого соединения компьютеров.

Входные данные
В первой строке входного файла содержится число компьютеров N, 1 <= N <= 25 000. В последующих строках файла содержатся N - 1 целых положительных чисел - расстояния между соседними компьютерами в метрах, по одному числу в каждой строке. Расстояние между первым и последним компьютером не превосходит 1 000 000.

Выходные данные
В выходном файле должно содержаться одно число - минимальная сумма длин проводов,
необходимых для соединения компьютеров.

Пример

input.txt	output.txt
6 2 2 3 2 2	7

Всем привет.
Условия задачи можно найти тут.
Файл с решением на C++

Решение
Вся соль задачи - в ее ограничениях. Действительно, нельзя хранить названия всех лодок, потому что можно использовать всего лишь 16 Мб памяти. С другой стороны ограничение по времени в 2 секунды, за которое нельзя не только сравнить строки при помощи функции strcmp, но и просто считать файл. Когда я тестировал решения, то получил примерно такие результаты для считывания данных(тест был только один: 1000000 лодок с названиями в 20 символов длиной):
fscanf - 4-5 сек.
ifstream fout >>  - 10 сек.
ifstream fout.read(somestring, 100) - 1.5-1.6 сек. //этот вариант вполне подходит, правда нужно пробегать по строке и вытаскивать оттуда названия лодок, потому что точной длинны мы не знаем.

Итак, со считывание разобрались, осталось сравнение строк. Заметим, что по условию названия всех лодок кроме одной встречаются по 2 раза, следовательно мы можем использовать свойство функции XOR.  A ^ B ^ A = B. Т.е. делаем посимвольный xor названий, после этого мы получаем название нужной нам лодки.

Итак, новая интересная задачка. Правила решения задач читаем тут.

О гирях на весах

Ограничения
Ограничение по времени: 5 сек.

Условия
Два игрока имеют гири на чашах весов. Гири первого игрока (N штук) стоят на первой чаше, а второго (M штук) - на второй. Гири отличаются весом, для каждой гири задан свой вес. Двух гирь с одинаковым весом нет. В начальный момент суммарный вес гирь на чашах - разный. Игра заключается в следующем. Первым ходит тот игрок, у кого суммарный вес гирь больше. Тот, кто ходит, убирает гири по одной со своей чаши до тех пор, пока вес его гирь не станет меньше веса гирь противника. После этого ход переходит к противнику. Выигрывает тот, кто первым уберет все гири. Требуется определить, кто из них выигрывает при оптимальной стратегии обоих игроков.

Входные данные
В первой строке входного файла содержатся два числа (через пробел) - N и M, 0 < N <= 50000, 0 < M <= 50000. В последующих N + M строках расположены целые положительные числа Ai (0 < Ai <= 1000000, 1 <= i <= N + M) веса гирь сначала первого, а затем второго игроков.

Выходные данные
В выходном файле должно содержаться одно число - 1 или 2 (номер выигравшего, только один символ).

Пример

input.txt	output.txt
3 3 1 3 5 2 4 6	2

Дополнительно
Можно присылать алгоритм.

В общем решил правила вынести в отдельный пост. Итак..

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

О решениях
Решения присылать мне по адресу vvovas@rambler.ru.
Убедительная просьба, в комментариях решения не публиковать. При нарушении этого правила никакие ваши решения данной задачи рассматриваться не будут
В комментариях нужно объявлять о решении поучаствовать.
Решения задач можно писать на языках c, c++, c#. Использование других языков лучше оговорить в комментариях.
В некоторых случаях можно присылать просто описание алгоритма решения(это будет отмечено в условиях задачи).

О результатах
Результаты тестирования я буду писать в комментариях.
Через некоторое время после публикации задачи(около недели) будет написан пост с описанием алгоритма решения и ссылкой на решение, которое показало лучшее время.

О тестах
К некоторым задачам у меня нет тестов, поэтому в условии будет пометка о том, что можно вместе с решением присылать тестовые данные, которые, по вашему мнению, смогут проверить правильность работы программы.

Всем привет. Вот нашел еще одну простенькую задачку. Правила по решению задач читать тут.



Дополнительно
Можно присылать алгоритм.

input.txt	output.txt
4 Titanic Argo2 285714 Beda Argo2 Titanic 285714	Beda

UPD (27.08.2008): В общем какие-то зверские ограничения по времени, поставлены на самом деле. Предлагаю их поменять на 5 секунд.