Решение g6 1001: Первая мысль, приходящая в голову, это написать программу, похожую на эту: a := B; b := A

Задача g6_1017: Демократия в опасности

Л.Волков
В одном из островных государств Карибского бассейна все решения традиционно принимались простым большинством голосов на общем собрании граждан, которых, к счастью, было не очень много. Одна из местных партий, стремясь прийти к власти как можно более законным путем, смогла добиться некоторой реформы избирательной системы. Главным аргументом было то, что население острова в последнее время значительно возросло, и проведение общих собраний перестало быть легкой задачей.
Суть реформы состояла в следующем: с момента введения ее в действие все избиратели острова делились на K групп (необязательно равных по численности). Голосование по любому вопросу теперь следовало проводить отдельно в каждой группе, причем считалось, что группа высказывается "за", если "за" голосует более половины людей в этой группе, а в противном случае считалось, что группа высказывается "против". После проведения голосования в группах подсчитывалось количество групп, высказавшихся "за" и "против", и решение вопрос решался положительно в том и только том случае, когда групп, высказавшихся "за", оказывалось более половины общего количества групп.
Эта система вначале была с радостью принята жителями острова. Когда первые восторги рассеялись, очевидны стали, однако, некоторые недостатки новой системы. Оказалось, что сторонники партии, предложившей систему, смогли оказать некоторое влияние на формирование групп избирателей. Благодаря этому, они получили возможность проводить некоторые решения, не обладая при этом реальным большинством голосов!
Пусть, например, на острове были сформированы три группы избирателей, численностью в 5, 5 и 7 человек соответственно. Тогда партии достаточно иметь трех сторонников в каждой из первых двух групп, и она сможет провести решение всего 6-ю голосами "за", вместо 9-и, необходимых при общем голосовании.
Вам надо написать программу, которая определяет по заданному разбиению избирателей на группы минимальное количество сторонников партии, достаточное, при некотором распределении их по группам, для принятия любого решения.
Ввод.
Входной файл для этой задачи состоит из двух строк. В первой строке файла записано натуральное число K Вывод.
В выходной файл следует записать единственное натуральное число - минимальное количество сторонников партии, способное решить исход голосования.

Пример файла input.txt.

Пример файла output.txt.

Решение g6_1017:

Для контроля над группой, нам достаточно простое большинство голосов в ней. В более маленькой группе нам нужно меньше людей, чтобы иметь простое большинство голосов в ней.
Отсортируем массив с количеством людей в группе по неубыванию. Возьмем (K div 2 + 1) первых групп (минимальных) и найдем сумму всех L = G[N] div 2 + 1, где G - отсортированный массив, с количеством людей в группе, N принимает значение от 1 до K div + 1.
Группы равноправны, а мы контролируем только наименьшие.
Разделяй и властвуй.

Задача g6_1018: Пуговицы
Л.Волков
Как уже несомненно стало известно всем, Екатеринбург добился права на проведение Летних Олимпийских игр 2032 года. Планируется, что России, как стране-организатору Олимпийских игр, будет разрешено внести минимальные изменения в программу Олимпиады. Так, с целью улучшения общего командного результата, было решено заменить соревнования по плаванию первенством в абсолютно новой игре "Пуговицы".
Правила игры очень просты. Перед двумя играющими находится кучка из K пуговиц. Играющие по очереди берут пуговицы из кучки, причем за один ход каждый из них может взять от 1 до L пуговиц. Выигрывает тот из спортсменов, которому удастся взять последнюю пуговицу.
Правила олимпийских соревнований будут лишь немного сложнее обычных. Тот из игроков, которому по жребию выпадает делать первый ход, получает возможность собственноручно назначить число K, руководствуясь в своем выборе только ограничениями 3 Задача
На вашу команду возлагается очень ответственная задание: необходимо написать программу, которая помогала бы второму игроку делать свой выбор. Другими словами, по заданному числу пуговиц в кучке K, необходимо определить такое число L, которое гарантирует победу второму игроку при наилучшей игре обеих сторон.
Так, например, если в кучке всего три пуговицы, то победу второму игроку обеспечивает выбор L=2. В самом деле, если первый игрок своим ходом заберет одну пуговицу, то второй сможет выиграть, взяв обе оставшихся пуговицы и, напротив, если первый возьмет две пуговицы, то второй победит, взяв последнюю. Исходные данные
Вход для этой задачи состоит из одной строки, в которой записано единственное число K - количество пуговиц в кучке, выбранное первым игроком.
Результат
На выход следует записать единственное целое число L - максимальное количество пуговиц, которое можно взять за один ход - обеспечивающее победу второму игроку. Если таких чисел несколько, то следует вывести наименьшее из них. Если таких чисел нет, то следует вывести число 0.

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

