Отправлено: 15.08.06 22:35. Заголовок: Олимпиада для учителей информатики

Напоминаю всем учителям информатики, что 10 сентября 2006 года стартует олимпиада по информатике для учителей информатики. Задачи разработаны доцентом кафедры математической информатики факультета кибернетики Киевского национального университета имени Тараса Шевченко Медведевым Михаилом Геннадьевичем.
Поступило предложение привлечь не только учителей, но и учеников. Как вы на это смотрите?
С началом конкурса мы определились, осталось определиться со сроком подведения итогов. У кого какие предложения по этому поводу, учитывая, что будет 5 задач не высокого, по олимпиадным меркам, уровня сложности?
Каким образом можно будет поощрить победителя?
Внимание! Три задачи для разминки (с решениями), будут выложены на сайте http://www.inf777.narod.ru/ до 20 августа 2006 года.

 Отправлено: 23.09.06 07:02. Заголовок: Re:

Задача 1-
uses crt;
var a,b,c:longint;
begin
clrscr;
readln(a);b:=0;
repeat
b:=b+(a mod 10);
a:=a div 10;
until(a<=0);
if b > 9 then begin
repeat
c:=c+(b mod 10);
b:=b div 10;
until(b<=0);
writeln(c);
end else writeln(b)
end.

 Отправлено: 25.09.06 20:55. Заголовок: Re:

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

Уже прошло достаточно времени, поэтому привожу решение задачи
про минимум, максимум и делитель (min,max, factor):

var min,max,factor,res:longint;
begin
readln(min,max,factor);
while(min mod factor <> 0) do Inc(min);
while(max mod factor <> 0) do Dec(max);
if (min > max) then res := 0
else res := (max - min) div factor + 1;
writeln(res);
end.

Ответ на упражнение про уничтожение последней единицы в бинарном представлении:

var n,res:longint;
begin
readln(n);
res := n and (n-1);
writeln(res);
end.

Подумайте, почему битовая операция n and (n-1) уничтожает последнюю единицу в двоичном представлении.


Следующие предлагаемые задачи я буду нумеровать.

Задача 1. Имеется кипа из numCrates корзин. Ее следует загрузить в машины, вместительность каждой из которых равна loadSize. Если кипа имеет размер, больший loadSize, то она делится пополам и каждую из частей рекурсивно грузят в машины. Если размер кипы нечетный (numCrates = 2n + 1), то при ее делении пополам в одной кипе окажется n корзин , а в другой n + 1. Сколько потребуется машин, чтобы загрузить все numCrates корзин?

Задача 2. (Условие ее приводил ранее, но попыток решения еще не видел) Для заданного числа n найти ближайшее целое, которое делится на b. Если таких чисел несколько, то найти наибольшее.
Например, если n = 100, b = 3, то ближайшим целым к 100, делящимся на 3, будет 99.
Если n = 5, b = 10, то ответом будет 10. По отношению к 5 числа 0 и 10 находятся на одинаковом расстоянии. Но по условию в таком случае требуется найти наибольшее число.
Если n = 4, b = 10, то ответом будет 0

Задача 3. В задаче требуется перевести значение температуры из одной шкалы в другую. Известно, что шкалы находятся в линейном соотношении. То есть если t1 и t2 – одна и та же температура в разных шкалах, то существуют такие действительные числа a и b, что t1 = a * t2 + b.
Известны точка замерзания f1 и точка кипения воды b1 первой шкалы, а также точка замерзания f2 и точка кипения b2 второй шкалы. Необходимо перевести значение температуры t из первой шкалы во вторую.
Например, если f1 = 0, f2=100, b1 = 1, b2 = 101, t = 28 то результатом будет 29.
Помните, что результат является действительным числом!

 Отправлено: 26.09.06 18:45. Заголовок: Решение задачи №1

var numCrates,loadSize:integer;
function load(n,m:integer):integer;
begin
if n<=m then load:=1 else
if n mod 2=0 then load:=2*load(n div 2,m) else
load:=load(n div 2,m)+load(n div 2+1,m)
end;
begin
readln(numCrates,loadSize);
writeln('m=',load(numCrates,loadSize));
readln
end.

 Отправлено: 26.09.06 19:07. Заголовок: Решение задачи 2

var n,b,d1,d2:integer;
begin
readln(n,b);
d1:=n-n mod b;
d2:=d1+b;
if n-d1 < d2-n then writeln(d1)
else writeln(d2);
readln;
end.

 Отправлено: 26.09.06 21:01. Заголовок: Подход к решению задачи о наследстве

Альберт разрежет кусок на такие части: 1 1 1 и 1 1 1 1 1 1, далее Бетти, чтобы не обидеть себя разрежет больший кусок на 1 1 1 и 1 1 1, и все получат поровну, т.е. по 3, при всех других вариантах Альберту достается меньше. Альберт, разрезая кусок, должен отрезать часть, составляющую ближайшее целое к трети наследства.

 Отправлено: 26.09.06 21:15. Заголовок: Неверно указала предыдущее решение про наследство

