| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | Пожалуйста, объясните как в действительности можно понять процесс "Not a proof" | Val | 1494. Монобильярд | 27 апр 2023 14:56 | 7 | Ближайший ответ, с которого вообще началась в моей голове подгонка логики, был изложен здесь: " http://acm.timus.ru/forum/thread.aspx?id=36278&upd=636360628408741039". Но непонятно как в последовательность из "4"-рёх чисел в действительность вот в реальной интерпретации, если бы вы сами играли в этот монобильярд доказать, что чичиков не был ЖУЛИКОМ. Последовательность: 3-4-2-1; (без учёта первого числа, как количества заброшенных шаров. Если с ним, то это будет: 4 3-4-2-1) Ведь если инспектор будет подходить каждый раз, то он явно заметит, что порядок нарушен. Пожалуйста, объясните - я могу понять последовательность по ссылке выше (там ответ от "Oleg Baskakov"), но я не могу представить себе подобную ситуацию в жизни и по этому не понимаю. Дополнительные тесты для разбора: 6 3-4-2-1-5-6 10 4-5-3-6-9-10-8-7-2-1 Заранее, спасибо. Edited by author 19.05.2019 11:14Для последовательности 3-4-2-1 существует такой порядок закатывания и забирания шаров:
1) Закатываем шар №1
2) Закатываем шар №2
3) Закатываем шар №3
4) Забираем последний закатившийся шар (№3)
5) Закатывает шар №4
6) Забираем последний закатившийся шар (№4)
7) Забираем последний закатившийся шар (№2)
8) Забираем последний закатившийся шар (№1) Спасибо за комментарий, может посмотрите мой) Знаете, а оказалось, жизненная интерпретация здесь довольно таки к месту)))
Как сказано из условия - на нашем столе может быть до 100000-сяч шаров, но проверять из них мы будем, к примеру, 8-мь (ибо Ревизор не может заниматься одним лишь Чичиковым и его время ограничено).
Для упрощения представления, условимся, что Ревизор подходит раз в 10-ть минут и берёт ПОСЛЕДНИЙ шар из лунки, не завися от того забивал ли Чичиков шары или нет, он будет каждые 10 минут приходить за последним из них.
Тестовая последовательность будет: 3-5-4-2-6-1-8-7
И началась игра!!!
Ревизор не следит за игрой - он разговаривает с хозяином завидения, пьёт чаи, гоняет бражку))) но за игрой не следит.
Отсчёт времени от "10.00".
"10.10" - Ревизор подошёл и достал шар с цифрой 3-и (далее №3).
Ревизор думает: "А он быстро играет, наверное уже забил шары с № (номером) 1, №2, №3. Чтож, пойду пообщаюсь с хозяином"
"10.20" - Ревизор подошёл и достал шар с №5.
Ревизор думает: "Удалец! Забросил уже шары с №4 и №5. При учёте того, что я забрал шар №3, то в лунку уже попали шары с №1, №2, №3(*), №4 и №5(*) - всё логично, всё честно. Пойду, чайку хряпну."
"10.30" - Ревизор подошёл и достал шар с №4.
Ревизор думает: "Хм. Чичиков видно решил передохнуть да тоже чай погонять, раз у меня шар с №4, а до этого я брал №5, но чтож - всё логично. Пойду дальше"
"10.40" - Ревизор подошёл и достал шар с №2.
Ревизор думает: "Да сколько же можно отдыхать! - у меня нет времени ждать пока он доиграет. В лунке остался только шар с №1, я так думаю, чтож - всё впорядке. Я вижу кекс)))"
"10.50" - Ревизор подошёл и достал шар с №6.
Ревизор думает: "Ну наконец-то, хоть один шар забил".
"11.00" - Ревизор подошёл и достал шар с №1.
Ревизор думает: "И опять пропал - забил один шар и пропал... Лодырь и есть лодырь. Даже играть долго не может"
"11.10" - Ревизор подошёл и достал шар с №8.
Ревизор думает: "Ещё два шара, шар №7 он уже закинул, я так думаю."
"11.20" - Ревизор подошёл и достал шар с №7.
Ревизор говорит: "Да катитесь вы лесом! Снова этот Чичиков ушёл отдыхать!! 8-мь шаров почти что за полтора часа!!! Досвидани хозяин игорного заведения - у меня больше нет времени, мне пора. А что на счёт Чичикова - то он НЕ ЖУЛИК."
Как то так мне помогли представить эту задачу.) Thank you very much! With such a detail explanation the tasks is perfectly clear and solution becomes obvious. Спасибо за интерпретацию, стало ясно, что от меня требуется. Весьма доходчиво! | | Help plz. WA on test 10 | David Tvaltchrelidze | 1494. Монобильярд | 7 апр 2022 19:32 | 11 | [code deleted]
Please help me I have WA on test 10.
Edited by moderator 13.02.2007 20:47 4
2 4 3 1
correct answer 'Not a proof'
but your answer 'Cheater' [code deleted]
//
I passed your test but also WA#10
Edited by moderator 13.02.2007 20:47 Bewere here is something like test 10:
6
435261
Not a proof My program passed all this tests but it's WA#10. Can some one give more tests to compile program? Oh, I found my mistake and got AC.
It's also good test:
7
1645327
Cheater
Edited by author 15.12.2007 00:59 Passed all tests, but WA10. Did anyone know what test 10 is? Same problem here. All these tests passed, but still WA10. .-.
It appears no one knows what the test is. Can you explain this test
6
435261
Not a proof Can you explain this test
6
435261
Not a proof I don't get this one neither... 6
435261
1234 // take 4, take 3
12 // wait for 5
125 // take 5, take 2
1 // wait for 6
16 // take 6, take 1
empty //
There is a scenario when Chichikov may not be cheating. So you can't say that Chichikov is cheating certainly. Answer is "Not a proof". | | Test #11 | Danlo | 1494. Монобильярд | 23 мар 2022 23:50 | 2 | If you get WA on test #11, try this test:
4
1 3 4 2
Not a proof Thanks man, I appreciate it | | Some tests for... :-) | Oleg Strekalovsky [Vologda SPU] | 1494. Монобильярд | 20 сен 2021 14:03 | 4 | 5
2 4 3 1 5
Not a proof
5
2 4 1 3 5
Cheater I thought he could only come in the end. Thanks :) Удалил сообщение, т.к. понял свою ошибку.
Edited by author 20.09.2021 14:14 | | Key hint | ajay jadhav | 1494. Монобильярд | 5 май 2020 23:55 | 1 | Inspector can come at any point.
after 1 ball pocketed
after 2 ball pocketed
or even at the end when n balls are pocketed
Inspector can collect any number of available balls
e.g if he comes after ball 3 is pocketed he can take just 3, or 3 2 or all 3 2 1 | | WA 23 .... wth is this. -_- | Mewtwo | 1494. Монобильярд | 24 фев 2019 01:32 | 5 | I used a simple algo... I am just checking 3 consecutive numbers... If any 3 consecutive numbers from the given numbers are like this, n1>n3>n2 (mid one is the smallest, first one is the largest and the last one lies in between these two values) , then the sequence is invalid (Cheater) ... else , I print "Not a proof" ...
Is my algo ok? If so, then please help me with some test cases...
I have tried all the test cases found in the discussions and my program passed all of them...
Thanks a lot for your answer. I haven't heard about "Process Modelling" ... I'll look into it asap. And my algo that I used is wrong actually. It fails in this type of cases... 4 3 1 4 2 Correct answer is "Cheater", but my program shows "Not a proof"... I wonder how it passed 22 tests... 0_O Thanks again... :) «I haven't heard about "Process Modelling" ... I'll look into it asap.»
Well, it's simple. Basically you just put balls into array in a proper order, and when the last ball is a current takeout request, you take it out of the array and move to next takeout request, and repeat if needed. If at certain point the takeout ball is not the one you expect, the answer is cheater. Good luck~ | | hint and test | Otabek Toshkanov | 1494. Монобильярд | 24 фев 2019 01:31 | 3 | I used DSU algorithm and AC 0.046.
test:
10
4 5 3 6 9 10 8 7 2 1
answer: Not a proof. good test tho
I used stack & queue and got AC I used DSU algorithm and AC 0.046.
test:
10
4 5 3 6 9 10 8 7 2 1
answer: Not a proof. Thanks for the test case... Helped a lot to find bug in my algo. I am wondering how to use DSU here... Would you please mail me your idea? ealham86@gmail.com Thanks again. | | Есть ли неточность в условии ? | Gulliput | 1494. Монобильярд | 27 ноя 2018 00:08 | 1 | А вот эта фраза "Пока господин Чичиков играл, ревизор несколько раз подходил к столу и забирал из лузы последний закатившийся туда шар" может быть понята двояко. Либо буквально "последний закатившийся", и тогда после изъятия последнего закатившегося шара нельзя брать ещё, пока не появится следующий последний закатившийся (то есть до следующего забитого шара: потому что последний уже взят, и следующий шар в лузе - предпоследний закатившийся), либо имеется в виду просто верхний, который может быть последним из оставшихся неизъятыми, а не буквально "последним закатившимся". Так что же имеется в виду авторами задачи и, главное, тестов к ней ?
Это важно, потому что я читал эту фразу буквально, а при таком прочтении обязательное условие относительно шаров, изъятых до конца игры - то, что они должны идти по возрастанию. В случае второго варианта этого условия нет. Я-то привык всегда понимать задание буквально, считая, что авторы задания чётко понимают смысл своих слов. | | TLE test 28. Why this code is slow ? | cs_Diablo | 1494. Монобильярд | 12 май 2018 10:00 | 3 | I've got TLE on test no. 28; here is the "main" piece of code, im wondering why it is slow. Isn't O(n) complexity? Thanks to everyone who help me in advance. Here is the code
void solve()
{
int p=1;
f(i,1,n)
{
f(j,p,b[i])
{
if (!used[j]) { s.push(j); used[j]=1; }
}
if (s.top()==b[i]) s.pop();
else
{
cout<<"Cheater\n";
return;
}
p=b[i];
}
if (s.empty()) cout<<"Not a proof\n";
else cout<<"Cheater\n";
}
Here f(i,beg,end) == for(int i=beg; i<=end; i++), s-STL stack<int>, b[] contains the input and used[] is a control array which shows me if ball with number i was already used. Can someone give me a test on which this code will TL ? To anyone who has the same problem, let's try this test:
100000
1
100000
2
99999
3
99998
...
49999
50000
It gives me TL cause of the inside cycle f(i,p,b[i]) I tried this test, but there is TL.
In VS this test takes less then 40 ms.
What's this test 28? | | Пара тестов | DarkSun1997 | 1494. Монобильярд | 19 июл 2017 12:07 | 7 | Есть наверно несколько решений этой задачи.
Я использовал стек пар. first это было верхняя грань пары, second нижняя.
Как только я считал число, я посмотрел на первый элемент в стеке на его верхнюю грань, если она совпадала, то я понижал грань на -1, если в стеке еще и грани местами менялись то есть first<second, то удалял элемент.
Если же элемент который я считал был меньше чем верхняя грань первого элемента в стеке, то выводил фразу читер!!!!
Если стек оказывался пустым или элмент считывания оказывался больше чем верхняя грань первого элемента, то создавал новую пару и ее грани first присваивал считанное значение, а second присваивал значение h. h это число которое в начале было равно 1 а после добавления нового элемента в стек становилось считанное число +1. Оно менялось у меня только когда добавлял что-то.
Потом проверял если новый элемент стека верхняя и нижняя грань совпадает то удалял его, иначе понижал нверхнюю границу на -1.
Если в конце чтения стек становился пустым, то значит выводим фразу Not a proof.
К сожалению нельзя кидать код программ...
Но могу поделиться парой тестов:
5
3
2
5
4
1
Not a proof
5
3
5
2
4
1
Cheater
4
3
4
1
2
Cheater Да это адская задача, я уже решаю года полтора безуспешно
Решение не пытаюсь посмотреть принципиально
Ничего не помогает решить Ничего тут сложного нет, просто симулируем сам процесс закатывания.
Разберём например тест 10 5 8 7 6 4 10 2 1 3 9.
Пускай мы встретили во входе 5, значит докидываем в массив 1 2 3 4 5. Затем процесс удаления: сравниваем 5 из входа с последним элементом, они равны, значит становится 1 2 3 4.
Потом встретили 8, оно больше нашего последнего закинутого шара, докидываем 6 7 8, получаем 1 2 3 4 6 7 8. И повторяем процесс удаления, описанный выше.
Потом допустим 7, 6, 4, и каждый раз число из входа совпадает с последним элементом массива. Поудаляли, получили 1 2 3.
Потом получаем 10, оно больше последнего закинутого шара, докидываем в массив, получаем 1 2 3 9 10 (и сразу же удаляем, получаем 1 2 3 9).
Потом получаем 2, но последний элемент 9, а не 2, и тут мы понимаем, что ответ Cheater. Ну я не смотрю решений.
Сам додуматься не могу.
Я хочу как-нибудь ссимулировать.
Не могу придумать, как это сделать.
Лучше скажите мне, что решить, какие задачи, которые бы меня подготовили к решению этой. Да тот же 1220 stacks, который вы недавно пытались решать.
Разница лишь в следующем:
— там много стаков, а тут один
— тут только pop-запросы
— pop-запрос, который больше всех предыдущих, автоматически означает, что перед ним надо допушить недостающие шары. Ну я сделал двусвязный список в статическом массиве
И проверял всегда ли верно
Что я беру либо непосредственно следующий шар из оставшихся
Либо любой шар выше Поздравляю с AC :)
P. S. Двусвязный список, кстати, не обязателен, я делал просто массив, и у меня была переменная для текущего размера массива, и если удаляем элемент, то я просто её уменьшал, а если добавляем, то увеличивал и менял элемент на новый.
Edited by author 19.07.2017 12:11 | | Add test please | Fyodor Menshikov | 1494. Монобильярд | 21 июн 2016 11:34 | 2 | I know heuristic solution to problem 1494 that passes all Timus tests but fails tests of some kind. The simplest test that it does not pass is
5
4
2
5
3
1 | | WA#8 | Auslender | 1494. Монобильярд | 28 авг 2015 18:00 | 1 | WA#8 Auslender 28 авг 2015 18:00 have no idea what this test may be | | ACCEPT 0.015sec ! | arrammis | 1494. Монобильярд | 13 июн 2015 17:11 | 1 | For the first time used deque which got 0.204sec after I have changed data structure to a vector got 0.015 sec runing time!
insane :) | | WA#12 | Dewang Sultania | 1494. Монобильярд | 19 май 2015 18:03 | 1 | WA#12 Dewang Sultania 19 май 2015 18:03 Can someone tell what test case 12 is?? | | foe those who ask which data xstructure u need to solve it | Arseniy | 1494. Монобильярд | 29 янв 2015 20:01 | 2 | You need set.
Think how to use it here No, you don't need a set. Any simple linear data structure will do. | | Which STL to use? | Alibi | 1494. Монобильярд | 21 янв 2015 10:46 | 1 | In this task you can use stack!!!! | | Data structures? | Alexey Dergunov [Samara SAU] | 1494. Монобильярд | 8 июл 2012 16:49 | 2 | Why is it tagged as 'data structures'? I used only one array to store the input.
Edited by author 08.07.2012 15:47 | | Fast algo - modelling works!!! | Smilodon_am | 1494. Монобильярд | 15 окт 2011 16:39 | 3 | My AC program uses algorithm with process modelling. It's complexity is O(N) in memory and time. Yes, this is the best algo. I use this too. If "process modelling" is for "linked list structure', then I can say the same.
The algorithm is so trivial, that the previous sentence is already a sufficient hint.
Edited by author 15.10.2011 16:40 | | What is test 22? | KALO | 1494. Монобильярд | 8 окт 2010 02:04 | 1 | I've got AC (but only with dirty cheatings).
Edited by author 21.10.2010 03:31 | | hint | Hanzbrow (TNU) KCC | 1494. Монобильярд | 1 авг 2009 23:01 | 1 | hint Hanzbrow (TNU) KCC 1 авг 2009 23:01 it is easy)
use stack and a little thinking:) |
|
|
