- AtCoder Problems * Use Recommendations to solve past problems. Thanks to AtCoder and AtCoder Problems.

*AtCoder Beginner Contest 129 C - Typical Stairs*
Difficulty: 795

The theme of the first part is Fibonacci Ruby

Number of stairs | Combination pattern | Number of combinations |
---|---|---|

1 | 1 | 1 |

2 | 1-2 | 1 |

3 | 1-2-3/1-3 | 2 |

4 | 1-2-3-4/1-2-4/1-3-4 | 3 |

5 | 1-2-3-4-5/1-2-3-5/1-2-4-5/1-3-4-5/1-3-5 | 5 |

** Addition ** Number of stairs = step at your feet + next step. Thank you for your comment, @swordone.

The way to go up the stairs is as above, but the one with a good idea is ** [Fibonacci number](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3 You will notice that% 83% 9C% E3% 83% 8A% E3% 83% 83% E3% 83% 81% E6% 95% B0) **.

Therefore, find the number of consecutive stairs, `example. #. # ...`

-> `1, 1, 3`

, and multiply the total number of combinations. `fib (1) * fib (1) * fib (3)`

`ruby.rb`

```
n, m = gets.split.map(&:to_i)
a = []
1.upto(m) do |i|
a[i] = gets.to_i
end
a[0] = -1
a.push(n + 1)
b = []
1.upto(m + 1) do |i|
if a[i] - a[i - 1] == 1
puts "0"
exit
end
b.push(a[i] - a[i - 1] - 1)
end
fib = []
fib[1] = 1
fib[2] = 1
3.upto(n + 1) do |i|
fib[i] = fib[i - 1] + fib[i - 2]
fib[i] %= 1_000_000_007
end
ans = 1
0.upto(b.size - 1) do |i|
ans *= fib[b[i]]
ans %= 1_000_000_007
end
puts ans
```

`WA.rb`

```
ans %= 1_000_000_007
ans %= 1e9 + 7
```

If you write the divisor as 1e9 + 7, it will be treated as a real number in * Ruby *, and it will be WA </ font> due to the error after the decimal point. Please attach. Perl

`perl.pl`

```
chomp (my ($n, $m) = split / /, <STDIN>);
my @a;
for my $i (1..$m) {
chomp (my $in = <STDIN>);
$a[$i] = $in;
}
$a[0] = -1;
push @a, $n + 1;
my @b;
for my $i (1..$m+1) {
if ($i != 1 && $a[$i] - $a[$i - 1] == 1) {
print "0\n";
exit;
}
push @b, $a[$i] - $a[$i - 1] - 1;
}
my @fib;
$fib[1] = 1;
$fib[2] = 1;
for my $i (3..$n+1) {
$fib[$i] = $fib[$i - 1] + $fib[$i - 2];
$fib[$i] %= 1e9 + 7;
}
my $ans = 1;
for my $i (@b) {
$ans *= $fib[$i];
$ans %= 1e9 + 7;
}
print "$ans\n";
```

- Perl * is a more dynamic type than * Ruby *. Java

`java.java`

```
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.next());
int m = Integer.parseInt(sc.next());
int a[] = new int[m + 2];
for (int i = 1; i <= m; i++) {
a[i] = Integer.parseInt(sc.next());
}
sc.close();
a[0] = -1;
a[m + 1] = n + 1;
List<Integer> b = new ArrayList<>();
for (int i = 1; i <= m + 1; i++) {
if (a[i] - a[i - 1] == 1) {
System.out.println(0);
return;
}
b.add(a[i] - a[i - 1] - 1);
}
long fib[] = new long[n + 2];
fib[1] = 1;
fib[2] = 1;
for (int i = 3; i <= n + 1; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
fib[i] %= 1_000_000_007;
}
long ans = 1;
for (int i = 0; i < b.size(); i++) {
ans *= fib[b.get(i)];
ans %= 1_000_000_007;
}
System.out.print(ans);
}
}
```

We promise that if you don't use long, you'll get RE </ font>.

Ruby | Perl | Java | |
---|---|---|---|

Code length | 457 Byte | 522 Byte | 1106 Byte |

Execution time | 64 ms | 85 ms | 343 ms |

memory | 3836 KB | 10368 KB | 45652 KB |

This is usually the end, but this time I met a lot in the corner case, so I will post another solution.

- ABC 129 C was solved with difficulty
- Become familiar with Ruby
- Become familiar with Perl
- Become familiar with Java

Recommended Posts