[Solution] Pizza Delivery Solution Round E 2022 | Kick Start 2022

Problem

Ada delivers pizzas in a city consisting of a grid of N$N$ horizontal and N$N$ vertical streets, heading from North to South and from West to East, respectively, and numbered from 1$1$ to N$N$. The top left street crossing of the grid is (1,1)$(1,1)$.

Today, Ada has to deliver P$P$ pizzas, one for each of P$P$ customers. Each customer lives at a different street crossing; the k$k$-th customer lives at street crossing (Xk,Yk)$({\mathbf{X}}_{\mathbf{k}},{\mathbf{Y}}_{\mathbf{k}})$ and will pay Ada Ck${\mathbf{C}}_{\mathbf{k}}$ coins after the pizza is delivered to their location.

Ada starts at her pizza restaurant at (Ar,Ac)$({\mathbf{A}}_{\mathbf{r}},{\mathbf{A}}_{\mathbf{c}})$ with 0$0$ coins and carrying P$P$ pizzas. Her goal is to deliver all of the pizzas within M$M$ minutes. She is free to take any path she likes around the city and finish deliveries anywhere, as long as she manages to drop off all P$P$ pizzas to their respective customers within M$M$ minutes. It takes one minute to walk between two adjacent street crossings, and takes no additional time to drop off a pizza at a customer's location. There are some additional rules and constraints to note:

• Ada is not allowed to go outside the grid.
• No customer lives at the same street crossing as the pizza restaurant Ada starts her trip.
• At any point in time Ada can choose to stay in her current location and not move.
• Ada can also choose not to deliver a pizza when at a customer's location.

Formally, if Ada is currently at street crossing (i,j)$(i,j)$, where i$i$ is i$i$-th row from the top, and j$j$ is j$j$-th column from the left, she can decide to do any of the following as long as she does not go outside the grid:

• Go north, she reaches street crossing (i−1,j)$(i-1,j)$.
• Go east, she reaches street crossing (i,j+1)$(i,j+1)$.
• Go west, she reaches street crossing (i,j−1)$(i,j-1)$.
• Go south, she reaches street crossing (i+1,j)$(i+1,j)$.
• Stay at street crossing (i,j)$(i,j)$.

The city has a unique toll system in place for using the streets. There is a toll for using each street and the toll depends on Ada's current number of coins and the direction in which she is travelling to. The toll function is defined for every cardinal direction (North, East, West, South) separately. The toll function Fd$F_d$ for d∈{North,East,West,South}$d\in \{North,East,West,South\}$ returns the amount of coins Ada will have after moving in the direction d$d$ and is defined as follows:

Fd$F_d$ = c$c$ OPd$\mathbf{O}{\mathbf{P}}_{\mathbf{d}}$ Kd${\mathbf{K}}_{\mathbf{d}}$

where c$c$ is the current number of coins that Ada has and OPd$\mathbf{O}{\mathbf{P}}_{\mathbf{d}}$ is an operator and Kd${\mathbf{K}}_{\mathbf{d}}$ is a fixed positive integer. The allowed operators are:

• + (addition),
• - (subtraction),
• * (multiplication),
• / (integer division).

For example, we can have FNorth$F_{North}$ = c$c$ + 3$3$, FEast$F_{East}$ = c$c$ * 4$4$, FWest$F_{West}$ = c$c$ - 4$4$, FSouth$F_{South}$ = c$c$ / 2$2$. That means that if Ada moves North one street then she will have 3$3$ more coins; if Ada moves East then Ada's coins will quadruple; if Ada moves West then she loses 4$4$ coins; and if Ada moves South then her coins are halved.

All divisions are integer divisions and are computed by using floor function. For example, −14=⌊−14⌋=−1$\frac{-1}{4}=\lfloor \frac{-1}{4}\rfloor =-1$. Notice that Ada is allowed to have a negative number of coins. Note that the tolls might actually give Ada coins.

Find out if Ada can deliver all the P$P$ pizzas in M$M$ minutes and, if so, the maximum number of coins Ada could have after M$M$ minutes.

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow.

The first line of each test case contains N$N$, P$P$, M$M$, Ar${\mathbf{A}}_{\mathbf{r}}$, Ac${\mathbf{A}}_{\mathbf{c}}$ denoting the grid size, the number of pizzas to deliver, the minutes in which all pizzas should be delivered, and the coordinates of the street crossing at which Ada starts respectively.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The next four lines denote the toll functions for North, East, West, South respectively. Each of these lines contains OPd$\mathbf{O}{\mathbf{P}}_{\mathbf{d}}$, denoting the operator (one of +, -, *, /), and Kd${\mathbf{K}}_{\mathbf{d}}$, the positive integer used in toll function.

