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

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

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

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

Вывод. На каждый запрос выведите -1, если есть вариант, при котором колония проживёт вечно. Иначе выведите максимальное количество дней, которые она может протянуть.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nixy
ComfyMobile
 Аватар для Nixy
399 / 280 / 8
Регистрация: 24.07.2012
Сообщений: 916
02.03.2013, 16:32     Задача Популяция #2
получается мы должны будем перебрать все возможные варианты от А до В ? А если половина случаев один расклад а половина другой, что будет ответом, какаято мутная задача
HardLogin
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 692
Записей в блоге: 1
02.03.2013, 19:49  [ТС]     Задача Популяция #3
да уж
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.03.2013, 22:54     Задача Популяция #4
Цитата Сообщение от Nixy Посмотреть сообщение
получается мы должны будем перебрать все возможные варианты от А до В ? А если половина случаев один расклад а половина другой, что будет ответом, какаято мутная задача
нормальная задача:
Цитата Сообщение от HardLogin Посмотреть сообщение
На каждый запрос выведите -1, если есть вариант, при котором колония проживёт вечно.
Цитата Сообщение от HardLogin Посмотреть сообщение
Иначе выведите максимальное количество дней, которые она может протянуть.
HardLogin
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 692
Записей в блоге: 1
03.03.2013, 00:23  [ТС]     Задача Популяция #5
а как её решить? для начала я не могу придумать пример чисел при которых колония проживет вечно
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 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
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 692
Записей в блоге: 1
03.03.2013, 11:10  [ТС]     Задача Популяция #7
Цитата Сообщение от valeriikozlov Посмотреть сообщение
5, 14, 7, 20, 10
только эти числа что ли дают вечную жизнь?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 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
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 692
Записей в блоге: 1
03.03.2013, 12:33  [ТС]     Задача Популяция #9
я не понял( как это работает(
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 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     Задача Популяция
Ответ Создать тему
Опции темы

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