Олимпиадные задачи.

[Kitozavr]

Нашёл вчера листок с олимпиадными задачами по информатике:
1)
Петя, Катя и Серёжа делают из бумаги журавликов. Вместе они сделали $S$ журавликов. Сколько журавликов сделал каждый ребёнок, если известно что Петя и Серёжа сделали одинаковое количество журавликов, а Катя - в два раза больше чем Петя и Серёжа вместе?
Входные данные:
одно натуральное число $S<10^6$
Выходные данные:
Три числа, разделённые пробелами - количество журавликов, которые сделал каждый ребёнок (Петя, Катя, Серёжа).

2)
Дни недели пронумерованы следующим образом: 1 - понедельник, 2 - вторник... Дано целое число $K$, лежащее в диапазоне 1-365, и целое число $N$, от 1 до 7.
Написать программу, определяющую номер для $K$-го дня года, если известно что 1 января было днём недели с номером $N$.
Входные данные:
Два числа через пробел: $0<K<366$ и $0<N<8$
Выходные данные:
Одно число - номер дня недели для $K$-го дня года.

3)
Из шахматной доски по границам клеток выпилили связную (не распадающуюся на части) фигуру без дыр. Требуется определить её периметр.
Входные данные:
сначала вводится число $1<N<64$ - количество выпиленных клеток. В следующих $N$ строках вводятся координаты выпиленных клеток, разделённые пробелом (номер строки и столбца - число от 1 до 8). Каждая выпиленная клетка указывается один раз.
Выходные данные:
Выведите одно число - периметр выпиленной фигуры (сторона одной клетки единица)

Я решил первые две (то есть мне так кажется - у меня нет ответов).

[PAV]

В чем вопрос-то заключается?

(И для какого класса эти олимпиадные задачи?)

[Kitozavr]

Надо программы написать. Нам давали в 11 классе, но олимпиада почему-то накрылась.

[venco]

Первые две задачи похожи на обычное домашнее задание.
Т.е. если в классе учат именно программированию, то такие задачи должны уметь решать все.

[Kitozavr]

(Оффтоп)

С информатикой у нас в школе было плохо. До 6-го класса информатика была, но учитель на уроке смотрел порнографию , а самые приличные из класса резались в КС, остальные тоже смотрели. Потом его уволили, слышал будто завуч засекла его за просмотром, и до 10 класса информатики не было. Даже эти два года много уроков пропускалось - однажды учительница попала в аварию.

Посмотрел листок - это олимпиада для 8-11 классов, там должны быть ещё три задачи, но они у меня не сохранились.

[PAV]

Kitozavr в сообщении #342750 писал(а):

Надо программы написать.

Ну и в чем конкретные затруднения? Вы же на форуме не первый день, должны знать местные порядки.

[Kitozavr]

Да я уже решил, просто хотел обществу показать.

[PAV]

Вообще-то эти задачи слишком простые, чтобы они могли кого-то серьезно заинтересовать.

Хотя...
Можете сделать в третьей задаче вычислительную часть (без учета загрузки данных) с фиксированным временем (не зависящим от числа клеток в фигуре, ну и, разумеется, на порядок меньшим чем общее число клеток на доске) и без единого if'а?

[lim0n]

Информатику в школе не застал, поэтому не судите строго.

Используется синтаксис C

#include <stdio.h>

void main()
{
    int result = 0;
    int i, n, row, col;
    /* границы клеток доски */
    int vert[9][8], hor[9][8]; 

    for (row=0; row<9; row++)
        for (col=0; col<8; col++)
            vert[row][col] = hor[row][col] = 3;

    scanf("%d", &n);
    for (i=0; i<n; i++)
    {
        printf("%1d: ", i+1);
        scanf("%d %d", &row, &col);
        result += \
            (vert[col-1][row-1] -= 2) + \
            (vert[col][row-1] -= 2) + \
            (hor[row-1][col-1] -= 2) + \
            (hor[row][col-1] -= 2);
    }
    printf("%d\n", result);
}

[ewert]

PAV в сообщении #342875 писал(а):

Можете сделать в третьей задаче вычислительную часть (без учета загрузки данных) с фиксированным временем (не зависящим от числа клеток в фигуре, ну и, разумеется, на порядок меньшим чем общее число клеток на доске) и без единого if'а?

