четверг, 29 октября 2015 г.

Модель RGB. Работы учащихся

Модель RGB

Свет – это непрерывный поток электромагнитных волн. Человек видит волны с длиной от 400 до 700 нм. Образование «картинки» из световой энергии происходит в результате весьма сложного процесса, в котором задействован и глаз и мозг. Человек смотрит глазами, а видит мозгом.


Спектр

Со времен Ньютона известно, что луч белого (солнечного) света, входящий в стеклянную призму, разлагается на составляющие цвета. Выделяют красный, оранжевый, желтый, зеленый, голубой, синий и фиолетовый – цвета спектра или радуги.
http://chandra.harvard.edu/edu/stop/explore/images/rainbow_image2.jpg
Вместе с тем, нужны лишь три цветных луча, в сочетании дающие белый свет: это красный (Red),  зеленый (Green), синий(Blue). Это основные цвета. Цветовая модель, позволяющая получить белый свет из лучей красного, зеленого и синего цветов, взятых с соответствующими интенсивностями, называется цветовой моделью RGB.
http://www.nwpro.ru/files/images/rgb-cmyk.png
На рисунке представлены вторичные цвета: голубой (Cyan), пурпурный (Magenta), желтый (Yellow), Так как цвета получаются сложением основных цветов, говорят, что RGB - аддитивная модель.
Упражнение. Построить в графическом редакторе пересечение трех окружностей и выполнить заливку основными и дополнительными цветами.

Цветовой круг

Запомнить, из каких основных цветов получаются дополнительные цвета, поможет цветовой круг:
http://ok-t.ru/studopediaru/baza2/2064443794075.files/image001.jpg

Цветовой куб

Так как интенсивности основных цветов могут быть разными, то можно говорить о цветовом трехмерном пространстве, координаты которого R, G, B. Если принять, что интенсивность каждого цвета изменяется от 0 до 1, т.е.  0≤R≤1, 0≤G≤1, 0≤B≤1, то говорят о цветовом кубе:
http://prosjekt.ffi.no/unik-4660/lectures04/chapters/jpgfiles/RGB_cube_color.jpg


Кодирование цвета в модели RGB


В компьютерных приложениях интенсивность основных цветов задается целыми числами. Самый распространенный диапазон интенсивности в OS Windows – от 0 до 255, то есть один байт на цвет.  Обозначим r, g и b — интенсивность (в диапазоне от 0 до 255) соответственно красной, зелёной и синей составляющих определяемого цвета C. Тогда цвет C будет задаваться тройкой чисел (r, g, b). То есть ярко-синий цвет может быть определён как (0,0,255), красный как (255,0,0), ярко-фиолетовый — (255,0,255), чёрный — (0,0,0), а белый — (255,255,255).
Упражнение. В графическом редакторе постройте изображение трех лиц и выполните заливку телесными цветами (европеоидная, монголоидная, негроидная расы). Определите цвет тройкой  чисел (r, g, b).


Работа Опариной Дарии
Работа Абрамовой Евгении















Работа Ковальчук Алексея






Упражнение. В графическом редакторе постройте три прямоугольника.  Залейте прямоугольники цветом, моделируя цвет старой бумаги, папируса, пергамента. Определите цвет тройкой  чисел (r, g, b).

Работа Зориной Евгении



Работа Паршукова Кирилла



понедельник, 19 октября 2015 г.

Регистрация на личный тур Открытого чемпионата СыктГУ по программированию

Личный тур «ПЕРВОКУРСНИК» проводится 
            7 ноября 2015 г. с 13.00 до 16.00             
