Качих всички 50 теста и ретествах всички предадени решения. Предаването на решения е отново отворено за дорешаване! Финалното класиране е публикувано в новината на informatika.bg. Победителите моля да се свържат с мен на thinkcreative@outlook.com.

След като разбра, че художникът Леонид Афремов рисува с нож, Ели се запита какви други оръжия могат да бъдат използвани за целта. Експериментите ѝ с отрова, въже и динамит (за момента) са неуспешни, но огнестрелните оръжия като че ли имат потенциал!

В случая, момичето ползва пушка за пейнтбол, с която изстрелва цветни топчета към бяло платно. Удряйки се в платното, топчетата образуват цветни кръгове (или части от кръгове, ако излизат от него). В зависимост от какво разстояние ги изстрелва Ели, получените кръгове са с различен радиус. Кръговете на по-късно изстреляни топчета покриват с техния цвят оцветеното от предишни такива (няма смесване на цветовете).

За целите на задачата ще считаме, че топчетата могат да бъдат изстреляни от разстояние от платното

Di

между 1 и 100, включително. Топче, изстреляно от разстояние

Di

, прави нещо-като-кръг с радиус

Di

, което ще наричаме "петно". Всяко топче има цвят (

Ri

,

Gi

,

Bi

), който е цветът на образуваното петно върху платното.

Ели е много точна и при всеки изстрел топчето се разбива в избрани от нея координати (

Xi

,

Yi

), където

Xi

е редът от горе надолу, а

Yi

е колоната, от ляво надясно върху растеризираното платно. Всеки пиксел (

X

,

Y

) от платното има шанс да бъде оцветен от това топче равен на:

1 - pow(min(1, max(0, (dist - Di * 0.6) / (Di * 0.4))), 2)
Тук

dist

е евклидовото разстояние между (

X

,

Y

) и (

Xi

,

Yi

), а

pow(val, 2)

е вдигане на

val

на квадрат. Така "центърът" на петното - пикселът (

Xi

,

Yi

) - бива винаги оцветен, а с отдалечаване от него шансът намалява, ефективно създавайки "пръски" около центъра. (Реално, пиксели на разстояние до 0.6 *

Di

биват винаги оцветени, а от там нататък шансът намалява квадратично, докато стане 0 при

dist ≥ Di

.)

Пикселите от петното, които излизат извън платното, просто биват игнорирани, но е задължително центърът му (

Xi

,

Yi

) да е вътре в него (иначе топчето няма да се разбие).

Ето пример с няколко изстрела с D = 5, 13, 29, 42, 69, и 100 върху платно с размер 128 х 400:

Забележете, че изстрелът с диаметър 100 (голямото синьо петно) и този с диаметър 69 (зеленото петно) излизат частично извън платното. Също така забележете, че изстрелът с радиус 29 (червеното петно) е изстрелян след този с радиус 100, като е разположен върху него. Ако, обаче, беше изстрелян преди него, нямаше да се вижда.
Генерирането на пръските за всеки изстрел е независимо от останалите – тоест два последователни изстрела с един и същ център и еднаква сила биха направили (по всяка вероятност) различни пръски! Системата ползва зададен random seed S за всеки тест, който гарантира, че бихте получили консистентни резултати при една и съща стратегия на "стреляне" (печатане на един и същ отговор). Макар и за вас това число да е без значение, то е зададено във входа за нуждите на системата.

Сега момичето иска да "пресъздаде", доколкото може, дадена картина - например някоя картина на Леонид Афремов, или пък българското знаме, или пък картинка как прасе яде тиква. Помогнете на момичето като напишете програма, която намира стратегия на "стреляне", която пресъздава картинката възможно най-добре с не повече от 10,000 изстрела! На първия ред на стандартния вход (

stdin

) ще бъдат зададени три цели числа N, M и S – съответно броя редове и броя колони на картинката, която се опитваме да пресъздадем, следвани от seed-а на рандом генератора, който системата ще ползва за този тест. На всеки от следващите N реда ще има по 3 * M числа в интервала [0, 255] задаващи (R, G, B) компонентите за всеки от пикселите на този ред от картинката. На първия ред на стандартния изход (

stdout

) изведете едно цяло число

K

– броя изстрели, които ще ползвате. На всеки от следващите

K

реда изведете по шест цели числа, разделени с интервали:

1. Xi

   – редът на центъра на петното

2. Yi

   – колоната на центъра на петното

3. Di

   – разстоянието, от което е изстреляно топчето

4. Ri

   – червената компонента на цвета на топчето

5. Gi

   – зелената компонента на цвета на топчето

6. Bi

   – синята компонента на цвета на топчето

• 128 ≤ N ≤ 512
• 128 ≤ M ≤ 512
• 1 ≤ S ≤ 100
• 0 ≤

  K

  ≤ 10,000
• 0 ≤

  Xi

  < N
• 0 ≤

  Yi

  < M
• 1 ≤

  Di

  ≤ 100
• 0 ≤

  Ri

  ,

  Gi

  ,

  Bi

  , ≤ 255

Примерен Вход	Примерен Изход
100 200 42 23 78 166 251 188 4 227 116 0 … 52 168 83 66 133 244 219 68 55 … …	2 42 42 100 61 55 118 13 17 5 69 69 69

Ако отговорът ви не спазва някое от ограниченията и/или формата на задачата; използвате повече от разрешеното време; използвате повече от разрешената памет; или по някаква причина решението ви не завърши успешно (crash-не), то ще получите 0 точки за този тест.

В случай, че всичко е наред, точките за съответния тест ще бъдат формирани по следния начин. Системата ще симулира изстрелите, които сте извели като отговор, ползвайки рандом генератор инициализиран с числото S за съответния тест. След това, за всеки пиксел от резултатната мацаница картинка ще сметнем "разстояние" от (

R1

,

G1

,

B1

) цвета му до този на съответния му пиксел в оригиналната картинка (

R2

,

G2

,

B2

) като сума от разликите в компонентите на квадрат:

(R1 - R2)2 + (G1 - G2)2 + (B1 - B2)2

.

Нека

ourScore

е сумата от тези разстояния за цялата картинка, а

bestScore

e най-малката такава сума за този тест измежду всички участници. Точките ни за този тест ще бъдат равни на

4 * ((bestScore + 1) / (ourScore + 1))

- тоест релативно оценяване спрямо най-доброто решение. Докато състезанието тече ще бъдат дадени 25 теста, на базата на които ще бъде налично временно класиране, достъпно за всички участници. След края на състезанието ще бъдат качени други 25 теста, на базата на които ще се изготви финално класиране. Забележете, че първите 25 няма да допринасят за точките на участниците във финалното класиране, но ще са донякъде подобни на финалните. За удобство на участниците задачата има визуализатор. След като предадете решение, тестовете, на които сте извели валиден отговор (отбелязани като зелени кръгчета на системата), стават линкове, чрез които можете да отворите визуализацията за съответния тест. Наградите и крайния срок за предаване ще бъдат публикувани на www.informatika.bg.