Пример результата

Решение g6_1018:

Решение g6_1019:

Я загадаю целое число из интервала [A,B]. Напишите программу, которая за минимальное число вопросов отгадает это число. Играть будем так. Я сообщаю программе числа A и B, программа выводит свою версию ответа. Если это меньше задуманного мною, я сообщу программе об этом числом -1, если больше - числом 1, а если угадано - числом 0. Так будет продолжаться, пока программа не угадает число (естественно, я буду играть честно!). Постарайтесь, чтобы ваша программа угадала число за минимальное число ходов.

Ввод-вывод: В первой строке вводите с клавиатуры два целых числа через пробел - границы диапазона. Программа на экран выводит свою версию в новой строке. С новой строки вы вводите "-1", "1" или "0" ( без кавычек). Так продолжается до того момента, пока число не будет угадано (т.е. ваш ответ "0" должен завершить работу программы).

Пример:

Ограничения : -100000

Решение g6_1020:
У нас есть два начальных числа, причем X > A и X 1) Число совпало, вываливаемся, ура!
2) Число меньше, чем X1. Тогда присваиваем B значение X.
3) Число больше, чем X1. Тогда присваиваем A значение X.
Повторяем вышеприведенные строки, до тех пор, пока не получим загаданное число.
В этом решении количество действий порядка log₂(B-A), т.е. каждый раз мы уменьшаем область поиска вдвое.

Задача g6_1021: 2ⁿ

Вывести в файл output.txt число 2ⁿ, n

Решение g6_1021:
Наконец-то мы дошли до длинной арифметики! 2¹⁰⁰⁰⁰ имеет порядка 3000 десятичных знаков, так что ни о каких extended'ах, а тем более longint'ах речи быть не может.
Существует такое понятие - длинная арифметика - выполнение арифметических операций в массиве (естественно, с потерями в скорости, но что же делать). В нашем случае нам нужно реализовать одно из простейших действий над длинными числами - умножение на 2.
Для надежности заведем массив длиной 4000, состоящий из элементов типа byte. Их будет достаточно для хранения одной десятичной цифры(можно хранить 2 и даже чуть больше десятичных цифр, но это сопряжено с извращениями и усложнениями, так что не будем экономить память, а будем экономить время и нервы). Обнулим массив и присвоим 4000 элементу значение 1 = 2⁰. Затем в цикле от 1 до n будем запускать процедуру умножения на 2.
Вы наверняка хорошо представляете процедуру умножения на 2 в столбик. Здесь все точно также! Двигаясь от последнего элемента к первому(он будет определяться динамически и в начальный момент времени равен 4000), мы будем умножать его на 2 и, в случае если он превысил 9, будем брать остаток от деления на 10, а результат деления заносить в специальную переменную - так называемый флаг переноса. Это можно ассоциировать с умножением в столбик, например 8*2 - 6 пишем, 1 в уме. Главное, не забыть прибавить значение счетчика к следующему разряду.
Если цикл закончился, а флаг переноса не равен 0, то следует уменьшить счетчик, указывающий на первую цифру числа(сначала он был равен 4000), и присвоить элементу с номером счетчика значение флага переноса. В принципе, можно было проходить весь массив от конца к началу, но многократное бесполезное умножение 2 на 0 заметно снижает скорость, что немаловажно.
Стоит заметить, что некоторые предпочитают записывать младшие разряды числа в начале массива, но это непринципиально ни по размеру памяти, ни по времени работы. Кому как удобнее.
Задача g6_1022: Ниточка

