Bitset<30> operation "|"
helps to avoid inner N-loop

= 、=  Using edge list, got TLE. I got AC changed edge list to adjacency matrix.

use greedy algo instead.
choose the largest numbers for the innermost square roots so that their values get depreciated with each iteration.
this is how i did.
sort arr in reverse order

[code deleted]

cur is the final answer

Edited by moderator 19.10.2019 19:45

you can use dp in this task, like in the classical task "how to multiply n matrices in optimal way". it's O(n^3), so suitable.

also there's greddy algorithm, O(n).

1 1 2
1

1 2 3
2

234 532 245
3

12345 87654 23456
4

1223456 8098887645 567321
4

12345 654345678 1234567890
5

Edited by author 05.07.2011 20:09

1000 1 0 2 1
the answer
 4.34665576869374564E+0208

Why do you think it is "almost solved"? A problem may have arbitrary number of tests (sometimes 200+), so WA #18 doesn't mean "almost solved", it means "not solved".

for n = 10000 and m = 100000 you get approximately 2.10^6. the only way to get 0.79 is if the constant is big enough.
mine is O(m + n) and I get 0.079

thanks a lot. I really didn't know what to do with test 13

Cockroaches!蟑螂
Time Limit: 1 second
Memory Limit: 1000K


It's well-known that the most tenacious of life species on the Earth are cockroaches. They live everywhere if only there in food. And as far as they are unpretentious in food you can find them absolutely everywhere.
众所周知地球上最顽强的生命种类是蟑螂，他们生活在有食物的任何地方。只要有食物，你就可以发现他们的影踪。

A little Lyosha studies at school on a Space station. During one of the school competitions his class has reached the final. A task of the final contest is to exterminate all the cockroaches in the cargo module within minimal time.
Lyosha 在太空站的学校学习。在学校的一项竞赛里，他们班已经到达接近尾声，其中一项任务是在最小的时间里消灭货物仓里的蟑螂。

Within the long history of the competitions a unified tactics was worked out. The tactics is as follows: a poison gas is let in one of the module compartments and after that the baffle that separates the compartment from one of the adjacent ones is opened.  Cockroaches can't stand the smell of the gas and run to the other compartment. When there's no cockroaches in the treated compartment the baffle is closed. Afterwards analogously the next compartment is treated, and so on. The goal is to move all the cockroaches to the floodgate of the cargo module. Then the outward door is opened and all the cockroaches are engulfed by an open Space.
他们在长时间的竞赛里，已经形成了统一的战术。 战术是这样的：把毒气放在一个厢房里，另外，打开闸门（隔开相邻厢房的门）。蟑螂不能忍受毒气的味道，会纷纷逃向隔壁的已打开的厢房，如此下去。目标是把所有的蟑螂赶向floodgate货物仓（的闸门）。

Lyosha is responsible for programming the control board of the baffles in his team. The baffles are opened slowly, so it's very important to make do with minimal number of baffle openings in order to win in the contest. Your task is to help Lyosha to compute this number.
Lyosha负责闸门的规划控制，闸门开得慢，所以这项工作对于竞赛的胜负是很重要的，要设法使到开最少的门。你的任务是帮助Lyosha 计算这个数。

Input
The first line contains a name of the floodgate compartment. Each of the next lines contains description of one of the baffles - the names of two compartments separated with a dash (-). The last line contains the only symbol "#". There are cockroaches in all the compartments of the module at first. It's possible to get to the floodgate from every compartment of the module passing several baffles. The total number of compartments doesn't exceed 30. The name of a compartment consists of no more than 20 Latin letters and digits. The large and the small letters should be distinguished.
首行为floodgate厢房名。以下每一行为两个厢房间的闸门名，两个厢房间用(-)隔开。最后一行只有“#”结束。开始时每个厢房都有蟑螂。每个厢房的蟑螂经过几个闸门后都能到达floodgate。厢房的数量不超过30个。厢房名不超过20个字母数字，区分大小写。

Output
Your program is to output the only number - the minimal amount of baffles that should be opened (and then closed) in order to move all the cockroaches to the floodgate.
输出最小的数字，即为了能把蟑螂赶到指定的floodgate,要开的门数 （当然开完后又关上）

Sample Input
Gateway
Machinery-Gateway
Machinery-Control
Control-Central
Control-Engine
Central-Engine
Storage-Gateway
Storage-Waste
Central-Waste
#
Sample Output
6

The sum of 2 odd numbers is always an odd number.

To have 2 numbers sum up to an odd number, one needs an even number and an odd number. In this case, 2 + (n-2) (because 2 is the only even prime).

Now, I'm stuck on how to solve the problem fast for even numbers

YAHOO!!! I got AC.

if you get WA4 -> travel card = unlimit
if you get WA6 -> test when answer = 0

thanks a lot!!

http://acm.timus.ru/forum/thread.aspx?id=30379&upd=635228341227003651
read this
it is fully solved task

Edited by author 17.12.2013 00:14

I wa on test 10 many times too.
thx

Pirated is
 Licensed to Pirated
 Pirated to Pirated

Licensed is
 Licensed to Licensed

Cracked is
 Pirated to Pirated
 Licensed to Licensed

To everyone. If you have WA#10 read the problem state carefully. A pirated program can never become licensed again.

you did not account for the max size limit on the input....

Each sentence in problem statement makes sense, it can't be reduced.
There are three author solutions, but two other guys didn't submit them.
BTW, I don't think that this problem so difficult, try to solve it.

P.S. "Условие задачи" = "Problem statement", "condition" - условие, которое может быть истинным или ложным

Edited by author 14.12.2013 18:41