Цифрийн тоо

1s

256MB

1800

0%

MathSortingTwo PointersBinary Search

Бат $N \times N$ хэмжээтэй хүснэгтийн нүд бүрийг бүхэл тоогоор дүүргэхээр шийджээ. Тодруулбал, $A_1, A_2, \ldots, A_N$ болон $B_1, B_2, \ldots, B_N$ гэсэн хоёр тоон дарааллын утгуудаар хүснэгтийн дээрээсээ $i$ -р мөр ( $1 \le i \le N$ ), зүүнээсээ $j$ -р баганад ( $1 \le j \le N$ ) байрлах нүдэнд тэрээр $A_i+B_j$ гэсэн тоог бичих болно. Хүснэгтийг ийнхүү бөглөхдөө Бат нийт хэдэн цифр бичихээ мэдмээр байгаа тул та түүнд тусална уу. Өөрөөр хэлбэл, та Батын $N \times N$ хүснэгтэд бичсэн бүхэл тоонуудын оронгуудын нийт тоог олох хэрэгтэй.

Даалгавар: $A_i$ ( $1 \le i \le N$ ) болон $B_j$ ( $1 \le j \le N$ ) утгууд өгөгдсөн бол Батын хүснэгтэд бичсэн тоонуудын оронгуудын нийт тоог тооцоолох программ бичнэ үү.

Эх сурвалж: Японы Мэдээлэл зүйн олимпиадын хороо, JOIG 2023/2024, Many Digits, Монгол хэлнээ тохируулсан; CC BY-SA 4.0.

Оролтын формат

Оролтын өгөгдөл дараах форматтай байна.

text
N
A_1 A_2 ... A_N
B_1 B_2 ... B_N

Гаралтын формат

Батын хүснэгтэд бичсэн тоонуудын цифрүүдийн нийт тоог илэрхийлэх нэг бүхэл тоог хэвлэнэ.

Хязгаарлалт

$1 \le N \le 150\,000$ .
$1 \le A_i \le 999\,999\,999$ ( $1 \le i \le N$ ).
$1 \le B_j \le 999\,999\,999$ ( $1 \le j \le N$ ).
Оролтын бүх өгөгдөл бүхэл тоо байна.

Дэд бодлого

Дэд бодлого	Оноо	Нэмэлт хязгаарлалт
1	5	$N=1$
2	11	$N \le 2\,000$
3	15	$A_i \le 2\,000$ ( $1 \le i \le N$ ), $B_j \le 2\,000$ ( $1 \le j \le N$ )
4	8	$100\,000\,000 \le A_i \le 500\,000\,000$ ( $1 \le i \le N$ ), $100\,000\,000 \le B_j \le 500\,000\,000$ ( $1 \le j \le N$ )
5	22	$100\,000\,000 \le A_i$ ( $1 \le i \le N$ ), $100\,000\,000 \le B_j$ ( $1 \le j \le N$ )
6	12	$A_i \le 150\,000$ ( $1 \le i \le N$ ), $B_j=j$ ( $1 \le j \le N$ )
7	13	$B_j=j$ ( $1 \le j \le N$ )
8	14	Нэмэлт хязгаарлалт байхгүй

Жишээ

Оролт1

3
97 79 7
20 2 21

Гаралт1

Оролт2

4
8 97 996 9995
1 2 3 4

Гаралт2

Оролт3

1
500000000
500000000

Гаралт3

0.1 / 64 KiB

Редактор уншиж байна...