ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 2071. Фруктовые коктейли

WA 23 any ideas?
Послано Nodir NAZAROV [TUIT-Karshi] 8 дек 2015 08:58
I didn't find any case that my algorithm fails.

Please give me test cases for test #23, I see there are a lot of WA#23.
Re: WA 23 any ideas?
Послано Jane Soboleva (SumNU) 9 дек 2015 12:48
I guess, it has to do with something when certain types of drinks are not present.

Initially, i only analyzed one possible permutation, and got WA15. Then, i added another one to check, and got WA31. I threw in 4 more to check before giving answer, and got WA95. I probably missed just a few more unique cases, though i never figured out what was the problem.

Well, in the end, i stopped bothering and just checked all 7! permutations. It's a lot more excessive than just checking a few selected, but will guarantee AC. You should do that too, probably.
Re: WA 23 any ideas?
Послано Nodir NAZAROV [TUIT-Karshi] 9 дек 2015 20:56
Thanks Jane for your advice!

It's obvious that possible number of pourings are 1 to 5. So I've put all the conditions that requires certain number of pourings. If these conditions are set well you don't have to check all the 7! permutations (I think that's quicker and easier solution, maybe I'm wrong).
Re: WA 23 any ideas?
Послано Jane Soboleva (SumNU) 9 дек 2015 23:57
No problem~
Also, the worst case is 4, see
A AB ABP AP P BP B
1 pouring for A, 1 pouring for P, 2 pourings for B, if all present.
That's the only one i checked when i got WA15.
I guess, at that point, my fault was something like... if AP and P aren't present, then we don't interrupt our pouring, and B is 1 pouring then.
Or maybe that wasn't the thing... anyway i fixed that in my final version.
Re: WA 23 any ideas?
Послано Nodir NAZAROV [TUIT-Karshi] 11 дек 2015 20:54
hey Jane,

How come the worst case is 4, not 5? If all types are present then it should be as following (You cannot pour P over B, hence 1 A, 2 B, and 2 P):

12345
A....
AB...
ABP..
A.P..
..P..
...BP
...B.

Please correct me if I'm wrong.
Re: WA 23 any ideas?
Послано Jane Soboleva (SumNU) 11 дек 2015 23:43
Um, i just listed pourings in an order of a growing number of them, a proper order is, of course, 1 for A, 2 for B and 1 for P. As for your table, i'm not sure why you put that P to the right.
A....
AB...
ABP..
A.P..
..P..
..PB.
...B.
I mean, PB doesn't mean we pour P first, but if we represent it _this_ way...

Add:
I'm not sure if above was proper explanation, maybe i'll explain it like this:
in A AB ABP AP P BP B, it goes
1. Pour A in 1-4.
2. Pour B in 2-3 and 6-7
3. Pour P in 3-6.

Oh, and you can email me if you want to...

Edited by author 12.12.2015 00:31
Re: WA 23 any ideas?
Послано Nodir NAZAROV [TUIT-Karshi] 12 дек 2015 10:09
Thanks a lot. That explains well. Actually I thought the order should be maintained, probably most of the WA#23 because of wrong understanding of the problem statement.
Re: WA 23 any ideas?
Послано Jane Soboleva (SumNU) 12 дек 2015 14:15
Good job on finally making it~

Edited by author 15.12.2015 01:37