(Чем if'ы-то не угодили?...)

Судя по уровню остальных задач, и учитывая, что клеток всего лишь 64 -- дешевле всего будет самый тупой алгоритм. Заготавливаем доску 10 на 10 (чтоб избежать проверки попадания на край -- добавляем по одной линии по краям). Помечаем вырезанные клетки (в т.ч. добавленные) единичками и оставшиеся ноликами. Проходим по всей внутренней части 8 на 8 таблички (т.е. по фактической доске) и для каждой невырезанной клетки подсчитываем количество вырезанных соседей -- это и будет длина очередного участка границы. Здесь if'ов действительно можно при желании избежать, но единственное преимущество такого подхода -- ухудшение быстродействия.

Непонятно, при чём тут связность и односвязность фигуры. Это ограничение имело бы смысл, если бы предполагался обход только граничных клеток -- с тем, чтобы снизить объём вычислений до якобы $O(n)$. Но это лишь якобы: как минимум все вырезанные клетки так или иначе перебрать придётся, а их типичное количество всё равно порядка $O(n^2)$.

[Circiter]

На счет третьей задачки. Фигура суть многоугольник на целочисленной решетке с вершинами в её узлах. Допустим, пары координат выпиленных клеток подаются на вход алгоритма упорядоченными по строке.

Читая номера столбцов клеток для каждой строки выпиленной фигуры находим среди них минимальный и максимальный номер. Зная такие два числа для двух смежных строк-блоков фигуры находим степень перекрытия строк, которая на единицу больше количества целочисленных точек, попавших внутрь объединения рассматриваемых строк.

Суммируя по всем смежным строкам получаем количество внутренних целочисленных точек во всей фигуре. Теперь, зная число точек решетки внутри фигуры и её площадь (она же $N$), сразу же находим периметр фигуры по теореме Пика.

Итого, получаем $\mathcal{O}(1)$ по памяти и $\mathcal{O}(N)$ по времени алгоритм для доски любых размеров. Важно, чтобы фигура была односвязной (что гарантируется условием). Конечно, если координаты сыпятся в произвольном порядке, то сортировка все испортит. В этом случае такой алгоритм будет не лучше алгоритма ewert'а, который к тому же не требует связности.

2PAV
Функциональная парадигма учит, что любую программку можно написать вообще без явных условных операторов... :)

-- Сб авг 07, 2010 22:50:48 --

Кажется, сортировка в моем алгоритме приведет к необходимости линейного по стороне доски размера памяти. Асимптотики по времени это вроде-бы не коснется... Так что это (почти) оптимальный алгоритм, ну если в нем нет ошибок. :)

[ewert]

Circiter в сообщении #343120 писал(а):

Функциональная парадигма учит, что любую программку можно написать вообще без явных условных операторов... :)

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

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

[Circiter]

Дык я не говорил, что надо избегать условных операторов, я лишь сказал, что при желании из любой программки их можно безболезненно выбросить совершенно "стандартным" путем, поэтому задача "написать без if'ов" не требует напрягания мозгов. Воть. :) Воспринимайте ту мою реплику просто как лемму, ни к чему не обязывающую...

-- Вс авг 08, 2010 01:35:57 --

Кстати, может быть какую-нибудь практическую пользу от выкидывания if'ов в вашем алгоритме извлечь можно. Например если алгоритм сформулировать в терминах матриц, сверток и т.д., то возможно какой-нибудь DSP позволит решать исходную задачку очень шустро, буквально за пару тактов. :)

[lim0n]

Читатели форума имеют разный уровень подготовки, и им, наверное, были бы полезны конкретные примеры реализации алгоритмов. Вернемся к предложению PAV(кстати, а где он сам): "... и без единого if'а".

ewert писал(а):

...и для каждой невырезанной клетки подсчитываем количество вырезанных соседей...

Circiter писал(а):

...находим среди них минимальный и максимальный номер...

Здорово! Но как это реализовать? "Код в студию".

2ewert
Относительно $\mathcal{O}(N^2)$ - не понял.
Подсчитал количество переборов клеток в алгоритмах:
ваш - $100+(64-N)*2$ (и даже чуть меньше; при проходе слева направо сверху вниз проверяем правого и нижнего соседа);
мой - $4N$.

[ewert]

lim0n в сообщении #343185 писал(а):

Здорово! Но как это реализовать? "Код в студию".

for i:=1 to 8 do
  for k:=1 to 8 do
    len:=len + (1-t[i,k]) * (t[i-1,k]+t[i+1,k]+t[i,k-1]+t[i,k+1]);

lim0n в сообщении #343185 писал(а):

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

... мы обходим всю доску, а это -- $n^2$ действий.