#2246. Kraljice

Kraljice

Kraljice

题目描述

Izborne pripreme – prvi izborni ispit Zadatak Kraljice 18. lipnja 2022. 1 sekunda / 512 MiB / 100 bodova Zadatak Kraljice Dana je N × N šahovska ploča. Odredite najveći broj kraljica koji se može postaviti na ploču, poštujući sljedeće pravilo: Kraljicu je dozvoljeno staviti na bilo koje prazno polje koje trenutno napada paran broj već postavljenih kraljica. Napomena: Jednom kad je postavljena na ploču, kraljica napada sva polja u istom retku, stupcu i na dijagonalama. Ulazni podaci U prvom i jedinom retku je prirodan broj N, dimenzija šahovske ploče. Izlazni podaci U prvi redak ispišite prirodan broj K, najveći broj kraljica koji se može postaviti na ploču poštujući zadano pravilo. U i-tom od sljedećih K redaka ispišite prirodne brojeve Ri i Si, redak i stupac u koji je stavljena i-ta kraljica. Ako postoji više načina za postaviti kraljice, ispišite bilo koji. Bodovanje Podzadatak Broj bodova Ograničenja 1 ≤N ≤16 1 6 1 ≤N ≤64 2 11 1 ≤N ≤256 3 28 1 ≤N ≤1024 4 55 Probni primjeri ulaz ulaz ulaz 1 2 3 izlaz izlaz izlaz 1 1 9 1 1 1 1 2 3 3 1 2 2 1 1 3 3 3 2 1 2 1 3 2 1 1 od 6 Izborne pripreme – prvi izborni ispit Zadatak Kraljice 18. lipnja 2022. 1 sekunda / 512 MiB / 100 bodova Pojašnjenje trećeg probnog primjera: Z0Z Z0Z Z0Z Z0Z l0Z 0Z0 0Zq 0Zq 0lq 0lq Z0Z Z0Z l0Z l0Z l0Z l0Z l0Z lqZ lql lql 0lq 0lq 0lq 0lq qlq l0l lql lql lql lql 2 od 6

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1
1
1 1

样例 2

2
1
1 1