Форум » Олимпиадное программирование » Олимпиада для учителей информатики » Ответить

Олимпиада для учителей информатики

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

Ответов - 59, стр: 1 2 3 All

Олег: Задача 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.

medv73: 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. Помните, что результат является действительным числом!

Nadegda: 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.


Nadegda: 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.

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

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

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

Nadegda: Строим уравнение прямой, проходящей через точки (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. Только вот как учесть ограничения на допустимость исходных данных?

medv73: 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.

nikifor: Задача 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.

nikifor: Задача 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.

Nadegda: 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.

nikifor: 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

medv73: 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.

Nadegda: 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 тоже совпадают с вашими.

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

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

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

medv73: To all: что-то я снова перепутал нумерацию задач. Задача про процессоры и операции чтения/записи имеет номер 5. To Nadegda: Что-то Ваша программа на все мои тесты дает ответ 0. Может вместо if trace='w' then Вы хотели написать if trace='w' then ... Задача 6. Рассмотрим следующую телеигру. Имеется три двери, за двумя из которых спрятано по корове, а за третьими – приз. Игрок выбирает дверь, стараясь угадать, где находится приз. Ведущий после выбора игроком двери предлагает следующую сделку: он согласен открыть некоторую дверь, за которой находится корова в обмен на то, что игрок обязательно сменит дверь (поменяет свое мнение). Вопрос: как следует поступить игроку: менять свое мнение или нет? Подсказка: Подсчитайте вероятность выигрыша приза в случаях, когда игрок меняет свое мнение и когда нет. Задача 7. При покупке - продаже товаров объем, как правило, выступает стоимостной величиной. Например, если арбуз разделить на несколько частей, то сумма этих частей стоит столько же, сколько и весь арбуз. В некоторой стране к власти пришли математики и решили в качестве стоимостной величины считать не объем товара, а площадь его полной поверхности. Сфера делится на n равных частей – долек осевыми разрезами. Какую прибыль в процентах получит математик, если он купит сферу целиком, а продаст ее отдельно по долькам? Известно, что n > 0.

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



полная версия страницы