Шоколадка, найти все возможные количества съеденных долек

@beeaplir · Регистрация: 16.10.2021

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

Шоколадка
У Аленки есть шоколадка прямоугольной формы, размером n×m долек. Аленка разламывает ее на две части по вертикали или по горизонтали и съедает одну из двух частей. Если Аленка чувствует, что не наелась, то она снова может разломить оставшийся кусок на две части и съесть одну из них, и так далее. Всю шоколадку Аленка есть не будет, а оставит про запас как минимум одну дольку.

Производителям стало известно о такой привычке девочки и они захотели узнать, какое количество долек может быть съедено при таком алгоритме поедания шоколада. Они хотят, чтобы вы написали программу, которая по известному размеру шоколадки найдет все возможные количества съеденных долек и выведет их в порядке возрастания.

Рассмотрим такой пример. Шоколадка имеет размер 3×3. Тогда Аленка может разломить ее на две части 3×1 и 3×2. Таким образом, она сможет съесть 3 или 6 долек и остановиться. Но также Аленка сможет съесть кусок из 6 долек, а от оставшегося отломить 1 или 2 дольки и съесть еще и их. Таким образом, она сможет съесть 7 или 8 долек. Наконец, она сможет съесть кусок 3×1 а от оставшегося куска 3×2 отломить и съесть еще 2 дольки, тогда количество съеденных долек будет равно 5. Очевидно, что съесть 1, 2 или 4 дольки Аленка не сможет.

Формат входных данных
На вход в одной строке подается два натуральных числа nn и mm — размеры шоколадки. 1≤n,m≤100; n+m≥3.

Формат выходных данных
Программа должна вывести в одной строке через пробел все числа, являющиеся ответами к задаче. Числа должны выводиться в порядке возрастания без повторений.

Если вы программируете на Python, то убрать перенос строки в функции print можно при помощи именованного параметра end, например, print(a,end=' ').

Sample Input:
3 3

Sample Output:
3 5 6 7 8

@LegionK · 26.10.2021, 19:17

Кликните здесь для просмотра всего текста

C++

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
 
using namespace std;
 
int main()
{
    int n,m;
    cin >> n >> m;
 
    vector<int>ok(n*m+1);
 
    for(int i = 1;i<=n;++i){
 
        for(int j = 1;j<=m;++j){
 
            ok[n*m - i*j] = 1;
 
        }
 
    }
 
    for(int i = 1;i<ok.size();++i)if(ok[i])cout << i << ' ';
 
 
 
    return 0;
}

@Royal_X · 26.10.2021, 19:22

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

#include <algorithm>
#include <set>

для чего нужны эти заголовки?

@LegionK · 26.10.2021, 19:28

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

для чего нужны эти заголовки?

Женщина в маленьком городке не может найти гостиницу, в одну ткнулась, в другую - везде всё занято. В очередной ей говорят - нет мест, есть чукча в двухместном номере, если договоритесь с ним - ночуйте. Женщина - к чукче в номер, а тот сидит на кровати и на варгане играет - дзынь, дзынь, дзынь... Она:
- Молодой человек, можно я на второй кровати переночую у вас тут, нет мест в гостиницах!
Чукча утвердительно кивает головой.
Женщина готовится ко сну, чукча - дзынь, дзынь, дзынь, дзынь...
Женщина:
- Молодой человек, я Вас прошу, пожалуйста, голова раскалывается, Вы не могли бы перестать?
Чукча прекратил играть, сидит на кровати, молча смотрит на женщину.
Женщина приготовилась ко сну, начинает раздеваться. Чукча, не отводя глаз, смотрит на неё. Она скидывает платье. Он смотрит, не отрывая глаз. Женщина стягивает чулки. Чукча не отводит глаз. Женщина:
- Ну, что, хочешь?
Утвердительный кивок головой.
- Ну, давай, только один раз и очень быстро...
- Дзынь!

@Royal_X · 26.10.2021, 19:42

LegionK,

@LegionK · 26.10.2021, 19:51

Royal_X,

@Royal_X · 26.10.2021, 20:44

LegionK, вот это другое дело! Дерево в отсеке корабля это кульно.

