| ENG RUS | Timus Online Judge |
Обсуждение задачи 1878. Кубик РубинчикаACSpeed Can anyone explain to me the input ? [1] // Задача 1878. Кубик Рубинчика 24 ноя 2011 14:03 I don't understand how to translate them to the initial state . Tks Yuv Re: Can anyone explain to me the input ? // Задача 1878. Кубик Рубинчика 17 мар 2024 22:20 This is 4 layered Rubics Cube. These layers are situated behind each other (perpendicularly). You can think them as 4 Cards placed behind each other. Also, each layer is transparent. So, color on the second, third or fourth layer can be seen through the first layer. Top View is watching the cube from the first layer. As all the layers are transparent, so we can see the colors of each layer behind it from the first layer. So, from the TOP VIEW you will see a complete cube combining each layer's colors. In the description, the first picture is the 4 layers of the cube. Can you place them behind each other? What will you see if you observe them from the first layer and considering them as transparent? If you see them like below, then bingo you get the idea!! YRYB RRYY GGBB RGBG Here, the first Y and the last B color of the first row are coming from the 4th layer if you see. And so on for the rests. In the given input, let say the color code is like below, 1 - Red 2 - Yellow 3 - Blue 4 - Green. So, the input basically says that what you will see all the layers from the front of the first layer. If you replaced the number with the color, then you will get the exact same cube that is given in the description. (We have already built it above!!) morbidel WA3 [17] // Задача 1878. Кубик Рубинчика 22 окт 2011 16:05 Any hint for WA3? Anil Kishore Re: WA3 [15] // Задача 1878. Кубик Рубинчика 22 окт 2011 16:21 'm stuck with WA5 :( ZARHANE Re: WA3 // Задача 1878. Кубик Рубинчика 22 окт 2011 17:41 I have WA40 ! Strekalovsky Oleg [Vologda SPU #1] Re: WA3 [13] // Задача 1878. Кубик Рубинчика 23 окт 2011 23:43 Anil Kishore писал(a) 22 октября 2011 16:21 'm stuck with WA5 :( Don't forget rotate clockwise and anticlockwise at one step!morbidel Re: WA3 [12] // Задача 1878. Кубик Рубинчика 24 окт 2011 16:20 Yes, rotating just 90 degrees in either directions takes one step. What's the trick here? MOPDOBOPOT (USU) Re: WA3 [11] // Задача 1878. Кубик Рубинчика 25 окт 2011 13:49 This test helped me to overcome WA3: 4 2 2 3 3 1 4 1 3 2 3 1 1 4 4 2 The answer is 4. Because collect '4' needs 5 steps, but collect '1' needs only 4 steps. morbidel Re: WA3 [7] // Задача 1878. Кубик Рубинчика 25 окт 2011 15:15 My answer is 4. I made a classic backtracking which gets WA3 and also a Greedy who also gets WA3, which works as follows: - assume the square is solved with 1 in the upper left corner, compute the orientation of each of the layers (0 if ok, 1 or 3 if with a rotation we reach 1 in the corner, 2 if with 2 rotations). - now try to rotate the layers to achieve the color i in the upper left corner - so for each layer determine the minimal nr. of steps to move the color i from layer j in its correct position - compute the minimal number of moves to reach the solution with color i in upper-left - print the minimum out of those values Edited by author 25.10.2011 15:22 morbidel Re: WA3 [6] // Задача 1878. Кубик Рубинчика 26 окт 2011 00:00 I figured out the test #3, it has T[0][0] = 2, T[0][1] = T[1][0] = 1, T[1][1] = 3, "if (...) while(1);" did the trick. So the whole table I assume is 2 1 2 4 1 3 1 2 3 4 2 4 1 3 4 3 My program outputs 2 as a minimum (rotate layer 4 clockwise with 90, rotate layer 3 anti-clockwise with 90), resulting a solved cube with 1 in its left corner. The judge answer is 3, but I don't understand why. Am I missing something? Edited by author 26.10.2011 00:04 morbidel Re: WA3 // Задача 1878. Кубик Рубинчика 27 окт 2011 01:13 AC at last! The problem in my solution was that I assumed always that the colors were 1-red, 2-yellow, 3-green, 4-blue, but they say that one number is one color so they could be permuted in any way. Edited by author 27.10.2011 01:55 Lucian Ilea Re: WA3 [4] // Задача 1878. Кубик Рубинчика 7 ноя 2011 21:37 My AC program gives 2 as the answer for: 2 1 2 4 1 3 1 2 3 4 2 4 1 3 4 3 Soucup Adrian Re: WA3 [3] // Задача 1878. Кубик Рубинчика 29 июн 2012 20:52 Lucian Ilea писал(a) 7 ноября 2011 21:37 My AC program gives 2 as the answer for: 2 1 2 4 1 3 1 2 3 4 2 4 1 3 4 3 Strange. Mine gives 3. (Also AC). Edited by author 29.06.2012 20:52 Squire [Lviv NU] Re: WA3 // Задача 1878. Кубик Рубинчика 29 авг 2012 23:21 Soucup Adrian писал(a) 29 июня 2012 20:52 Lucian Ilea писал(a) 7 ноября 2011 21:37 My AC program gives 2 as the answer for: 2 1 2 4 1 3 1 2 3 4 2 4 1 3 4 3 Strange. Mine gives 3. (Also AC). Edited by author 29.06.2012 20:52 tepamid Re: WA3 [1] // Задача 1878. Кубик Рубинчика 2 июл 2019 19:32 Mine gives 2 and I got AC for this input: 2 1 2 4 1 3 1 2 3 4 2 4 1 3 4 3 Edited by author 02.07.2019 19:33 maslowmw Re: WA3 // Задача 1878. Кубик Рубинчика 17 май 2020 00:33 But this test incorrect, because always colours order 1-2-3-4 IN this tet 1-2-4-3. My AC solution also gives 3. Squire [Lviv NU] Re: WA3 [2] // Задача 1878. Кубик Рубинчика 29 авг 2012 23:31 MOPDOBOPOT (USU) писал(a) 25 октября 2011 13:49 This test helped me to overcome WA3: You're wrong. The answer is equal for every colour cause you cann't collect only one colour but all the colours together.4 2 2 3 3 1 4 1 3 2 3 1 1 4 4 2 The answer is 4. Because collect '4' needs 5 steps, but collect '1' needs only 4 steps. To collect '4' you must turn left inner square and turn right two outer squares each for 1 time. So we have 3 steps in sum. P. S. Sorry for bad english ( Edited by author 29.08.2012 23:31 Edited by author 29.08.2012 23:31 Edited by author 29.08.2012 23:33 MOPDOBOPOT (USU) Re: WA3 [1] // Задача 1878. Кубик Рубинчика 30 авг 2012 00:09 If we turn squares as you said we will get this situation: 4 3 3 3 4 4 3 2 4 1 2 2 1 1 1 2 Squire [Lviv NU] Re: WA3 // Задача 1878. Кубик Рубинчика 30 авг 2012 01:16 MOPDOBOPOT (USU) писал(a) 30 августа 2012 00:09 If we turn squares as you said we will get this situation: Yes, you're right )))4 3 3 3 4 4 3 2 4 1 2 2 1 1 1 2 We need one more step - turn right the square which includes element table[3][1]. So, the answer is 4. inatial_D Re: WA3 // Задача 1878. Кубик Рубинчика 5 мар 2013 16:55 ac is reached just using 4 elements in inputs. RinchinGaY ez problem c++ accept too easy lolololololllol solved 1 sec // Задача 1878. Кубик Рубинчика 20 мар 2019 19:16 #include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <set> #include <unordered_map> #include <map> #include <string> using namespace std; int main() { vector<vector<int>> v(4, vector<int>(4)); vector<int> col(4); for(int i= 0 ; i < 4; i++) { for(int j = 0; j < 4; j++) { cin >> v[i][j]; if(v[i][j] == 1) { if(((i == 0 || i == 1) && ((j == 0) || (j == 1)))) { col[0]++; } else if((i == 0 || i == 1) && ((j == 2) || (j == 3))) { col[1]++; } else if((i == 2 || i == 3) && (j == 0 || j == 1)) { col[2]++; } else { col[3]++; } } } } cout << min(min(col[1] + col[2] + col[3] + col[3], col[2] + col[0] + col[2] + col[3]), min(col[1] + col[2] + col[0] + col[0], col[0] + col[3] + col[1] + col[1])); } Kirill can anyone explain me how to do it??? // Задача 1878. Кубик Рубинчика 21 фев 2018 15:08 explain me the way of doing it or give a solution Edited by author 21.02.2018 16:21 Filip Franik Tests for WA7 // Задача 1878. Кубик Рубинчика 14 авг 2017 19:48 3 1 2 4 1 3 4 2 4 2 1 3 2 4 3 1 (4) 4 1 2 1 1 4 1 2 4 3 2 3 3 4 3 2 (2) Morteza Balvardi wa #21 // Задача 1878. Кубик Рубинчика 10 мар 2014 18:43 can anybody provide a test case for this error my method is quiet like a brute force but it seems i have forgotten sth Edited by author 10.03.2014 18:44 R. Dubinin WA # 7 // Задача 1878. Кубик Рубинчика 7 авг 2013 17:30 please give me some tests Edited by author 07.08.2013 17:31 Yagudin Ruslan WA 37 // Задача 1878. Кубик Рубинчика 22 окт 2012 10:38 Does correct test? Please give me test. Anatoly AC approach [3] // Задача 1878. Кубик Рубинчика 21 фев 2012 23:11 Brute force algo is just 4^5 actions. So, you can don't think about logical solution :) Andrew Sboev Re: AC approach [2] // Задача 1878. Кубик Рубинчика 30 май 2012 19:46 He-he, I could not understand how to solve it by bruteforce algo, because my bruteforce doesnt't pass some tests :) Logical algo is very simple. Edited by author 02.06.2012 15:45 Soucup Adrian Re: AC approach [1] // Задача 1878. Кубик Рубинчика 29 июн 2012 20:50 Brute force algo can be done in 2^4 steps and works. Andrew Sboev Re: AC approach // Задача 1878. Кубик Рубинчика 30 июн 2012 21:03 Hmm, my logical algo takes also 16 operations. Four iterations of cycle with four operations in each iteration. Edited by author 30.06.2012 21:04
|