Областная олимпиада

← →
ProgRAMmer Dimonych © (2007-01-04 18:42) [0]

Оцените задачки с областной олимпиады...

1. Пролетели не по-зимнему тёплые недели зимы и наступили рождественские раздники, а с ними и долгожданная деревенская рождественская спартакиада.
Традиционно спартакиаду открывает староста деревни. Торжественное открытие начинается с соревнования по перетягиванию каната. Чтобы сформировать из жителей 2 команды, которые будут участвовать в соревновании, староста выстраивает всех жителей деревни в шеренгу. После этого он проходит от левого края шеренги к правому и выборочно указывает на людей, которые примут участие в этом торжественном соревновании. Все выбранные старостой деревни жители (их всегда положительное и чётное число) делают шаг вперёд и последовательно рассчитываются на первый-второй, начиная с левого края. Из первых номеров формируется первая команда, а из вторых номеров - вторая команда.
Староста, являясь суеверным человеком, считает хорошим знаком, если выиграет первая команда. Известно, что староста знает всё о жителях деревни, в том числе и силу каждого из них, выраженную в числовом эквиваленте.
Помогите старосте выбрать участников соревнования так, чтобы после разделения их на две команды разница между силой первой команды и силой второй команды была максимальна. Силой команды будем называть сумму числовых эквивалентов сил всех её участников.

Входные данные:
Первая строка входного файла содержит целое число N (2<=N<=32767) - количество жителей деревни. Во второй строке файла записано N целых чисел P1, P2, ..., PN (1<=Pi<=100000), разделённых одиночными пробелами, где Pi - сила жителя, стоящего в шеренге на i-м слева месте. Жители в шеренге нумеруются с единицы, начиная с левого края.
Выходные данные:
Единственная строка выходного файла должна содержать одно целое число - максимально возможную разность между силой первой и второй команд.

Пример
input.txt output.txt
===============================================
2 9999
10000 1
------------------------------------------------------------
7 12
7 6 2 4 8 1 5
------------------------------------------------------------
4 -1
1 2 3 4

← →
ProgRAMmer Dimonych © (2007-01-04 19:12) [1]

У меня ни одного теста на самотестировании почему-то не взяла, хотя во время отладки всё выдавала правильно. Возможно, из-за того, что writeln"ом пользовался при выводе в файл. Но тогда создателей таких тестеров расстреливать следует... :)

← →
ors_archangel © (2007-01-04 19:17) [2]

Голимый перебор? А где же:
* Найдите приближённое решение алгоритмом с асимптотической эффективностью не хуже O(n log n), используя тот факт, что ....

← →
ProgRAMmer Dimonych © (2007-01-04 19:26) [3]

> Голимый перебор?
Да вот, к несчастью, нет. Результат: "Wrong Answer!".

← →
ors_archangel © (2007-01-04 19:34) [4]

Writeln как бы создаёт файл с двумя строками: вторая - пуста. Поэтому, лучше Write, чтобы в output.txt была единственная строка

← →
ProgRAMmer Dimonych © (2007-01-04 19:45) [5]

> ors_archangel © (04.01.07 19:34) [4]
Вот это-то и было первое, что пришло мне в голову через час после самотестирования :(

← →
ProgRAMmer Dimonych © (2007-01-04 20:18) [6]

Задача 2. Колхозное поле, на котором выращен богатый урожай, облюбовала стая пернатых. Поле представляет собой квадрат из NxN клеок. Для защиты урожая от непрошенных пернатых гостей председатель колхоза распорядился построить M механических отпугивающих устройств. Каждое такое устройство находится в центре некоторой клетки поля и позволяет обеспечить защиту этой клетки, а также всех клеток, лежащих с ней на одной диагонали.
Однажды председатель решил узнать, сколько клеток на колхозном поле не защищено от нападения птиц. А так как он очень занят организацией сбора урожая со всех угодий колхоза, то ответить на этот вопрос поручили Вам - местному компьютерному гению.
Входные данные:
Первая строка входного файла содержит целые числа N (1<=N<=1000000) и M (1<=M<=100000), разделённые пробелом. Каждая из следующих M строк описывает местоположение устройства и содержит два целых числа от 1 до N включительно - номер строки и номер столбца, на пересечении которых оно находится. Строки нумеруются снизу вверх, а столбцы - слева направо. Нумерация строк и столбцов начинается с единицы. Никакие два устройства не находятся в одной клетке.
Выходные данные:
Единственная строка выходного файла должна содержать одно целое число - количество клеток колхозного поля, которое не защищает ни одно из устройств.
Пример
input.txt output.txt
================================================
10 6 33
4 7
8 5
8 7
6 2
9 7
8 4

← →
ProgRAMmer Dimonych © (2007-01-04 20:45) [7]

Как к этой второй задаче вообще можно было подойти? Мне пришлось решить для небольших N, а для больших - обрубать. Слышал, что во FP скомпилировался array [1..1000000,1..1000000] of Boolean, но программа вылетала сразу же.

← →
Spirt (2007-01-04 20:48) [8]

Хорошо, что я до областной олимпиады ннемножко баллов не добрал :-)
Облажался бы :-)

