Xитр
oе жюри (2 уровень)Условие:
Дана последовательность целых чисел. Известно, что все числа в ней встречаются четное количество раз, кроме одного, которое встречается нечетное число раз. Требуется написать программу, которая определяет это число.
Технические условия:
Ограничение по времени тестирования: по 2 секунды на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит заданную последовательность. Каждое из чисел последовательности больше -2147483649 и меньше 2147483648. В каждой строке файла записано по одному числу. Общее количество чисел в файле не превышает 500001.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать найденное число.
Примеры входных и выходных файлов:
Input.txt
-1
2
-1
Output.txt
2
Решение:
---------- cut ----------
Рассмотрим следующую операцию сложения по модулю 2: 0+0=0, 1+0=1, 0+1=1 и 1+1=0. Многозначные числа будем складывать поразрядно после двоичного разложения каждого из слагаемых. Так определенная операция сложения обладает следующими свойствами: a+0=a, a+a=0, a+b=b+a, (a+b)+c=a+(b+c). Этих свойств достаточно, чтобы показать, что такая сумма чисел, удовлетворяющих условиям задачи, как раз и будет искомым числом. Действительно, числа, которые встречаются четное количество раз, дают в результате сложения 0 (после перегруппировки слагаемых), а, так как только одно из них встречается нечетное число раз, то оно и останется после всех сложений.
В математике и программировании описанное сложение еще называют исключающим “или”, а в Турбо Паскале это сложение реализована как операция “XOR” над целыми числами. Следуя авторам, подсказка была заложена в названии задачи. Приведенные соображения и реализованы в программе:
---------- cut ----------
var
x, y : longint;
f, g : text;
begin
assign(f,'input.txt');
reset(f);
assign(g,'output.txt');
rewrite(g);
x:=0;
while not eof(f) do
begin
readln(f,y);
x:=x xor y;
end;
writeln(g,x);
close(g)
end.
Условие:
Рассмотрим сумму:
где n! обозначает произведение 1*2*3*...*n. Требуется написать программу, которая по заданным n и k определяет k-ю цифру десятичного разложения дробной части числа S
n.Технические условия:
Ограничение по времени тестирования: по 3 секунды на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит две строки. В первой записано число n (2<n<=1000000000), во второй k (1<=k<=50000).
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать найденную цифру.
Примеры входных и выходных файлов:
Input.txt
3
100
Output.txt
3
Решение:
---------- cut ----------
Преобразуем сумму следующим образом:
Таким образом, задача свелась к вычислению десятичного разложения 1/n!. Для получения k-ой десятичной цифры воспользуемся длинной арифметикой. При этом учтем, что первые цифры в десятичной записи дроби 1/n! при увеличении n становятся нулями. Эти соображения и реализованы в программе:
---------- cut ----------
var
n, k, i, m, p, z : longint;
a : array [1..50000] of byte;
f, g : text;
begin
assign(f,'input.txt'); reset(f);
assign(g,'output.txt'); rewrite(g);
readln(f,n);
readln(f,k);
z:=0; m:=2;
a[1]:=5; for i:=2 to k do a[i]:=0;
while (z<k) and (m<n) do
begin
m:=m+1;
p:=0;
for i:=z+1 to k do
begin
p:=p*10+a[i];
a[i]:=p div m;
p:=p mod m
end;
while (z<k) and (a[z+1]=0) do z:=z+1
end;
write(g,9-a[k]);
close(g)
end.