А.Петров, Н.Шамгунов

Ваша задача - определить длину этой ниточки.

4 1
0.0 0.0

14.28

М. Густокашин

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

Пример входного фалйа

Пример выходного файла

Решение g6_1023:

В этом решении есть ошибка. То есть не то что ошибка, а недоделка. А что если какое то число встречается больше 65537 раз. Тогда произойдет переполнение переменной word и восстановить массив станет невозможно! Чтобы избавиться от этой проблемы надо завести массив из 3 элементов integer, в которых будут храниться указатели на переполнившейся элемент массива. Переделать вывод результатов с использованием этого массива - задача несложная, поэтому здесь рассматриваться не будет ;)

Задача g6_1024: Знакомые

Имеется N человек и прямоугольная таблица знакомств А[1:N,1:N], в которой элемент A[i,j] равен 1, если человек i знаком с человеком j, и, соответственно, наоборот, А[i,j]=А[j,i]. Выяснить, можно ли разбить людей на 2 группы так, чтобы в каждой группе были только незнакомые люди.
Информация о знакомствах содержится в файле input.txt, в первой строке которого находится число N

6
000101

Программа должна вывести в файл output.txt одно слово: YES!, если группы создать можно, и NO -- если нельзя.

Решение g6_1024:
Очередная задача со школьной OL11 (составитель М.Ю. Надточий).
Идея состоит в том, чтобы разделить людей на три части:
1)толпа - в ней стоят еще никуда не поставленные люди.
2)группа №1.
3)группа №2.
Возьмем первого человека из толпы и поставим его в одну из групп, при этом вычеркнув из толпы. Выберем всех знакомых ему людей и поставим их в другую группу. Затем для каждого из этих людей найдем его знакомых и поставим их в другую группу. На каждом шаге будем проверять, не оказался ли один и тот же человек сразу в двух группах, если оказался, то ответ NO. Такой способ дает нам гарантию, что два знакомых человека не будут в одной группе, например если два знакомых между собой человека знакомы третьему, то они оба окажутся сначала в одной группе, а затем, когда их знакомые будут переставляться в другую группу они окажутся и в другой группе.
А что делать, если в двух группах находятся незнакомые люди, а толпа еще не опустела? Тогда нужно выбрать любого человека и поставить его в любую группу (если он до сих пор в толпе, значит он не знаком ни с кем из поставленных в группы.
Главное правильно организовать проверки на то, не находится ли один человек в двух группах, и на изменение состава толпы при выборе случайного человека.
Чуть не забыл! Ответ YES надо выводить, когда толпа опустела, и каждый человек находится только в одной группе. Упс :)
Задача g6_1025: Домино

Задание. Написать программу DOMINO.*, подсчитывающую количество вариантов покрытия прямоугольника 2хN прямоугольниками 2х1. Покрытия, которые преобразуются одно в другое симметриями, считать различными.

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

DOMINO.DAT : 1

Решение g6_1025:

Теперь перед нами стоит задача посчитать числа Фибоначчи до 65536 члена. Сразу замечу, что я написал программу, которая считает 65536 член Фибоначчи примерно за 30 секунд на 400-ом Селероне. Если кто-нибудь напишет быстрее, присылайте - буду очень благодарен!

F(n)[c] := F(n-2)[c] + F(n-1)[c] + flag;

Сложение напоминает сложение столбиком, где переменная flag - это число "в уме"(первоначально равно нулю). После сложения стоит производить такие действия:

