Codeforces Round 171 (Div. 2)

Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
279 Codeforces Round 171 (Div. 2) FINISHED False 7200 369412199 March 4, 2013, 3:30 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 1449 ) E Beautiful Decomposition PROGRAMMING dp games greedy number theory 2100

B'Valera considers a number beautiful, if it equals 2k or -2k for some integer k (k xe2 x80 x89 xe2 x89 xa5 xe2 x80 x890). Recently, the math teacher asked Valera to represent number n as the sum of beautiful numbers. As Valera is really greedy, he wants to complete the task using as few beautiful numbers as possible. Help Valera and find, how many numbers he is going to need. In other words, if you look at all decompositions of the number n into beautiful summands, you need to find the size of the decomposition which has the fewest summands. The first line contains string s (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89|s| xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89106), that is the binary representation of number n without leading zeroes (n xe2 x80 x89> xe2 x80 x890). Print a single integer -- the minimum amount of beautiful numbers that give a total of n. In the first sample n xe2 x80 x89= xe2 x80 x892 is a beautiful number. In the second sample n xe2 x80 x89= xe2 x80 x897 and Valera can decompose it into sum 23 xe2 x80 x89+ xe2 x80 x89( xe2 x80 x89- xe2 x80 x8920). In the third sample n xe2 x80 x89= xe2 x80 x89109 can be decomposed into the sum of four summands as follows: 27 xe2 x80 x89+ xe2 x80 x89( xe2 x80 x89- xe2 x80 x8924) xe2 x80 x89+ xe2 x80 x89( xe2 x80 x89- xe2 x80 x8922) xe2 x80 x89+ xe2 x80 x8920.'...

Tutorials

