| ENG RUS | Timus Online Judge |
Общий форумJorjia AC 0.001s !!! // Задача 1618. Arrays Printing 5 окт 2018 14:53 Thx, it's nice problem. Pearl My solution // Задача 1792. Код Хэмминга 4 окт 2018 04:27 First, let give the bits some names, I put them inside the parentheses: Petal 1 (p1) = II (c2) + III (c3) + IV (c4) Petal 2 (p2) = I (c1) + III (c3) + IV (c4) Petal 3 (p3) = I (c1) + II (c2) + IV (c4) As p1, p2 and p3 are created from c1, c2, c3, c4, we check each change in c1, c2, c3, c4: When c1 change: p2 and p3 won't match the value calculated using the formular above (i.e: c1 + c3 + c4 != p2 and c1 + c2 + c4 != p3) When c2 change: p1 and p3 will go wrong When c3 change: p1 and p2 will go wrong As c4 contribute to the value of all three petals, if it is changed then p1, p2 and p3 will all go wrong. In short: Calculate ep1, ep2 and ep3 from the first 4 bits (the e in ep stand for expected), then compare them with the given p1, p2 and p3: All three pairs do not match: c4 is changed p1 and p2 do not match: c3 is changed p1 and p3 do not match: c2 is changed p2 and p3 do not match: c1 is changed Only p1 not match: p1 is changed Only p2 not match: p2 is changed Only p3 not match: p3 is changed ANTON BL1K `~ Solution // Задача 1111. Квадраты 3 окт 2018 20:52 The problem is rather easy, just compare squares due to rationality of numbers Pearl WA#13 // Задача 1224. Спираль 3 окт 2018 16:09 I print 2 * (n - 1) when n <= m and 2 * (m - 1) + 1 when n > m but got WA on test 13. What's wrong with my solution? Oh, I forgot to delete my check for m = 1 (in this case I output 1). This test seem to be 1 1 0 Edited by author 03.10.2018 17:42 Bliss Some hints. // Задача 1839. Ментакулус 2 окт 2018 18:17 You can solve the problem without using floating point calculations. in32 is enough for everything. You also needn't to implement BSTrees or Segment trees here. Using ordered sets is enough. #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef __gnu_pbds::tree< Point, __gnu_pbds::null_type, std::less_equal<>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set_less; typedef __gnu_pbds::tree< Point, __gnu_pbds::null_type, std::greater_equal<>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set_greater; Pearl My solution // Задача 1226. йынтарбО кодяроп 2 окт 2018 14:56 For those looking for a hint: I use stack. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Push the characters into stack, when a non-alphabetic character is read, pop out all the characters in stack and print them before printing the non-alphabetic character. Edited by author 02.10.2018 15:04 🦄Imosk72🦄[GTGU] is it NP problem? // Задача 1649. Абстракционизм в массы 2 окт 2018 10:25 AndriyKozak Please help) [1] // Задача 1877. Велосипедные коды 25 сен 2018 20:43 #include <stdio.h> int main() { char a[3],b[3]; gets(a); gets(b); int x; if (a[3]=='0'||a[3]=='2'||a[3]=='4'||a[3]=='6'||a[3]=='8') x=1; if (b[3]=='1'||b[3]=='3'||b[3]=='5'||b[3]=='7'||b[3]=='9') x=1; if(x==1) printf("yes"); else printf("no"); } Pearl Re: Please help) // Задача 1877. Велосипедные коды 2 окт 2018 10:10 The two codes are just two numbers, think about it this way. If I write more, the solution will be obvious and you will get nothing. D4nick Question about the task Вопрос по условию задачи [1] // Задача 1924. Четыре чертёнка 23 сен 2018 20:53 Do I uderstand it right, that numbers are placed in increasing order, there's nothing said about it??? Правильно понимаю, что числа должны быть в порядке возрастания? Pearl Re: Question about the task Вопрос по условию задачи // Задача 1924. Четыре чертёнка 2 окт 2018 10:04 Yes, they are in ascending order. Edited by author 02.10.2018 10:05 0blivium C++ Hint [1] // Задача 1617. Ползуны 1 окт 2018 21:55 You can solve this problem quickly by using the multiset and set data structures. To find the answer, use the set iterator. Pearl Re: C++ Hint // Задача 1617. Ползуны 2 окт 2018 09:32 My solution is similar: map x to x - 600 and use array to count its frequency. Then accumulate all the freq[x] / 4 and just print the sum. As the diameter is constrained in [600,700], there will be at most 101 different values. Salavat Python2.7 WA#4 what problem, help please? [1] // Задача 2023. Дональд-почтальон 8 авг 2018 19:49 #! /usr/bin/env python # -*- coding: utf-8 -*- from itertools import count mailBox = {"Alice": 1, "Ariel": 1, "Aurora": 1,"Phil": 1, "Peter": 1,"Olaf": 1,"Phoebus": 1, "Ralph": 1, "Robin": 1, "Bambi": 2, "Belle": 2,"Bolt": 2, "Mulan": 2,"Mowgli": 2,"Mickey": 2,"Silver": 2,"Simba": 2,"Stitch": 2, "Dumbo": 3, "Genie": 3,"Jiminy": 3, "Kyzko": 3,"Kida": 3,"Kenai": 3,"Tarzan": 3,"Tiana": 3,"Winnie": 3, } # кол-во писем n = int(raw_input()) # list с именами адресатов inputMailFrom = [] # цикл по заполению адресатов for n in range(n): inputMailFrom.append(mailBox.get(raw_input())) step = [] if len(inputMailFrom) == 1: if inputMailFrom[0] == 1: print (0) if inputMailFrom[0] == 2: print (1) if inputMailFrom[0] == 3: print (2) else: for i in range(n): step.append(abs(inputMailFrom[i]-inputMailFrom[i+1])) print (sum(step) Pearl Re: Python2.7 WA#4 what problem, help please? // Задача 2023. Дональд-почтальон 2 окт 2018 09:27 Try this 2 Tiana Aurora The correct answer is 4. Initially he stands near the leftmost case, but the first letter does not need to be sent to the first case. Александр WA #6 ??? [1] // Задача 2023. Дональд-почтальон 29 авг 2018 12:35 n=int(input()) s1=['Alice','Ariel','Aurora','Phil','Peter','Olaf','Phoebus','Ralph','Robin' ] s2=['Bambi','Belle', 'Bolt','Mulan','Mowgli','Mickey','Silver','Simba','Stitch'] s3=['Dumbo','Genie','Jiminy','Kuzko','Kida','Kenai','Tarzan','Tiana','Winnie'] a=s1 k=0 for i in range(n): s=input() if s in s1: if a==s1: continue elif a==s2: k+=1 a=s1 elif a==s3: k+=2 a=s1 elif s in s2: if a==s1: k+=1 a=s2 elif a==s2: continue elif a==s3: k+=1 a=s2 elif s in s3: if a==s1: k+=2 a=s3 elif a==s2: k+=1 a=s2 elif a==s3: continue print(k) Pearl Re: WA #6 ??? // Задача 2023. Дональд-почтальон 2 окт 2018 09:15 elif s in s3: if a==s1: k+=2 a=s3 elif a==s2: k+=1 a=s2 Wait, doesn't this letter is sent to block s3, why a = s2? Dmitry_Terenichev give tests,please! [2] // Задача 2035. Очередной пробный тур 2 апр 2017 18:33 give me tests,please! all my tests give ok results. i have wa 19. help! MassterMax`~ Re: give tests,please! // Задача 2035. Очередной пробный тур 21 янв 2018 17:15 Edited by author 21.01.2018 17:25 Pearl Re: give tests,please! // Задача 2035. Очередной пробный тур 2 окт 2018 09:11 I got WA 14 and after I fixed the program to handle the first test, it went AC. 5 2 7 5 2 2 5 7 2 5 1000 1000 1 1 0 or 0 1 1 500 5 1 4 or 0 5 2 3 10 Impossible 5 1 5 5 0 or 4 1 2 1 0 0 0 Edited by author 02.10.2018 09:12 Minos Skistonrak abcdefghijklmopqrstuvwxyz [1] // Задача 1723. Книга Сандро 9 апр 2018 10:10 What answer in this case? Pearl Re: abcdefghijklmopqrstuvwxyz // Задача 1723. Книга Сандро 1 окт 2018 19:08 "Output any of the most powerful spells..." Any of them. Kirom `Ekexity [SESC17]💻 Объяснение сути // Задача 1109. Конференция 1 окт 2018 14:08 Нужно убрать максимальное количество ребёр, но чтобы все вершины имели ненулевую степень. IlushaMax why stack so long [1] // Задача 1654. Шифровка 14 апр 2016 01:26 I thought that stack is the best thing in this case but I've seen 0.015 and 0.001 sec . I've got 0.046 Pearl Re: why stack so long // Задача 1654. Шифровка 1 окт 2018 13:38 Maybe it's because of the choice of language. I use C++17 and it run in 0.001s Pearl My solutions // Задача 1196. Экзамен по истории 1 окт 2018 12:45 First method: Use multiple baskets, each basket is a list (in my case, i use vector<int>). Put the date d into the basket numbered d % number_of_baskets. To check the student answer, just pick the basket out and perform binary search. I chose 100 000 as the number of baskets, tried 1 000 000 baskets but it works much worse. Second method: Use vector<bool> (not bool array, the later cost 8 times more) to mark numbers under 300 000 000 (actually the vector size can go up to 500 000 000, but for some unknown reason, this smaller size run faster). Create another vector<int> to store the numbers that can't be marked using the bool vector above. Use binary_search to check for existence. It seem like the IO is bottleneck, I used ios::sync_with_stdio(false) and my program run from ~1.5s to ~0.2s Edited by author 01.10.2018 12:46 Shen Yang can O(n^2/64) fit in 1 sec?? [6] // Задача 1897. Алиса и Боб и строка 27 сен 2018 06:10 seems I have solved memory problem.. but I don't know if bitset can fit in time can O(1e8) fit into 1 sec?? Edited by author 27.09.2018 06:21 Shen Yang Re: can O(n^2/64) fit in 1 sec?? [5] // Задача 1897. Алиса и Боб и строка 27 сен 2018 06:31 memory can be done O(n*sqrt(n)/64) Shen Yang Re: can O(n^2/64) fit in 1 sec?? [4] // Задача 1897. Алиса и Боб и строка 30 сен 2018 07:13 finally I came up with N*LG(N) sol, I nearly spent 4 days on this problem... Shen Yang Re: can O(n^2/64) fit in 1 sec?? // Задача 1897. Алиса и Боб и строка 30 сен 2018 09:12 I think I can optimize it to O(n) suffix array can bedone by sa_is Edited by author 30.09.2018 09:13 solace Re: can O(n^2/64) fit in 1 sec?? [2] // Задача 1897. Алиса и Боб и строка 30 сен 2018 13:15 Hey, I've been spending some time thinking over this problem and I'm really stuck on how to make it work fast enough. I was wondering if you could point me in the direction I should be looking to solve it. What I did first was to write a simple bruteforcer and to just verify that that works. It is of course way to slow to get the answer as the input size grows. My next idea was to create a graph out of the possible solutions and this seems promising, but just the time spent building the graph seems to be to much in itself to get a pass, not to speak of the memory requirements. Right now I've been looking into suffix trees, but I don't really know how they would help me here, it's just the closest data structure to the problem that I could find. I really want to solve this on my own, but right now I don't know what topics to research. Could you give me a hint in what direction I should be looking? Shen Yang Re: can O(n^2/64) fit in 1 sec?? [1] // Задача 1897. Алиса и Боб и строка 30 сен 2018 13:38 My sol involves suffix array and some count tricks. first of all we initialization [i,n-1] [0,i] is losing state, and the substring with same oddity is losing state a different is winning state and count winning state +1 (it is a segment you can use fenwick tree to doit) then we consider to enum the length of longest common substring, and merge the substring with longest common length of this length,if one of them is winning states ,then all of them are winning states. how to merge them: using disjoint set, and how to find winning states we can record substring [x,y] pref[x+y],win[x+y] as previous substring [l,r] with l+r==x+y and find this wining state by differece of odditiy of current substring and pref[x+y]. when merging them delete the node if it is not the root node, (i.e. do it count minus one count the all segments [l,r] l-x==y-r with same oddity if it is win,different if it is lose. fenwick array can do it) and change the count when root node's winning states is update.. btw in fact we can throwout fenwick just using ordinary array and count sum of prefix of the array as number of its winning states. I have heard there is O(N) rmq so this problem can be done in O(n) btw there are many details on implement in my sol so I have spent nearly one week on this problem. maybe there are better sols... Edited by author 30.09.2018 13:46 Edited by author 30.09.2018 14:01 adamant Re: can O(n^2/64) fit in 1 sec?? // Задача 1897. Алиса и Боб и строка 1 окт 2018 00:00 Hi! I'm the author of the problem, feel free to discuss solution with me in hangouts: adamant.pwn@gmail.com, or (preferrably) telegram: @adamant_pwn. If you want to :) zorggish Best tests // Задача 1601. АнтиКАПС 30 сен 2018 19:11 If you got WA, especially if you got WA9 First line is input string, second is answer TEST. TEST? TEST! TEST. Test. Test? Test! Test. ?????????????????????? ?????????????????????? !TEST!TEST! !Test!Test! A A TEST TEST TEST Test test test TEST T TEST Test t test Also try empty input. Edited by author 30.09.2018 19:14 Gulliput Test 8 [2] // Задача 1484. Кинорейтинг 29 сен 2018 21:49 This enchanted test 8: I just can not get through it. Maybe there is just that unrepresentable case of "impossible", the emergence of which, under given conditions, I can not even imagine? Gulliput Re: Test 8 [1] // Задача 1484. Кинорейтинг 29 сен 2018 22:18 I have a feeling that there is still some condition that the author forgot to mention. Most likely, this is the upper limit for the result. Edited by author 29.09.2018 22:19 Gulliput Re: Test 8 // Задача 1484. Кинорейтинг 29 сен 2018 23:57 I do it !
|