| ENG RUS | Timus Online Judge |
Discussion of Problem 1494. MonobilliardsVal Пожалуйста, объясните как в действительности можно понять процесс "Not a proof" [6] // Problem 1494. Monobilliards 19 May 2019 11:05 Ближайший ответ, с которого вообще началась в моей голове подгонка логики, был изложен здесь: "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 👨💻tproger👨💻[GTGU] Re: Пожалуйста, объясните как в действительности можно понять процесс "Not a proof" [1] // Problem 1494. Monobilliards 19 May 2019 13:23 Для последовательности 3-4-2-1 существует такой порядок закатывания и забирания шаров: 1) Закатываем шар №1 2) Закатываем шар №2 3) Закатываем шар №3 4) Забираем последний закатившийся шар (№3) 5) Закатывает шар №4 6) Забираем последний закатившийся шар (№4) 7) Забираем последний закатившийся шар (№2) 8) Забираем последний закатившийся шар (№1) Val Re: Пожалуйста, объясните как в действительности можно понять процесс "Not a proof" // Problem 1494. Monobilliards 19 May 2019 20:43 Спасибо за комментарий, может посмотрите мой) Val Re: Пожалуйста, объясните как в действительности можно понять процесс "Not a proof" [3] // Problem 1494. Monobilliards 19 May 2019 20:42 Знаете, а оказалось, жизненная интерпретация здесь довольно таки к месту))) Как сказано из условия - на нашем столе может быть до 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-мь шаров почти что за полтора часа!!! Досвидани хозяин игорного заведения - у меня больше нет времени, мне пора. А что на счёт Чичикова - то он НЕ ЖУЛИК." Как то так мне помогли представить эту задачу.) tepamid Re: Пожалуйста, объясните как в действительности можно понять процесс "Not a proof" // Problem 1494. Monobilliards 27 Jun 2019 01:25 Thank you very much! With such a detail explanation the tasks is perfectly clear and solution becomes obvious. Alexander Petrov Re: Пожалуйста, объясните как в действительности можно понять процесс "Not a proof" // Problem 1494. Monobilliards 21 Apr 2021 16:03 Спасибо за интерпретацию, стало ясно, что от меня требуется. Весьма доходчиво! Unho Re: Пожалуйста, объясните как в действительности можно понять процесс "Not a proof" // Problem 1494. Monobilliards 27 Apr 2023 14:56 лучший, спасибо David Tvaltchrelidze Help plz. WA on test 10 [10] // Problem 1494. Monobilliards 20 Dec 2006 23:32 [code deleted] Please help me I have WA on test 10. Edited by moderator 13.02.2007 20:47 Dembel {AESC USU} Re: Help plz. WA on test 10 [9] // Problem 1494. Monobilliards 22 Dec 2006 14:05 4 2 4 3 1 correct answer 'Not a proof' but your answer 'Cheater' Macuk_Yuri Re: Help plz. WA on test 10 [8] // Problem 1494. Monobilliards 12 Feb 2007 22:14 [code deleted] // I passed your test but also WA#10 Edited by moderator 13.02.2007 20:47 Lomir Re: Help plz. WA on test 10 [7] // Problem 1494. Monobilliards 13 Feb 2007 02:49 Bewere here is something like test 10: 6 435261 Not a proof ₦¯ίμ®@£ Re: Help plz. WA on test 10 [3] // Problem 1494. Monobilliards 13 Dec 2007 14:30 My program passed all this tests but it's WA#10. Can some one give more tests to compile program? ₦¯ίμ®@£ Re: Help plz. WA on test 10 [2] // Problem 1494. Monobilliards 15 Dec 2007 00:59 Oh, I found my mistake and got AC. It's also good test: 7 1645327 Cheater Edited by author 15.12.2007 00:59 blondi12 Re: Help plz. WA on test 10 [1] // Problem 1494. Monobilliards 14 Apr 2021 20:00 Passed all tests, but WA10. Did anyone know what test 10 is? Name-must-be-given-in-English Re: Help plz. WA on test 10 // Problem 1494. Monobilliards 7 Apr 2022 19:32 Same problem here. All these tests passed, but still WA10. .-. It appears no one knows what the test is. Nebojsa Re: Help plz. WA on test 10 [2] // Problem 1494. Monobilliards 2 May 2008 03:07 Can you explain this test 6 435261 Not a proof mYst Re: Help plz. WA on test 10 [1] // Problem 1494. Monobilliards 3 May 2008 01:31 Nebojsa wrote 2 May 2008 03:07 Can you explain this test I don't get this one neither...6 435261 Not a proof sylap Re: Help plz. WA on test 10 // Problem 1494. Monobilliards 3 Oct 2013 22:48 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". Danlo Test #11 [1] // Problem 1494. Monobilliards 5 Jan 2015 14:02 If you get WA on test #11, try this test: 4 1 3 4 2 Not a proof thanhtrung24 Re: Test #11 // Problem 1494. Monobilliards 23 Mar 2022 23:50 Thanks man, I appreciate it Oleg Strekalovsky [Vologda SPU] Some tests for... :-) [3] // Problem 1494. Monobilliards 18 Mar 2009 19:23 5 2 4 3 1 5 Not a proof 5 2 4 1 3 5 Cheater MAK Re: Some tests for... :-) // Problem 1494. Monobilliards 11 May 2010 17:11 Thank you very much! Abhirath Re: Some tests for... :-) // Problem 1494. Monobilliards 29 Dec 2016 08:07 I thought he could only come in the end. Thanks :) Vitalii Re: Some tests for... :-) // Problem 1494. Monobilliards 20 Sep 2021 14:03 Удалил сообщение, т.к. понял свою ошибку. Edited by author 20.09.2021 14:14 ajay jadhav Key hint // Problem 1494. Monobilliards 5 May 2020 23:55 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 Mewtwo WA 23 .... wth is this. -_- [4] // Problem 1494. Monobilliards 3 Apr 2016 23:34 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... Jane Soboleva (SumNU) Re: WA 23 .... wth is this. -_- [3] // Problem 1494. Monobilliards 3 Apr 2016 23:55 I used to have WA23, but then i looked through discussions and saw this http://acm.timus.ru/forum/thread.aspx?id=22907&upd=634542935571668865 Process modelling is really the best thing here imo, so i advise to go with it. Mewtwo Re: WA 23 .... wth is this. -_- [2] // Problem 1494. Monobilliards 4 Apr 2016 00:43 Jane Soboleva (SumNU) wrote 3 April 2016 23:55 I used to have WA23, but then i looked through discussions and saw this http://acm.timus.ru/forum/thread.aspx?id=22907&upd=634542935571668865 Process modelling is really the best thing here imo, so i advise to go with it. 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... :) Jane Soboleva (SumNU) Re: WA 23 .... wth is this. -_- [1] // Problem 1494. Monobilliards 4 Apr 2016 00:50 «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~ Ealham Re: WA 23 .... wth is this. -_- // Problem 1494. Monobilliards 24 Feb 2019 01:32 Thanks a lot... Got AC. Otabek Toshkanov hint and test [2] // Problem 1494. Monobilliards 2 May 2018 16:36 I used DSU algorithm and AC 0.046. test: 10 4 5 3 6 9 10 8 7 2 1 answer: Not a proof. CoubeX Re: hint and test // Problem 1494. Monobilliards 27 Oct 2018 01:25 good test tho I used stack & queue and got AC Ealham Re: hint and test // Problem 1494. Monobilliards 24 Feb 2019 01:31 Otabek Toshkanov wrote 2 May 2018 16:36 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 Есть ли неточность в условии ? // Problem 1494. Monobilliards 27 Nov 2018 00:08 А вот эта фраза "Пока господин Чичиков играл, ревизор несколько раз подходил к столу и забирал из лузы последний закатившийся туда шар" может быть понята двояко. Либо буквально "последний закатившийся", и тогда после изъятия последнего закатившегося шара нельзя брать ещё, пока не появится следующий последний закатившийся (то есть до следующего забитого шара: потому что последний уже взят, и следующий шар в лузе - предпоследний закатившийся), либо имеется в виду просто верхний, который может быть последним из оставшихся неизъятыми, а не буквально "последним закатившимся". Так что же имеется в виду авторами задачи и, главное, тестов к ней ? Это важно, потому что я читал эту фразу буквально, а при таком прочтении обязательное условие относительно шаров, изъятых до конца игры - то, что они должны идти по возрастанию. В случае второго варианта этого условия нет. Я-то привык всегда понимать задание буквально, считая, что авторы задания чётко понимают смысл своих слов. cs_Diablo TLE test 28. Why this code is slow ? [2] // Problem 1494. Monobilliards 22 Dec 2011 16:54 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 ? cs_Diablo Re: TLE test 28. Why this code is slow ? [1] // Problem 1494. Monobilliards 22 Dec 2011 16:58 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]) Hexter Re: TLE test 28. Why this code is slow ? // Problem 1494. Monobilliards 12 May 2018 10:00 I tried this test, but there is TL. In VS this test takes less then 40 ms. What's this test 28? DarkSun1997 Пара тестов [6] // Problem 1494. Monobilliards 18 Jul 2017 18:04 Есть наверно несколько решений этой задачи. Я использовал стек пар. 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 Mahilewets Re: Пара тестов [5] // Problem 1494. Monobilliards 18 Jul 2017 20:48 Да это адская задача, я уже решаю года полтора безуспешно Решение не пытаюсь посмотреть принципиально Ничего не помогает решить Oleg Baskakov Re: Пара тестов [4] // Problem 1494. Monobilliards 19 Jul 2017 02:56 Ничего тут сложного нет, просто симулируем сам процесс закатывания. Разберём например тест 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. Mahilewets Re: Пара тестов [3] // Problem 1494. Monobilliards 19 Jul 2017 08:45 Ну я не смотрю решений. Сам додуматься не могу. Я хочу как-нибудь ссимулировать. Не могу придумать, как это сделать. Лучше скажите мне, что решить, какие задачи, которые бы меня подготовили к решению этой. Oleg Baskakov Re: Пара тестов [2] // Problem 1494. Monobilliards 19 Jul 2017 10:29 Да тот же 1220 stacks, который вы недавно пытались решать. Разница лишь в следующем: — там много стаков, а тут один — тут только pop-запросы — pop-запрос, который больше всех предыдущих, автоматически означает, что перед ним надо допушить недостающие шары. Mahilewets Re: Пара тестов [1] // Problem 1494. Monobilliards 19 Jul 2017 11:28 Ну я сделал двусвязный список в статическом массиве И проверял всегда ли верно Что я беру либо непосредственно следующий шар из оставшихся Либо любой шар выше Oleg Baskakov Re: Пара тестов // Problem 1494. Monobilliards 19 Jul 2017 12:07 Поздравляю с AC :) P. S. Двусвязный список, кстати, не обязателен, я делал просто массив, и у меня была переменная для текущего размера массива, и если удаляем элемент, то я просто её уменьшал, а если добавляем, то увеличивал и менял элемент на новый. Edited by author 19.07.2017 12:11 Fyodor Menshikov Add test please [1] // Problem 1494. Monobilliards 23 Nov 2012 10:59 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 Inventive Re: Add test please // Problem 1494. Monobilliards 21 Jun 2016 11:34 it is "Cheater" Auslender WA#8 // Problem 1494. Monobilliards 28 Aug 2015 18:00 have no idea what this test may be arrammis ACCEPT 0.015sec ! // Problem 1494. Monobilliards 13 Jun 2015 17:11 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 :) Dewang Sultania WA#12 // Problem 1494. Monobilliards 19 May 2015 18:03 Can someone tell what test case 12 is?? Arseniy foe those who ask which data xstructure u need to solve it [1] // Problem 1494. Monobilliards 25 Feb 2014 01:51 You need set. Think how to use it here Otrebus Re: foe those who ask which data xstructure u need to solve it // Problem 1494. Monobilliards 29 Jan 2015 20:01 No, you don't need a set. Any simple linear data structure will do. Alibi Which STL to use? // Problem 1494. Monobilliards 21 Jan 2015 10:46 In this task you can use stack!!!! Alexey Dergunov [Samara SAU] Data structures? [1] // Problem 1494. Monobilliards 8 Jul 2012 15:44 Why is it tagged as 'data structures'? I used only one array to store the input. Edited by author 08.07.2012 15:47 Andrew Sboev Re: Data structures? // Problem 1494. Monobilliards 8 Jul 2012 16:49 It means to use stack :) Smilodon_am Fast algo - modelling works!!! [2] // Problem 1494. Monobilliards 1 Aug 2009 15:23 My AC program uses algorithm with process modelling. It's complexity is O(N) in memory and time. Elisabeth Re: Fast algo - modelling works!!! [1] // Problem 1494. Monobilliards 1 Aug 2009 17:53 Yes, this is the best algo. I use this too. S.77 Just scratch the process on a paper sheet // Problem 1494. Monobilliards 15 Oct 2011 16:39 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 KALO What is test 22? // Problem 1494. Monobilliards 8 Oct 2010 02:04 I've got AC (but only with dirty cheatings). Edited by author 21.10.2010 03:31 Hanzbrow (TNU) KCC hint // Problem 1494. Monobilliards 1 Aug 2009 23:01 it is easy) use stack and a little thinking:)
|