в рамках очередного XVII открытого чемпионата СыктГУ по программированию.
Регистрация закончена
Приглашаются все, среди первокурсников СыктГУ итоги подводятся отдельно

  1. Мельников Вадим Андреевич,  СыктГУ, 135 группа
  2. Гужева Татьяна Дмитриевна, СыктГУ , 135 группа
  3. Фельцингер Василина Сергеевна,  СыктГУ, 135 группа
  4. Лысов Юрий Юрьевич, СыктГУ, 135 группа
  5. Шосталь Борис Сергеевич, СыктГУ, 135 группа
  6. Шморгунов Александр Алексеевич, Гимназия им. А.С. Пушкина, 9 класс
  7. Виноградов Олег Дмитриевич, ГОУ РК ФМЛИ, 10 класс
  8. Галуцкий Артемий Александрович, СыктГУ, 125 группа
  9. Королев Иван Федорович, СыктГУ, 125 группа
  10. Белых Евгений Анатольевич, СыктГУ, 135 группа
  11. Осипов Михаил Леонидович, ГОУ РК ФМЛИ, 10 класс
  12. Иванов Дмитрий Сергеевич, ГОУ РК ФМЛИ, 10 класс
  13. Кит Сергей Владимирович, СыктГУ, 135 группа
  14. Попов Антон Дмитриевич, ЛНД, 10 класс
  15. Дуркин Анатолий Альбертович, СыктГУ, 119 группа
  16. Васильев Арсений Иванович, СыктГУ, 111 группа
  17. Костюк Александр Борисович,  СыктГУ, 111 группа
  18. Осташов Артур Владимирович,  СыктГУ, 115 группа
  19. Костылев Михаил Ильич, МАОУ "Технологический лицей", 11 класс
  20. Ничипорович Елизавета Дмитриевна, МАОУ "Технологический лицей", 11 класс
  21. Перков Дмитрий Георгиевич, МАОУ "Технологический лицей", 10 класс
  22. Ищук Виталий Владимирович, СыктГУ, 115 группа
  23. Петренко Константин Сергеевич, СыктГУ, 145 группа
  24. Андрей Васильевич Макаров, СыктГУ, 145 группа
  25. Бир Екатерина Алексеевна, СыктГУ, 135 группа 
  26. Мажутко Валентин Александрович, СыктГУ, 135группа
  27. Соколов Александр Сергеевич, СыктГУ, 111 группа
  28. Рябий Максим, СыктГУ, 127 группа
  29. Осипов Константин Сергеевич, СыктГУ, 149 группа
  30. Богдан Константин Вячеславович, МАОУ "Лицей народной дипломатии",11 класс
  31. Чухно Никита Александрович, МАОУ "Лицей народной дипломатии", 11 класс
  32. Пешкин Юрий Сергеевич, ЛСГУ, 8 класс
  33. Гачан Антон Романович, ЛСГУ,  9 класс
  34. Вереитин Вячеслав Анатольевич, ЛСГУ,  10 класс
  35. Катаев Егор Евгеньевич, ЛСГУ,  10 класс
  36. Туманов Дмитрий, гимназии №1, 11 класс
  37. Михайлов Юрий , гимназии №1, 11 класс
  38. Хилько Алексей, гимназии №1, 11 класс
  39. Никифоровский-Томов Владислав, гимназии №1, 11 класс
  40. Колесников Андрей Николаевич,   СыктГУ, 115 группа
  41. Торкунов Евгений Игоревич, ГОУ РК ФМЛИ, 9 класс
  42. Колегов Андрей Александрович, ГОУ РК ФМЛИ, 10 класс
  43. Терентьев Даниил Васильевич, ГОУ РК ФМЛИ, 9 класс
  44.  Рубцов Павел Александрович, ГОУ РК ФМЛИ, 9 класс
  45. Рябинин Андрей Олегович, ГОУ РК ФМЛИ, 9 класс
  46. Зиновьев Илья Сергеевич, ГОУ РК ФМЛИ, 9 класс
  47. Матвеев Константин Дмитриевич, ГОУ РК ФМЛИ, 9 класс
  48. Завьялов Никита Игоревич, ГОУ РК ФМЛИ, 10 класс
  49. Ивашева Валерия Михайловна, ГОУ РК ФМЛИ, 10 класс
  50. Зизганова Елена Сергеевна, ГОУ РК ФМЛИ, 10 класс
  51. Вологдин Максим Дмитриевич, ГОУ РК ФМЛИ, 10 класс
  52. Десятников Григорий Евгеньевич, ГОУ РК ФМЛИ, 10 класс
  53. Гладин Виталий Александрович, СыктГУ, 149 группа
  54. Кравцов Максим Станиславович , СыктГУ , 115 группа 
  55. Шелаев Илья Ростиславович, МАОУ "Лицей Народной Дипломатии", 10 класс
  56. Ванюта Егор Анатольевич, СыктГУ, 117 группа
  57. Гичев Аркадий Олегович, СыктГУ, 117 группа
  58. Крючкова Марина Дмитриевна, СыктГУ, 117 группа
  59. Саяпин Владислав Маркович, СыктГУ, 117 группа
  60. Федяева Татьяна Владимировна, СыктГУУ, 117 группа
  61. Шиханов Андрей Васильевич, СыктГУ, 117 группа