The following P$P$ lines describe the customers. Each of these lines consists of three integers Xk${\mathbf{X}}_{\mathbf{k}}$, Yk${\mathbf{Y}}_{\mathbf{k}}$, Ck${\mathbf{C}}_{\mathbf{k}}$ denoting the row number of the k$k$-th customer from the top of the grid, the column number of the k$k$-th customer from the left of the grid, and the amount of coins they pay on delivery, respectively.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is IMPOSSIBLE if all pizzas cannot be delivered within M$M$ minutes; otherwise, the output should be the maximum number of coins Ada can have after M$M$ minutes (which could be negative).

Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
1≤N≤10$1\le \mathbf{N}\le 10$.
1≤M≤20$1\le \mathbf{M}\le 20$.
1≤Ar,Ac≤N$1\le {\mathbf{A}}_{\mathbf{r}},{\mathbf{A}}_{\mathbf{c}}\le \mathbf{N}$.
1≤Xk,Yk≤N$1\le {\mathbf{X}}_{\mathbf{k}},{\mathbf{Y}}_{\mathbf{k}}\le \mathbf{N}$, for all k$k$.
1≤Ck≤4$1\le {\mathbf{C}}_{\mathbf{k}}\le 4$, for all k$k$.
1≤Kd≤4$1\le {\mathbf{K}}_{\mathbf{d}}\le 4$, for all d$d$.
OPd$\mathbf{O}{\mathbf{P}}_{\mathbf{d}}$ is one of (+, -, *, /), for all d$d$.
It is guaranteed that no customer lives at the same street crossing as the pizza restaurant Ada starts her trip, i.e. (Xk,Yk)≠(Ar,Ac)$({\mathbf{X}}_{\mathbf{k}},{\mathbf{Y}}_{\mathbf{k}})\ne ({\mathbf{A}}_{\mathbf{r}},{\mathbf{A}}_{\mathbf{c}})$, for all 1≤k≤P$1\le k\le \mathbf{P}$.
It is guaranteed that every customer lives at a different street crossing, i.e. (‘Xk,Yk)≠(Xl,Yl)$(‘X_k,{\mathbf{Y}}_{\mathbf{k}})\ne ({\mathbf{X}}_{\mathbf{l}},{\mathbf{Y}}_{\mathbf{l}})$, for all 1≤k,l≤P$1\le k,l\le \mathbf{P}$ and k≠l$k\ne l$.

Test Set 1

P=0$\mathbf{P}=0$.

Test Set 2

0≤P≤10$0\le \mathbf{P}\le 10$.

Sample

Note: there are additional samples that are not run on submissions down below.

In Additional Sample Case #1, Ada started at street crossing (1,3)$(1,3)$ with 0$0$ coins. Ada can receive maximum coins by following the steps below:

• Go west to (1,2)$(1,2)$. Using the toll function for moving west Fwest$F_{west}$ = c$c$ * 1$1$, Ada now has 0∗1=0$0\ast 1=0$ coins.
• Do not deliver the pizza at (1,2)$(1,2)$ yet, and go south to (2,2)$(2,2)$. Using the toll function for moving south FSouth$F_{South}$ = c$c$ / 4$4$, Ada now has 0/4=0$0/4=0$ coins.
• Go north to (1,2)$(1,2)$. Using the toll function for moving north FNorth$F_{North}$ = c$c$ + 4$4$, Ada now has 0+4=4$0+4=4$ coins.
• Deliver the pizza at (1,2)$(1,2)$. Ada receives 4$4$ additional coins for delivering the pizza. Ada has a total of 8$8$ coins in the end.

In Additional Sample Case #2, Ada cannot deliver two pizzas in one minute, so the output is IMPOSSIBLE.

In Additional Sample Case #3, Ada started at street crossing (1,3)$(1,3)$ with 0$0$ coins. Ada can receive maximum coins by following the steps below:

• Go west to (1,2)$(1,2)$. Using the toll function for moving west FWest$F_{West}$ = c$c$ - 3$3$, Ada now has 0−3=−3$0-3=-3$ coins.
• Go south to (2,2)$(2,2)$. Using the toll function for moving south FSouth$F_{South}$ = c$c$ / 4$4$, Ada now has −3/4=⌊−34⌋=−1$-3/4=\lfloor \frac{-3}{4}\rfloor =-1$ coins.
• Deliver the pizza at (2,2)$(2,2)$. Ada receives 2$2$ additional coins for delivering the pizza. Ada has a total of 1$1$ coins in the end.