160929 recipes - История изменений

Burunduk в 18:38, 3 октября 2016

2016-10-03T18:38:10Z

Burunduk в 18:37, 3 октября 2016

2016-10-03T18:37:44Z

Roman.kolganov в 12:34, 3 октября 2016

2016-10-03T12:34:55Z

Burunduk в 14:04, 2 октября 2016

2016-10-02T14:04:49Z

Burunduk в 14:04, 2 октября 2016

2016-10-02T14:04:30Z

Burunduk в 14:03, 2 октября 2016

2016-10-02T14:03:21Z

Burunduk: Новая страница: «* Задача A. Квадратный корень 1. `unsigned long long` -- всё должно быть именно такого типа. 2.
2016-10-02T14:03:06Z

Новая страница: «* Задача A. Квадратный корень 1. <code>unsigned long long</code> -- всё должно быть именно такого типа. 2. <co…»

Новая страница
* Задача A. Квадратный корень

1. <code>unsigned long long</code> -- всё должно быть именно такого типа.
2. <code>unsigned long long l = 0, r = -1;</code> // границы бинпоиска,
3. Чтение до конца файла: добавлен специальный пример по C++
4. У вас WA? Вы тестировали? Спокойно сядьте, и вбейте 20 разных тестов, включая максимальные и минимальные.
5. У вас TL? Может быть, бинпоиск виснет? Может быть, вы не умеете читать файл?

* Задача B.

Если вы пользуетесь функциями STL <code>lower_bound/upper_bound</code>, в чём может быть проблема? =)
TL? Наверное, вы медленно читаете/выводите.

@@ Строка 29: / Строка 29: @@
 * Задача D. minmax.
-В этой задаче нужно написать две кучи. Как при удалении из первой кучи быстро найти элемент во второй?
+В этой задаче нужно написать две кучи. Как при удалении из первой кучи быстро найти и удалить элемент во второй?
 Есть два разных способа, один подход будет на лекции в среду, а второй вы уже знаете с прошлой лекции &minus; "обратные ссылки".

@@ Строка 19: / Строка 19: @@
 * Задача C. find3.
-. Если вы вызываете один бинпоиск, а потом линейно проходите по равным, получите TL. Задача решается небольшим числом вызовов бинпоиска.
+Если вы вызываете один бинпоиск, а потом линейно проходите по равным, получите TL. Задача решается за O(log n).
-. Если вы пишете два разных бинпоиска, то задача не будет зачтена!!!
+<!--
+  небольшим числом вызовов бинпоиска.
-. Сделать все одинаковым бинпоиском было бы тяжело, если бы числа в массиве были вещественные. Но они целые.
+. Если вы пишете два разных бинпоиска, то задача не будет зачтена!!!
 * Задача D. minmax.
-Есть два разных способа синхронизировать две кучи. Один подход будет на лекции в среду.
+В этой задаче нужно написать две кучи. Как при удалении из первой кучи быстро найти элемент во второй?
-А второй уже был на лекции. Если мы помним position[i], где в куче лежит a[i], то можно из нее удалить. Удалить произвольный элемент почти так же, как вершину (но нужно заметить тонкость).
+<!--
+heap[i] = j
 Меняя элементы местами, не забывайте менять и position.
 Для этого нужно и в куче помнить позиции элементов.

← Предыдущая		Версия 12:34, 3 октября 2016
Строка 16:		Строка 16:

	2. TL? Наверное, вы медленно читаете/выводите.		2. TL? Наверное, вы медленно читаете/выводите.
		+
		+	* Задача C. find3.
		+
		+	1. Если вы вызываете один бинпоиск, а потом линейно проходите по равным, получите TL. Задача решается небольшим числом вызовов бинпоиска.
		+
		+	2. Если вы пишете два разных бинпоиска, то задача не будет зачтена!!!
		+
		+	3. Сделать все одинаковым бинпоиском было бы тяжело, если бы числа в массиве были вещественные. Но они целые.
		+
		+	* Задача D. minmax.
		+
		+	Есть два разных способа синхронизировать две кучи. Один подход будет на лекции в среду.
		+
		+
		+
		+	А второй уже был на лекции. Если мы помним position[i], где в куче лежит a[i], то можно из нее удалить. Удалить произвольный элемент почти так же, как вершину (но нужно заметить тонкость).
		+
		+	Меняя элементы местами, не забывайте менять и position.
		+
		+	Для этого нужно и в куче помнить позиции элементов.

@@ Строка 13: / Строка 13: @@
 * Задача B. Бинпоиск.
-Если вы пользуетесь функциями STL <code>lower_bound/upper_bound</code>, в чём может быть проблема? =)
+. Если вы пользуетесь функциями STL <code>lower_bound/upper_bound</code>, в чём может быть проблема? =)
 TL? Наверное, вы медленно читаете/выводите.

@@ Строка 1: / Строка 1: @@
-* Задача A. Квадратный корень
+* Задача A. Квадратный корень.
 . <code>unsigned long long</code> -- всё должно быть именно такого типа.
@@ Строка 11: / Строка 11: @@
 . У вас TL? Может быть, бинпоиск виснет? Может быть, вы не умеете читать файл?
-* Задача B.
+* Задача B. Бинпоиск.
 Если вы пользуетесь функциями STL <code>lower_bound/upper_bound</code>, в чём может быть проблема? =)
 TL? Наверное, вы медленно читаете/выводите.

@@ Строка 2: / Строка 2: @@
 . <code>unsigned long long</code> -- всё должно быть именно такого типа.
 . <code>unsigned long long l = 0, r = -1;</code> // границы бинпоиска,
 . Чтение до конца файла: добавлен специальный пример по C++
 . У вас WA? Вы тестировали? Спокойно сядьте, и вбейте 20 разных тестов, включая максимальные и минимальные.
 . У вас TL? Может быть, бинпоиск виснет? Может быть, вы не умеете читать файл?