воскресенье, 18 октября 2015 г.

Разбор задач контеста на закрытии сезона 2014/2015 от В.Максименко

В мае 2015 года прошло соревнование по программированию в ФМЛ (Закрытие сезона 2014/2015). Задачи предоставил  В. Максименко. И вот, наконец, появился их разбор!

http://xupypr.com/2015/10/fml-zakryitie-sezona-2014-2015/

Цитирую.  "Я предоставил 4 задачи на этот контест. Дополнительно я предоставил ещё 3 задачи, которые являлись более строгими формулировками имеющихся задач. Я ожидал что лидеры решат минимум 4 задачи, а первые места разделят те, кто решит хотя бы одну из задач повышенной сложности. Сложные задачи, в отличие от простых не могли быть решены очевидными алгоритмами и требовали использования эффективных алгоритмов и структур данных. Вдохновение для задач я черпал из "Черепашек ниндзя" (описание задач) и курсом Роберта Седжвика Algorithms & Algorithms II наhttp://coursera.org. По итогам соревнования, сложные задачи так и не были решены ни одним участником. Это говорит о том, что ребятам нужно подтягивать свои навыки, чтобы быть успешным на соревнования Всероссийского уровня.
С текстами задач можно познакомиться тут.
С решениями и тестами тут".

вторник, 13 октября 2015 г.

Личный тур Чемпионата СыктГУ по программированию


ИТНИТ
кафедра прикладной математики и информационных технологий в образовании

объявляют о проведении личного тура «ПЕРВОКУРСНИК»
в рамках очередного XVII открытого чемпионата СыктГУ
по программированию

Приглашаются все, среди первокурсников СыктГУ итоги подводятся отдельно


 Личный тур чемпионата состоится в субботу  
7 ноября 2015 г. с 13.00 до 16.00 
в    компьютерных классах лаборатории по информатике

Регистрация участников   проводится на кафедре прикладной математики и информационных технологий в   образовании (ауд.426), а также по почте popova@syktsu.ru. Для регистрации сообщите: Фамилия Имя Отчество       Школа/ВУЗ   Класс/Группа.

 Желающим принять участие в соревнованиях необходимо зарегистрироваться до   3 ноября 2015 г.

Организационный комитет чемпионата

суббота, 3 октября 2015 г.

Разбор задач квалификационного тура четвертьфинала 2015

