ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1696. Salary for Robots

mnovakovic Why 7 in example [6] // Problem 1696. Salary for Robots 18 Apr 2011 09:13
Can somebody explain why 7 is the result of the given test?

What is wrong with the following list of tuples:

1. 1 1 1
2. 1 1 2
3. 1 1 3
4. 1 2 1
5. 1 3 1
6. 2 1 1
7. 3 3 3

In this list of tuples, there is no tuple where all 3 elements have the same salary as before

Edited by author 18.04.2011 09:13
Uros Joksimovic Re: Why 7 in example [4] // Problem 1696. Salary for Robots 19 Apr 2011 06:04
I think you're missing a few, for example:
2 2 2
1 3 2
etc.

The robot can't pay with rank1<rank2<rank3 & payment1>payment2>payment3 but he can do it if
rank1<rank2<rank3 & payment1<payment2>payment3.

Basically, for the 7 3 example you can do all permutations with repetition except for
3 2 1
so its 2 to the power of 3 minus 1.
mnovakovic Re: Why 7 in example [3] // Problem 1696. Salary for Robots 19 Apr 2011 22:52
I can see why 3 2 1 is not allowed (constraint rank1<rank2<rank3 & payment1>payment2>payment3) and that is fine.

But why 2^3? You have 3 options for salary for each of 3 robots, I would say it is 3^3 - 1?
bsu.mmf.team Re: Why 7 in example [2] // Problem 1696. Salary for Robots 20 Apr 2011 00:41
Yes, the count of allowed configurations of salaries is 26. So the accountant-robot will rust in 27th month, i.e. in 7th month of the year. That's why the answer is 7.
mnovakovic Re: Why 7 in example [1] // Problem 1696. Salary for Robots 20 Apr 2011 10:03
thanks!
Uros Joksimovic Re: Why 7 in example // Problem 1696. Salary for Robots 21 Apr 2011 07:59
Pardon, it was a typo, I meant 3^3-1. :)
SuperLight Re: Why 7 in example // Problem 1696. Salary for Robots 19 Apr 2011 13:59