| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Страница 2 |
| Graph | zhnzhang61 | 1225. Флаги | 11 янв 2024 07:56 | 1 |
Graph zhnzhang61 11 янв 2024 07:56 n = 1 2 3 4 5
R RW RWR RWRW RWRWR
W WR WRW WRWR WRWRW
RBW RBWR RBWRW
WBR WBRW WBRWR
RWBR RWBRW
WRBW WRBWR
RWRBW
WRWBR
RBWBR
WBRBW
Each column can be derived from:
1. the column on its left + R or W
and
2. the column on its left's left + BR or BW |
| C++ accepted | Evgeny | 1225. Флаги | 31 июл 2023 19:58 | 1 |
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int N = 45;
int M;
cin >> M;
vector <long long> a(N+2);
a[0] = 2, a[1] = 2;
for (int i = 0; i < N; i++)
{
a[i+2] = (a[i+1] + a[i]);
}
//Fibonacci sequence
// F0 = 2;
// F1 = 2;
// Fn = Fn-1 + Fn-2
cout << a[M-1];
return 0;
} |
| In fact it's doubled Fibonacci sequence. Easy game. | Vyacheslav Glushkov | 1225. Флаги | 11 апр 2021 19:39 | 1 |
|
| Страница 1 |
| Why fo N = 6 answer is 16 instead of 14? | IlyaGrebenyuk | 1225. Флаги | 2 мар 2020 14:14 | 2 |
Ya popitalsya perebrat' vse varianti dlya N = 6 i smog naschitat' tolko 14 vot oni:
1. WRWRWR 9. WRWRBW
2. RWRWRW 10. RWRWBR
3. WBRWRW 11. WBRBWR
4. RBWRWR 12. RBWBRW
5. WRBWRW 13. WRBWBR
6. RWBRWR 14. RWBRBW
7. WRWBRW 15. ??????
8. RWRBWR 16. ??????
Kakie dva ya upustil? |
| An explanation why the doubled Fibanucci sequence is suitable here | Ivan Avdonin (Vologda ML) | 1225. Флаги | 11 янв 2018 09:34 | 1 |
Let's define C(k,n) = n!/(k!(n-k)!). Binomial coefficients are widely used in combinatorics. The number of ways you can place something on something is an binomial coefficient. But we can't place the blue stripe on the end of the flag and side by side. It is well-known, that C(0,n) + C(1,n) + ... + C([n/2],[n/2]) = F[n+1] where F[n+1] is (n+1)-th Fibonacci number and [n/2] is integer division [1]. I hope this my small review does not spoil you the solving of the problem. Thank you. [1] https://en.wikipedia.org/wiki/Fibonacci_number (Use in Mathematics) accepted/sended = 13616/35461 Edited by author 11.01.2018 10:21 Edited by author 17.06.2019 01:04 Edited by author 17.06.2019 01:04 |
| Assembler in Pascal | Zinovij | 1225. Флаги | 1 дек 2017 20:47 | 1 |
var
n:Integer;
r:cardinal;
begin
read(n);
asm
xor eax,eax
mov ebx,eax
inc eax
mov esi,eax
mov edi,eax
mov ecx,1 shl 5
@@3:
or ecx,ecx
je @@1
mov eax,ebx
mul eax
mov ebx,eax
mov eax,esi
mul eax
add eax,ebx
mov esi,eax
mov eax,edi
mul eax
add eax,ebx
mov edi,eax
sub eax,esi
mov ebx,eax
test n,ecx
je @@2
add edi,ebx
add ebx,esi
mov esi,edi
sub esi,ebx
@@2:
shr ecx,1
jmp @@3
@@1:
mov eax,ebx
shl eax,1
mov r,eax
end;
write(r);
end. |
| I understand myself. Here is explaining | IlushaMax | 1225. Флаги | 12 мар 2016 16:59 | 1 |
Let W is WHITE, R is RED, B is BLUE
So for n=1:
f(n)=2
W or R;
for n=2:
f(n)=2 too
WR or RW;
And now the most interesting:
for n=3:
f(n)=
We add to combinations of n-1 W or R: WRW or RWR;
+
We add to combinations of n-2 RB or WB: RBW or WBR;
=f(n-1)+f(n-2);
So you can check it for n=4 and n=5///It's really easy |
| Is it possible to mathematically prove that it is necessary to use the Fibonacci numbers | IlushaMax | 1225. Флаги | 11 янв 2018 09:50 | 2 |
I mean not just to see on examples and find a pattern |
| How to solve it ? | prostack | 1225. Флаги | 6 фев 2014 19:38 | 3 |
I'm newby here and I didn't solve this kind of tasks before.
I know, that must be very easy, give me please some pieces of advice to solve it. Think abstractly! It's very easy!
Edited by author 06.02.2014 05:58
Edited by author 06.02.2014 05:58 You can either take it the mathematical way, and solve it by induction: assume you know the number of ways for 1..N stripes, how to find out the ways for N+1?
Or you can make a brute-force algorithm (backtracking) that simply counts and prints the number of ways for each N between 1 and 10-20 (until it gets too slow), then try to deduce a general rule for N, based on this series.
Good luck! |
| How to use dynamic programming to solve this problem? | Nick | 1225. Флаги | 27 дек 2017 18:09 | 5 |
How to use dynamic programming to solve this problem? I used fibonacci. As far as I understand, this problem is about combinations and not about fibonacci.
If there was only the first condition, then for any N we have only 2 possibilities to create the flag.
That is, f(1) = 2, f(2) = 2, f(3) = 2, f(4) = 2, ..., f(N) = 2;
This is true, because the choice of the first stripe determines the rest of the flag automatically. If you choose the first stripe to be white-colored then you are destined to choose the red stripe to be the second one. And vice versa. Don't make my words a HOLY WISDOM - think about it till you can feel it yourself. Don't read next, until you fully and completely get it.
The second condition is here to complicate your life. It doesn't do anything to our function f(x) if x equals to 1 or 2. That is, f(1) and f(2) are still equal to 2.
(By the way, I've just noticed that I've pulled the function from under the pillow. Well, in my mind this function returns the amount of different flags that can be created if you need to make it from x stripes. Ok, now we're moving on...)
But it allows us to INSERT the blue stripe between the two: white and red stripes.
This concept of INSERTION is really the key here. Think about it. If you were supposed to gain anything intellectually from solving this task at all, I bet, it was this very concept.
If we have some sequence of 2-colored flag: WRWRWRWRWRWRWR (White and Red), and this sequence contains all the N stripes that we need, then we really don't have any place to INSERT our blue stipe.
You think, ok, that's fair, and remove one of the stipes (e.g. the left-most). Now you have the place for your blue stripe ... and you can insert it in many ways: wBrwrwrwrwr or wrBwrwrwrwr or wrwBrwrwrwr ... well, you get the point :)
This way, by removing one of the stripes you have created X COMBINATIONS. This word is also important, that is why it is all upper-case :)
If you remove ONE MORE stripe (think about removing as n - 1 or better n--), you now have to INSERT 2 blue stripes somewhere in the sequence wrwrwrwrwrwr...
E.g. wBrBwrwrwrwrwrwr, or wBrwrwrwrwrwrwBr. Now there should be more COMBINATIONS than in the previous case (figure out yourself, how many :) ).
The last point I want to make is that you have to know your limits. That is, you have to understand when to stop removing stipes from the flag and stop INSERTING blue stripes in it. When you get to this point (keeping in mind all the previous points), you will figure this out by yourself easily...
Edited by author 20.08.2015 02:16
Edited by author 20.08.2015 02:18
Edited by author 20.08.2015 02:23
Edited by author 20.08.2015 02:23
Edited by author 20.08.2015 02:25
Edited by author 20.08.2015 02:26
Edited by author 20.08.2015 02:27
Edited by author 20.08.2015 02:27
Edited by author 15.10.2016 20:15
Edited by author 15.10.2016 20:16
Edited by author 15.10.2016 20:20
Edited by author 15.10.2016 20:21
Edited by author 15.10.2016 20:21 This is really extremely helpful in reasoning about the problem, thank you Егору зачет! За крутое решение и за знание англ) |
| Why? | Delpher | 1225. Флаги | 12 дек 2013 01:54 | 2 |
Why? Delpher 22 авг 2013 11:22 Why, if one of the strip, the answer is 2? "Red" and "Red"? Re: Why? Franco Cáceres Gutiérrez 12 дек 2013 01:54 If n = 1, then the only strip may be Red or White, so answer is 2.
If n = 2, then you can either start with Red or White, but for each, you can only place White or Red respectively for the second strip, so answer is 2 again. |
| Wrong answer!!! | Bibhubrata Narendra | 1225. Флаги | 25 июн 2013 20:25 | 6 |
I am not getting how my program is giving wrong answer for some test case#12.
Can someone help pls
[code deleted]
Edited by author 21.06.2013 16:13
Edited by moderator 21.10.2013 20:39 Hi Alexey,
Thanks for the reply. Could you pls elaborate.I still cant get the point. long long arr[46];
...
printf("%lld", arr[N]); data type
Edited by author 25.06.2013 20:33
Edited by author 25.06.2013 20:33 |
| Incorrect reasoning ? | artem | 1225. Флаги | 4 дек 2014 02:12 | 2 |
Let me know please, why i should not think in this way -
i have A ways to make n-1 strip sequences. If i will add red or white strip from the
left side, i have A ways to make n strip sequences.
R/W + [n-1.....]
But in the same time i can add red or white strip from the right side, and so i'll have another
A ways to make n strip sequences.
[n-1....] + R/W
So, now i have 2*A ways to make n strip sequences.
What's wrong in this kind of argumentation ? Some ways may be counted twice, so the ways will be less than 2A |
| access violation | lasha peradze[FreeUni] | 1225. Флаги | 27 янв 2012 03:54 | 1 |
it has all right answer and why access violation? #include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> int a[40][50]; using namespace std; int main(){ int n,i,j,k; cin>>n; a[0][0]=2; a[1][0]=2; if (n>1){ for (i=2; i<n; i++){ for (j=0; j<39; j++){ a[i][j]=a[i-1][j]+a[i-2][j]; } for (j=0; j<19; j++){ a[i][j+1]+=a[i][j]/10; a[i][j]=a[i][j]%10; } } } for (i=39; i>-1; i--){ if (a[n-1][i]>0){ for (j=i; j>-1; j--){ cout<<a[n-1][j]; } break; } } //system("pause"); } |
| Confusing problem statement | Siroj Matchanov [TUIT] | 1225. Флаги | 12 мар 2012 02:52 | 3 |
What is the number N ? Is it the number of colors or of flags?
From the problem discussion, it turns out to be a fibonacci sequence.
And...
N = 3 M = 4
N = 4 M = 6 ---------?? how come?
N = 5 M = 10
and etc...
How come M = 6 when N = 4? N, the number of the stripes, stripes isn't a color neither flags, it's just the columns of the table ;)
Edited by author 11.11.2011 20:24 Let red color is 1, white color is 2 and blue color is 3. We can get only 6 positions that correspond to our condition. They are 1321, 2132, 1321,2312,1212,2121, is it right? |
| dynamic solution | Zero | 1225. Флаги | 13 окт 2011 04:42 | 2 |
f(i,red)=f(i-2,white)+f(i-1,white)
f(i,white)=f(i-2,red)+f(i-1,red)
Use long long because when n=45 the answer exceeds maxlongint. 1) ...and we get just doubled fibonacci sequence.
2) unsigned long is enough ;) |
| How to solve this prolbem !!! I have thought about it for 3 days... | vongang | 1225. Флаги | 30 сен 2011 19:20 | 1 |
Edited by author 30.09.2011 19:21
Edited by author 30.09.2011 19:22 |
| allright | airlord | 1225. Флаги | 21 окт 2010 01:10 | 1 |
Edited by author 21.10.2010 01:16 |
| Compilation error... | Yermakov Alex <ONPU> | 1225. Флаги | 11 май 2010 02:34 | 2 |
#include <iostream>
long int fibonacci(const int );
int main()
{
int N;
std:: cin>>N;
const int M=N;
std::cout << fibonacci(M)*2;;
return 0;
}
long int fibonacci(const int n)
{ const int m = n;
long int t[m],i;
int first = 0, second = 1;
t[first]=0; t[second]=1;
for (i=second+1; i<m-1; ++i)
{
t[i] = t[first] + t[second];
first = second;
second = i;
}
return t[i];
}
Edited by author 10.05.2010 18:58 When you got Compil. Error you may check the reason clicking on red Caompilation error link at your submit. |
| How we know- THE ANSWER | Veselin Kolev | 1225. Флаги | 24 апр 2005 23:05 | 1 |
If you write a simple solution for this task (with recursion for about 5 min) and see the successive answers you will find the dependance alone! (of course if you have enough experience to see it ;) |
