AlgoChief Sprint Round 4
A. Least Penalty
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob are playing a game of cards.

You have a total of $$$n$$$ cards to be distributed among each other. You are also given a parameter $$$k$$$

Alice and Bob are given the cards in a particular order, and they have to play the game in that particular order only.

Example : if Bob gets = $$$[3, 2, 1]$$$, it means he needs to play $$$3$$$ first, then $$$2$$$, then $$$1$$$.

If the sum of values of Alice And Bobs Cards on a particular round exceed $$$k$$$, that means you have distributed the cards unfairly.

You can shuffle the cards in any order you want, you have to make sure that least number of pairs on a current round have sum exceeding $$$k$$$

It is guaranteed that $$$n$$$ is even

If there are multiple ways of shuffling cards with same minimum pairs, it is accepted

Input

The first line of input contains 2 integers, $$$n$$$ and $$$k$$$ $$$(1 \leq n \leq 10^5)$$$ $$$(1 \leq k \leq 10^9)$$$

The second line of input contains $$$n$$$ integers, the card values $$$(1 \leq a[i] \leq 10^9)$$$

Output

On the First line you need to print the minimum number of rounds such that the sum of Alice and Bobs Card Values are exceeding $$$k$$$

On the Second line you need to print $$$n / 2$$$ values, Representing Alice's Cards

On the Third line you need to print $$$n / 2$$$ values, Representing Bob's Cards

Example
Input
6 6
1 2 3 4 5 6
Output
1
6 5 4  
3 1 2
Note

In the Sample Testcase, only the first pair $$$(6 + 3)$$$ is exceeding $$$6$$$, rest $$$2$$$ pairs are $$$ \lt = k$$$.

B. Maximum Combo
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are playing a game where you have $$$n$$$ portals.

  1. Each Portal is labelled from $$$1$$$ to $$$n$$$
  2. You are Starting on Portal $$$1$$$
  3. If you are currently on Portal $$$i$$$, you can jump on Portal $$$j$$$ only if $$$j$$$ > $$$i$$$
  4. You will receive $$$i * j$$$ points for jumping from Portal $$$i$$$ to Portal $$$j$$$

You want to find that for a given $$$n$$$, what is the maximum points you can recieve if you jump optimally.

Since this score might be very large, find the answer modulo $$$998244353$$$

Input
  1. First line consists of a single integer $$$t$$$, number of testcases $$$(1 \leq t \leq 10^4)$$$
  2. For each test, a single integer is present $$$n$$$, the number of portals $$$(1 \leq n \leq 10^6)$$$
Output

Each test consists of a single integer as output, the maximum points

Example
Input
10
1
2
3
4
5
6
7
8
9
10
Output
0
2
3
10
10
21
21
42
42
55

C. F1 Glory
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are interviewing for the role of Strategist in a F1 Team. To impress the team principal, you need to write a program giving the most optimal strategy to win an F1 Race.

The main motive of a race is to complete the race in as minimal time as possible. You need to build a tire strategy to help that.

F1 has 3 types of tires, Lets call them Soft, Medium and Hard, each tire has different age and speed.

  1. Soft Tires have the best speed but they wear off quickly
  2. Medium Tires have medium speed and medium wear
  3. Hard Tires have lowest speed but very long lasting

You are given fresh speed of all 3 tires, namely $$$c1$$$, $$$c2$$$, $$$c3$$$

Lets say your tires are $$$x$$$ laps old

  1. Lap time with soft tire = $$$c1 + 3x$$$
  2. Lap time with medium tire = $$$c2 + 2x$$$
  3. Lap time with hard time = $$$c3 + x$$$
Input

The only line of input has 7 integers, $$$laps$$$, $$$c1$$$, $$$c2$$$, $$$c3$$$, $$$stop$$$, $$$minstop$$$, $$$maxstop$$$

  1. $$$lap$$$ = Number of laps in the race $$$(1 \leq n \leq 100)$$$
  2. $$$c1$$$ = Fresh Speed of Soft Tire $$$(1 \leq c1 \leq 100)$$$
  3. $$$c2$$$ = Fresh Speed of Medium Tire $$$(1 \leq c2 \leq 100)$$$
  4. $$$c3$$$ = Fresh Speed of Hard Tire $$$(1 \leq c3 \leq 100)$$$
  5. $$$stop$$$ = Time Taken for a Pitstop $$$(1 \leq stop \leq 20)$$$
  6. $$$minstop$$$ = Minimum Number of Pitstops to be done $$$(0 \leq mn \leq 3)$$$
  7. $$$maxstop$$$ = Maximum Number of Pitstops to be done $$$(0 \leq mx \leq 3)$$$
Output
  1. On the First Line u need to print two integers, first the minimum time to complete the race, and second the starting tire that you have chosen
  2. On the Second Line u need to print a single integer $$$k$$$ $$$(mn \leq k\leq mx)$$$, the number of pitstops u decide to perform
  3. Then follow $$$k$$$ lines, each line contain 2 integers, the first is the lap number where u are pitting, the second is the tire you are putting on

If you have multiple strategies with same minimum time, they are accepted

Examples
Input
5 1 2 3 1 0 2
Output
13 1
2
2 1
4 1
Input
5 1 2 3 1 0 1
Output
18 1
1
3 1
Input
80 1 12 20 20 0 3
Output
2320 1
3
15 1
30 3
55 3
Note

Lets take the First Example

  1. Starting Tire = Soft
  2. Lap 1 -> 1s
  3. Lap 2 -> 4s
  4. Lap 2 -> Pit and take fresh softs -> 1s
  5. Lap 3 -> 1s
  6. Lap 4 -> 4s
  7. Lap 4 -> Pit and take fresh softs -> 1s
  8. Lap 5 -> 1s
  9. Total Time = 1 + 4 + 1 + 1 + 4 + 1 + 1 = 13s