Нет, я не права. Если Альберт разрежет кусок на такие части: 1 1 1 и 1 1 1 1 1 1, далее Бетти, разрежет больший кусок на части 1 и 1 1 1 1 1, Карина заберет кусок 1 1 1 1 1, Бетти все равно достается 1 1 1, отрезанный Альбертом, тогда Альберту достанется всего 1. …Надо еще подумать.

 Отправлено: 26.09.06 21:26. Заголовок: Снова наследство

Альберт, зная тактику сестер, должен отрезать кусок заведомо меньший трети. Т.е в нашем случае он разрежит на 1 1 и 1 1 1 1 1 1 1, тогда Бетти делит больший кусок, стремясь к равным частям, в данном примере 1 1 1 и 1 1 1 1, Альберту достается кусок 1 1.

 Отправлено: 27.09.06 06:50. Заголовок: Решение задачи №3

Строим уравнение прямой, проходящей через точки (f1,f2) и (b1,b2), оно будет выражать зависимость t2(t1)

var f1,f2,b1,b2,t1,t2: real;
begin
readln(f1,f2,b1,b2,t1);
if b1<>f1 then t2:=(b2-f2)*t1/(b1-f1)+(f2*b1-b2*f1)/(b1-f1)
else t2:=t1;
writeln(t2:0:3);
readln
end.

Только вот как учесть ограничения на допустимость исходных данных?

 Отправлено: 27.09.06 08:31. Заголовок: To Nadegda:

1. Задача 1 о загрузке машин решена верно. Реализация рекурсивного варианта - именно то, чего хотел автор.
2. Задача о разделе имущества решена верно. Альберт в лучшем случае может получить кусок 1 1.
3. Задача 2 про округление чисел решена верно. НО: попробуйте ее решить при помощи лишь одного выражения,
не используя условных операторов.
4. Задача решена неправильно. Например, на тестах f1 = 17, f2 = 98, b1 = -123, b2 = 12, t1 = 22 Ваша программа дает 101.071,
а правильный ответ -114.6666667.
Или например для f1 = 0, f2 = 10, b1 = -10, b2 = 0, t1 = 2 Ваша программа дает 12.000, а должно быть -8.000.

Таким образом задача про раздел имущества и о загрузке машины (задача 1) считаются решенными.
Решения задач 2 и 3 принимаются еще пару дней.

Задача 4. В строке задано арифметическое выражение, содержащее однозначные числа и операции ‘+’, ‘-’ или ‘*’. Выражение не содержит пробелов. Необходимо найти значение этого выражения, если известно, что все операции имеют одинаковый приоритет и выполняются слева направо.
Например, для входной строки '2+2*2' ответ должен быть 8 (все операции имеют одинаковый приоритет!), а для
строки '4-8*9*1' ответом будет -36.

 Отправлено: 27.09.06 08:47. Заголовок: Re:

Задача 1
var n,l,s:longint;
procedure p(n:longint);
begin
if n>l then begin
p(n div 2);
p(n - (n div 2));
end
else
inc(s);
end;
begin
readln(n,l);
s:=0;
p(n);
writeln(s);
end.

 Отправлено: 27.09.06 09:36. Заголовок: Re:

Задача 1
var n,l,s:longint;
procedure p(n:longint);
begin
if n>l then begin
p(n div 2);
p(n - (n div 2));
end
else
inc(s);
end;
begin
readln(n,l);
s:=0;
p(n);
writeln(s);
end.

Задача 2

var n,b:longint;
begin
readln(n,b);
if n<n-abs(n mod b)+b/2 then
writeln(n-abs(n mod b))
else
writeln(n+b-abs(n mod b));

end.

 Отправлено: 27.09.06 18:06. Заголовок: Решение задачи 4

var s:string;r,o,err:integer;
begin
readln(s);
val(s[1],r,err);
delete (s,1,1);
while length(s)>1 do
begin
val(s[2],o,err);
case s[1] of
'+':r:=r+o;
'-':r:=r-o;
'*':r:=r*o;
end;
delete (s,1,2);
end;
writeln(r);
readln;
end.

 Отправлено: 28.09.06 02:15. Заголовок: Решение задачи №3

var f1,b1,f2,b2,t1,t2:real;
begin
readln(f1,b1);
readln(f2,b2);
readln(t1);
t2:=(f2-b2)*(t1-b1)/(f1-b1)+b2;
writeln(t2);
end.
Тесты при решении задачи №3 неверные
Порядок ввода не соблюдается, в условии задачи №3

 Отправлено: 29.09.06 12:26. Заголовок: RE:

To Nadegda:
Задача о вычислении выражения решена верно.

To nikifor:
Извиняюсь. Вы правы. Ваша программа работает верно.

Задача 2 про округление чисел. Решение:
var
n,b,res:integer;
begin
readln(n,b);
res := ((n + b div 2) div b) * b;
writeln(res);
end.


Задача 4. В компьютерных системах несколько процессов могут одновременно читать данные, но только один процесс может выполнять операцию записи в течение одного такта времени. Строка trace содержит историю работы системы и состоит из символов ‘R’ (чтение) и ‘W’ (запись). Вычислить минимальное время, за которое могут быть произведены все операции procs процессами.
Например, если trace = 'RWWRRR', procs = 3, то ответом будет 4.
если trace = 'RRRRRRRRRR', procs = 4, то ответом будет 3.

 Отправлено: 29.09.06 16:37. Заголовок: Решение задачи 4.2

var trace:string;
procs,i,k,kr:integer;
begin
readln(trace);
readln(procs);
k:=0;
kr:=0;
for i:=1 to length(trace) do
begin
if trace='w' then
begin
k:=k+1;
if kr<>0 then begin k:=k+1; kr:=0;end;
end;
if (trace='r') then
begin
kr:=kr+1;
if kr=procs then begin k:=k+1; kr:=0 end;
end
end;
if kr<>0 then k:=k+1;
writeln (k);
readln;
end.

При изменении порядка исходных данных результаты моей программы по задаче №3 тоже совпадают с вашими.

 Отправлено: 30.09.06 21:24. Заголовок: Задача от админа

Мне понравилась задачка о дележе наследства. От себя тоже хочу «подкинуть» логическую задачу. Чтобы не путать нумерацию назову ее «Задача от админа».
Имеется 10 кучек монет, в каждой кучке по 10 монет. Одна из кучек состоит из фальшивых монет. Известен вес настоящей монеты и установлено, что каждая фальшивая монета на один грамм тяжелее настоящей. Монеты можно взвешивать на пружинных весах. Как за одно взвешивание отыскать кучку состоящую из фальшивых монет?
Правильного ответа я не знаю J, но у меня есть своя версия решения задачи.

 Отправлено: 01.10.06 08:58. Заголовок: Решение задачи от админа

Из каждой кучки берем количество монет равное ее номеру. При взвешивании оказывается, что вес всего этого количества монет больше на N граммов, чем если бы все монеты были настоящими. N-номер кучки с фальшивыми монетами.
Решение придумала не сама, где-то читала.
Спасибо администратору за организацию интересного форума

 Отправлено: 01.10.06 10:07. Заголовок: Решение задачи от админа

Я согласен с решением задачи про монеты, у меня был такой же вариант. Решение пришло в голову довольно быстро. Предложил решить эту задачу ученикам на уроке информатики, но пока решение они не нашли.
У меня есть задумка собрать побольше подобных задач и давать их ученикам в начале каждого урока. Дело в том, что в поиск правильного решения включаются даже самые нерадивые ученики. Если у кого-то есть сборник подобных задач, то прошу выслать мне на e-mail. Можно сначала давать по одной задачке на форуме (для учителей), а затем использовать их на уроках.
Что касается благодарностей по поводу форума, то идея создания этого раздела принадлежит исключительно Михаилу Медведеву, так что все благодарности направляйте в его адрес.

 Отправлено: 01.10.06 20:46. Заголовок: Re:

To all: что-то я снова перепутал нумерацию задач.
Задача про процессоры и операции чтения/записи имеет номер 5.

To Nadegda:
Что-то Ваша программа на все мои тесты дает ответ 0.
Может вместо if trace='w' then Вы хотели написать if trace='w' then ...

Задача 6. Рассмотрим следующую телеигру. Имеется три двери, за двумя из которых спрятано по корове, а за третьими – приз. Игрок выбирает дверь, стараясь угадать, где находится приз. Ведущий после выбора игроком двери предлагает следующую сделку: он согласен открыть некоторую дверь, за которой находится корова в обмен на то, что игрок обязательно сменит дверь (поменяет свое мнение). Вопрос: как следует поступить игроку: менять свое мнение или нет?
Подсказка: Подсчитайте вероятность выигрыша приза в случаях, когда игрок меняет свое мнение и когда нет.

Задача 7. При покупке - продаже товаров объем, как правило, выступает стоимостной величиной. Например, если арбуз разделить на несколько частей, то сумма этих частей стоит столько же, сколько и весь арбуз. В некоторой стране к власти пришли математики и решили в качестве стоимостной величины считать не объем товара, а площадь его полной поверхности.
Сфера делится на n равных частей – долек осевыми разрезами. Какую прибыль в процентах получит математик, если он купит сферу целиком, а продаст ее отдельно по долькам? Известно, что n > 0.

 Отправлено: 01.10.06 20:52. Заголовок: Re:

я понял - форум съедает квадратные скобки.
To Nadegda: Ваша программа правильна. Просто я вводил строку заглавными буквами, а Вы обрабатывали малые буквы.
Старайтесь придерживаться спецификации входных данных.