Codeforces Round 148 (Div. 1)

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
238 Codeforces Round 148 (Div. 1) FINISHED False 7200 385653597 Nov. 4, 2012, 4 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 2056 ) A Not Wool Sequences PROGRAMMING constructive algorithms math 1700

B'A sequence of non-negative integers a1, xe2 x80 x89a2, xe2 x80 x89..., xe2 x80 x89an of length n is called a wool sequence if and only if there exists two integers l and r (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89l xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89r xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n) such that . In other words each wool sequence contains a subsequence of consecutive elements with xor equal to 0. The expression means applying the operation of a bitwise xor to numbers x and y. The given operation exists in all modern programming languages, for example, in languages C++ and Java it is marked as "^", in Pascal -- as "xor". In this problem you are asked to compute the number of sequences made of n integers from 0 to 2m xe2 x80 x89- xe2 x80 x891 that are not a wool sequence. You should print this number modulo 1000000009 (109 xe2 x80 x89+ xe2 x80 x899). The only line of input contains two space-separated integers n and m (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n, xe2 x80 x89m xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89105). Print the required number of sequences modulo 1000000009 (109 xe2 x80 x89+ xe2 x80 x899) on the only line of output. Sequences of length 3 made of integers 0, 1, 2 and 3 that are not a wool sequence are (1, 3, 1), (1, 2, 1), (2, 1, 2), (2, 3, 2), (3, 1, 3) and (3, 2, 3).'...

Tutorials

