OJ Board

I 'hard-coded' and got an AC for this problem......

But I really want to know how to calculate the answer.

Please tell me how. Thanks!

You said you got AC.
What is the problem?
Can you write an idea briefly? I have been solving this problem for 2 months and still don't know the answer...
Can you send me your code?

Nah...

I just 'hard-coded' the whole thing.

That means I simply find the answers for n = 1 to 30 from the web and put them directly in the program. I have no idea how to do the calculation......

P.S. When n = 30, Ans. = 90479177302242 !!!!

Where did you find it???

I don't appreciate hard-coding (I feel sorry for myself after hard-coding ).

But if you really need some help, try this website

The On-Line Encyclopedia of Integer Sequences
http://www.research.att.com/~njas/sequences/index.html


There you can find many interesting integer sequences (including the one in this qq!!!)

A formula (which I couldn't understand) is even provided.

What is the answer for n=3? 3?
Because I can not find the sequence

It is really cool site

Hey, Dmytro_Chernysh, I saw your name on the Ranklist!!!

So how did you solve the problem?

Please tell me!!!!!!!!!!!!

Well, I just precalculated the answer ...
Moreover, I took the outputs from that site
BUT, I DON'T think that this is "solution"

Well......



So, could anyone tell me the "real solution" to that problem?

I really wanna know...................................




Btw, what does the formula given on that website mean?

Hello, is anybody here??!!!!

I have bad felling that everyone cheated
I guess only a few people know how to solve the problem, not just the copied answer.

Let's hope that's not true......

hi everyone

i think i find a way to count the number of different answer, but i dont try to implement it uptonow

my idea is this:

for any acceptable answer generate a sequence of number and then count the no of this sequence.
the sequence must be unique for every answer (i mean that no two answer should generate the same sequence) and every sequence must generate a valid answer.

the way that i use to generate the sequence is this:
i consider all the gate with length of 1 which has no parallel gate to be +1 and all the other to be -length (gate), except the case there exists two or more parallel gate with length = 1, in this case one of the gate will be shown by 1 and the other(s) will be shown by -1.also if there are multiple minus gate, i use -1(2), which means that two gates in backward direction exist.

to clearify i try write the sequence for example in the problem 10253, for n= 4:

1 1 1 1
1 -1(3)
1 1 1 -1(1)
1 1 -2 (2)
1 1 -2(1) 1
1 -1(1) 1 -2(1) is it correct
1 1 -1 (2)
1 1 1 -3(1)
1 -1(1) 1 -1(1)
1 1 -1 -1

i hope this idea works.
i think it is easy to avoid the repeated answer by checking their sequence

I suffered from stupid mistakes I made in solving this problem and I just got AC.

You can tackle this problem with dynamic programming. You should focus on there are two types of networks: one kind which are parallel connected, and another kind which are serial connected.

You'll have enumerable number of partitioning edges among serial(parallel) connected sections (since N <= 30). The sections are independant to each other.

I posted my solution to find help when it didn't work, but deleted it because it might be a spoiler.

Hope this could be some help.

ps. Guess what? This is my 700th problem!

oh, what are the details of this DyP solution?
can anybody tell me?

thx very much!!!