Задача в неделю (стр. 4 )

Требуется написать программу, которая определяет результат умножения Q на N, то есть непериодическую часть и минимальный период числа QxN. В случае получения результата умножения в виде конечной дроби скобки опускаются.

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

Ограничение по времени тестирования: 1 секунда на один тест.

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

Входной файл INPUT. TXT содержит две строки. В первой строке задается дробь Q, а во второй - число N.

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

В единственной строке выходного файла OUTPUT. TXT должен содержаться результат умножения Q на N.

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

0.1(6)

3

Пример файла выходных данных (для приведенного выше входного файла):

0.5

Разбор задачи № B

Задача имеет 2 решения. Например, можно перевести дробь в обыкновенную, потом числитель умножить на N, а затем снова делить, выделяя период. Но в длинной арифметике это технически сделать сложно. Проще разработать алгоритм умножения периода на число, а потом, если потребуется, период сократить, при этом еще нужно помнить, что 0.(9)=1, иначе период не будет минимальным.

Можно использовать следующее правило умножения периода правильной дроби на произвольное натуральное число:

1) если при умножении периода дроби на некоторое число количество цифр в произведении равно количеству цифр в периоде исходного числа, то период результата равен полученному произведению и переходим к (6), в противном случае - к (2);

2) "лишними" цифрами будем считать n-k первых слева цифр результата, где n - количество цифр в результате, k - количество цифр в периоде исходной дроби;

3) сложим число, образованное "лишними" цифрами, с числом, образованным правыми k цифрами промежуточного результата;

4) если количество цифр в получившемся результате сложения больше чем k, то процесс следует повторить с (2);

5) если количество цифр результата сложения стало равным количеству цифр периода исходной дроби, то период произведения равен последнему результату суммирования;

6) теперь надо попытаться сократить период. Для этого ищем повторяющиеся части периода и, если они есть, то уменьшаем длину периода. После этого, по возможности, сдвигаем период влево. Если период равен 9, то его удаляем, добавляя 1 к последнему разряду.

7) непериодическая (целая - для чисто периодических дробей) часть результата равна сумме чисел, образованных из "лишних" цифр каждого этапа. Если же у исходной дроби изначально была своя непериодическая часть, то умножить также следует и ее, а затем сложить с результатом умножения периода.

Рассмотрим два примера. Вначале выполним умножение 0,(7)*16. Для этого умножим период дроби на 16: 7*16=112. В периоде дроби одна цифра, а в произведении - три цифры. Следовательно "лишними" являются две левые цифры, образующие число 11. Прибавив 11 к 2, получим 13, что опять превышает исходную длину периода на одну цифру. Вновь сложим "лишнее" число 1 с правой цифрой результата, 1+3=4. Количество цифр результата равно количеству цифр в периоде исходной дроби, следовательно, период произведения равен 4. Целая же часть результата умножения равна 11+1=12 (в процессе ее формирования участвуют только "лишние" цифры). Таким образом получается ответ: 0,(7)*16=12,(4).

В качестве второго примера выполним умножение 0,7(6)*12. Для этого сначала умножим на 12 периодическую часть. 6*12=72. В получившемся произведении две цифры, а в исходном периоде - одна. Следовательно, "лишнее" число равно 7, результат сложения равен 2+7=9. В получившемся результате количество цифр равно количеству цифр в периоде исходной дроби, т. е. период произведения равен 9. Непериодическая часть произведения равна единственному "лишнему" числу - 7. Таким образом, 0,0(6)*12=0,7(9)=0,8. Затем умножим на 12 непериодическую часть исходной дроби 0,7*12=8,4. В результате получаем: 0,7(6)*12 = 8,4+0,8= 9,2.

Задача C. "Сообщение" (20 баллов)