← →
default © (2007-01-04 20:50) [9]

попробуйте исследовать свойства максимального решения
по этим свойствам потом "собирать" решение уже для конкретного набора жильцов
я думаю это перспективный подход, я думаю он положит задачу прямо-таки на лопатки;)

← →
ProgRAMmer Dimonych © (2007-01-04 20:51) [10]

> Spirt (04.01.07 20:48) [8]
Может, махнёмся? Меня от этих задач на рвоту тянет: задачи ужасно сложные, а программы, написанные для их решения, - абсолютно бесполезные. :(

← →
ProgRAMmer Dimonych © (2007-01-04 20:53) [11]

> default © (04.01.07 20:50) [9]
Я после олимпиады совсем в танке :( Переформулируйте, пожалуйста, Вашу мысль, а то у меня чего-то в голове каша, которая мешает разглядеть суть...

← →
Spirt (2007-01-04 20:55) [12]

> ProgRAMmer Dimonych © (04.01.07 20:51) [10]

Во-во, меня тоже бесполезность мутит, смысла не вижу :-) У нас на городской тупые проверяющие были, вот я и баллов недобрал, ну невдомек им было, что одну и ту же задачу разными способами решить можно, а тот факт, что прога работала их нисколько не волновал

← →
ProgRAMmer Dimonych © (2007-01-04 21:00) [13]

> Spirt (04.01.07 20:55) [12]
> > ProgRAMmer Dimonych © (04.01.07 20:51) [10]
> Во-во, меня тоже бесполезность мутит, смысла не вижу :-)
> У нас на городской тупые проверяющие были, вот я и баллов
> недобрал, ну невдомек им было, что одну и ту же задачу разными
> способами решить можно, а тот факт, что прога работала их
> нисколько не волновал
Самое обидное, что объективнее всё равно ничего не будет: писать действительно полезные программы как будто проще, поэтому оценивать придётся интерфейс, а оценка интерфейса - личное дело каждого :(

← →
Virgo_Style © (2007-01-04 21:03) [14]

2. А если не все поле "засеивать", а потом считать, а каждую клетку по очереди проверять?
Хотя, меня гложет подозрение, что есть более хитрый способ.

← →
ProgRAMmer Dimonych © (2007-01-04 21:11) [15]

> Virgo_Style © (04.01.07 21:03) [14]
Проблема в том, что клеток-то в таком "квадратике" 1000000x1000000, т.е. 10^12. А на работу программы, кстати, отводится столько же, сколько на первую задачу, т.е. 0,5 сек. Так что, действительно, должен быть более хитрый подход. :(

← →
Virgo_Style © (2007-01-04 21:14) [16]

Так. Мысля. Надо работать не с клетками, а с диагоналями...

← →
Юрий Зотов © (2007-01-04 21:14) [17]

Нереальные задачи.

"Деревенская рождественская спартакиада", "колхозное поле, на котором выращен богатый урожай" - это где ж такое видано?

← →
$Pl@Sh © (2007-01-04 21:17) [18]

> Поле представляет собой квадрат

Из области фантастики вообще

← →
ProgRAMmer Dimonych © (2007-01-04 21:20) [19]

> Virgo_Style © (04.01.07 21:14) [16]
Была такая. За 3 часа продумал. диагоналей - 2*(2N-1)=4N-2, при N=1000000 - виселица. 3999998 - 125000 LongInt"ов!!! :(
> Юрий Зотов © (04.01.07 21:14) [17]
Жаль, не прочитают организаторы этого дебилизма нашей веточки :(

← →
ProgRAMmer Dimonych © (2007-01-04 21:22) [20]

> $Pl@Sh © (04.01.07 21:17) [18]
> > Поле представляет собой квадрат
> Из области фантастики вообще
Собственно только то, что поле не представляет собой идеальную окружность (в смысле, круг) и грело...

← →
$Pl@Sh © (2007-01-04 21:23) [21]

> Торжественное открытие начинается с соревнования по перетягиванию
> каната.

Торжественное открытие не с этого начинается или я чё-то недопонимаю в русских деревнях :-)

← →
TUser © (2007-01-04 21:24) [22]

Кажется нигде ненакосячил, хотя неплохо бы погонять еще на тестовых примерах. Алгоритм выделен жирным.

{$apptype console} uses SysUtils; var f: textfile; n: integer; a: array of integer; r: array of integer; s: string; i, j, k: integer; begin assignfile (f, "input.txt"); reset (f); readln (f, s); n := StrToInt (s); SetLength (a, n); readln (f, s); i := 0; j := 1; k := 0; while j <= length (s) + 1 do begin if (j = length (s) + 1) or (s[j] = " ") then begin a[i] := StrToInt (copy (s, k + 1, j - k - 1)); inc (i); k := j; end; inc (j); end; closefile (f); { writeln (n); for i := 0 to n - 1 do write (a[i], " "); writeln; } SetLength (r, n); r[n-1] := 0; for i := n-2 downto 0 do begin if r[i+1] = 0 then r[i] := -MaxInt else r[i] := r[i+1]; for j := i + 1 to n - 1 do begin k := a[i] - a[j]; if j < n - 1 then inc (k, r[j+1]); if k > r[i] then r[i] := k; end; end; // writeln (r[0]); assignfile (f, "output.txt"); rewrite (f); write (f, r[0]); closefile (f); end.

← →
$Pl@Sh © (2007-01-04 21:24) [23]

> Собственно только то, что поле не представляет собой идеальную
> окружность (в смысле, круг) и грело...

да... или сферу...

← →
Gero © (2007-01-04 21:34) [24]

Обычная олимпиадная задача.

> [3] ProgRAMmer Dimonych © (04.01.07 19:26)
> Результат: «Wrong Answer!».

Ты накосячил значит.

> [12] Spirt (04.01.07 20:55)
> У нас на городской тупые проверяющие были, вот я и баллов
> недобрал, ну невдомек им было, что одну и ту же задачу разными
> способами решить можно, а тот факт, что прога работала их
> нисколько не волновал

Ьред сивой кобылы.

← →
default © (2007-01-04 21:43) [25]

A1/A2, B1/B2 - это две выбранные пары жильцов
если решение максимально, то будет выполнено
число жильцов по краям и в промежутках выбрано произвольно
(их может вообще не быть, быть больше или меньше)

l1<=l2<= A1 >=a1>=a2>= A2 <= m1<=m2<= B1 >=b1>=b2>= B2 <= r1<=r2

помедитируй над этим

← →
Sha © (2007-01-04 21:45) [26]

> ProgRAMmer Dimonych © (04.01.07 21:20) [19]
> Жаль, не прочитают организаторы этого дебилизма нашей веточки :(

Шутка это.
Нормальные задачи.

← →
$Pl@Sh © (2007-01-04 22:01) [27]

> Spirt (04.01.07 20:55) [12]

Эт ты накосячил

← →
default © (2007-01-04 22:04) [28]

а во второй задаче надо просто иметь массив диагоналей булева типа и уметь пересчитывать координаты клетки в две диагонали которые покрывает устройство расположенное в этой клетке

Задача 3. В империи кукурака вот уже на протяжении 32 лет правит император Горделиус, известный всем как очень мудрый и честный правитель, который больше жизни любит свой народ. Всё бы хорошо, но годы начали брать своё, всё реже и реже жители империи могли видеть и общаться со своим императором, да и сам он понимал, что у него уже не та хватка и ловкость, что была ранее. В один из вечеров император принял решение об уходе в отставку. Прямых наследников у Горделиуса не было. По законам, в этом случае ему предстояло разделить всю империю на части и раздать во владение своим двум заместителям. Но как это сделать, чтобы навсегда остаться ля жителей мудрым и честным?
У императора есть подробная карта империи, которая досталась ему по наследству от отца. Известно, что империя имеет форму прямоугольника протяжённостью N километров с севера на юг и M километров с запада на восток. На карте проведены специальные горизонтальные и вертикальные линии, называемые линиями широты и долготы соответственно. Линии широты идут строго с севера на юг, их количество равно M-1. Известно, что линии широты и долготы параллельны границам империи и разбивают его территорию на N*M квадратов с длиной стороны в один километр. Для лучшей ориентации на карте император ввёл на ней декартову прямоугольную систему координат, направив ось абсцисс Ox с запада на восток через северную границу империи, а ось ординат Oy - с севера на юг через западную границу империи.
Экономическим отделом империи для каждого из квадратов было вычислено и нанесено на карту неотрицательное целое число, соответствующее качеству и плодородию земли в этом квадрате. Это число называется ценой квадрата.
Император решил разделить империю достаточно простым способом - провести через всю карту прямую, пересекающую прямоугольник, соответствующий границам империи, или касающуюся его. Все квадраты, находящиеся полностью по одну сторону от прямой и не имеющие с ней ни одной общей точки, он решил отдать одному своему заместителю, а все квадраты полностью находящиеся по другую сторону от прямой и не имеющие с ней ни одной общей точки, - другому заместителю. Возникает вопрос, а что же делать с квадратами, которые пересечёт проведённая императором прямая? В этом вопросе император был однозначен - все эти квадраты будут объявлены достоянием народа.
Ваша задача - помочь императору провести разделительную прямую так, чтобы сумма цен квадратов, пересекаемых прямой, была максимальной.
Будем считать, что:
- толщина всех линий и границ равна нулю;
- разделительная прямая пересекает квадрат, если она имеет с ним хотя бы одну общую точку.
Входные данные
В первой строке входного файла находятся два целых числа N и M (1<=N, M<=40), разделённые одним пробелом.
Каждая из следующих N строк содержит M целых чисел от 0 до 10^7, разделённых одиночными пробелами, где i-е число в j-й строке - это цена квадрата, юго-восточный угол которого имеет координаты (i,j).
Выходные данные
Единственная строка выходного файла должна содержать одно целое число - сумму цен квадратов, пересекаемых разделительной прямой.
Пример
input.txt output.txt
==========================================
4 3 17
3 1 2
2 2 1
3 1 0
1 2 4
------------------------------------------------------
1 3 4
1 2 1

← →
Zeqfreed (links) (2007-01-04 22:13) [31]

default,
По-моему проще посчитать длины всех диагоналей и затем вычесть кол-во пересечений диагонялей всех устройств.

P.S. Кнопка "цитата" в links не работает! :(

> TUser © (04.01.07 22:07) [29]
> > default © (04.01.07 21:43) [25]
> Я, по правде говоря, ничего не поянял.
Он имеет в виду то, что я, собственно, и сделал. Идём слева направо. Сначала до тех пор, пока сила каждого следующего больше, чем предыдущего, последнего запоминаем. Потом - пока сила каждого следующего меньше, чем предыдущего, вычисляем разность. Если ряд не закончился - повторяем процедуру отбора.

> default © (04.01.07 22:04) [28]
> а во второй задаче надо просто иметь массив диагоналей булева типа и
> уметь пересчитывать координаты клетки в две диагонали которые
> покрывает устройство расположенное в этой клетке

Можно проще

> Ьред сивой кобылы.
Максимум, процентов на 25.

> В империи кукурака

Когда составитель прочитал первые две задачи, он напился...

> $Pl@Sh © (04.01.07 22:15) [35]
> > В империи кукурака
> Когда составитель прочитал первые две задачи, он напился...
А я, когда прочитал все три - грязно выругался (мысленно)...

> $Pl@Sh © (04.01.07 22:15) [35]
> > В империи кукурака
> Когда составитель прочитал первые две задачи, он напился...
И обкурился:
> У императора есть подробная карта империи,
У беларускай мове ёсць слова "падробка", якое на рускай мове гучыць як "подделка". Ассоциации у меня какие-то нездоровые...

default © (04.01.07 22:04) [28] умную вещь сказал.

Но если устройств намного меньше, чем размеры поля,
то будет очень неэффективно растрачена память.

Подумай над этим )

> Возникает вопрос, а что же делать с квадратами, которые
> пересечёт проведённая императором прямая?

В России с таким вопросом быстро разбираются

Областная олимпиада Найти похожие ветки