Editorial for Codeforces Round #148

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
3127778 Mosyagin A Feb. 14, 2013, 10:27 a.m. OK Delphi TESTS 43 46 102400 1700
2508157 Misha100896 A Nov. 4, 2012, 7:59 p.m. OK Delphi TESTS 43 62 0 1700
2498053 tourist A Nov. 4, 2012, 4:03 p.m. OK Delphi TESTS 43 62 0 1700
2508190 AleksanderBalobanov A Nov. 4, 2012, 8:08 p.m. OK Delphi TESTS 43 62 102400 1700
2502288 KaiZeR A Nov. 4, 2012, 5:03 p.m. OK Delphi TESTS 43 62 102400 1700
2505332 ruban A Nov. 4, 2012, 6:59 p.m. OK Delphi TESTS 43 78 0 1700
4165750 Omelianenko A July 25, 2013, 8:52 p.m. OK FPC TESTS 43 15 0 1700
2863820 vlad107 A Jan. 1, 2013, 2:13 p.m. OK FPC TESTS 43 15 0 1700
5605921 Wolfik A Jan. 2, 2014, 5:04 p.m. OK FPC TESTS 43 30 0 1700
4271553 tsunayoshi A Aug. 13, 2013, 3:12 a.m. OK FPC TESTS 43 30 0 1700
4210742 Nik_Storm_2010 A July 31, 2013, 7:38 p.m. OK FPC TESTS 43 30 0 1700
3111220 leha_raketa96 A Feb. 13, 2013, 10:57 a.m. OK FPC TESTS 43 31 0 1700
2553828 JustN A Nov. 13, 2012, 4:56 p.m. OK FPC TESTS 43 31 0 1700
2509296 nhandi A Nov. 5, 2012, 5:15 a.m. OK FPC TESTS 43 31 0 1700
2501622 Oryshych A Nov. 4, 2012, 4:48 p.m. OK FPC TESTS 43 31 0 1700
2500406 Furko A Nov. 4, 2012, 4:25 p.m. OK FPC TESTS 43 31 0 1700
3180149 cpy A Feb. 24, 2013, 12:51 p.m. OK GNU C TESTS 43 15 0 1700
2909257 kira A Jan. 12, 2013, 6:32 p.m. OK GNU C TESTS 43 15 0 1700
9729357 Luqman A Feb. 5, 2015, 4:01 p.m. OK GNU C TESTS 43 30 0 1700
2566234 duoluo123 A Nov. 16, 2012, 8:10 a.m. OK GNU C TESTS 43 31 0 1700
2525046 pedja A Nov. 8, 2012, 11:55 p.m. OK GNU C TESTS 43 31 0 1700
4140000 monajem A July 23, 2013, 9:49 a.m. OK GNU C++ TESTS 43 15 0 1700
4128004 Karoluch A July 21, 2013, 9:14 a.m. OK GNU C++ TESTS 43 15 0 1700
4083026 CSUvjudge1 A July 17, 2013, 12:50 a.m. OK GNU C++ TESTS 43 15 0 1700
4083018 csuchenan A July 17, 2013, 12:49 a.m. OK GNU C++ TESTS 43 15 0 1700
4070164 KrK A July 14, 2013, 2:33 p.m. OK GNU C++ TESTS 43 15 0 1700
4055208 iscsi A July 12, 2013, 1:55 p.m. OK GNU C++ TESTS 43 15 0 1700
4039133 kzr.buet08 A July 8, 2013, 1:57 p.m. OK GNU C++ TESTS 43 15 0 1700
3961280 niyaznigmatul A June 25, 2013, 6:38 p.m. OK GNU C++ TESTS 43 15 0 1700
3956334 wangshufeng A June 24, 2013, 4:03 p.m. OK GNU C++ TESTS 43 15 0 1700
3956332 vjudge3 A June 24, 2013, 4:03 p.m. OK GNU C++ TESTS 43 15 0 1700
4913736 harhrayr A Oct. 27, 2013, 2:41 p.m. OK GNU C++0x TESTS 43 15 0 1700
3956434 A_Le_K A June 24, 2013, 4:33 p.m. OK GNU C++0x TESTS 43 15 0 1700
3285810 ishikado A March 10, 2013, 7:46 p.m. OK GNU C++0x TESTS 43 15 0 1700
3229788 EarlOfDitches A March 2, 2013, 11:34 a.m. OK GNU C++0x TESTS 43 15 0 1700
2851008 ArkChar A Dec. 29, 2012, 2:42 a.m. OK GNU C++0x TESTS 43 15 0 1700
9219336 suchir A Dec. 21, 2014, 9:33 p.m. OK GNU C++0x TESTS 43 30 0 1700
7366077 PraveenDhinwa A Aug. 7, 2014, 9:42 a.m. OK GNU C++0x TESTS 43 30 0 1700
7243862 suchir A July 25, 2014, 4:12 p.m. OK GNU C++0x TESTS 43 30 0 1700
6415204 johnchen902 A April 19, 2014, 5:14 a.m. OK GNU C++0x TESTS 43 30 0 1700
5191290 2011330300713 A Nov. 22, 2013, 11:14 a.m. OK GNU C++0x TESTS 43 30 0 1700
27326934 dragonslayerintraining A May 24, 2017, 10:44 p.m. OK GNU C++11 TESTS 43 30 0 1700
22718283 Melnyk A Dec. 5, 2016, 7:21 p.m. OK GNU C++11 TESTS 43 30 0 1700
20746948 aka.Sohieb A Sept. 19, 2016, 3:10 a.m. OK GNU C++11 TESTS 43 30 0 1700
20634019 vjudge1 A Sept. 15, 2016, 7:24 a.m. OK GNU C++11 TESTS 43 30 0 1700
19228848 darry140 A July 19, 2016, 9:40 a.m. OK GNU C++11 TESTS 43 30 0 1700
18887803 Tibixb A July 4, 2016, 6:36 p.m. OK GNU C++11 TESTS 43 30 0 1700
18831769 Trumen A June 30, 2016, 11 p.m. OK GNU C++11 TESTS 43 30 0 1700
18779573 TheNewStart A June 29, 2016, 8:17 a.m. OK GNU C++11 TESTS 43 30 0 1700
17036422 .888 A March 30, 2016, 3:07 p.m. OK GNU C++11 TESTS 43 30 0 1700
16350564 .tx A Feb. 26, 2016, 4:45 p.m. OK GNU C++11 TESTS 43 30 0 1700
31784238 shyamkb A Oct. 27, 2017, 5:49 a.m. OK GNU C++14 TESTS 43 30 0 1700
30908617 waynetuinfor A Oct. 1, 2017, 12:28 p.m. OK GNU C++14 TESTS 43 30 0 1700
30621069 Minnakhmetov A Sept. 22, 2017, 4:56 p.m. OK GNU C++14 TESTS 43 30 0 1700
30388032 Heart_Blue A Sept. 16, 2017, 4:22 p.m. OK GNU C++14 TESTS 43 30 0 1700
30332140 LiChenKoh A Sept. 14, 2017, 3:29 p.m. OK GNU C++14 TESTS 43 30 0 1700
29544791 Shalchian A Aug. 18, 2017, 6:43 a.m. OK GNU C++14 TESTS 43 30 0 1700
29527475 nima10khodaveisi A Aug. 17, 2017, 1:41 p.m. OK GNU C++14 TESTS 43 30 0 1700
22136866 lnzva A Nov. 9, 2016, 6:19 p.m. OK GNU C++14 TESTS 43 30 0 1700
20643695 totsamyzed A Sept. 15, 2016, 4:04 p.m. OK GNU C++14 TESTS 43 30 0 1700
22853698 aman_soni72 A Dec. 10, 2016, 11:26 a.m. OK GNU C++14 TESTS 43 30 102400 1700
52291149 Nakagawa.Kanon A April 4, 2019, 1:50 a.m. OK GNU C++17 TESTS 43 30 0 1700
67873408 -____- A Dec. 29, 2019, 12:22 p.m. OK GNU C++17 TESTS 43 60 0 1700
58532069 Test2311 A Aug. 10, 2019, 10 a.m. OK GNU C++17 TESTS 43 60 0 1700
38905055 alidadar7676 A June 2, 2018, 11:14 p.m. OK GNU C++17 TESTS 43 60 3379200 1700
69521099 kunj017 A Jan. 25, 2020, 1:28 p.m. OK GNU C++17 TESTS 43 60 7987200 1700
68118336 tnakao A Jan. 3, 2020, 12:20 p.m. OK GNU C++17 TESTS 43 62 0 1700
62104458 sorcerer48 A Oct. 8, 2019, 10:17 a.m. OK GNU C++17 TESTS 43 62 0 1700
61764559 sammithkanur A Oct. 3, 2019, 8:11 a.m. OK GNU C++17 TESTS 43 62 0 1700
60849142 NotGivingUp A Sept. 19, 2019, 1:29 p.m. OK GNU C++17 TESTS 43 62 0 1700
60476339 kopok2 A Sept. 13, 2019, 8:20 a.m. OK GNU C++17 TESTS 43 62 0 1700
2505299 cojna A Nov. 4, 2012, 6:56 p.m. OK Haskell TESTS 43 46 0 1700
2552539 mukku A Nov. 13, 2012, 11:59 a.m. OK Java 6 TESTS 43 78 0 1700
2551429 Azat_Yusupov A Nov. 13, 2012, 10:38 a.m. OK Java 6 TESTS 43 78 0 1700
2501058 piotr.kukla A Nov. 4, 2012, 4:37 p.m. OK Java 6 TESTS 43 78 0 1700
2500369 sweiss A Nov. 4, 2012, 4:24 p.m. OK Java 6 TESTS 43 78 0 1700
2500235 mdldml A Nov. 4, 2012, 4:22 p.m. OK Java 6 TESTS 43 78 0 1700
2498316 ysyshtc A Nov. 4, 2012, 4:05 p.m. OK Java 6 TESTS 43 78 0 1700
3150754 jmoreira A Feb. 20, 2013, 2:36 p.m. OK Java 6 TESTS 43 93 0 1700
3013501 svm11 A Jan. 26, 2013, 5:20 p.m. OK Java 6 TESTS 43 93 0 1700
2560481 luckman A Nov. 14, 2012, 6:43 p.m. OK Java 6 TESTS 43 93 0 1700
2508709 SkorKNURE A Nov. 5, 2012, 12:59 a.m. OK Java 6 TESTS 43 93 0 1700
2505163 PlayLikeNeverB4 A Nov. 4, 2012, 6:46 p.m. OK Java 7 TESTS 43 78 0 1700
2499518 Jokser A Nov. 4, 2012, 4:14 p.m. OK Java 7 TESTS 43 78 0 1700
2532821 trunghieu11 A Nov. 11, 2012, 9:54 a.m. OK Java 7 TESTS 43 93 0 1700
2505189 gridnevvvit A Nov. 4, 2012, 6:48 p.m. OK Java 7 TESTS 43 93 0 1700
2504120 jjd5 A Nov. 4, 2012, 5:47 p.m. OK Java 7 TESTS 43 93 0 1700
2500632 S.Yesipenko A Nov. 4, 2012, 4:29 p.m. OK Java 7 TESTS 43 93 0 1700
2500223 ant.ermilov A Nov. 4, 2012, 4:22 p.m. OK Java 7 TESTS 43 93 0 1700
2499625 pyshnograev A Nov. 4, 2012, 4:15 p.m. OK Java 7 TESTS 43 93 0 1700
2499473 antonkov A Nov. 4, 2012, 4:14 p.m. OK Java 7 TESTS 43 93 0 1700
2499306 nitegazer A Nov. 4, 2012, 4:13 p.m. OK Java 7 TESTS 43 93 0 1700
25327521 pitfall A March 7, 2017, 6:36 p.m. OK Java 8 TESTS 43 218 20582400 1700
28544947 tomdmitriev A July 14, 2017, 10:03 a.m. OK Java 8 TESTS 43 248 20582400 1700
11965128 hsnprsd A July 7, 2015, 10:18 p.m. OK Java 8 TESTS 43 278 0 1700
37475473 barakraganosungam A April 20, 2018, 1:35 a.m. OK Java 8 TESTS 43 278 20684800 1700
44707981 Anonymous A Oct. 22, 2018, 5:35 p.m. OK Java 8 TESTS 43 280 0 1700
40210421 KulikAlex A July 11, 2018, 6:56 p.m. OK Java 8 TESTS 43 280 0 1700
9403923 AStepanov A Jan. 11, 2015, 3:43 p.m. OK Java 8 TESTS 43 310 0 1700
42528292 mohit8055kumar A Sept. 5, 2018, 7:44 p.m. OK Java 8 TESTS 43 312 0 1700
38469601 Makhatayeva A May 20, 2018, 9:05 p.m. OK Java 8 TESTS 43 312 0 1700
42528375 mohit8055kumar A Sept. 5, 2018, 7:49 p.m. OK Java 8 TESTS 43 342 0 1700
2499108 it4.kp A Nov. 4, 2012, 4:11 p.m. OK Mono C# TESTS 43 125 1843200 1700
2499045 fiver A Nov. 4, 2012, 4:10 p.m. OK Mono C# TESTS 43 140 11776000 1700
16637811 og.kostya A March 10, 2016, 6:09 p.m. OK MS C# TESTS 43 154 102400 1700
3503456 mopodao A April 11, 2013, 12:13 p.m. OK MS C++ TESTS 43 15 0 1700
2880676 Gideon_Reivenor A Jan. 7, 2013, 2:11 p.m. OK MS C++ TESTS 43 15 0 1700
2880619 Gideon_Reivenor A Jan. 7, 2013, 1:50 p.m. OK MS C++ TESTS 43 15 0 1700
3066851 pencil_man A Feb. 3, 2013, 11:19 a.m. OK MS C++ TESTS 43 15 0 1700
2865281 tomriddle A Jan. 2, 2013, 5:03 a.m. OK MS C++ TESTS 43 15 819200 1700
5852373 k1nval A Jan. 30, 2014, 9:34 p.m. OK MS C++ TESTS 43 30 0 1700
9391076 Rostislav_the_great A Jan. 9, 2015, 10:31 a.m. OK MS C++ TESTS 43 30 0 1700
4480916 Awa149 A Sept. 16, 2013, 1:50 a.m. OK MS C++ TESTS 43 30 0 1700
2748300 Olja A Dec. 10, 2012, 4:26 p.m. OK MS C++ TESTS 43 31 0 1700
2748302 Erop A Dec. 10, 2012, 4:28 p.m. OK MS C++ TESTS 43 31 0 1700
51823046 ashok123 A March 25, 2019, 12:55 p.m. OK PyPy 2 TESTS 43 248 204800 1700
3726630 lyrics A May 16, 2013, 9:59 a.m. OK Python 2 TESTS 43 93 0 1700
3883370 vjudge1 A June 14, 2013, 1:54 p.m. OK Python 2 TESTS 43 93 0 1700
3138788 m1_k3 A Feb. 17, 2013, 9:11 a.m. OK Python 2 TESTS 43 93 0 1700
3883423 vjudge5 A June 14, 2013, 2:13 p.m. OK Python 2 TESTS 43 109 0 1700
3138765 m1_k3 A Feb. 17, 2013, 9:05 a.m. OK Python 2 TESTS 43 109 0 1700
2977626 laurion A Jan. 21, 2013, 9:59 a.m. OK Python 2 TESTS 43 109 0 1700
2787690 ghafi007 A Dec. 17, 2012, 2:47 p.m. OK Python 2 TESTS 43 124 1638400 1700
2517049 dut200901102 A Nov. 7, 2012, 6:04 a.m. OK Python 2 TESTS 43 125 0 1700
2509754 abc_1988_1106 A Nov. 5, 2012, 7:45 a.m. OK Python 2 TESTS 43 125 0 1700
2629885 cxianliang A Nov. 23, 2012, 3:49 a.m. OK Python 2 TESTS 43 125 1638400 1700
6614868 yugle7 A May 14, 2014, 12:04 p.m. OK Python 3 TESTS 43 216 0 1700
22063671 Amores A Nov. 5, 2016, 7:23 p.m. OK Python 3 TESTS 43 218 0 1700
7364276 TsunamiNoLetGo A Aug. 7, 2014, 1:55 a.m. OK Python 3 TESTS 43 248 0 1700
41983586 Mk_Python_v1 A Aug. 23, 2018, 4:07 a.m. OK Python 3 TESTS 43 312 0 1700
2567688 PaulRS A Nov. 16, 2012, 3:20 p.m. OK Ruby TESTS 43 203 0 1700
2996869 ixxa A Jan. 23, 2013, 12:11 p.m. OK Scala TESTS 43 343 102400 1700

remove filters

Back to search problems