Untitled
unknownplain_text
a month ago
9.3 kB
2
Indexable
Never
[Problem Description]
You are required to develop a puzzle game that promotes intellectual development in children.
One piece of the puzzle consists of 5 bars. The heights of the bars may vary from 1 to 10.
Each piece is made by standing up the bars vertically and then attaching them together.
For example, (a) in [Fig. 1] shows a piece made with the 5 bars of 3, 5, 4, 2, and 3.
[Fig. 1] shows pieces of different shapes.
[Fig. 1]
This game has simple rules as follows:
For each turn, given a piece made with 5 bars and a task that can be performed using the piece. The given task is one of the following:
1) Build a wall using a piece
If there is no wall, stand the given piece vertically to create one.
If there is a wall, attach the given piece to the right end of the wall to extend it.
[Fig. 2] shows the latter.
[Fig. 2]
2) Find and remove a part of the wall, which fits a given piece
A given piece and a part of the wall are perfectly fitted together if:
A perfect rectangle, which is 5 wide, can be made by rotating the given piece 180 degrees and fitting it into the part of the wall. When making such a rectangle, the same widths of the part and the piece must be used, which is 5.
(a) in [Fig. 3] shows that the piece and the part are perfectly fitted together.
On the other hand, (b), (c), and (d) show that the piece does not perfectly fit the part: in (b), the piece and the part do not make a perfect rectangle. In (c) and (d), the piece and the part make a perfect rectangle, but the width of the part used is 4, not 5.
[Fig. 3]
Upon request to find a part of the wall that fits the given piece, the following steps take place:
Move from the very right to the left of the wall by bar, and
search for a part of the wall with which the given piece can make a perfect rectangle.
If such a part is found, locate the index of the rectangle.
After removing the rectangle,
fill the gap by attaching the divided parts together to make one connected wall.
[Fig. 4] shows an example.
[Fig. 4]
In Step1, rotate the given piece 180 degrees.
In Step2, move from the right to the left by bar and search for a part of the wall that fits the rotated piece.
In this example, both (a) and (b) are candidates, but (a) is selected because it is found first.
In Step3, fit the piece into the part of the wall to make a perfect rectangle, and locate the index of the rectangle.
The index of the rectangle means “the very left bar of the rectangle is located in what place in the wall from the left.”
In this example, the index of the rectangle is “12.”
In Step4, remove the rectangle and fill the gap to make one wall.
[Fig. 5] shows when two pieces are given and the steps take place accordingly after [Fig. 4].
[Fig. 5]
The number of pieces to be searched is up to 15,000 for each game, but it is guaranteed that the number of pieces that perfectly fit the wall is up to 500.
Implement each required function by referring to the following API description.
※ The function signature below is based on C/C++. As for Java, refer to the provided Solution.java and UserSolution.java.
The following is the description of API to be written in the User Code.
void init()
This function is called in the beginning of each test case.
The length of the wall is 0.
void makeWall(int mHeights[5])
This function builds or extends a wall using a given piece.
Given an array named mHeights which contains information on the respective heights of the 5 bars of the piece.
Parameters
mHeights[]: an array that contains the respective heights of the 5 bars of the piece
(1 ≤ mHeights[i] ≤ 10, 0 ≤ i ≤ 4)
int matchPiece(int mHeights[5])
This function searches for a part of the wall which fits a given piece and returns the index of the rectangle.
Given an array named mHeights which contains information on the respective heights of the 5 bars of the piece.
If a perfect rectangle is made, it is removed. If there is no rectangle made, return -1.
It is guaranteed that the number of rectangles made is less or equal to 500 for each test case.
Parameters
mHeights[]: an array that contains the respective heights of the 5 bars of the piece
(1 ≤ mHeights[i] ≤ 10, 0 ≤ i ≤ 4)
Returns
The index of the rectangle; -1 if there is no rectangle made.
[Example 1]
Order
Function
return
Figure
1
init()
2
makeWall([1, 2, 2, 1, 1])
3
makeWall([2, 2, 2, 2, 2])
4
makeWall([4, 3, 4, 4, 3])
5
makeWall([3, 3, 5, 4, 2])
6
matchPiece([2, 2, 1, 1, 2])
12
[Fig. 4]
7
matchPiece([3, 3, 2, 2, 3])
1
[Fig. 5](a), (b)
8
matchPiece([1, 3, 2, 4, 4])
4
[Fig. 5](c), (d), (e)
9
makeWall([3, 3, 2, 2, 2])
[Fig. 6] (a)
10
makeWall([2, 2, 2, 2, 3])
[Fig. 6] (b)
11
matchPiece([2, 2, 3, 1, 3])
3
[Fig. 6] (c)
12
matchPiece([4, 1, 2, 2, 2])
-1
13
matchPiece([1, 1, 1, 1, 1])
5
[Fig. 7] (a)
14
matchPiece([7, 8, 8, 8, 8])
1
[Fig. 7] (b)
15
matchPiece([2, 1, 2, 1, 2])
-1
At Order #1, the puzzle game starts.
From Order #2 to #5, a wall is built using the given pieces.
Following the steps explained above, 12, 1, and 4 are returned respectively at Order #6, 7, and 8. (Refer to [Problem Description] for [Fig. 4] and [Fig. 5].)
At Order #9 and #10, the wall is extended as shown in (a) and (b) in [Fig. 6].
At Order #11, as shown in (c) in [Fig. 6], the rectangle, which is made by fitting the piece into the part of the wall, is removed.
[Fig. 6]
At Order #12, -1 is returned since no rectangle is made.
The width of the wall then becomes 0 since the rectangles are made and removed at Order #13 and #14, as shown in [Fig. 7].
At Order #15, -1 is returned since there is no wall left.
[Fig. 7]
[Constraints]
1. The function init is called in the beginning of each test case.
2. For each test case, the sum of calls of the functions makeWall and matchPiece is up to 20,000.
3. For each test case, the function matchPiece can be called up to 15,000.
4. It is guaranteed that the number of rectangles, which are made by the function matchPiece, is less or equal to 500 for each test case.
5. Even if there is no wall (or the length of a wall is 0), matchPiece can still be called.
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#define BAR_LEN 5
#define CMD_INIT 100
#define CMD_MAKEWALL 200
#define CMD_MATCHPIECE 300
extern void init();
extern void makeWall(int mHeights[BAR_LEN]);
extern int matchPiece(int mHeights[BAR_LEN]);
static bool run()
{
int N;
int cmd;
int heights[BAR_LEN];
int ret = 0;
int ans = 0;
scanf("%d", &N);
scanf("%d", &cmd);
bool okay = false;
if (cmd == CMD_INIT)
{
init();
okay = true;
}
for (int turn = 0; turn < N-1; turn++)
{
scanf("%d", &cmd);
for (int i = 0; i < BAR_LEN; i++)
{
scanf("%d", &heights[i]);
}
switch (cmd)
{
case CMD_MAKEWALL:
makeWall(heights);
break;
case CMD_MATCHPIECE:
ret = matchPiece(heights);
scanf("%d", &ans);
if (ans != ret)
okay = false;
break;
}
}
return okay;
}
int main()
{
setbuf(stdout, NULL);
//freopen("sample_input.txt", "r", stdin);
int T, MARK;
scanf("%d %d", &T, &MARK);
for (int tc = 1; tc <= T; tc++)
{
int score = run() ? MARK : 0;
printf("#%d %d\n", tc, score);
}
return 0;
}
#include <set>
#include <unordered_map>
using namespace std;
struct node{
int
};
int calcKeyToHash(int mHeights[5]){
int min=0;
int ans=0;
for(int i=0;i<5;i++) ans=ans*11+mHeights[i]-min;
return ans;
}
unordered_map<int, set<node*, compare>> comfort;
void init()
{
}
void makeWall(int mHeights[5])
{
}
int matchPiece(int mHeights[5])
{
return -1;
}
25 100
15
100
200 1 2 2 1 1
200 2 2 2 2 2
200 4 3 4 4 3
200 3 3 5 4 2
300 2 2 1 1 2 12
300 3 3 2 2 3 1
300 1 3 2 4 4 4
200 3 3 2 2 2
200 2 2 2 2 3
300 2 2 3 1 3 3
300 4 1 2 2 2 -1
300 1 1 1 1 1 5
300 7 8 8 8 8 1
300 2 1 2 1 2 -1
21
100
200 3 8 9 9 9
200 8 4 4 5 1
200 7 9 3 3 5
300 2 8 4 5 5 7
300 5 7 10 4 6 -1
300 4 10 5 7 4 -1
200 6 7 1 6 7
200 8 2 2 1 10
300 1 5 4 8 8 -1
300 9 7 6 1 5 -1
300 9 7 3 3 1 -1
200 2 6 3 4 5
200 5 10 7 5 1
200 6 3 2 6 8
300 8 10 10 7 1 -1
200 6 9 5 3 1
200 6 3 9 3 1
300 6 5 2 7 3 29
300 3 2 8 6 2 -1
300 2 7 7 8 9 23