QOJ.ac

QOJ

Time Limit: 1.0 s Memory Limit: 512 MB Total points: 100

#81. Dekorasi Piramida

Statistics

Ada $L\times(L+1)\times(L+2)/6$ batu. Snuke menumpuk batu-batu ini membentuk tetrahedron (benda tiga dimensi dengan empat sisi berbentuk segitiga). Posisi sebuah batu dinyatakan oleh tupel bilangan bulat $(i,j,k)$ ($1\le k\le j\le i\le L$). Jika $i<L$, batu pada $(i,j,k)$ ditumpuk di atas tiga batu pada $(i+1,j,k)$, $(i+1,j+1,k)$, dan $(i+1,j+1,k+1)$.

Snuke mewarnai batu-batu tersebut dengan cara berikut. Pertama, ia mewarnai semua batu pada lapisan paling bawah. Untuk setiap $i$ ($1\le i\le N$), ia mewarnai batu pada $(L,A_i,B_i)$ hitam, dan mewarnai batu-batu lain pada lapisan paling bawah putih. Kemudian ia mewarnai batu-batu lainnya dari bawah ke atas. Ia mewarnai batu pada $(i,j,k)$ hitam jika banyaknya batu hitam di bawahnya (pada $(i+1,j,k)$, $(i+1,j+1,k)$, dan $(i+1,j+1,k+1)$) adalah nol atau dua. Jika tidak, ia mewarnai batu tersebut putih.

Tentukan warna batu paling atas.

Masukan

Format masukan adalah:

$$ \begin{gathered} L\quad N \\ A_1\quad B_1 \\ \vdots \\ A_N\quad B_N \end{gathered} $$

  • $2\le L\le10^9$
  • $0\le N\le\min(1000,L\times(L+1)/2)$
  • $1\le B_i\le A_i\le L$
  • Semua tupel $(A_i,B_i)$ berbeda satu sama lain.

Keluaran

Keluarkan Iori jika batu paling atas berwarna hitam. Jika tidak, keluarkan Yayoi.

Contoh

Masukan 1

2 2
2 1
1 1

Keluaran 1

Iori

Masukan 2

3 0

Keluaran 2

Yayoi

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.