| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| it takes my days | Abid29 | 1696. Зарплата для роботов | 10 апр 2021 22:04 | 1 |
you can easily find the solution with O(nk^3)
but it will give u tle
after optimization with cumulative sum array it will be O(nk^2) |
| WA4? | Ana93 | 1696. Зарплата для роботов | 12 окт 2016 00:50 | 2 |
WA4? Ana93 17 апр 2011 17:19 What is in test 4?
I have WA and I dont know what is wrong. Personally I had problem with modular arythmerics |
| More Tests | Mohamed K. Cena | 1696. Зарплата для роботов | 8 янв 2014 01:10 | 2 |
Could you please provide more tests.
I have WA#2 No idea why! although all the tests in the other discussions succeeded including the original test case Answer for #2 is P. So have to be carefull not to print ( sol + 1 ) % P. You have to print
just sol + 1 because months are numbered from 1 to P.
Tests:
20 30 1000 ans: 177
41 56 23 ans: 12
10 5 1000 ans: 185 |
| Complexity | Zayakin A. [Perm SU] | 1696. Зарплата для роботов | 10 июл 2011 03:55 | 1 |
Can this solve with complexity lower than O(N*k^2)? |
| Example tests | Tomislav Gudlek | 1696. Зарплата для роботов | 24 апр 2011 04:57 | 4 |
Could somebody give me any additional test cases?
For example,
4 3 1000000
5 6 1000000 3 3 20 = 7 is covered in the problem itself, but here are two more:
n k p result
1 1 30 2
1 2 12 3
Edited by author 13.04.2011 22:35 Thanks, 1 1 30 helped a lot :) Some additional tests:
4 3 1000000
73
5 6 1000000
4369
1000 200 777
141 |
| Why 7 in example | mnovakovic | 1696. Зарплата для роботов | 21 апр 2011 07:59 | 7 |
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 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. 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? 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. Pardon, it was a typo, I meant 3^3-1. :) |
| It's a beautiful problem. Thanks to author. | Alex Tolstov (Vologda STU) | 1696. Зарплата для роботов | 6 апр 2011 01:26 | 2 |
|
| How to solve this problem? | ErOPb|4[USU] | 1696. Зарплата для роботов | 9 авг 2009 18:44 | 2 |
I have TL#4 and I don't know how optimize my solution. There are many DP schemes for this problem
but only rather good help to avoid TL. |
| Some questions | SerailHydra | 1696. Зарплата для роботов | 28 май 2009 16:05 | 2 |
1:) Is it actually only (n-1) robots? (One for the accountant)
2:) What's the salary arrangement of the first 6 months in the sample?
3:) Is p always larger than the answer? What if not?
4:) What's the answer for the test 4 3 100?
Thanks for answering. Somebody please answer these questions. I don't understand the problem. |