Задача А. ДДД
Правильный ответ задачи – 69.
Задача B. Про Дениса М.
Время, которое потратит команда, можно вычислить по формуле t = 112 + (391 + B + 1) + (B * 20), число B дано на входе. Нужно вычислить значение формулы и сравнить его с числом 738. Получается, что при B = 11 Денис ещё выходит в финал, а при B = 12 уже нет.
Задача C. Тройка чисел
Обозначим числа из входных данных a, b, c. Нам нужно выбрать максимум из a, b, c, ab, ac, bc, abc. Последнее произведение не влезает ни в один целочисленный тип, поэтому следует использовать для вычисления произведений и их сравнения тип double.
Задача D. Классификатор Тимуса
Это техническая задача, нужно написать любое решение, выполняющее то, что сказано в условии.
Задача E. Берегите брови!
Ключевые слова: дерево отрезков, дерево Фенвика, бинарное сбалансированное дерево. Если вы не сумели сдать задачу на контесте и не знаете этих слов, то вам будет полезно найти и почитать информацию о них.
Создадим бинарное сбалансированное дерево, ключами в котором будут названия напитков, а значениями – текущее количество данного напитка в шоте. В таком случае наливание жидкости – это просто увеличение значения в одной из вершин. В каждой вершине требуется дополнительно хранить сумму значений на поддереве. Тогда нахождения напитка по заданной глубине можно будет найти простым спуском по дереву.
Выпивание части одного из ликёров – это просто вычитание из значения в одной из вершин. Выпивание всего ликёра – это удаление вершины из дерева. Заметим, что удалений вершин не может быть более, чем n.
Все вышеперечисленные операции выполняются за время O(log n), что позволяет решить всю задачу за время O(n log n).
Кроме того, названия всех напитков известны заранее, поэтому мы можем заранее занумеровать их числами от 1 до n и вместо бинарного сбалансированного дерева использовать дерево отрезков или дерево Фенвика.
Задача F. Парадокс трамвая
Ключевые слова: Теория вероятности, метод динамического программирования.
Будем считать, что если в первом и втором вагоне трамвая стало равное число людей, то все останавливаются и процесс не продолжается.
dp[i][j] – вероятность того, что в какой-то момент времени в первом вагоне будет i человек, во втором – j человек. Такая функция пересчитывается за время O(1). Ответом будет сумма dp[i][i] по всем i. Итого получили решение за время O(n * n), требующее также O(n * n) памяти. По ограничению на память это решение не пройдёт, поэтому нужно сделать «расслоение». Т.е. хранить только две диагонали, начиная с диагонали с уравнением i + j = a + b, затем i + j = a + b + 1 и т.д.
Задача G. Васиана
Ключевые слова: поворот точки на угол, параллельный перенос, BigInteger (java), BigDecimal (java).
Если повернуть множество точек на угол atan2(a, d), а после этого параллельно перенести, то получится одна из четырёх фигур:
1)      Точка (0, 0)
2)      Луч с вершиной в (0, 0), направленный вверх
3)      Прямая, совпадающая с осью OY
4)      Парабола y = p * x * x
Случаи 1, 2, 3 тривиальны. В случае 4 следует растянуть параболу и окружность по обеим осям в p раз. В таком случае радиус окружности вырастет в p раз, а центр её переместится. Парабола превратится в y = x * x. Теперь единственная переменная – это y-координата точки. Далее осталось решить биквадратное уравнение.
Числа на входе превышают все возможные целые и вещественные типы, поэтому для решения задачи нужна длинная арифметика. Можно либо использовать тип BigInteger и решать в рациональных дробях, либо использовать тип BigDecimal. Все решения жюри, в том числе на C++ с самописной длинной арифметикой на массивах и на векторах, а также на Java с использованием BigInteger и BigDecimal, работают не более 0.5 секунды. Однако важно заметить, что в решении через BigDecimal используется EPS = 1e-75 (c 1e-70 даёт WA).
У жюри нет решения задачи с помощью численных методов, укладывающееся в TL. Возможно, оно есть у вас? J
Задача H. Сокращения
Ключевые слова: бор, сжатый бор, LCA – наименьший общий предок.
Заметим, что чтобы минимизировать сумму сокращений, требуется просто минимизировать длину каждого сокращения независимо.
Пусть L – суммарная длина строки.
Построим бор всех слов. Для каждой вершины сформируем список номеров строк, которым она принадлежит (суммарный размер всех списков в таком случае равен L). Каждая вершина в боре – это префикс какого-то набора исходных слов.
Также построим бор всех развёрнутых слов, назовём его B. Его использование мы опишем далее.
Будем обозначать сокращение парой чисел (a, b). Для сокращения через тире: a – длина префикса до тире, b – длина суффикса после тире. Для сокращения через точку: a – длина префикса, b = 0.
Переберём все вершины бора. Пусть мы зафиксировали некоторую вершину v и её глубина h (расстояние в буквах до корня). Для всех строк, которым принадлежит данная вершина, найдём минимальное z такое, что (h, z) – её корректное сокращение.  
Сделаем это следующим образом: возьмём список всех слов, лежащих в данной вершине, построим сжатый бор развёрнутых слов для них. Мы это можем сделать за время O(m * log m), где m – количество слов в данной вершине. Для построения такого бора можно использовать вызов функции LCA от бора B. В таком боре будет не более 2m вершин. Значит, за время O(m) мы можем обработать их все и получить ответ на все m запросов.
Общее время работы решения – O(L * log L)
Задача I. XOR
Если 2k = A XOR B, то B = A XOR 2k. Представим все числа в двоичном виде. XOR на степень двойки заменяет одну единицу нулём, либо наоборот, поэтому он меняет чётность количества единиц в двоичной записи числа. Задачу можно решить так: первая группа состоит из всех чисел с чётным числом единиц в двоичной записи, вторая группа – из всех остальных чисел.
Задача J. Делегация УрФУ
Если a делится на 3, то ответ a + b – 1, в противном случае 3 * (a + b) – 1.
Задача K. Шахматный эндшпиль

