Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1
  1  Я ВОР АУЕ КСТА, 11 апреля 2020 г. 23:16:39
     Уххх, сдал эту крошку! Действительно, если посидеть и подумать, то задача не очень сложная, однако, как уже было сказано ниже, она довольна коварна на "ловушки"
  2  Давид Нигматуллин, 24 апреля 2019 г. 11:00:59
     самое сложное - решить проблему с переполнением, всякими хитрыми штуками, либо юзать питон, остальное - работа для моего сына, он вон уже какой большой, в садик скоро пойдет
  3  Глубокий Станислав Сергеевич, 30 августа 2016 г. 0:22:53
     Чтобы оптимально рассчитать сочетания, используйте формулу:
C (N, K) = C (N - 1, K) + C (N - 1, K - 1).
Для хранения значений массива [30][30] хватит с лихвой.
Не забывайте учесть случай, когда N < K.
  4  Зарічковий Олександр Анатольович, 07 августа 2014 г. 11:42:07
     Вот пару тестов (они мне оч. помогли):
34 4
3

41 0
5

87 2
22

25 1
7

3154 13
0
  5  Глембоцкий Владислав Олегович, 03 июня 2013 г. 16:12:51
     Емммм... А почему комбинаторика? Довольно известное ДП как на меня.
     Задачу можно решать и комбинаторными формулами, но по сути это тоже ДП. Ведь число сочетаний имеет динамическую основу, а задача, в которых требуется посчитать количество вариантов по определению является комбинаторной.
  6  Волынский Игорь Владимирович, 04 марта 2013 г. 8:18:57
     183 5=22
207 3=54
20000 7=3674
1024 10=1
1024 9=1
если кому то пригодится
     Да, верные тесты.
  7  М М М, 24 февраля 2013 г. 17:58:44
     Козлов Валерий Викторович, 10 марта 2010 г. 7:06:41
Зубашев Степан, Ваши тесты с вариантами 1000000000 10 и 500000000 10 неверные. Вот правильные ответы:
1000000000 10 = 48572885
500000000 10 = 30882943
Ты не прав или с другим ответом я прошел, т.е. Зубашев Степан - правильно!
     Да, Ваши варианты правильные.
  8  Шавалиев Рустам, 03 марта 2011 г. 21:01:23
     да как же сосчитать варианты в последнем разряде... =(
  9  Платто Павел Константинович, 04 ноября 2010 г. 17:44:21
     Прекальк на 5 минут и перебор не более 10 в 7 чисел тоже проходит:-)
     Да, зато думать не надо.
  10  Хус, 15 октября 2010 г. 16:01:17
     то есть получаетмя мое решение может не проканать на тимусе?номер задачки этой на тимусе не скажете?просто интересно стало?
     На тимусе ее номер 1057. лет 5 назад я ее, как помнится, решал...
  11  Хус, 14 октября 2010 г. 10:04:40
     пипец зачем тут факториалы?неужели люди решающие задачи с такой сложностью, используют наивную формулу сочетаний?
     Ну сами то сочетания тут использовать не бессмысленно, другое дело, что не стоит их вычислять многократно по формуле. Их лучше либо 1 раз вычислить, либо кешировать, не вычисляя повторно каждый раз одно и то же. На тимусе, кстати, есть усложненный вариант этой задачки.
  12  Маскин М.В., 25 июля 2010 г. 0:24:57
     Соболев Евгений Кстати, пункт 5 из твоего алгоритма обязателен, потому что ты проверяешь строго меньшие числа (у тебя прямо так и написано), а ведь само число может тоже быть как вариант, и когда ты проверяешь что ноликов в числе ровно k, поэтому надо проверять единицу. Хотя думаю ты и сам знаешь судя по количеству решенных задач=), но вдруг кому то кто читает обсуждение все-таки интересно почему надо прибавлять единицу)
  13  Козлов Валерий Викторович, 10 марта 2010 г. 7:06:41
     Зубашев Степан, Ваши тесты с вариантами 1000000000 10 и 500000000 10 неверные. Вот правильные ответы:
1000000000 10 = 48572885
500000000 10 = 30882943
  14  Зубашев Степан, 16 ноября 2009 г. 12:21:12
     Вах вах вот эта задачка =) вроде понятно как решается, а мелочей учесть нужно массу. Интересно как Лунёв Антон, везде решает всё по 200-300 символов на код? сдаётся что там просто чтото вроде case (x) of и вывод ответов ;)
В очередной раз убедился что java это чит, можно сдать просто факториалами, без учёта разного рода мелочей :D

Вот парочка новых тестов если кому надо:
500000000 10 = 21474180
1000000000 10 = 34597290
55 4 = 6
12345685 1 = 253
  15  Cihad OGE, 09 ноября 2009 г. 10:05:49
     Должен ли я рассчитать C (1000000000,500000000)? Требуется ли?
     Нет, что вы! Тем более запись неверная. Обычно в C(k,n) k<=n. Буквально у вас это должно быть равно нулю. Но если их поменять, то получится очень большое число, которое конечно же вычислять немыслимо.
  16  Соболев Евгений, 21 марта 2009 г. 15:27:45
     Алгоритм вкратце можно описать следующим образом: 1) перевожу число в двоичную систему; 2) если k>числа разрядов - выводить 0; 3) Ищу количество чисел с меньшим числом разрядов и с ровно k нулями; 4) ищу числа с таким же количеством разрядов, это делаю так: ищу только такие числа, у которых первые i разрядов совпадают с исходным числом (причем только тогда когда i+1 символ это 1, чтобы его можно было заменить на 0 и получить строго меньшее число). 5) если нулей в исходном числе ровно k - прибавляю к ответу 1.
  17  Шипелов Роман Борисович, 19 марта 2009 г. 4:20:19
     11 часов на задачу убил...а сначала она показалась легкой...
     А мне до сих пор легкой кажется :)
  18  Людвиченко Виталий Андреевич, 05 марта 2009 г. 20:45:00
     Реально! там все равно в конце последний разряд в лоб надо. а предыдушие можно акториалиами
Больше че то я не придумал
     Если под "в лоб" понимается какой то перебор весьма большого промежутка чисел, то это здесь не подойдет, тут все решается комбинаторикой.
  19  Бобер Александр Дмитриевич, 11 мая 2007 г. 21:29:59
     Оптимально-это рекурсивно или через логарифмы? Все равно "хвостик" между степенью двойки и N надо бить в "лоб"!
     Это комбинаторика понимаете ли... В лоб бить не нужно.
  20  Кузнецов Георгий Сергеевич, 04 апреля 2007 г. 13:41:48
     При малых n моя программа бысро работает. А при n=1000000000 и k=1 программа 10 минут думала(пока я её не вырубил).
     Ну оно и понятно :) Что вы так просто ее решить хотите? Здесь простым полным перебором не обойтись! Тут нужно использовать комбинаторику, да еще и оптимально вычислять C(k,n).
 1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru