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

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

 Отправлено: 18.10.17 16:42. Заголовок: Конкурс по информатике "Отличник"

Конкурс по информатике "Отличник" - всероссийский дистанционный конкурс, в котором могут принять участие ученики 2-11 классов, а также студенты первых курсов учреждений среднего профессионального образования.

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

https://konkurs-otlichnik.ru/inf

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

Итак, олимпиада началась, на данный момент получены и проверены решения трех участников соревнований. Лидером, набравшим 4,5 балла из 5 возможных стал Везиков Сергей Викторович, учитель ИВТ Краснокоммунарской средней школы.
Решения всех олимпиадных задач лично проверяет Михаил Медведев. Кроме того, мы постараемся каждому участнику выслать краткий разбор «полетов» по всем задачам.
И это еще не все хорошие новости. Михаил Медведев предложил каждые 2-3 дня выкладывать на форуме по одной новой задаче для решения. После истечения этого времени, Михаилом Медведевым будет дан подробный разбор задачи, а также будет указано на ошибки, допущенные при решении. Таким образом, у вас постоянно будет возможность заниматься решением олимпиадных задач и получать квалифицированную помощь.

Итак, первая задача:
Написать программу решения следующей задачи.
По заданному натуральному числу ищется его сумма цифр. Если сумма больше 9, то снова ищется ее сумма цифр. Процесс продолжается до тех пор, пока очередная сумма не станет меньшей 10. Необходимо найти это значение последней суммы.
Например, для числа 12345 сумма цифр равна 1 + 2 + 3 + 4 + 5 = 15. Ищем сумму цифр числа 15. Она равна 1 + 5 = 6. Результатом будет 6.

Желаю успеха!

 Отправлено: 18.09.06 19:55. Заголовок: Решение первой задачи

Это решение первой задачи поступило от Везикова Сергея Викторовича. Напоминаю, что эти задачи рассчитаны для разбора решений именно на форуме, так что отправлять решения на e-mail нет необходимости. Размещайте свои решения прямо в этом разделе форума.
uses crt;
var
a,s:integer;
function sum(a:integer):integer;
var
i:integer;
begin
i:=0;
while a<>0 do begin
i:=i+(a mod 10);
a:=a div 10;
end;
sum:=i
end;
begin
clrscr;
readln(a);
s:=sum(a);
while s>10 do
s:=sum(s);
writeln(s);
readkey
end.

 Отправлено: 18.09.06 13:53. Заголовок: Re:

Решения задач предлагается писать здесь же, в форуме.
Я постараюсь комментировать Ваши решения - здесь же, в форуме.

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

Определить, сколько чисел в инервале от min до max (включительно) нацело делится на factor. Например, если min = 7, max = 24, factor = 3, то ответ будет 6, так как между числами 7 и 24 (включительно) находится 6 чисел, делящихся на 3: 9, 12, 15, 18, 21, 24.

 Отправлено: 18.09.06 16:31. Заголовок: Решение предыдущей задачи

var
i,j,factor, max,min:Integer;
begin
Write('Input min=');ReadLn(min);
Write('Input max=');ReadLn(max);
Write('Input factor=');ReadLn(factor);
for i:=min to max do
if i mod factor=0 then inc(j);
Write('Output > ',j);
end.

 Отправлено: 18.09.06 16:48. Заголовок: To sedovmih

Попробуйте оптимизировать программу. Считайте, что значения min и max порядка 10^16 (в Паскале Вам пришлось бы воспользоваться типом Extended, в Си и уже в Делфи для этого есть 64 битовый тип).
В таком случае при использовании
for i:=min to max do
вы получили бы ошибку "Time Limit". Жду следующих вариантов Вашей программы.

 Отправлено: 18.09.06 20:01. Заголовок: Re:To sedovmih

var
i,j,factor, max,min:Integer;
begin
ReadLn(min);
ReadLn(max);
ReadLn(factor);
i:=min;
repeat
if i mod factor =0 then
begin
min:=i;
j:=1;
end
until j<>1;
j:=((max-min) div factor)+1;
Writeln('Output > ',j);
end.

 Отправлено: 18.09.06 21:15. Заголовок: To: Решение первой задачи and sedovmih

Уважаемые участники форума! Задачи я подбираю начиная с простого
уровня. Но некоторые из них кроме очевидного решения, имеют
довольно интересное, простое олимпийское решение. Есть две категории:
техника - умение решать классические задачи классическим путем
и математика - умение находить именно "красивое " решение.

