Solving in Ruby, Perl, Java, and Python AtCoder ARC 066 C Iterative Squares Hash

Introduction

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

This theme

AtCoder Regular Contest 066 C - Lining Up Difficulty: 927

This theme, iterative squares and hash Ruby This is a symmetrical problem, so if you assign it to a hash, you can expect it to be a values array like 2221222 for odd names and 22222222 for even names. In other cases, it can be determined that there is no arrangement.

Also, it's time for the previously posted * Solving with Ruby, Perl, Java and Python AtCoder ATC 002 B* to help. Since it is the number of combinations of multiplication of 2, the iterative square method (function | method) created in the above post can be used as it is.

ruby.rb

n = gets.to_i
a = gets.split.map(&:to_i)
h = Hash.new(0)
a.each do |x|
  h[x] += 1
end
f = true
h.each do |k, v|
  if n.odd? && k == 0
    if v != 1
      f = false
      break
    end
  elsif v != 2
    f = false
    break
  end
end
MOD = 1_000_000_007
def mpow(n, p, mod)
  r = 1
  while p > 0
    r = r * n % mod if p & 1 == 1
    n = n * n % mod
    p >>= 1
  end
  r
end
puts (f ? mpow(2, n / 2, MOD) : 0)

mpow.rb

def mpow(n, p, mod)
  r = 1
  while p > 0
    r = r * n % mod if p & 1 == 1
    n = n * n % mod
    p >>= 1
  end
  r
end

I am using it as it is. Python

python.py

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
h = Counter()
for x in a:
    h[x] += 1
f = True
for k, v in h.most_common():
    if n % 2 == 1 and k == 0:
        if v != 1:
            f = False
            break
    elif v != 2:
        f = False
        break
MOD = 1000000007
def mpow(n, p, mod):
    r = 1
    while p > 0:
        if p & 1 == 1:
            r = r * n % mod
        n = n * n % mod
        p >>= 1
    return r
print(mpow(2, n // 2, MOD) if f else 0)

hash.py

from collections import Counter

Declare from collections import Counter when using hashes.

mod.py

MOD = 1000000007
MOD = 1_000_000_007

In my ring Python 3.8.2 (default, Apr 16 2020, 16:12:56), you can write 1_000_000_007, but in the AtCoder environment it seems to be WA. Perl

perl.pl

chomp (my $n = <STDIN>);
chomp (my @a = split / /, <STDIN>);
my %h;
$h{$_}++ for @a;
my $f = 1;
for my $k (keys %h) {
  if ($n % 2 == 1 && $k == 0) {
    if ($h{$k} != 1) {
      $f = 0;
      last;
    }
  } elsif ($h{$k} != 2) {
    $f = 0;
    last;
  }
}
my $MOD = 1_000_000_007;
sub mpow {
  my ($n, $p) = @_;
  my $r = 1;
  while ($p > 0) {
    $r = $r * $n % $MOD if $p & 1;
    $n = $n * $n % $MOD;
    $p >>= 1;
  }
  $r;
}
print ($f ? mpow(2, int($n / 2)) : 0), "\n";

As it is ... Java

java.java

import java.math.BigInteger;
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        HashMap<Integer, Integer> h = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(sc.next());
            if (h.containsKey(a)) {
                h.put(a, h.get(a) + 1);
            } else {
                h.put(a, 1);
            }
        }
        sc.close();
        boolean f = true;
        for (int k : h.keySet()) {
            if (n % 2 == 1 && k == 0) {
                if (h.get(k) != 1) {
                    f = false;
                    break;
                }
            } else if (h.get(k) != 2) {
                f = false;
                break;
            }
        }
        BigInteger bn = new BigInteger("2");
        BigInteger bm = new BigInteger("1000000007");
        BigInteger bp = new BigInteger(Integer.toString(n / 2));
        System.out.println((f ? bn.modPow(bp, bm) : 0));
    }
}

Summary

• Solved ARC 066 C
• Become familiar with Ruby
• Become familiar with Python
• Become familiar with Perl
• Become familiar with Java

Referenced site

• [Python] dictionary (hash) *
• Python's or and and operator trap *