AtCoder Beginner Contest 129 C - Typical Stairs Difficulty: 795
Das Thema des ersten Teils ist Fibonacci Ruby
| Anzahl der Treppen | Kombinationsmuster | Anzahl der Kombinationen |
|---|---|---|
| 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 |
** Ergänzung ** Anzahl der Schritte = Schritte zu Ihren Füßen + Nächster Schritt. Vielen Dank für Ihren Kommentar, @swordone.
Der Weg die Treppe hinauf ist wie oben, aber der mit der guten Idee ist ** [Fibonatch-Nummer](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3 Sie werden feststellen, dass% 83% 9C% E3% 83% 8A% E3% 83% 83% E3% 83% 81% E6% 95% B0) **.
Suchen Sie daher die Anzahl der aufeinanderfolgenden Treppen, z. B. #. # ... -> 1, 1, 3`, und addieren Sie die Gesamtzahl der Kombinationen. "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
Wenn Sie den Divisor als 1e9 + 7 schreiben, wird er in * Ruby * als reelle Zahl behandelt und aufgrund des Fehlers nach dem Dezimalpunkt WA </ font>. Seien Sie also vorsichtig. Bitte Anhängen. 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";
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);
}
}
Es ist ein Versprechen, dass Sie RE </ font> erhalten, ohne lange zu verwenden.
| Ruby | Perl | Java | |
|---|---|---|---|
| Codelänge | 457 Byte | 522 Byte | 1106 Byte |
| Ausführungszeit | 64 ms | 85 ms | 343 ms |
| Erinnerung | 3836 KB | 10368 KB | 45652 KB |
Dies ist normalerweise das Ende, aber dieses Mal habe ich im Eckfall viel getroffen, also werde ich eine andere Lösung veröffentlichen.
Recommended Posts