루미 알고리즘

#1401플래티넘Magic Show

PO 2016 훈련 캠프코딩출제 Johan Sannemo영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Mårten the Magician is currently performing in a magnificent magic competition. The show consists of N rounds. In each round, Mårten uses his magic to perform one of two tricks: either he makes some number x rabbits appear, or he sabotages his opponents' tricks by making some number y of their rabbits disappear. He can also choose to do neither.

For each rabbit Mårten makes appear or disappear, he must use 1 magick. In the beginning of the show, Mårten has K magicks. When he has run out of magicks, he can no longer perform a trick.

The scoring of the competition is easy. In the i:th round, let

S_i = x if Mårten made x rabbits appear -y if Mårten made y rabbits disappear 0 if Mårten didn't perform a trick

In round i, if S_i is in the interval [L[i], R[i]] where L[i] and R[i] are integers specific to the round, he gets |S_i - (L[i] + R[i])/2| points. If S_i is outside this interval, Mårten gets 0 points. Note that Mårten cannot perform his magic on fractional rabbits, thus S_i will always be an integer.

Mårten's total score in the competition is the sum of scores among all the rounds. What is the maximum score Mårten can get if he performs optimally?

Example

Consider a competition with N = 4 rounds, where Mårten has K = 5 magicks at the start of the show. The round intervals are [3, 5] for the first round, [-2, 2] for the second round, [-2, 0] for the third round, and [2, 6] for the last round.

The optimal play from Mårten is then to do nothing in the first round (0 points), remove two rabbits in the second (|-2 - 0| = 2 points), do nothing in the third round (|0 - (-1)| = 1 point), and create 2 rabbits in the last round (|2 - 4| = 2 points).

This totals 0 + 2 + 1 + 2 = 5 points, which is the best possible score. Note that there are several optimal strategies in the example. In total, he used 0 + 2 + 0 + 2 = 4 magicks, leaving an unused magick after the last round.

Task

Given all the rounds of the competition, you are to determine the maximum score Mårten can get, and construct instructions for him.

You should implement the function magic_score(N, K, L, R).

• magic_score(N, K, L, R) - this function will be called exactly once by the judge.

  • N: the number of rounds in the competition.
  • K: the amount of magicks Mårten has in the beginning of the show.
  • L: an array with N elements, containing the values L[i] as descriped in the task.
  • R: an array with N elements, containing the values R[i] as descriped in the task.
  • -1000000 ≤ L[i] ≤ R[i] ≤ 1000000
  • L[i] + R[i] is even
  • The function should return the maximum score Mårten can obtain.

Additionally, you should call the function trick(X) to tell Mårten what he should do in each round.

• trick(X) - this function should be called by your program once for every round. The i:th call should give the instruction to Mårten in the i:th round if Mårten wants to play optimally.

  • X: this parameter should give the value S_i of each of Mårten's rounds. If Mårten should add rabbits, this value should be the number of rabbits Mårten should add. If he should remove rabbits, it should be the negative value of the number of rabbits he removes. If he should not do any trick in the round, the value should be 0.
  • The function has no return value.

A code skeleton containing the function to be implemented, together with a sample grader, can be found at http://progolymp.se/uploads/kattis-attachments/magic.zip.

Subtasks

The problem consists of a number of subtasks. Each subtask gives some amount of points, and to pass the subtask you must pass all the test cases in the subtask.

For each subtask, if the return value of magic_score(N, K, L, R) is correct, but your calls to trick(X) is not a valid sequence giving the maximum score, you will get 75% of the score of the subtask. This will show up as Partially correct on these test cases. Note that you always must make exactly N calls to trick(X), even if the sequence is incorrect.

SubtaskPointsLimits
120N ≤ 100, K ≤ 100
220N ≤ 1000, K ≤ 1,000 L[i] ≥ 0
320N ≤ 1000, K ≤ 1,000, R[i] = 2 + L[i]
440N ≤ 1000, K ≤ 1,000

Input format

The sample judge reads input in the following format:

  • line 1: N K
  • line 2: L[0] L[1] .. L[N - 1]
  • line 3: R[0] R[1] .. R[N - 1]

Output format

The sample judge writes output in the following format:

  • line 1: the return value of magic_score(N, K, L, R) on a line
  • line 2: N integers, the values given from the calls to trick(X) in order.

예제

예제 1

입력
4 5
3 -2 -2 2
5 2 0 6
출력
5
0 2 0 2

출처 표기

출처: Programmeringsolympiaden 2016년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.