@beeaplir 0 / 0 / 0 Регистрация: 16.10.2021 Сообщений: 6
		1
	Шоколадка, найти все возможные количества съеденных долек 26.10.2021, 18:01. Показов 1622. Ответов 6 Метки нет (Все метки) Шоколадка У Аленки есть шоколадка прямоугольной формы, размером n×m долек. Аленка разламывает ее на две части по вертикали или по горизонтали и съедает одну из двух частей. Если Аленка чувствует, что не наелась, то она снова может разломить оставшийся кусок на две части и съесть одну из них, и так далее. Всю шоколадку Аленка есть не будет, а оставит про запас как минимум одну дольку. Производителям стало известно о такой привычке девочки и они захотели узнать, какое количество долек может быть съедено при таком алгоритме поедания шоколада. Они хотят, чтобы вы написали программу, которая по известному размеру шоколадки найдет все возможные количества съеденных долек и выведет их в порядке возрастания. Рассмотрим такой пример. Шоколадка имеет размер 3×3. Тогда Аленка может разломить ее на две части 3×1 и 3×2. Таким образом, она сможет съесть 3 или 6 долек и остановиться. Но также Аленка сможет съесть кусок из 6 долек, а от оставшегося отломить 1 или 2 дольки и съесть еще и их. Таким образом, она сможет съесть 7 или 8 долек. Наконец, она сможет съесть кусок 3×1 а от оставшегося куска 3×2 отломить и съесть еще 2 дольки, тогда количество съеденных долек будет равно 5. Очевидно, что съесть 1, 2 или 4 дольки Аленка не сможет. Формат входных данных На вход в одной строке подается два натуральных числа nn и mm — размеры шоколадки. 1≤n,m≤100; n+m≥3. Формат выходных данных Программа должна вывести в одной строке через пробел все числа, являющиеся ответами к задаче. Числа должны выводиться в порядке возрастания без повторений. Если вы программируете на Python, то убрать перенос строки в функции print можно при помощи именованного параметра end, например, print(a,end=' '). Sample Input: 3 3 Sample Output: 3 5 6 7 8 0

@Royal_X 3256 / 1477 / 468 Регистрация: 01.06.2021 Сообщений: 4,985
	26.10.2021, 19:22	3
	Сообщение от LegionK #include <algorithm> #include <set> для чего нужны эти заголовки? 0

@LegionK 392 / 262 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	26.10.2021, 19:28	4
	Сообщение от Royal_X для чего нужны эти заголовки? Женщина в маленьком городке не может найти гостиницу, в одну ткнулась, в другую - везде всё занято. В очередной ей говорят - нет мест, есть чукча в двухместном номере, если договоритесь с ним - ночуйте. Женщина - к чукче в номер, а тот сидит на кровати и на варгане играет - дзынь, дзынь, дзынь... Она: - Молодой человек, можно я на второй кровати переночую у вас тут, нет мест в гостиницах! Чукча утвердительно кивает головой. Женщина готовится ко сну, чукча - дзынь, дзынь, дзынь, дзынь... Женщина: - Молодой человек, я Вас прошу, пожалуйста, голова раскалывается, Вы не могли бы перестать? Чукча прекратил играть, сидит на кровати, молча смотрит на женщину. Женщина приготовилась ко сну, начинает раздеваться. Чукча, не отводя глаз, смотрит на неё. Она скидывает платье. Он смотрит, не отрывая глаз. Женщина стягивает чулки. Чукча не отводит глаз. Женщина: - Ну, что, хочешь? Утвердительный кивок головой. - Ну, давай, только один раз и очень быстро... - Дзынь! 1

@Royal_X 3256 / 1477 / 468 Регистрация: 01.06.2021 Сообщений: 4,985
	26.10.2021, 19:42	5
	LegionK, Миниатюры 0

@LegionK 392 / 262 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	26.10.2021, 19:51	6
	Royal_X, Миниатюры 1

@Royal_X 3256 / 1477 / 468 Регистрация: 01.06.2021 Сообщений: 4,985
	26.10.2021, 20:44	7
	LegionK, вот это другое дело! Дерево в отсеке корабля это кульно. 0