Здесь нужно аккуратно разобрать все случаи. От хода f5-e6 защититься нельзя, соответственно, для него ответ «mate». От хода b3-c3 единственная защита: d4-c3. От всех остальных ходов защищает a7-b6.

Размороженный монитор отбора на четвертьфинал 2015

Квалификационный тур четвертьфинала

Полную турнирную таблицу вышлю по запросу. Здесь публикую части, касающиеся команд, выступавших на Сыктывкарской площадке.

Место
Участник
A
B
C
D
E
F
G
H
I
J
K
Решено
Время
1
Ural FU: Dandelion (Merkurev, Sivukhin, Daniliuk)
+
+
+
+
+
+
+4
+
+
+
+
11
866
2
Ural FU: DandyLion (Permyakov, Kuchumov, Borozdin)
+1
+
+
+
+1
+

+4
+
+1
+
10
1050
3
Tyumen SU: Last Try (Durynin, Avriskin, Yagudin)
+3
+
+2
+
+4
+


+1
+
+2
9
773
.....
.........................................










.......................
70
Syktyvkar SU: Server region (Tyupikin, Ryabiy, Tkacheva)
+
+
+2





–2
+
+2
5
448

78
*Syktyvkar SCH: VOT. (Trofimova, Osipov, Vinogradov)
+4
+2
+1





–5
+1
+6
5
541

112
Syktyvkar SU: ROLL S LOSOSEM (Melnikov, Belykh, Kit)
+3
+1
+2
+





–13
+5
5
774

116
Syktyvkar SU: Brothers (Ichshuk, Durkin, Vanyuta)
+2
+1
+8






+1
+2
5
808

125
Syktyvkar SU: OEM (Lahtionov, Osipov, Gladin)
+3
+1
+4






+
+5
5
887

138
Syktyvkar SU: JolyMortNyr (Egorov, Lebedev, Drizenkov)
+1
+
+6





–9
+
+8
5
1098

178
Syktyvkar SU: SyktSU125 (Korolev, Galutskiy, Pervakov)
+
+
–3






+
+2
4
616

181
Syktyvkar SU: SyktGU145 (Drovnin, Petrenko, Makarov)
+1
+
+3
–2





–5
+8
4
684

191
Syktyvkar SU: MKN2 (Bozhok, Zhibalova, Turaew)
+
+1
+7






+4

4
762

203
Syktyvkar SU: Judas Programmist (Kuklis, Fedyaeva, Shihanov)
+6
+
+10






–8
+1
4
945

250
Syktyvkar SU: qwerty (Kozlov, Kolesnikov, Golovatenko)
+5
+
–3






+2

3
427

289
Syktyvkar SU: MNYPN (Feltsinger, Gyzheva, Bir)
+
+1
–4








2
62

304
Syktyvkar SU: Vindigo (Shostal, Nafidin, Lysov)
+1
+
–3






–2

2
123

330
Syktyvkar SU: GreenPeace (Glinko, Kravtsov, Ostashov)
+1
+3
–8








2
291

354
Syktyvkar SU: LordGrivon (Pavlovich, Veprev, Misharin)
+1
–4
–4








1
33