Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 704
Записей в блоге: 1
#1

Задача Популяция - C++

02.03.2013, 14:40. Просмотров 640. Ответов 9
Метки нет (Все метки)

Ни для кого не секрет, что студенты ОНУ больше всех любят биологию. Но мало кто знает, что именно студент кафедры Увеселительной Теории Василий Простонародьев вывел новую разновидность саранчи – саранча сиракузская. Это милое насекомое живёт в стаях и питается всем, что попадётся – рой саранчи способен в считанные минуты съесть молодые посевы рапса, конопли, а так же он не гнушается мелкими рептилиями и млекопитающими. Единственная проблема заключается в том, что насекомые не выносят одиночества – оставшись одна, саранча тут же умирает от тоски. Кроме того многочисленные наблюдения позволили, студенту вывести интересную закономерность: популяция саранчи в стае меняется каждый день и не зависит ни от количества пищи, ни от времени года, а лишь от количества насекомых, находящихся в стае в предыдущий день. Если вчера популяция составляла N особей и N чётно, то сегодня их, увы, останется N/2. Зато если N было нечётно, то сегодня нас порадует задорным жужжанием аж 3*N-1 насекомое. Сейчас Василий наблюдает новую колонию саранчи. К сожалению, он не может назвать точного числа насекомых в ней, а значит, предсказать дальнейшее развитие популяции. Единственное, в чём он уверен, это то, что количество насекомых не меньше натурального числа A и не больше натурального числа B. Осчастливьте студента Простонародьева известием, что данная колония будет жить вечно, либо с прискорбием сообщите, какое максимальное число дней она может просуществовать. Но говорите только правду! Вася чувствует, когда ему лгут.

Ввод. Первая строка ввода содержит количество тестов T (1 ≤ T ≤ 100000). Каждая из следующих T строк содержит по одному запросу – пару чисел A и B (1 ≤ A ≤ B ≤ 11111).

Вывод. На каждый запрос выведите -1, если есть вариант, при котором колония проживёт вечно. Иначе выведите максимальное количество дней, которые она может протянуть.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
02.03.2013, 16:32     Задача Популяция #2
получается мы должны будем перебрать все возможные варианты от А до В ? А если половина случаев один расклад а половина другой, что будет ответом, какаято мутная задача
HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 704
Записей в блоге: 1
02.03.2013, 19:49  [ТС]     Задача Популяция #3
да уж
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.03.2013, 22:54     Задача Популяция #4
Цитата Сообщение от Nixy Посмотреть сообщение
получается мы должны будем перебрать все возможные варианты от А до В ? А если половина случаев один расклад а половина другой, что будет ответом, какаято мутная задача
нормальная задача:
Цитата Сообщение от HardLogin Посмотреть сообщение
На каждый запрос выведите -1, если есть вариант, при котором колония проживёт вечно.
Цитата Сообщение от HardLogin Посмотреть сообщение
Иначе выведите максимальное количество дней, которые она может протянуть.
HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 704
Записей в блоге: 1
03.03.2013, 00:23  [ТС]     Задача Популяция #5
а как её решить? для начала я не могу придумать пример чисел при которых колония проживет вечно
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.03.2013, 00:50     Задача Популяция #6
Цитата Сообщение от HardLogin Посмотреть сообщение
для начала я не могу придумать пример чисел при которых колония проживет вечно
например 5.
события будут развиваться так: 5 -> 14 -> 7 -> 20 -> 10 -> 5 и так далее...
Т.е. любой начальный вариант: 5, 14, 7, 20, 10 дает вечную жизнь
HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 704
Записей в блоге: 1
03.03.2013, 11:10  [ТС]     Задача Популяция #7
Цитата Сообщение от valeriikozlov Посмотреть сообщение
5, 14, 7, 20, 10
только эти числа что ли дают вечную жизнь?
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.03.2013, 12:02     Задача Популяция #8
Цитата Сообщение от HardLogin Посмотреть сообщение
только эти числа что ли дают вечную жизнь?
нет конечно )
Эти числа приведены в качестве примера. Из них можно получить еще кучу чисел с вечной жизнью. Вот некоторые из них: 28, 56, 40 80, 160...
Но лучше делать не так, а завести например массив a[11112]. Всем элементам присвоить значение -1. Элементам a[0] и a[1] присвоить значения 0 (значение a[x] - сколько дней проживет колония с количеством саранчи равной x).
Затем использовать очередь. В очередь помещаем значение 1 (для этого значения в массиве a[1] уже есть значение 0 - что означает что одна саранча проживет 0 дней). Затем алгоритм такой:
Берем очередной элемент Y из очереди. Если Y*2<=11111, то a[Y*2]=a[Y]+1 и помещаем элемент Y*2 в очередь. И здесь же: if( (Y+1)%3==0 && ((Y+1)/3)%2==1 && a[(Y+1)/3]==-1 ) то a[(Y+1)/3]=a[Y]+1 и помещаем элемент (Y+1)/3 в очередь. Когда очередь опустеет, то в массиве a[] будут все нужные значения: или -1 (что означает, что колония будет жить вечно), или количество дней, сколько проживет колония.
HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 704
Записей в блоге: 1
03.03.2013, 12:33  [ТС]     Задача Популяция #9
я не понял( как это работает(
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.03.2013, 15:48     Задача Популяция #10
Цитата Сообщение от HardLogin Посмотреть сообщение
я не понял( как это работает(
тогда лучше так понимать:
1 саранча живет 0 дней
2 саранчи живут 1 день
4 саранчи живут 2 дня
8 живут 3 дня
вот здесь развилка:
- 16 живут 4 дня
- 3 живут 4 дня
после развилки:
- 32 живут 5 дней
- 6 живут 5 дней
и т.д.
Yandex
Объявления
03.03.2013, 15:48     Задача Популяция
Ответ Создать тему
Опции темы

Текущее время: 11:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru