Welcome all to Codeforces Beta Round #17, which will be held 10 June (Thursday) 2010, 19:00 (UTC +4, Moscow time). This contest will represent I.

I would like to thank Mike Mirzayanov who made this contest possible, Artem Rakhov for helping to test authors solutions and Julia Satushina for nice the translation of problem statements into English. Great thank Gennady Korotkevich for preparation problem, writing authors solution and nice idea's. Hope you will like the problems.

I hope that number 17 would be interesting for you!

You can discuss the problems here in the comments after the end of the contest.

http://codeforces.com/profile/MikeMirzayanov

There you can send a personal message if you want, ofc.

Also, there were a link on the contest page to publish a question.

using map in c++?

what about this?

3

3 2 13

1 2 400

1 3 100

2 3 100

How do you handle that? I was going to write

3

3 2 1

3

1 2 400

1 3 200

2 3 100

I think it should do better with Prim's.

The problem assure us that the input is well formed (q[j]>q[i]). So we don't need to process the q value and the name of the employee that made the offer.

At the end we only need to check if at most one employee is without a boss.

For some reason during all the contest I thought that the string could contain any characters from 'a' to 'z' . I just realized that the only allowed characters are 'a','b' and 'c' =(

I will try to solve it using DP as you suggested =)

If n is quite small (say, less than 5 digits), then you can simply calculate

b^{n - 1}(b- 1) modulo c.Otherwise, let

c=c_{1c}_{2}withc_{1}andc_{2}coprime, andc_{1}consisting of primes dividingb. Thenb^{n - 1}= 0(modc_{1}) (because n-1 is very large), andb^{n - 1}=b^{(n - 1)modφ(c2)}(modc_{2}) (because b andc_{2}are coprime).And if we know the remainders modulo

c_{1}andc_{2}, then we can calculate the remainder modulo c, using the GCD representationkc_{1}+lc_{2}= 1.if n is less than 1000 then n1 = n;

else n1 = n mod phi(c) + 10 * phi( c );

answer is b1^n1 mod C

Instead of dividing the bignum by 2 directly I multiply it by 5 and divide it by 10, and just keep a variable to point the first number before the decimal point.

let n = 10^k,

my solution is O(klogk) and k is at most 1 million. Most problemas I've done it's enough to pass.

So can someone please explain the problem with this approach? Or the idea it was intented to pass and the implementation was bad?

Thank you in advance.

So in the end you have an O(d

^{2}) algorithm which is too slow when d~10^{6}as in this problem.Decide = принять решение

Solve = решить (задачу)