Форум » Олимпиадное программирование » Готовимся к олимпиадам 2009/2010 учебного года » Ответить

Готовимся к олимпиадам 2009/2010 учебного года

inf777: Раздел создан для учащихся Старополтавской СОШ. Т.к. у нас кружок по программированию будет проводиться только раз в неделю, будем пробовать решать некоторые задачи в этой теме. Приглашаю порешать задачки всех желающих.

Ответов - 11

inf777: Условие задачи: На числовой прямой заданы два отрезка концами своих координат. Концы первого отрезка имеют координаты a и b, второго c и d. Необходимо проверить, пересекаются ли эти отрезки. Отрезки пересекаются, если они имеют хотя бы одну общую точку. Вход. Четыре целых числа a, b, c, d (a < b, c < d) – координаты концов двух отрезков на числовой прямой. Выход. Строка “YES” или “NO” в зависимости от того, пересекаются ли два заданных отрезка. Пример входа 3 7 6 7 Пример выхода YES

inf777: Задачка простая, но в ней есть подвох. Расскажу какой произошел курьез с этой задачей пару лет назад. Данную задачу подготовил Михаил Медведев для конкурса проводимого на сайте Информатика в школе. Условие этой задачи, параллельно, решили использовать в одном из регионов России на региональной олимпиаде. В итоге, решение одного из участников было признано верным на региональной олимпиаде (в жюри входили кандидаты наук). А вот, тоже кандидат наук, Михаил Медведев, признал его не верным. Как такое могло произойти при решении такой простой задачи, я расскажу немного позже, когда появятся первые варианты решений.

inf777: Просьба не оставлять ссылки на сайт "slil.ru" - антивирус AVAST воспринимает ссылки на этот сайт как троян. Видимо сайт занесен в "черный" список программы. Теперь по решению: uses crt; var a,b,c,d:integer; res:string; begin res:=('yes'); read (a,b,c,d); if (a<c) and (b<c) then res:=('no'); if (c<a) and (d<a) then res:=('no'); write (res); end. Красиво, но если ввести координаты отрезков так a=8, b=4, c=3, d=5, то результат будет "no", хотя второй отрезок лежит на первом. Вот вам и "подвох" о котором я говорил ранее, ведь в условии задачи не указанно, как именно вводить координаты отрезков, значит их можно вводить произвольно, т.е сперва конец, а потом начало отрезка.


SIV: В условии сказано: a < b, c < d

inf777: SIV пишет: В условии сказано: a < b, c < d Просмотрел

inf777: Найти сумму цифр целого числа при N <= 10. Пример входа 5 12345 Пример выхода 15

inf777: inf777 пишет: Найти сумму цифр целого числа при N <= 10. Собственно это и не задача, а задачка не технику программирования. Десятизначное число поместиться в переменную типа longint. Далее запускаем цикл и используя x mod 10 получаем последнюю цифру, а используя x div 10 эту цифру удаляем из числа, т.к. мы ее уже посчитали.

inf777: Это одна из самых простых задач которые предстояло решить участникам областной олимпиады по информатике среди школьников в январе 2009 года (г. Волгоград, Политехнический университет). Черно-белая графика Имя входного файла: bw.in Имя выходного файла: bw.out Максимальное время работы на одном тесте: 2 секунды Максимальный объем используемой памяти: 64 мегабайта Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной w и высотой h, разбитых на w×h единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы. Во многих областях очень часто возникает задача комбинации изображений. Одним из простейших методов комбинации, который используется при работе с черно-белыми изображениями, является попиксельное применение некоторой логической операции. Это означает, что значение пиксела результата получается применением этой логической операции к соответствующим пикселам аргументов. Логическая операция от двух аргументов обычно задается таблицей истинности, которая содержит значения операции для всех возможных комбинаций аргументов. Например, для операции «исключающее ИЛИ» эта таблица выглядит так. Первый аргумент Второй аргумент Результат 0 0 0 0 1 1 1 0 1 1 1 0 Требуется написать программу, которая вычислит результат попиксельного применения заданной логической операции к двум черно-белым изображениям одинакового размера. Формат входных данных Первая строка входного файла содержит два целых числа w и h (1 ≤ w, h ≤ 100). Последующие h строк описывают первое изображение и каждая из этих строк содержит w символов, каждый из которых равен нулю или единице. Далее следует описание второго изображения в аналогичном формате. Последняя строка входного файла содержит описание логической операции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат применения логической операции в случае, если оба аргумента – нули, второе – результат в случае, если первый аргумент – ноль, второй – единица, третье – результат в случае, если первый аргумент – единица, второй – ноль, а четвертый – в случае, если оба аргумента – единицы. Формат выходных данных В выходной файл необходимо вывести результат применения заданной логической операции к изображениям в том же формате, в котором изображения заданы во входном файле. Пример входных и выходных данных bw.in bw.out 5 3 01000 11110 11110 11100 01000 11110 10110 00010 10110 0110