Из пункта А в пункт Б с помощью двух курьеров было отправлено сообщение, состоящее из символов 0 и 1. Каждый из курьеров шутки ради проделал несколько раз следующее преобразование сообщения: любую часть, содержащую две единицы записал в обратном порядке (перевернул). Например, в сообщении 11010100 курьер мог перевернуть подстроку, составленную из символов со 2 по 5 позиции, и тогда получалось сообщение 10101100. Получив два сообщения в пункте Б решили проверить их эквивалентность, т. е. можно ли получить одно из другого с помощью описанных преобразований.

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

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

Ограничение по времени тестирования: 3 секунды на один тест.

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

Входной файл состоит из двух строк – полученных сообщений. Их длина не превышает 100 символов.

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

Если сообщения не эквивалентны, то выходной файл должен содержать только строку «No». Если сообщения эквивалентны, то в первую строку выходного файла нужно вывести слово «Yes», в последующие последовательность преобразований первого сообщения во второе. Каждое преобразование записывается в отдельной строке в виде пары чисел i, j (разделенных пробелом), означающей, что переворачивается подстрока, составленная из символов с номерами i, i+1, ..., j.

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

100011100

001011001

Пример файла выходных данных (для приведенного выше входного файла):

Yes

6 9

3 8

1 5

Задача D. "Свинья-копилка" (30 баллов)

Для того чтобы начать свой бизнес, юный коммерсант решил накопить немного денег. С этой целью он отыскал свинью-копилку и начал собирать деньги.

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

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

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

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

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

Входной файл INPUT. TXT состоит из следующей последовательности строк. В первой строке содержатся два целых числа:

E – вес пустой копилки (1≤E≤10000);

F – вес копилки, заполненной монетами (1≤E≤F≤10000);

Вторая строка содержит целое число N (1≤N≤500) — количество типов монет.

Каждая из последующих N строк служит для описания монет заданных типов и содержит по два целых числа — Pi и Wi (1≤ Pi ≤30000, 1≤ Wi ≤10000, 1≤ i ≤ N), где Pi — достоинство монеты i-го типа, а Wi — ее вес.

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

Выходной файл OUTPUT. TXT должен содержать одно целое число — значение минимальной суммы денег, которая может находиться в копилке. Если заданный вес копилки F не может быть достигнут с монетами заданного типа, то выходной файл должен содержать сообщение "No".

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

INPUT. TXT	OUTPUT. TXT
10 110	60
2
1 1
30 50
INPUT. TXT	OUTPUT. TXT
10 110	100
2
1 1
50 30
INPUT. TXT	OUTPUT. TXT
1 6	No
2
10 3
20 4

Разбор задачи № D

Задача решается методом динамического программирования. Для этого обозначим через D(w, k) – минимальную сумму монет в копилке, которые имеют вес w и состоят из монет первых k типов. Для этой функции имеет место следующее соотношение D(w, k)= min{D(w, k-1), D(w-Wk, k)+Pk}. Ответом задачи будет значение функции D(F-E, N). Вычисление этого выражения легко организовать с помощью одного одномерного массива. Реализацию представленного алгоритма смотрите в программе.

var

e, f, n, i, j : integer;

m : longint;

P, W : array [1..500] of integer;

D : array [0..10000] of longint;

f1, f2 : text;

begin

assign(f1,'input. txt'); reset(f1);

read(f1,e, f);

f:=f-e;

read(f1,n);

for i:= 1 to n do read(f1,P[i],W[i]);

D[0]:=0; for i:=1 to f do D[i]:=maxlongint;

for i:=1 to n do

begin

j:=W[i];

while j<=f do

begin

m:=D[j-W[i]];

if m<maxlongint then m:=m+P[i];

if m<D[j] then D[j]:=m;

j:=j+1

end

end;

assign(f2,'output. txt'); rewrite(f2);

if D[f]=maxlongint then write(f2,'No')

else write(f2,D[f]);

close(f2)

end.

Задача E. "Сундук Билли Бонса" (20 баллов).

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