for c := k to 20000 do begin
F(n-2)[c] := F(n-1)[c];
F(n-1)[c] := F(n)[c];
end;

Мы записываем в F(n-2) число F(n-1), а в число F(n-1) - число F(n), т.е. увеличиваем n на 1.

Имеются монеты c различными фиксированными номиналами, выраженными в копейках (например, 3 и 5 копеек) в достаточном количестве. Написать программу COINS.*, которая:

а) определяет, можно ли представить заданную сумму S (выраженную в копейках), пользуясь монетами заданных номиналов,
б) если это возможно, то представляет эту сумму с помощью минимального количества монет.

Входные данные: Входной файл COINS.DAT содержит в первой строке сумму S (0

Выходные данные: Выходной файл COINS.SOL должен содержать в первой строке знак "+", если заданную сумму S можно представить, и знак "-", если нельзя. Если представленная сумма существует, то следующие N строк должны содержать количества монет каждого номинала, которые необходимы для представления суммы S с помощью минимального количества монет.

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

Представить 514 копеек с помощью монет номиналом в 3 и 5 копеек

COINS.DAT:

COINS.SOL:

Представить 27 копеек с помощью монет номиналом в 5 и 13 копеек

COINS.DAT:
27
2
5
13

COINS.SOL:

Решение g6_1026:

Даны натуральное число n, 1
Требуется получить последовательность x1, y1, x2, y2, ..., xk, yk, где x1, x2, ..., xm -- взятые в порядке следования четные (делящиеся нацело на 2) члены последовательности a1, a2, ..., an, а y1, y2, ..., yl -- взятые в порядке следования нечетные члены последовательности a1, a2, ..., an, k = min(m, l), m + l = n.

Формат входных данных

Пример:
10

Формат выходных данных

Пример:
98 33 56 73 8 41 48 93

Решение g6_1027:
Простая задача. Заведем два дополнительных массива размерностью 50, один из которых будет хранить четные, а другой - нечетные члены последовательности. Для каждого из массивов заведем собственный счетчик, указывающий на количество членов в данном массиве.
Первоначально инициализируем счетчики нулем. Затем, при чтении очередного числа, проверяем, четное ли оно и, в зависимости от четности, помещаем в один из массивов(до этого увеличив соответственный счетчик на 1).
После того, как разбиение последовательности на две закончено, найдем, какой из счетчиков меньше. В случае если минимальный счетчик раве 0 - выводим 0 и выходим, иначе последовательно выводим сначала четное число с номером n, а затем нечетное с номером n (n изменяется от 1 до min).
Задача g6_1028: Считаем кораблики

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

Формат входных данных

Формат выходных данных

Пример:
7

Решение g6_1028:
В этой задаче нам понадобиться все кораблики "утопить". На самом деле решение простое:
Идем от левого верхнего угла по строкам (сначала просматриваем первую строку, затем вторую и т.д.). В случае если нашли "1" (кусок корабля), то увеличиваем счетчик на 1, а кораблик топим. Я топил кораблики рекурсивно, хотя здесь можно было сделать это без рекурсии, потому как кораблики не гнутые. Но с рекурсией короче и универсальнее.
У нас есть координата одного сегмента корабля и знание о том, что выше и левее от него никого нет, т.е. от этого сегмента кораблик может идти только вправо или вниз. "Утопим" этот сегмент корабля(т.е. присвоим этой клетки значение, отличное от 1). Проверим, если клетка правее содержит в себе сегмент кораблика, то нашлем на нее нашу рекурсивную процедуру-убийцу(не увеличивая счетчик - кораблик то один и тот же). Точно также поступим, если клетка снизу от нашего сегмента занята корабликом. В итоге весь кораблик будет иметь статус утопленного, и мы можем смело смотреть наше поле дальше, в поиске следующих жертв маньячной процедуры (всех кого найдет - утопит, только если этот кораблик не авианосец в форме перевернутой буквы "П", но их в этой игре вроде бы нет, да и исправить процедуры несложно :).