Fişierul intrare/ieşire:	ciocolata2.in, ciocolata2.out	Sursă	Algoritmiada 2017, Runda 1
Autor	Vlad Gavrila	Adăugată de	Gavrila Vlad •GavrilaVlad
Timp execuţie pe test	0.5 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Ciocolata 2

Luând o pauză de la curăţenie, Henry şi Hetty se joacă cu un caroiaj de dimensiuni N * M şi multe bucăţi de ciocolată de dimensiuni 2 * 1. Fiecare bucată de ciocolată poate fi plasată oriunde în caroiaj cât timp acoperă exact două celule. Bucăţile de ciocolată pot fi plasate atât vertical cât şi orizontal, şi nu trebuie să se suprapună cu alte bucăţi. O celulă se consideră acoperită dacă există o bucată de ciocolată plasată deasupra ei.

Henry şi Hetty vor executa K+1 paşi. La pasul 0, Henry o roagă pe Hetty să aşeze o mulţime A₀ bucăţi de ciocolată în caroiaj astfel încât să acopere toate celulele. Apoi, paşii de la 1 la K constau în următoarele etape:

1. Henry alege o mulţime C_i de celule nemarcate şi le marchează. Odată ce o celulă este marcată, ea rămâne astfel pentru toţi paşii ce vor urma.
2. Hetty trebuie acum să se asigure că toate celulele marcate sunt descoperite, şi toate celulele nemarcate sunt acoperite. Pentru a face acest lucru, ea va alege o mulţime E_i de bucăţi de ciocolată aşezate pe caroiaj şi le va elimina; apoi, ea va aşeza pe caroiaj o altă mulţime A_i de bucăţi de ciocolată (posibil vidă).

Ajutaţi-o pe Hetty să facă paşii necesari: dacă reuşeşte să îi execute corect, poate mânca toată ciocolata folosită pentru joc!

Date de intrare

Pe prima linie a fişierului de intrare ciocolata2.in se vor afla trei numere naturale N, M şi K, cu semnificaţia din enunţ. Următoarele linii descriu paşii de la 1 la K: pe prima linie ce descrie pasul i se va afla un număr natural B_i - numărul de celule marcate de Henry la pasul i. Pe următoarele B_i linii se vor afla perechi de numere naturale X şi Y, reprezentând coordonatele celulelor marcate de Henry la pasul curent.

Date de ieşire

O mulţime de bucăţi de ciocolată este afişată în felul următor: pe prima linie afişaţi un număr natural P, reprezentând dimensiunea mulţimii. Apoi, pe următoarele P linii, afişaţi patru numere naturale X₁, Y₁, X₂, Y₂ reprezentând coordonatele celulelor (X₁, Y₁) şi (X₂, Y₂) acoperite de bucata curentă. Atenţie: aceste celule trebuie să fie adiacente.

În fişierul de ieşire ciocolata2.out trebuie să afişaţi întâi mulţimea A₀ de bucăţi de ciocolată adăugate de Hetty la pasul 0. Apoi, pentru fiecare pas i din cei K rămaşi, trebuie să afişaţi întâi mulţimea E_i de bucăţi eliminate de Hetty, şi apoi mulţimea A_i de bucăţi adăugate de Hetty, în această ordine. Dacă nu este posibil ca Hetty să execute pasul i, afişaţi "-1" şi terminaţi execuţia programului, ignorând paşii rămaşi.

Restricţii

• 1 ≤ N, M ≤ 70
• 1 ≤ K ≤ 1700
• Pentru 10% din teste, 1 ≤ N, M ≤ 10.
• Pentru 40% din teste, 1 ≤ N, M ≤ 50.
• Se garantează că pasul 0 poate fi mereu efectuat.
• Se garantează că nicio celulă nu va fi marcată de două ori.
• Coordonatele celulelor sunt indexate de la 1.

Afişare rapidă

Deoarece fişierele de ieşire generate pot fi mari, se recomandă parsarea afişării. Pentru a vă fi de ajutor, vă oferim următorul cod:

#include <fstream>
 
using namespace std;
 
class Writer {
  public:
    Writer(const char *name):
        m_stream(name) {
        memset(m_buffer, 0, sizeof(m_buffer));
        m_pos = 0;
    }
 
    Writer& operator<<(int a) {
        int many = 0;
        do {
            digit_buffer[many++] = a % 10 + '0';
            a /= 10;
        } while (a > 0);
        for (int i = many - 1; i >= 0; --i)
            putchar(digit_buffer[i]);
        return *this;
    }
 
    Writer& operator<<(const char *s) {
        for (; *s; ++s)
            putchar(*s);
        return *this;
    }
 
    ~Writer() {
        m_stream.write(m_buffer, m_pos);
    }
 
  private:
    void putchar(char c) {
        m_buffer[m_pos++] = c;
        if (m_pos == kBufferSize) {
            m_stream.write(m_buffer, m_pos);
            m_pos = 0;
        }
    }
 
    static const int kBufferSize = 32768;
    ofstream m_stream;
    char m_buffer[kBufferSize];
    char digit_buffer[30];
    int m_pos;
} fout("ciocolata2.out");

Această clasă poate afişa doar numere naturale nenegative şi şiruri de caractere. Spre exemplu, pentru a afişa o pereche de numere separate prin spaţiu, respectiv numărul -1, folosiţi:

fout << a << " " << b << "\n";
fout << "-1\n";

Exemplu

Cum se trimit solutii?