trang chủ / đề bài / icpc23_mn_c

Khối lập phương

Đề bài

Mô tả

Giáo sư Thanh thiết kế một khối lập phương rất đặc biệt có kích thước n×n×n đơn vị. Ông dựng hệ tọa độ Oxyz tại một đỉnh của khối, sao cho ba mặt của khối lập phương nằm trên ba mặt phẳng Oxy, Oyz và Ozx.

Mỗi khối đơn vị của khối lập phương được xác định bởi bộ ba số (x,y,z) như một điểm trong không gian ba chiều (0≤x,y,z≤n−1). Giáo sư Thanh gọi các khối đơn vị "tiềm năng" là các khối (x,y,z) có đúng một tọa độ bằng 0, tức là chúng nằm trên một trong ba mặt Oxy, Oyz, Ozx nhưng không nằm trên các trục tọa độ.

Giáo sư Thanh chọn k khối đơn vị tiềm năng. Với mỗi khối, ông khoan từ tâm của ô vuông nằm trên mặt của khối lập phương, theo hướng vuông góc với mặt chứa ô đó, xuyên qua toàn bộ khối lập phương. Nói cách khác, mũi khoan từ khối (x,y,0) đi qua mọi khối (x,y,t), mũi khoan từ khối (0,y,z) đi qua mọi khối (t,y,z), và mũi khoan từ khối (x,0,z) đi qua mọi khối (x,t,z), với 0≤t≤n−1.

Hãy giúp giáo sư Thanh đếm số khối đơn vị bị ít nhất một mũi khoan đi qua.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và k (1≤n≤109, 1≤k≤103).

Mỗi dòng trong k dòng tiếp theo chứa ba số nguyên x,y,z (0≤x,y,z≤n−1): vị trí của một khối đơn vị tiềm năng. Trên mỗi dòng có đúng một trong ba số bằng 0.

Dữ liệu ra

In ra một số nguyên là số khối đơn vị bị ít nhất một mũi khoan đi qua.

Ràng buộc

  • 1≤n≤109, 1≤k≤103
  • 0≤x,y,z≤n−1, đúng một trong ba số bằng 0

Ví dụ

Input Output Giải thích
3 4
2 1 0
0 1 1
1 0 1
2 0 1
9 Bốn mũi khoan, mỗi mũi qua 3 khối. Khối (2,1,1) nằm trên mũi khoan thứ nhất, thứ hai và thứ tư; khối (1,1,1) nằm trên mũi khoan thứ hai và thứ ba. Tổng cộng 12−2−1=9 khối.
2 5
1 1 0
1 1 0
0 1 1
0 1 1
1 0 1
4 Có ba mũi khoan khác nhau (hai mũi khoan bị lặp lại), cắt nhau tại khối (1,1,1): 6−2=4 khối.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0