dwsd

// Standard iostream objects -*- C++ -*-

// Copyright (C) 1997-2014 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file include/iostream
 *  This is a Standard C++ Library header.
 */

//
// ISO C++ 14882: 27.3  Standard iostream objects
//

#ifndef _GLIBCXX_IOSTREAM
#define _GLIBCXX_IOSTREAM 1

#pragma GCC system_header

#include <bits/c++config.h>
#include <ostream>
#include <istream>

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  /**
   *  @name Standard Stream Objects
   *
   *  The &lt;iostream&gt; header declares the eight <em>standard stream
   *  objects</em>.  For other declarations, see
   *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/io.html
   *  and the @link iosfwd I/O forward declarations @endlink
   *
   *  They are required by default to cooperate with the global C
   *  library's @c FILE streams, and to be available during program
   *  startup and termination. For more information, see the section of the
   *  manual linked to above.
  */
  //@{
  extern istream cin;		/// Linked to standard input
  extern ostream cout;		/// Linked to standard output
  extern ostream cerr;		/// Linked to standard error (unbuffered)
  extern ostream clog;		/// Linked to standard error (buffered)

#ifdef _GLIBCXX_USE_WCHAR_T
  extern wistream wcin;		/// Linked to standard input
  extern wostream wcout;	/// Linked to standard output
  extern wostream wcerr;	/// Linked to standard error (unbuffered)
  extern wostream wclog;	/// Linked to standard error (buffered)
#endif
  //@}

  // For construction of filebuffers for cout, cin, cerr, clog et. al.
  static ios_base::Init __ioinit;

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace

#endif /* _GLIBCXX_IOSTREAM */

😕

You are playing with a really long strip consisting of $10^{18}$ white cells, numbered from left to right as $0$, $1$, $2$ and so on. You are controlling a special pointer that is initially in cell $0$. Also, you have a "Shift" button you can press and hold. In one move, you can do one of three actions: move the pointer to the right (from cell $x$ to cell $x + 1$); press and hold the "Shift" button; release the "Shift" button: the moment you release "Shift", all cells that were visited while "Shift" was pressed are colored in black. (Of course, you can't press Shift if you already hold it. Similarly, you can't release Shift if you haven't pressed it.) Your goal is to color at least $k$ cells, but there is a restriction: you are given $n$ segments $[l_i, r_i]$ — you can color cells only inside these segments, i. e. you can color the cell $x$ if and only if $l_i \le x \le r_i$ for some $i$. What is the minimum number of moves you need to make in order to color at least $k$ cells black? The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $1 \le k \le 10^9$) — the number of segments and the desired number of black cells, respectively. The second line contains $n$ integers $l_1, l_2, \dots, l_n$ ($1 \le l_1 < l_2 < \dots < l_n \le 10^9$), where $l_i$ is the left border of the $i$-th segment. The third line contains $n$ integers $r_1, r_2, \dots, r_n$ ($1 \le r_i \le 10^9$; $l_i \le r_i < l_{i + 1} - 1$), where $r_i$ is the right border of the $i$-th segment. Additional constraints on the input: every cell belongs to at most one segment; the sum of $n$ doesn't exceed $2 \cdot 10^5$. For each test case, print the minimum number of moves to color at least $k$ cells black, or $-1$ if it's impossible. Input The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $1 \le k \le 10^9$) — the number of segments and the desired number of black cells, respectively. The second line contains $n$ integers $l_1, l_2, \dots, l_n$ ($1 \le l_1 < l_2 < \dots < l_n \le 10^9$), where $l_i$ is the left border of the $i$-th segment. The third line contains $n$ integers $r_1, r_2, \dots, r_n$ ($1 \le r_i \le 10^9$; $l_i \le r_i < l_{i + 1} - 1$), where $r_i$ is the right border of the $i$-th segment. Additional constraints on the input: every cell belongs to at most one segment; the sum of $n$ doesn't exceed $2 \cdot 10^5$. Output For each test case, print the minimum number of moves to color at least $k$ cells black, or $-1$ if it's impossible. 4 2 3 1 3 1 4 4 20 10 13 16 19 11 14 17 20 2 3 1 3 1 10 2 4 99 999999999 100 1000000000 8 -1 7 1000000004 Note In the first test case, one of the optimal sequences of operations is the following: Move right: pointer is moving into cell $1$; Press Shift; Release Shift: cell $1$ is colored black; Move right: pointer is moving into cell $2$; Move right: pointer is moving into cell $3$; Press Shift; Move right: pointer is moving into cell $4$; Release Shift: cells $3$ and $4$ are colored in black. We've colored $3$ cells in $8$ moves. In the second test case, we can color at most $8$ cells, while we need $20$ cell to color. In the third test case, one of the optimal sequences of operations is the following: Move right: pointer is moving into cell $1$; Move right: pointer is moving into cell $2$; Move right: pointer is moving into cell $3$; Press Shift; Move right: pointer is moving into cell $4$; Move right: pointer is moving into cell $5$; Release Shift: cells $3$, $4$ and $5$ are colored in black. We've colored $3$ cells in $7$ moves.

An integer template is a string consisting of digits and/or question marks. A positive (strictly greater than $0$) integer matches the integer template if it is possible to replace every question mark in the template with a digit in such a way that we get the decimal representation of that integer without any leading zeroes. For example: $42$ matches 4?; $1337$ matches ????; $1337$ matches 1?3?; $1337$ matches 1337; $3$ does not match ??; $8$ does not match ???8; $1337$ does not match 1?7. You are given an integer template consisting of at most $5$ characters. Calculate the number of positive (strictly greater than $0$) integers that match it. The first line contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Each test case consists of one line containing the string $s$ ($1 \le |s| \le 5$) consisting of digits and/or question marks — the integer template for the corresponding test case. For each test case, print one integer — the number of positive (strictly greater than $0$) integers that match the template. Input The first line contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Each test case consists of one line containing the string $s$ ($1 \le |s| \le 5$) consisting of digits and/or question marks — the integer template for the corresponding test case. Output For each test case, print one integer — the number of positive (strictly greater than $0$) integers that match the template. 8 ?? ? 0 9 03 1??7 ?5? 9??99 90 9 0 1 0 100 90 100

6