Résolution avec Ruby, Perl et Java AtCoder ABC 129 C (Partie 1)

introduction

Ce thème

AtCoder Beginner Contest 129 C - Typical Stairs Difficulty: 795

Le thème de la première partie est Fibonacci Ruby

Nombre d'escaliers Motif de combinaison Nombre de combinaisons
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 ** Nombre d'étapes = Étapes à vos pieds + Étape suivante. Merci pour votre commentaire, @swordone.

La façon de monter les escaliers est comme ci-dessus, mais celle avec une bonne idée est ** [numéro Fibonatch](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3 Vous remarquerez que% 83% 9C% E3% 83% 8A% E3% 83% 83% E3% 83% 81% E6% 95% B0) **.

Par conséquent, trouvez le nombre d'escaliers consécutifs et ajoutez le nombre total de combinaisons à «exemple. #. # ...» -> «1, 1, 3». 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

Si vous écrivez le diviseur comme 1e9 + 7, il sera traité comme un nombre réel dans * Ruby *, et il sera WA </ font> en raison de l'erreur après la virgule décimale, alors soyez prudent. Veuillez joindre. 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 * est un type plus dynamique que * 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);
    }
}

C'est une promesse que vous obtiendrez RE </ font> sans utiliser long.

Ruby Perl Java
Longueur du code 457 Byte 522 Byte 1106 Byte
Temps d'exécution 64 ms 85 ms 343 ms
Mémoire 3836 KB 10368 KB 45652 KB

C'est généralement la fin, mais cette fois j'ai beaucoup rencontré dans le cas du coin, donc je publierai une autre solution.

Résumé

  • ABC 129 C a été résolu avec difficulté
  • Familiarisez-vous avec Ruby
  • Familiarisez-vous avec Perl
  • Familiarisez-vous avec Java

Recommended Posts