To Везиков, по поводу первой задачи:
попробуйте найти решение, вообще не использующее ни единого
цикла :-)

To sedovmih:
Ваша программа дает неверный ответ для min = 3, max = 4, factor = 5.
Ваша программа дает 1, а на самом деле ответ должен быть 0, так как
между 3 и 4 нет чисел, делящихся на 5.
На тесте min = 2, max = 8, factor = 2 программа зацикливается.

Я постараюсь в следующих задачах конкретнее задавать спецификацию
входа и выхода. Например, для второй задачи (с учетом целочисленного типа integer в Паскале)
имеют место ограничения -30000 <= min, max <= 30000,min <= max, 1 <= factor <= 30000.

Предлагаю следующий вариант работы: или Вы в какой-то момент предлагаете мне вывесить
свое решение с объяснением, или подождать, дать время подумать (но не более 2-3 дней :) ).

 Отправлено: 19.09.06 00:06. Заголовок: Re:

Предлагаю Вашему вниманию задачу посложнее.

Альберт и его две сестры Бетти и Карина делят имущество. Стоимости вещей, доставшихся в наследство, выписаны на куске бумаги и задаются массивом assets. Альберт берет ножницы и разрезает бумагу между некоторыми двумя числами. Потом Бетти таким же образом разрезает один из кусков. Далее Карина выбирает кусок с максимальной суммой. Из оставшихся двух кусков выбор делает Бетти. Последний кусок достается Альберту.
Каждый из участников при выборе старается получить максимальную сумму наследства. Сестры обижены на брата, и в своих выборах будут наказывать его, если только при этом не пострадает их прибыль. Например, если у одной из сестер есть два разные варианта получить одну и туже сумму имущества, то она выберет тот из вариантов, при котором ее сестра получит больше. Найти максимальную сумму, которую может обеспечить Альберт своим первым разрезом.

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

 Отправлено: 20.09.06 12:35. Заголовок: Решение задачи про сумму цифр числа

Повторю еще раз условие задачи:

По заданному натуральному числу ищется его сумма цифр. Если сумма больше 9, то снова ищется ее сумма цифр. Процесс продолжается до тех пор, пока очередная сумма не станет меньшей 10. Необходимо найти это значение последней суммы.
Например, для числа 12345 сумма цифр равна 1 + 2 + 3 + 4 + 5 = 15. Ищем сумму цифр числа 15. Она равна 1 + 5 = 6. Результатом будет 6.

Решение:
Обозначим сумму цифр числа n через S(n). Число n делится на 9 тогда и только
тогда, когда S(n) делится на 9. В задаче требуется найти значение S(S(...S(n)...)),
которое меньше 10. Оно равно n mod 9, так как числа n и S(S(...S(n)...)) дают одинаковый
остаток при делении на 9. При этом если входное значение n = 0, то результат равен 0.
Если n > 0 и n mod 9 = 0, то результирующее значение равно 9.

program sum;
var
n:integer;
begin
readln(n);
if (n = 0) then writeln(0) else
if (n mod 9 = 0) then writeln(9)
else writeln(n mod 9);
end.

 Отправлено: 20.09.06 12:48. Заголовок: Re:

У нас еще осталась одна нерешенная задача, но я хочу предложить следующую:

Для заданного числа n найти ближайшее целое, которое делится на b. Если таких чисел несколько, то найти наибольшее.

Например, если n = 100, b = 3, то ближайшим целым к 100, делящимся на 3, будет 99.
Если n = 5, b = 10, то ответом будет 10. По отношению к 5 числа 0 и 10 находятся на одинаковом расстоянии. Но по условию в таком случае требуется найти наибольшее число.
Если n = 4, b = 10, то ответом будет 0
Ограничения на входные данные: 0 < n <= 10^6, 2 <= b <= 500. В Паскале используйте тип longint. (операция ^ - это степень)

Жду Ваших решений :-)

 Отправлено: 20.09.06 13:05. Заголовок: Re:

Для умения эффективного решения олимпиадных задач следует обладать двумя способностями:
1. Алгоритмическое мышление - то есть умение математически решать задачу.
2. Техника. Для каждого языка она своя, в Си она на порядок выше, но пока остановимся на Паскале.