Codeforces Round #171 (Div. 2) Разбор Задач

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
41247943 TShT E Aug. 5, 2018, 2:15 p.m. OK FPC TESTS 60 92 12492800 2100
37290246 rainboy E April 13, 2018, 3:49 p.m. OK GNU C TESTS 60 92 4300800 2100
26881792 vjudge2 E May 5, 2017, 1:37 p.m. OK GNU C++ TESTS 60 60 1024000 2100
20439340 duongkhoaitay E Sept. 7, 2016, 2:52 p.m. OK GNU C++ TESTS 60 60 2048000 2100
35443527 Scut82 E Feb. 18, 2018, 10:54 a.m. OK GNU C++ TESTS 60 60 4096000 2100
38317277 Scut82 E May 16, 2018, 10:37 a.m. OK GNU C++ TESTS 60 62 4812800 2100
38315964 Scut82 E May 16, 2018, 9:46 a.m. OK GNU C++ TESTS 60 62 12595200 2100
26819843 vjudge5 E May 3, 2017, 1:41 p.m. OK GNU C++ TESTS 60 62 14950400 2100
26818834 vjudge3 E May 3, 2017, 12:43 p.m. OK GNU C++ TESTS 60 62 14950400 2100
40990146 ReaLNero1 E July 30, 2018, 11:38 p.m. OK GNU C++ TESTS 60 92 9011200 2100
38318758 Scut82 E May 16, 2018, 11:28 a.m. OK GNU C++ TESTS 60 92 9318400 2100
28413442 yura08 E July 10, 2017, 6:20 p.m. OK GNU C++ TESTS 60 92 44236800 2100
21112828 dreamplay E Oct. 2, 2016, 11:17 a.m. OK GNU C++11 TESTS 60 30 2048000 2100
26925875 Shayan E May 7, 2017, 2:57 p.m. OK GNU C++11 TESTS 60 30 10137600 2100
25097931 sajibreadd E Feb. 28, 2017, 10:34 a.m. OK GNU C++11 TESTS 60 60 3174400 2100
26925942 Shayan E May 7, 2017, 3:02 p.m. OK GNU C++11 TESTS 60 60 10137600 2100
21788622 OmarHashim E Oct. 26, 2016, 7:11 a.m. OK GNU C++11 TESTS 60 62 1024000 2100
19592512 kfoozminus E Aug. 3, 2016, 6:52 a.m. OK GNU C++11 TESTS 60 62 1024000 2100
65795831 handlip E Nov. 27, 2019, 4:32 a.m. OK GNU C++11 TESTS 60 62 1024000 2100
68157232 YHHxBULIATANIA E Jan. 4, 2020, 9:24 a.m. OK GNU C++11 TESTS 60 62 1024000 2100
39667528 LODB---D E June 26, 2018, 6:43 a.m. OK GNU C++11 TESTS 60 62 2048000 2100
19604294 tahsynx E Aug. 3, 2016, 7:14 p.m. OK GNU C++11 TESTS 60 62 2048000 2100
30881099 wp32pw E Sept. 30, 2017, 6:46 p.m. OK GNU C++14 TESTS 60 60 1024000 2100
21401442 Arpa E Oct. 13, 2016, 11:20 a.m. OK GNU C++14 TESTS 60 60 4505600 2100
23168094 McGinn E Dec. 20, 2016, 2:44 a.m. OK GNU C++14 TESTS 60 60 6963200 2100
25557816 step_by_step E March 16, 2017, 6:34 p.m. OK GNU C++14 TESTS 60 60 7475200 2100
24608188 satishrdd E Feb. 12, 2017, 12:15 p.m. OK GNU C++14 TESTS 60 60 11468800 2100
25554392 wrinx E March 16, 2017, 4:01 p.m. OK GNU C++14 TESTS 60 60 12083200 2100
44950354 Muhammad.Magdi E Oct. 27, 2018, 11:49 a.m. OK GNU C++14 TESTS 60 62 1024000 2100
59874273 No_CodeNoLifeSyy E Sept. 1, 2019, 9:33 p.m. OK GNU C++14 TESTS 60 62 2048000 2100
57891532 TopGun__ E July 28, 2019, 12:01 p.m. OK GNU C++14 TESTS 60 62 2150400 2100
30577334 nima10khodaveisi E Sept. 21, 2017, 12:32 p.m. OK GNU C++14 TESTS 60 62 2560000 2100
62331551 igba E Oct. 10, 2019, 9:03 p.m. OK GNU C++17 TESTS 60 62 1024000 2100
61935913 k0walsk1 E Oct. 5, 2019, 5:44 p.m. OK GNU C++17 TESTS 60 62 2048000 2100
40510843 arbitrary_A E July 18, 2018, 10:58 a.m. OK GNU C++17 TESTS 60 62 2150400 2100
46247670 HazemEssawi E Nov. 26, 2018, 12:23 p.m. OK GNU C++17 TESTS 60 62 2150400 2100
40521959 sombra99 E July 18, 2018, 5:05 p.m. OK GNU C++17 TESTS 60 62 2150400 2100
49669232 Excogitatoris E Feb. 9, 2019, 3:57 p.m. OK GNU C++17 TESTS 60 62 3276800 2100
45476914 vjudge4 E Nov. 9, 2018, 12:53 p.m. OK GNU C++17 TESTS 60 92 2150400 2100
52029378 Patwari26 E March 30, 2019, 4:46 p.m. OK GNU C++17 TESTS 60 92 2150400 2100
61871123 ivan100sic E Oct. 4, 2019, 6:14 p.m. OK GNU C++17 TESTS 60 92 2150400 2100
54247355 Mohammad-Alsaad E May 16, 2019, 3:28 p.m. OK GNU C++17 TESTS 60 92 2560000 2100
45454973 PrakharJain E Nov. 8, 2018, 6:25 p.m. OK Java 8 TESTS 60 280 0 2100
20461232 Dukkha E Sept. 8, 2016, 3:19 p.m. OK Java 8 TESTS 60 280 2867200 2100
23688044 Ahmad_Elsagheer E Jan. 10, 2017, 9:25 p.m. OK Java 8 TESTS 60 312 26214400 2100
68645246 Hemose E Jan. 12, 2020, 8:51 a.m. OK Java 8 TESTS 60 342 18227200 2100
23687749 Ahmad_Elsagheer E Jan. 10, 2017, 8:48 p.m. OK Java 8 TESTS 60 374 28774400 2100
45173936 Anonymous E Nov. 1, 2018, 1:54 p.m. OK Java 8 TESTS 60 466 3276800 2100
64305197 AvinashKartik E Nov. 5, 2019, 11:16 a.m. OK PyPy 3 TESTS 60 716 36352000 2100
35856427 _____i_____ E March 2, 2018, 8:20 p.m. OK Python 2 TESTS 60 810 7168000 2100
35856300 _____k_____ E March 2, 2018, 8:17 p.m. OK Python 2 TESTS 60 810 7168000 2100
35847605 ______k______ E March 2, 2018, 4:45 p.m. OK Python 2 TESTS 60 810 7168000 2100
35847602 ______h______ E March 2, 2018, 4:45 p.m. OK Python 2 TESTS 60 810 7168000 2100
35857128 ______u______ E March 2, 2018, 8:34 p.m. OK Python 2 TESTS 60 810 7168000 2100
35842821 ______M______ E March 2, 2018, 3 p.m. OK Python 2 TESTS 60 810 7168000 2100
35847235 ______i______ E March 2, 2018, 4:40 p.m. OK Python 2 TESTS 60 810 7168000 2100
35856856 ______n______ E March 2, 2018, 8:28 p.m. OK Python 2 TESTS 60 810 7168000 2100
25833531 mhorst E March 27, 2017, 7:36 a.m. OK Python 2 TESTS 60 934 14336000 2100
25778372 mhorst E March 24, 2017, 4:26 p.m. OK Python 2 TESTS 60 1092 16384000 2100

remove filters

Back to search problems