Разбор ДВГУПС — тренировка 28

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

А. Ярмарка оружия [реализация, математика] Следовало последовательно сравнить силы наборов, если текущая сила строго больше максимальной предыдущей, то обновляем максимальную и индекс лучшего набора. Вычислить силу набора можно было в нецелых числах как (сумма s_i, j / w_i), или сохранить числитель и знаменатель дроби (sum_s_max и w_max) и сравнивая с текущим набором домножить обе части на (w_max·w_i). Не стоит забывать, что суммирование 10⁵ чисел до 10⁹ приведёт к переполнению типа integer.

Решение в нецелых числах: $O(n)$

Rev.	By	When	Δ	Comment
ru23	nikich340	2017-08-15 02:06:12	57
ru22	nikich340	2017-08-14 03:38:53	0	(опубликовано)
ru21	nikich340	2017-08-14 03:37:24	0
ru20	nikich340	2017-08-14 03:37:24	6
ru19	nikich340	2017-08-14 03:35:31	879	Мелкая правка: 'няется $x^cnt[x] % m$. Сде' -> 'няется $x^{cnt[x]} % m$. Сде'
ru18	nikich340	2017-08-14 03:21:52	1685
ru17	nikich340	2017-08-14 02:55:25	337	Мелкая правка: '(b + 1)$\n$\frac{f' -> '(b + 1)$\n\n$\frac{f'
ru16	nikich340	2017-08-14 02:47:51	294
ru15	nikich340	2017-08-14 02:43:54	387
ru14	nikich340	2017-08-14 02:38:00	2110
ru13	nikich340	2017-08-14 02:19:17	112
ru12	nikich340	2017-08-14 02:17:37	2	Мелкая правка: 'руктуру.\nАсимптот' -> 'руктуру.\n\nАсимптот'
ru11	nikich340	2017-08-14 02:16:48	72	Мелкая правка: 'решения:\n- Для хе' -> 'решения:\n\n- Для хе'
ru10	nikich340	2017-08-14 02:14:24	189
ru9	nikich340	2017-08-13 15:40:50	4
ru8	nikich340	2017-08-13 15:39:04	139
ru7	nikich340	2017-08-13 15:35:40	15
ru6	nikich340	2017-08-13 15:34:54	10
ru5	nikich340	2017-08-13 15:33:54	427
ru4	nikich340	2017-08-13 15:20:03	2245	Мелкая правка: 'ематика]\nСледовал' -> 'ематика]\n\nСледовал'
ru3	nikich340	2017-08-13 15:15:48	16
ru2	nikich340	2017-08-13 15:15:20	616
ru1	nikich340	2017-08-13 14:57:12	113	Первая редакция (сохранено в черновиках)

History