Предлагаю следующие упражнения (задачи) на технику:
1. В переменных a и b находятся целые числа. Поменять значения переменных местами. Ни у кого
не возникнет проблемы решения задачи, вводя новую переменную. А попробуйте решить
эту задачу не вводя новой переменной.

2. Все вы наверное знаете что такое двоичная система исчисления. Например, 7 = 111, 10 = 1010.
В задаче требуется по заданному натуральному числу n уничтожить последнюю единицу
в ее бинарном представлении. То есть если n = 7, то ответом будет 6. Пояснение: 7 = 111,
уничтожая последнюю единицу, получим 110, что является 6 в десятичном представлении.
Если n = 10, то ответом будет 8, так как 10 = 1010, уничтожаем последнюю единицу: 1000 = 8.
Для числа n = 8 ответом будет 0.

Я пока не хочу давать наводящих ответов, но и затягивать решения задач не хочется.
Давайте установим срок 3-4 дня, после чего я вывешу ответы.

 Отправлено: 20.09.06 21:25. Заголовок: Меняем значения переменных местами

Честно говоря, мне уже попадалась где-то эта задача. Вот решение:
var
x,y: integer;
begin
x:= 1;
y:= 2;
x:= x+y;
y:= x-y;
x:= x-y;
writeln (x,y);
end.
На входе 1 и 2, на выходе 2 и 1.
Может стоит ввести сквозную нумерацию всех задач? Например 1А, 7В и т.д.?

 Отправлено: 21.09.06 08:16. Заголовок: TO Учитель

Решение засчитывается!
Только вывод лучше писать так: writeln (x,' ',y); Так красивее.
Вообще многие предлагаемые мной задачи встречались. Задача про обмен местами значений, например, есть в книге Шеня.

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

У нас еще остались нерешенными две задачи и одно упражнение.

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

Упражнение 2
var n,m,k:integer;
begin
readln(n); m:=1; k:=n;
while n mod 2<>1 do
begin n:=n div 2; m:=m*2 end;
writeln(k-m);
end.

 Отправлено: 05.10.06 09:49. Заголовок: задача2

program task2;
var n, b, c, d,i: integer;
begin
write('n=');readln(n);
write('b=');readln(b);
c:=n;d:=n;
if (n mod b)=0 then writeln('Otvet=',c)
else
begin
repeat
c:=c+1;
until (c mod b)=0;
repeat
d:=d-1;
until (d mod b)=0;
if abs(d-n)=abs(c-n) then writeln('Otvet=',c) else

if abs(d-n)<abs(c-n) then writeln('Otvet=',d) else
writeln('Otvet=',c);
end;
readln;
end.

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

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

 Отправлено: 22.09.06 15:45. Заголовок: TO nikifor:

Упражнение 2 работает правильно. А попробуйте сделать его без цикла!
На то и олимпиадная задача, чтобы написать олимпиадное решение :-)
Подсказка: решение можно написать одним выражением.

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

Кстати, небольшая поправочка к моему решению задачи про сумму цифр числа.
Вместо кода

program sum;
var
n:integer;
begin
readln(n);
if (n = 0) then writeln(0) else
if (n mod 9 = 0) then writeln(9)
else writeln(n mod 9);
end.

можно написать

program sum;
var
n:integer;
begin
readln(n);
writeln((n-1) mod 9 + 1);
end.

Код явно короче, и оно работает! Работает потому что в Паскале -1 mod 9 = -1,
хотя математически это будет 8.

 Отправлено: 22.09.06 22:43. Заголовок: Re:

program factor;
var
kol,mx,mn,min,max,factor:integer;
begin
readln(min);
readln(max);
readln(factor);
mn:= min div factor;
mx:= max div factor;
kol:=mx-mn;
if (min mod factor)=0 then inc(kol);
writeln(kol);
end.

 Отправлено: 22.09.06 23:19. Заголовок: To Geliya

Ваша программа дает верные ответы, когда входные числа неотрицательны.
По условию входные числа целые. Например, Ваша программа не верна когда
min = -3, max = 0, factor = 5. Программа дает ответ 0, хотя должна 1 (имеется число 0, которое делится на 5).

Что-то никто не предлагает решение задачи про раздел имущества брата и двух сестер
(условие смотри выше). Задача сложная, но я прошу не писать программу, а просто дать
ответ для конкретного входного значения 1 1 1 1 1 1 1 1 1 (9 единиц).