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

→ Pay attention

Before contest
Codeforces Round 950 (Div. 3)
01:02:03
Register now »

→ Streams

Codeforces Round 950 Solution Discussion

By aryanc403

Before stream 03:17:01

View all →

→ Top rated

#	User	Rating
1	tourist	3757
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	maomao90	171
2	awoo	165
3	adamant	163
4	TheScrasse	159
5	maroonrk	155
6	nor	154
7	-is-this-fft-	152
8	Petr	147
9	orz	146
10	pajenegod	145

View all →

→ Find user

→ Recent actions

Detailed →

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

Revision ru2, by nikich340, 2017-08-13 15:15:20

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

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

разбор, двгупс, тренировка

History

Revisions

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	Первая редакция (сохранено в черновиках)