ID #123 · Colecția InfoAs · Operatori și expresii

Problema Supererou

Cartierul Soarelui este format dintr-un șir de blocuri ce sunt lipite unul de altul, având înălțimi diferite. Acestea sunt notate astfel: `a<sub>0</sub>, a<sub>1</sub>, …, a<sub>n - 1</sub>`. Numim secvență o înșiruire de blocuri consecutive, spre exemplu `a<sub>2</sub>, a<sub>3</sub>, a<sub>4</sub>, a<sub>5</sub>` dar nu și `a<sub>2</sub>, a<sub>4</sub>, a<sub>5</sub>`. Lungimea unei secvențe este dată de numărul de blocuri care sunt incluse în secvență. Supereroul cartierului, Radu, are o abilitate specială, dar limitată însă: poate trece de pe un bloc pe altul vecin, doar dacă diferența de înălțime dintre cele două, în valoare absolută, este mai mică sau egală cu un număr `K` dat. ## Cerință Cunoscându-se numărul `K` (cu semnificația de mai sus), numărul `N` de blocuri din acel cartier și înălțimile fiecărui bloc, Radu are nevoie de ajutorul vostru în a determina câteva dintre multele întrebări pe care le are, așa că vă cere să aflați: 1. Înălțimea maximă a blocurilor din cartierul Soarelui pentru a cunoaște de unde poate supraveghea tot cartierul. 2. Lungimea maximă a unei secvențe de blocuri între care acesta poate trece de la un capăt la altul. 3. Lungimea maximă a unei secvențe de blocuri pe care o poate obține, știind că are puterea să distrugă unul dintre blocuri, pentru a putea acoperi o rază cât mai mare de cartier în cazul unei urgențe. Prin distrugerea unui bloc, cele doua blocuri din strânga și dreapta lui devin vecine. Spre exemplu, prin distrugerea blocului `a<sub>2</sub>`, blocurile `a<sub>1</sub>` și `a<sub>3</sub>` ar deveni vecine și astfel Radu ar putea trece de pe unul pe altul dacă respect condiția din enunț. Acesta poate alege să nu distrugă niciun bloc, dacă prin acest lucru obține cea mai lungă secvență de blocuri. ## Date de intrare Fișierul de intrare `supererou.in` conține pe prima linie un număr natural `C`, care poate fi `1`, `2` sau `3`. A doua linie conține numărul natural `K` (cu semnificația din enunț), iar apoi (separat printr-un spațiu) numărul natural `N` ce reprezintă numărul de blocuri din cartier. Pe a treia linie se află `N` numere naturale separate prin câte un spațiu ce semnifică înălțimile celor `N` blocuri în ordinea în care acestea sunt amplasate. ## Date de ieșire Dacă valoarea lui `C` este `1`, atunci se va rezolva **numai punctul 1 din cerință**. În acest caz, fișierul de ieșire `supererou.out` va conține pe prima linie un singur număr natural, reprezentând cea mai mare înălțime dintre toate blocurile din cartier. Dacă valoarea lui `C` este `2`, atunci se va rezolva **numai punctul 2 din cerință**. În acest caz, fișierul de ieșire `supererou.out` va conține pe prima linie un singur număr natural, reprezentând cea mai mare lungime a unei secvențe de blocuri între care Radu poate trece. Dacă valoarea lui `C` este `3`, atunci se va rezolva **numai punctul 3 din cerință**. În acest caz, fișierul de ieșire `supererou.out` va conține pe prima linie un singur număr natural, reprezentând cea mai mare lungime a unei secvențe de blocuri între care Radu poate trece care se obține prin distrugerea unui (sau a niciunui în unele cazuri) bloc. ## Restricții și precizări * `C` poate fi `1`, `2` sau `3` * `0 ≤ K ≤ 100.000` * `5 ≤ N ≤ 100.000` * Înălțimile blocurilor sunt numere naturale între `0` și `1.000.000` * Rezolvarea cerinței 1 garantează 30 de puncte, cerința 2 – 35 de puncte, iar cerința 3 – 35 de puncte