Недавно Влад победил на олимпиаде и выиграл современный квадрокоптер — дрон. Влад прикрутил к квадрокоптеру камеру, поднял его в воздух и начал фотографировать интересующие его места. Влад раздобыл карту местности, разбил её на квадраты и закрасил на ней интересующий его участок. Получилась схема, изображённая на рисунке 2. Ему необходимо сделать фотографии всех закрашенных квадратов. Теперь он хочет написать программу для дрона, поставить дрона в какой-нибудь закрашенной клетке и запустить его.
Программа для дрона — последовательность букв U, D, L, R, которые, соответственно, двигают дрон вверх, вниз, влево или вправо на 1 клетку. В процессе выполнения программы дрон сфотографирует каждую клетку ровно столько раз, сколько побывает на ней. Клетка, в которую дрон помещается вначале, сразу фотографируется им. Владу важно, чтобы были сфотографированы только закрашенные клетки. Одну и ту же клетку можно фотографировать несколько раз.
К сожалению, денег у Влада не очень много, поэтому он смог позволить себе очень маленькую карту памяти. Влада интересует, какую программу для дрона надо написать, чтобы сфотографировать только закрашенные клетки, сделав при этом как можно меньше фотографий.
Например, для участка, представленного на рисунке 1, оптимально будет задать программу «DLRDRLD», поместив изначально дрон в клетку (1, B), находящуюся на пересечении 1-й строки и B-го столбца. В этом случае будет сделано 8 фотографий — минимально возможное количество.
Рисунок 1
Перед Владом стоит более сложная задача — определить ответ для участка, схема которого изображена на рисунке 2.
В качестве ответа сдайте программу для дрона. Программа записывается в виде последовательности букв U, D, L, R, без кавычек, пробелов, иных разделителей. Вы можете сначала поставить квадрокоптер в любую клетку, из которой дрон начнет свой маршрут. Чем короче будет программа для дрона, тем больше вы получите.
PascalABC.NET 3.3.5, сборка 1660 от 20.04.2018 Внимание! Если программа не работает, обновите версию!
begin var a:=ArrRandom(ReadInteger('n='),-50,50); a.Println; var b:=ArrRandom(ReadInteger('n='),-50,50); b.Println; var sp:=b.Where(t->t>0).Sum; var im:=a.IndexMax; if im>0 then begin a:=ArrFill(im,sp)+a[im:]; a.Println end else Writeln('Максимальный элемент стоит первым') end.
Привет, код задачи приведен ниже 1. Отметь ответ как лучший (поставь 5 звезд). 2. Нажми кнопочку " " тут и в моем аккаунте
(За 8 былов такое никто не делает кроме меня будь благодарен в ответ)
Код прокомментирован, за дополнительными вопросами или информацией * Обращайся в комментарии, я отвечу на вопросы. * Зайди ко мне в профиль, в моих записях ты найдешь ссылки на полезные ресурсы.
FILE: CFraction.hpp
#ifndef CFRACTION_HPP #define CFRACTION_HPP
//Это класс дроби, тут мы храним чеслитель, знаменатель и функцию nesokr(). class CFraction { public:
CFraction(); //Конструктор класа
//"Геттеры" класса для получения значений приватных полей const unsigned int& getNumerator() const; const unsigned int& getDenumerator() const;
//"Сеттеры" класса для задани значений приватным полям void setNumerator(const unsigned int& value); void setDenumerator(const unsigned int& value);
//Функция заданная по заданию для сокращения дроби void nesokr();
private:
//Функция реализующая поиск найбольшего общего делителя по алгоритму Евклида const unsigned int getGreatestCommonDivisor() const; //Функция проверяющая, есть ли необходимость искать НОД const bool isRequireCalculationGCD() const;
private:
unsigned int mFirst; //Поле для числителя unsigned int mSecond; //Поле для знаменателя };
//Возращение значений происходит по константной ссылке. //Благодаря этому избегается копирование переменной, //а так же её модификация по ссылке. const unsigned int& CFraction::getNumerator() const { return mFirst; }
//Функция имеет в конце себя слово const сигнализирующее компилятору, //что метод не модифицировать поля класса. const unsigned int& CFraction::getDenumerator() const { return mSecond; }
//Передача аргумента в функцию так же реализуется по константной ссылке, //из тех же соображений что и возращение поля по константной ссылке. void CFraction::setNumerator(const unsigned int& value) { mFirst = value; }
void CFraction::setDenumerator(const unsigned int& value) { //Проверяем значение на 0, знаменатель не может быть равнм нулю. //Значение не проверяется на знак отрицания, по тому, что везде используется //беззнаковый целочисленный тип данных unsigned int. if (0 != value) { mSecond = value; } }
void CFraction::nesokr() { //Если есть необходимость проводить расчёты и сокращать дробь, то //находим НОД и делим на него чеслитель и знаменатель. if ( isRequireCalculationGCD() ) { unsigned int greatestCommonDivisor = getGreatestCommonDivisor();
const bool CFraction::isRequireCalculationGCD() const { //Проверяем, не является, ли знаменатель равным единице, //иначе нет смысла проводить безсмысленную работу, т.к. в любом случаи НОД //будет единица, то же самое делаем с числителем. return ( (1 != mSecond || 1 != mFirst) || (1 != mSecond && 1 != mFirst) ); }
const unsigned int CFraction::getGreatestCommonDivisor() const { //Алгоритм поиска НОД называется алгоритмом Евклида unsigned int remainder(1);
//Для его реадизации берем два числа и выделяем из них большее и меньшее. unsigned int gretestNumber = (mFirst > mSecond ? mFirst : mSecond); unsigned int leastNumber = (mFirst < mSecond ? mFirst : mSecond);
while (0 != remainder) { remainder = gretestNumber % leastNumber;
//Если остаток деления большего на меньшее равен нулю, //то НОД является меньшее из этих чисел if (0 != remainder) { //Если же остаток не равен нулю, //то большим числом становится предыдущее меньшее, //а меньшим становится остаток от леления. gretestNumber = leastNumber; leastNumber = remainder; } }
начало:А4
RUDRRURRRLUDLDLDDRLDL
Объяснение:
Вроде неплохо, но я не уверен что это минимум