Sleeping schedule

Darío has a weird sleeping schedule. And I mean really weird. It has
gotten so bad that, whenever the National Cybersecurity Agency needs a
pseudorandom number for encrypting purposes, they simply call Darío and
ask him what time he woke up that morning.

The constant calls are beginning to annoy Darío (how is he supposed to
think about math with all these interruptions?), so he has decided he is
going to standardize his routine. However, he wants his schedule to
satisfy a few restrictions.

To begin with, Darío’s days have h hours, instead of the usual 24, which
he numbers from 0 to h − 1. He will choose:

- a fixed time w at which to wake up, and

- a fixed time s at which to go to sleep.

Every day, he will sleep from w to s. In particular, if both times are
equal, he will sleep for 0 hours. For example, if h = 10, going to sleep
at 7:00 and getting up at 2:00 means that Darío will sleep for 5 hours.

His chosen times must also satisfy the following conditions:

- Both times must be multiples of an hour (e.g. he can go to sleep at
  9:00 or 4:00 but not at 4:23).

- He must wake up at a time when the dining hall is open (as everyone
  knows, a good day starts with a good breakfast).

- He must go to sleep at a time when there is no ICPC training
  (otherwise, he would never stick to his schedule).

Darío has given you a list with the n hours in which there is no ICPC
training, and the m hours in which the dining hall is open. He will
choose uniformly at random both w and s (one independently from the
other). Can you compute the average number of hours he will be sleeping
per day?

Input

Input consists of multiple cases, only with integer numbers. Each case
begins with h, n and m, all between 1 and 10⁵. Follow n distinct
integers a₁, …, a_(n) satisfying 0 ≤ a_(i) < h, indicating the hours
with no ICPC training. Follow m distinct integers b₁, …, b_(m)
satisfying 0 ≤ b_(i) < h, indicating the hours with the dining hall
open.

Output

For each case, print with 4 digits after the decimal point the expected
number of hours that Darío will be sleeping. The given input cases will
have no precission issues.

Problem information

Author: Xavier Povill
Event: Vint-i-quatrè Concurs de Programació de la UPC - Semifinal
Date: 2026-06-18

Generation: 2026-06-12T10:13:48.858Z

© Jutge.org, 2006–2026.
https://jutge.org
