Solving with Ruby, Perl and Java AtCoder ABC 129 C (Part 1)

Introduction

This theme

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.

Summary

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

Recommended Posts