Комбинации колон, (готовлюсь к icpc)

[Алексей_2012]

Ребят, у меня три вопроса:
1) как можно проверить число 10^9?
2) не очень понял суть задачи
3) и что значит время тестирования 3(сек./тест)?

Вообще, кто-нибудь там участвовал?) Какие впечатления?

[Alex11223]

как можно проверить число 10^9?

В смысле как? Взять и проверить. 10^9 = 1000000000. Ну или какая-нибудь стандартная функция power языка если не охота столько 0 писать самому.

и что значит время тестирования 3(сек./тест)?

Ну а что это может значить?
Программе разрешено работать не более 3 сек в каждом тесте.

[Алексей_2012]

так же по мимо самой задачи меня интересует вопрос быстродействия....где вообще можно прочитать более подробно об оптимизации кода? Притом, может быть, кто-то собрал все данные воедино? МОжет есть какая-нибудь статья,..., а то в интернете устал лазить по разным ресурсам, например на одном сайте чисто только о развертке цикла говориться

1) тернарный оператор или if else? (при условии того, что обо можно использовать, случаи, в которых тернарный оператор применить нельзя - не рассматриваю)

2) поток iostream или Printf, scanf отработает быстрее?

3) что лучше: цикл for, while или рекурсия?

4) using namespace std или using std::cin; using std::cout? (чтоб была привязка только к cin и cout, не более, поможет ли в быстродействии?)

5) i=i+1, i+=1? (пример других операторов *=, ну и т.д.)

[BDA]

Попробовал наивный алгоритм на informatics.mccme.ru - 7 тестов из 28 прошли (остальные не уложились в односекундный лимит). Все приведенные 5 примеров (ну кроме 3го), по моему мнению, не окажут существенного влияния на решение олимпиадных задач. Гораздо важнее сложность примененного алгоритма.

[FPaul]

На кибере видел алгоритм решения подобной задачи. Правда там не оговаривались ограничения по памяти. Идея - в массиве сохраняется количество делителей, а потом по массиву производится поиск.

Сам алгоритм был примерно таким.
1. Создаём массив a[1..10^9] of longint - тип можно подобрать по результатам домашних испытаний
2. В цикле i перебираем все числа от 1 до 10^9 (или оценить этот предел).
2.1 В цикле j от i до 10^9 шагом i увеличиваем на 1 a[j]
3. В цикле ищем такое a[i], чтобы оно было ["больше или" - Sorry, глупость сморозил, потому и исправил] равно n [и было как можно ближе к n - опять]. Ответом будет i.

К алгоритму можно добавить оптимизации, например, если при заполнении массива a[i]=n, то ответ. Или совместить заполнение и поиск, т.к. элементы массива с индексами ниже i не изменяются.

[Alex11223]

где вообще можно прочитать более подробно об оптимизации кода?

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

А почитать про "оптимизации"/"хороший код" и т.п. можно Code complete от S. McConnel, не зависимо от ЯП.

Но тут задачи вообще не про это наверно, а про алгоритмы, структуры данных. Так что надо приступать к изучению какого-нибудь стандартного курса/книги по алгоритмам (ну там где всякие сортировки, алгоритмы для графов/деревьев, комбинаторика, жадные алгоритмы, разделяй и властвуй, динамическое программирование и все такое) и структурам данных (список, стек/очередь, set, map, графы, деревья и т.п.), понимать какая где сложность и когда что лучше. Если что на всяких Coursera'х, хекслетах, лекториумах полно курсов по этому.