Спираль

@Человек Челов · Регистрация: 18.01.2023

Студворк — интернет-сервис помощи студентам

В левом верхнем углу прямоугольного поля размера N ×M сидит Черепашка. Она хочет закрасить некоторые клетки по спирали, закручивающейся к центру, как на рисунке: Определите, сколько клеток ей придётся закрасить.

Формат входных данных Первая строка входных данных содержит число N высоту прямоугольника, вторая строка содержит число M ширину прямоугольника. Все числа целые положительные и не превосходят 2 ×109.

Формат выходных данных Программа должна вывести одно целое число количество клеток, закрашенных Черепашкой. Обратите внимание, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Система оценки Решения, правильно работающие, когда числа N и M не превосходят 100, будут оцениваться в 40 баллов. Решения, правильно работающие, когда числа N и M не превосходят 105, будут оцениваться в 60 баллов.
Примеры стандартный ввод
5
6
Вывод
20

Ввод
1
5
Вывод
5

Помогите понять по какому принципу красятся клетки

@Человек Челов · 25.02.2023, 15:18 **[ТС]**

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int fourth()
{
    int N;
    int M;
    std::cin >> N;
    std::cin >> M;
    if (N == 1)
        return M;
    if (M == 1)
        return N;
    long long paintto{ 0 };
    paintto += N;
    N -= 1;
    M -= 1;
        do {
            if (N < 0 || M < 0)
                break;
            paintto += N;
            paintto += M;
            if (N <= 1 || M <= 2)
                return N + M - 1;
            M -= 2;
            N -= 2;
        } while (true);
        return paintto;
}

@TheCalligrapher · 25.02.2023, 16:52

Сообщение от Человек Челов

C++
1
2
/* 20 */    if (N <= 1 || M <= 2)
/* 21 */        return N + M - 1;

Ваш цикл "скорее всего" будет заканчиваться вот по этому return. При этом значение paintto игнорируется и все усилия по его накоплению идут коту под хвост. Вам это не кажется странным?

@Человек Челов · 25.02.2023, 18:07 **[ТС]**

TheCalligrapher, кажется, реализовал наперекосяк, хотел учесть некоторые условия

Добавлено через 38 секунд
По крайней мере код правильно отвечает на данные тесты, насчёт исключительных случаев уверен что результаты неверные

Добавлено через 3 минуты
TheCalligrapher, ваш код мне кажется верным , однако непонятно почему в цикле -2 без изначального вычета единицы.
Возникает последовательность -2 -4 ...

Добавлено через 3 минуты
TheCalligrapher, я поэтому и сказал, что если расписать ваш код с помощью нескольких условий и через другой цикл то результат будет неверным

@TheCalligrapher · 25.02.2023, 18:29

Сообщение от Человек Челов

что если расписать ваш код с помощью нескольких условий и через другой цикл то результат будет неверным

???

Если вы "расписали мой код через другой цикл" и результат у вас получился иным, значит вы неправильно "расписали мой код через другой цикл".

@Человек Челов · 25.02.2023, 18:41 **[ТС]**

Так почему уменьшение на 2 в цикле?

@TheCalligrapher · 25.02.2023, 18:51

Сообщение от Человек Челов

Так почему уменьшение на 2 в цикле?

Идея, которую я реализовывал в своем коде, сводится к "рекурсивному" рассмотрению проблемы.

На каждом этапе мы закрашиваем вертикаль и горизонталь из суммарно N+M клеток, после чего мы переходим к вложенной проблеме того же рода, но размера (N-2, M-2)

(Во вложенной проблеме на картинке выше мы будем начинать закрашивать дальше с правого нижнего угла, но это совершенно не принципиально.)

Вот так мы и решаем проблему: переходя от (N, M) к (N-2, M-2) и так далее...

Надо только быть осторожным с базисом рекурсии: когда задача становится узкой/маленькой (условие N <= 1 || M <= 2), решение равно не N+M, а N+M-1.

@Человек Челов · 25.02.2023, 18:53 **[ТС]**

Благодарю за пояснение

@TheCalligrapher · 25.02.2023, 19:38

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

@Человек Челов · 25.02.2023, 20:47 **[ТС]**

верно, у них на сайте было еще одно решение на питоне

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int (input ( ) )
m = int (input ( ) )
k = min( n − 1 , m − 1 ) // 2
ans = ( ( n + m) + ( n + m) − 4 ∗ ( k − 1 ) ) ∗ k // 2
n −= 2 ∗ k
m −= 2 ∗ k
i f n == 1 :
ans += m
e l i f m == 1 :
ans += n
e l i f m == 2 :
ans += n + 1
e l s e : # n == 2 , m > 2
ans += m + 2
pr int ( ans )

Добавлено через 12 минут
тут также получается прямоугольник N-2*M-2

Добавлено через 4 минуты
и стартует арифметическая прогрессия, только я не очень понял почему минимальное делится на 2

Добавлено через 13 минут
все же интересно,что нужно добавить в этот код, чтобы он был справедлив для всех значений

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int fourth()
{
    int N;
    int M;
    std::cin >> N;
    std::cin >> M;
    if (N == 1)
        return M;
    if (M == 1)
        return N;
    long long paintto{ 0 };
    paintto += N;
    N -= 1;
    M -= 1;
        do {
            if (N < 0 || M < 0)
                break;
            paintto += N;
            M -= 2;
            N -= 2;
        } while (true);
        return paintto;
}

@SmallEvil · 25.02.2023, 21:20

Сообщение от Человек Челов

верно, у них на сайте было еще одно решение на питоне

Самому то никак, ничего, не получилось ? Восходящая звезда

@Человек Челов · 25.02.2023, 21:29 **[ТС]**

SmallEvil, не отрицаю , получилось только на некоторую часть значений.(код выше)
а ты умник, покажи свой уровень и напиши как следует, научи

@SmallEvil · 25.02.2023, 21:40

Не по теме:

Сообщение от Человек Челов

покажи свой уровень и напиши как следует, научи

Не каждый может научить, и не каждый может научится.
Ты из последних.

К тому же, я на слабо не ведусь.

Добавлено через 1 минуту

Сообщение от Человек Челов

покажи свой уровень и напиши как следует

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

@Человек Челов · 25.02.2023, 21:49 **[ТС]**

так а что тебе доверять, ты в основном издеваешься , а не отвечаешь

@SmallEvil · 25.02.2023, 21:56

Когда я отвечаю, ты говоришь что тебе видней.
К тому же, тебе тут никто не обязан делать задания за тебя.

@Человек Челов · 25.02.2023, 22:01 **[ТС]**

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

@SmallEvil · 25.02.2023, 22:43

Сообщение от Человек Челов

но я говорю что ты твои ответы в основном бессмысленные

Ясно понятно.

Сообщение от SmallEvil

и не каждый может научится

@Человек Челов · 25.02.2023, 22:46 **[ТС]**

ладно.

Новые блоги и статьи Все статьи Все блоги /
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .

@Человек Челов 15 / 3 / 0 Регистрация: 18.01.2023 Сообщений: 282

	Спираль 23.02.2023, 18:01. Показов 2041. Ответов 36 Метки нет (Все метки) В левом верхнем углу прямоугольного поля размера N ×M сидит Черепашка. Она хочет закрасить некоторые клетки по спирали, закручивающейся к центру, как на рисунке: Определите, сколько клеток ей придётся закрасить. Формат входных данных Первая строка входных данных содержит число N высоту прямоугольника, вторая строка содержит число M ширину прямоугольника. Все числа целые положительные и не превосходят 2 ×109. Формат выходных данных Программа должна вывести одно целое число количество клеток, закрашенных Черепашкой. Обратите внимание, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#). Система оценки Решения, правильно работающие, когда числа N и M не превосходят 100, будут оцениваться в 40 баллов. Решения, правильно работающие, когда числа N и M не превосходят 105, будут оцениваться в 60 баллов. Примеры стандартный ввод 5 6 Вывод 20 Ввод 1 5 Вывод 5 Помогите понять по какому принципу красятся клетки Миниатюры 0

@Человек Челов 15 / 3 / 0 Регистрация: 18.01.2023 Сообщений: 282
	25.02.2023, 18:07 [ТС]
	TheCalligrapher, кажется, реализовал наперекосяк, хотел учесть некоторые условия Добавлено через 38 секунд По крайней мере код правильно отвечает на данные тесты, насчёт исключительных случаев уверен что результаты неверные Добавлено через 3 минуты TheCalligrapher, ваш код мне кажется верным , однако непонятно почему в цикле -2 без изначального вычета единицы. Возникает последовательность -2 -4 ... Добавлено через 3 минуты TheCalligrapher, я поэтому и сказал, что если расписать ваш код с помощью нескольких условий и через другой цикл то результат будет неверным 0

@Человек Челов 15 / 3 / 0 Регистрация: 18.01.2023 Сообщений: 282
	25.02.2023, 18:41 [ТС]
	Так почему уменьшение на 2 в цикле? 0

@Человек Челов 15 / 3 / 0 Регистрация: 18.01.2023 Сообщений: 282
	25.02.2023, 18:53 [ТС]
	Благодарю за пояснение 0

@TheCalligrapher Вездепух 13233 / 6865 / 1827 Регистрация: 18.10.2014 Сообщений: 17,398
	25.02.2023, 19:38
	... из этого всего, кстати, следует, что никакого цикла для решения этой задачи не нужно: задача может быть решена прямой формулой плюс, возможно, пара-тройка ветвлений. 1

@Человек Челов 15 / 3 / 0 Регистрация: 18.01.2023 Сообщений: 282
	25.02.2023, 21:29 [ТС]
	SmallEvil, не отрицаю , получилось только на некоторую часть значений.(код выше) а ты умник, покажи свой уровень и напиши как следует, научи 0

@Человек Челов 15 / 3 / 0 Регистрация: 18.01.2023 Сообщений: 282
	25.02.2023, 21:49 [ТС]
	так а что тебе доверять, ты в основном издеваешься , а не отвечаешь 0

@SmallEvil 4086 / 2975 / 813 Регистрация: 29.06.2020 Сообщений: 11,000
	25.02.2023, 21:56
	Когда я отвечаю, ты говоришь что тебе видней. К тому же, тебе тут никто не обязан делать задания за тебя. 0

@Человек Челов 15 / 3 / 0 Регистрация: 18.01.2023 Сообщений: 282
	25.02.2023, 22:01 [ТС]
	так я в курсе, но я говорю что ты твои ответы в основном бессмысленные так что неудивительно что по твоим советам никто(по крайней мере я) не делает 0

@Человек Челов 15 / 3 / 0 Регистрация: 18.01.2023 Сообщений: 282
	25.02.2023, 22:46 [ТС]
	ладно. 0

Спираль

Решение