Координаты картофелин |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Координаты картофелин |
Merhaba |
12.05.2011 19:48
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
Добрый Вечер!!!
Помогите Пожалуйста решить задачу, очень надо!!! Ограничение времени: 0.5 секунды Ограничение памяти: 64 МБ Анка и Петька ждали Чапаева и ели картошку. Вскоре они наелись и решили поиграть в «Чапаева» оставшимися четырьмя картофелинами. Петька достал доску размером 20 × 20 клеток, положил на неё картофелины и сказал, что по правилам никакие две картофелины не могут находиться в одной клетке, а одной картофелиной можно сбить другую только в том случае, если они расположены на одной горизонтали или вертикали и между ними нет других картофелин. Анка предложила взять некоторые картофелины и поставить их на другие свободные клетки так, чтобы каждой картофелиной можно было сбить ровно одну другую. Помогите Петьке переставить как можно меньше картофелин, чтобы выполнить её просьбу. Исходные данные В четырёх строках записаны координаты картофелин xi, yi — целые числа в пределах от 1 до 20. Никакие две картофелины не расположены в одной клетке. Результат Выведите новые координаты картофелин. Картофелины следует описывать в том же порядке, в котором они заданы на входе. Если возможных ответов несколько, выведите любой. Пример: 1 1 2 2 4 4 4 3 Результат: 1 2 2 2 4 4 4 3 |
Unconnected |
12.05.2011 23:57
Сообщение
#2
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Слабонервным не читать
{$APPTYPE CONSOLE} Вроде работает. Можно было местами сделать оптимальней, выполняются лишние движения, но я решил, что при таких небольших размерностях и так сойдёт) Сообщение отредактировано: Unconnected - 13.05.2011 0:04 -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Merhaba |
13.05.2011 6:23
Сообщение
#3
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
|
Unconnected |
13.05.2011 7:26
Сообщение
#4
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Задаётся массив из 4-х элементов типа TPotate, в нем будет храниться инфа о каждой картофелине - координаты и количество бьющих её картошек. В начале этот массив заполняется, функция bcount находит, сколько клеток бьют клетку, координаты которой во входных параметрах ф-ии. Ну и главный цикл - проход по всем элементам массива, если какой-то эл-т бьёт не 1 клетка, а больше или меньше (а по условию нужна именно одна), то ищем такую клетку, которую бьёт одна другая клетка.. и переставляем. И обновляем информацию о том, какую клетку сколько бьют.
Сообщение отредактировано: Unconnected - 13.05.2011 7:28 -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Merhaba |
13.05.2011 7:46
Сообщение
#5
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
Задаётся массив из 4-х элементов типа TPotate, в нем будет храниться инфа о каждой картофелине - координаты и количество бьющих её картошек. В начале этот массив заполняется, функция bcount находит, сколько клеток бьют клетку, координаты которой во входных параметрах ф-ии. Ну и главный цикл - проход по всем элементам массива, если какой-то эл-т бьёт не 1 клетка, а больше или меньше (а по условию нужна именно одна), то ищем такую клетку, которую бьёт одна другая клетка.. и переставляем. И обновляем информацию о том, какую клетку сколько бьют. Скажите Пожалуйста, а что обозначает " type TPotate=record" ? что происходит в "Function check:boolean;" ? что происходит в "function chklet(x2,y2:byte):boolean;" ? |
Unconnected |
13.05.2011 7:54
Сообщение
#6
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
type TPotate=record record - запись, тут описывается новый тип по имени TPotate (наряду с другими типами, byte,integer..), представляющий собой запись. У этого типа есть 3 поля, будто 3 ящика в тумбочке-переменной. И к каждому этому ящику-полю можно отдельно обратиться, например p[1].x:=5; p[1].y:=6; p[1].b:=1; Функция check проверяет, все ли картошки удовлетворяют условиям задачи, или ещё не все и нужно ещё раз пробежаться по массиву и что-то переставить. Хотя мне кажется, она здесь и не нужна, и все необходимые перестановки делаются за первый проход цикла while (в силу маленьких размерностей наверное). chklet проверяет, не занята ли клетка и можно ли туда поставить картошку. Анка и Петька ждали Чапаева и ели картошку. Вскоре они наелись и решили поиграть в «Чапаева» оставшимися четырьмя картофелинами. Сообщение отредактировано: Unconnected - 13.05.2011 7:55 -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Merhaba |
13.05.2011 8:30
Сообщение
#7
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
type TPotate=record record - запись, тут описывается новый тип по имени TPotate (наряду с другими типами, byte,integer..), представляющий собой запись. У этого типа есть 3 поля, будто 3 ящика в тумбочке-переменной. И к каждому этому ящику-полю можно отдельно обратиться, например p[1].x:=5; p[1].y:=6; p[1].b:=1; Функция check проверяет, все ли картошки удовлетворяют условиям задачи, или ещё не все и нужно ещё раз пробежаться по массиву и что-то переставить. Хотя мне кажется, она здесь и не нужна, и все необходимые перестановки делаются за первый проход цикла while (в силу маленьких размерностей наверное). chklet проверяет, не занята ли клетка и можно ли туда поставить картошку. Анка и Петька ждали Чапаева и ели картошку. Вскоре они наелись и решили поиграть в «Чапаева» оставшимися четырьмя картофелинами. Спасибо Вам Большое!!! Лучще бы они Чапаева съели вместо картошки |
Lapp |
13.05.2011 9:24
Сообщение
#8
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Un, что-то у тебя не то..
Я добавил псевдографику. Красные номера - это переставленные картошки. 1 2 3 4 + + + + + + Ты переставил все четыре там, где можно было переставить только 2. Да и вообще, мне кажется, что тут в любом случае можно обойтись двумя. Код Unconnected, дополненный выводом поля (Показать/Скрыть)
-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
sheka |
13.05.2011 9:43
Сообщение
#9
|
Я. Группа: Пользователи Сообщений: 809 Пол: Мужской Реальное имя: Саша Репутация: 11 |
Объясните задание, пожалуйста.
|
Lapp |
13.05.2011 10:53
Сообщение
#10
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Объясните задание, пожалуйста. На доске 4 ладьи. Переместить минимальное количество так, чтобы в результате каждая ладья била ровно одну другую. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Merhaba |
13.05.2011 18:47
Сообщение
#11
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
|
sheka |
13.05.2011 19:57
Сообщение
#12
|
Я. Группа: Пользователи Сообщений: 809 Пол: Мужской Реальное имя: Саша Репутация: 11 |
|
Merhaba |
13.05.2011 20:03
Сообщение
#13
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
|
Unconnected |
13.05.2011 20:29
Сообщение
#14
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Это не очень правильное решение, как оказалось, не стоит его разбирать.. сейчас или завтра покажу рекурсивное, с перебором, сейчас пока не хочет работать)
-------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Merhaba |
14.05.2011 17:44
Сообщение
#15
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
|
Merhaba |
18.05.2011 19:48
Сообщение
#16
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
На доске 4 ладьи. Переместить минимальное количество так, чтобы в результате каждая ладья била ровно одну другую. А можно сделать так? Картошек - 4. Из того, что одна бьет только одну, следует, что в каждом столбце и в каждой строке должно быть ровно 0, 1 или 2 картошки, также две непустые линии, в каждой из которых находится 2 картошки, не могут пересекаться в клетке с картошкой (иначе поледнюю будут бить 2 сразу). Значит нам нужно всего две пары расположить в разных линиях. Некоторые до этого могут уже быть итак разложены. Осталось только придумать способ. Можно сделать булевую матрицу и работать с ней. Можно сравнивать координаты. Помогите Пожалуйста реализовать код |
Unconnected |
21.05.2011 14:17
Сообщение
#17
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Не знаю, нужно ли ещё, но вот (экзамены на носу, времени мало, да и не получалось поначалу..).
Тут типа полный перебор, с отбором лучшего положения (страшноват, правда(очень)). Делаются лишние действия, но вроде работает. {$APPTYPE CONSOLE} Что интересно, процедура вывода матрицы изначально называлась wout; , что, наверное, является каким-то служебным словом.. факт в том, что readln; после последнего wout-а не останавливал прогу. Пришлось переименовать) И да, мне кажется в таких задачах лучше перебор (хоть и с оптимизациями возможными, отсечениями), чем думать что-то типа "таак, оптимальная ситуация это когда в одной грядке 2 картошки, и переставим ещё одну, тогда..."..., короче, пытаться сделать однопроходно. Ибо задача может трансформироваться в пересадку 5 картошек, и тогда думать придется заново) Сообщение отредактировано: Unconnected - 21.05.2011 15:50 -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Merhaba |
21.05.2011 19:47
Сообщение
#18
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
Не знаю, нужно ли ещё, но вот (экзамены на носу, времени мало, да и не получалось поначалу..). Тут типа полный перебор, с отбором лучшего положения (страшноват, правда(очень)). Делаются лишние действия, но вроде работает. Спасибо Вам Большое за помощь!!! попробовал закинуть на контест, выдало ошибку: ТаймЛимит на 1-ом тесте. Как можно оптимизировать код, чтобы уложится в 0,5 секунды? Сообщение отредактировано: Merhaba - 21.05.2011 19:49 |
Текстовая версия | 1.06.2024 7:07 |