inf777: Вот пример процедуры сложения двух целых чисел var x,y,z: integer; procedure sum(var a,b,c:integer); begin c:=a+b; end; begin read(x,y); sum(x,y,z); write(z); end.

inf777: Различие между процедурами и функциями Функции - это процедуры особого вида, результатом работы которых является некоторое значение, подобное переменной. Функция, как и процедура, может иметь список параметров, следующих за именем функции в круглых скобках. Но если имя процедуры используется только для ее вызова, то с именем функции связывается ее значение. На примере задачи сложения двух целых чисел проиллюстрируем возможности Турбо Паскаля 7.0 по оформлению подпрограмм при помощи процедур и функций, а также рассмотрим различия между этими двумя подходами. Program ProcedureAndFunction; Uses Crt; Var a, b, SumNumbers : integer; Procedure Summa1(Var Sum : integer; a, b : integer); Begin Sum:= a+b; End; Function Sum(a, b : integer) : integer; Begin Sum:= a+b; End; Begin ClrScr; a := 12; b := 15; Summa1(SumNumbers, a, b); writeln ('С помощью процедуры сумма чисел равна ', SumNumbers); writeln ('С помощью функции сумма чисел равна ', Sum(a, b)); End. Вызов процедуры производится по ее имени. Наряду с параметрами-значениями a и b, которые подлежат сложению, в списке параметров присутствует параметр-переменная Sum, который содержит возвращаемое процедурой значение – сумму. Функция же имеет только два параметра. Это связано с тем, что само имя функции представляет собой идентификатор параметра, значение которого после окончания работы функции равно результату вычисления. Этот параметр соответствует параметру-переменной Sum процедуры. При объявлении функции ей в соответствие ставят определенный тип данных – тип возвращаемого функцией значения. Объявление функции Function Sum(a, b : integer) : integer; внешне похоже на объявление переменной Sum типа integer. Тип функции объявляется следом за списком параметров – после закрывающейся скобки этого списка и двоеточия. Процедуры и функции в Турбо Паскале отличаются не только описанием, но и способом их вызова. Так вызов функции Sum можно произвести в следующей форме SumNumbers:= Sum(a,b); Если не обращать внимания на наличие списка параметров, то этот оператор выглядит как присвоение переменной SumNumbers значения переменной Sum. Компилятор, конечно же, знает, что Sum – это имя функции (т.к. определение функции предшествует ее использованию) и организует вычисления соответствующим образом. Точно так же, как константа или переменная, вызов функции может использоваться в списке параметров оператора write (см. программу), что для процедур невозможно. Последнее отличие процедур от функций заключается в необходимости присваивания результата вычисления в теле функции переменной, имя которой совпадает с именем функции. Если такое присваивание в теле функции не выполнено, то функция не возвратит никакого результата (точнее, возвратит произвольный результат). Итак, из вышесказанного возьмите на заметку следующее. Оформлять подпрограмму как функцию целесообразно только в том случае, если она имеет один выходной параметр. Если же последовательность команд ориентирована на выполнение некоторого действия (выдача информации на экран и т.п.), целесообразно оформлять ее как процедуру.

inf777: Предлагаю попробовать решить задачку про вырубку деревьев (встречается во многих источниках). Король Флатландии решил вырубить некоторые деревья, растущие перед его дворцом. Деревья перед дворцом короля посажены в ряд, всего там растет N деревьев, расстояния между соседними деревьями одинаковы. После вырубки перед дворцом должно остаться M деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Помогите королю выяснить, сколько существует способов вырубки деревьев. Требуется написать программу, которая по заданным числам N и M определит, сколько существует способов вырубки некоторых из N деревьев так, чтобы после вырубки осталось M деревьев и соседние деревья находились на равном расстоянии друг от друга. Входные данные Входной файл INPUT.TXT содержит два целых числа M и N (0 <= M <= N <= 1000). Выходные данные В выходном файле OUTPUT.TXT должно содержаться одно число - искомое количество способов. Пример INPUT.TXT: OUTPUT.TXT для примера: 5 3 4 Ограничение времени: 1 сек на тест



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