Untitled
unknown
plain_text
2 years ago
19 kB
10
Indexable
Price Tag
Cho một hình vuông NxN ô nhỏ (5 ≤ N ≤ 9), mỗi ô chứa 1 số từ 0 – 9.
Nhiệm vụ cần làm là cắt hình vuông lớn thành (N+1) hình có kích thước 1x(N-1). Mỗi hình kích thước 1x(N-1) bao gồm (N-1) chữ số và tạo thành 1 số nguyên (N-1) chữ số (đọc từ trái qua phải hoặc từ trên xuống dưới tùy theo phương án cắt).
Sau khi có được các miếng cắt, tính tổng các số thu được (chỉ tính các số có N-1 chữ số, ô còn sót lại sẽ không được tính vào tổng).
Hãy tìm ra phương án cắt có tổng thu được lớn nhất.
Input
Input sẽ chứa một hoặc nhiều test cases
Dòng đầu là số lượng test case T (T ≤ 50)
Dòng đầu tiên của mỗi test cases là kích thước hình vuông N (5 ≤ N ≤ 9)
N dòng tiếp theo lần lượt là giá trị trong các ô nhỏ của hình vuông lớn.
Output
Với mỗi test case, in ra tổng số lớn nhất thu được
Sample
Input
2
5
1 0 3 5 6
4 5 3 7 9
7 2 2 6 7
3 4 7 8 8
9 5 1 6 3
6
3 4 5 6 8 6
3 5 6 7 7 8
3 3 3 3 3 5
1 2 5 6 4 2
3 3 5 5 5 7
8 5 3 6 9 9
Output
#1 35000
#2 72000
Ngã Tư Đường- Hồ Quang Hiếu
Một khu đô thi được sắp xếp theo hình ô bàn cờ vuông với kích thước NxN có 15<=N<=100. Chủ thầu muốn mở rộng thêm đường để giảm ùn tắc giao thông bằng cách với mỗi ngã ba sẽ được mở thêm đường để thành ngã tư. Mô tả như hình vẽ sau đây (Màu trắng là đường, màu vàng là nhà ở):
Năm 1
Năm 2
Năm 3
Trong cùng một năm các con đường mới xây sẽ được cắt qua nhau.
Hãy tính số năm cần thiết để chủ đầu tư có thể mở được tất cả các ngã ba thành ngã tư.
Input:
Dòng đầu tiên là tổng số testcase 1<T<50;
Dòng tiếp theo là kích thước mảng N;
Tiếp theo là mảng gồm 0( đường đi) và 1( nhà ở).
Output:
In ra số năm theo dạng: #(số tc) (số năm)
2
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 1 1 1 1 1 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 1 1 1 1 0
0 0 0 0 1 1 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 0 0 0 0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 1 0 1 1 1 0 1 1 1 0
0 1 0 1 1 1 0 0 0 0 0 0 0 0 0
0 1 0 1 1 1 0 1 1 1 1 1 1 1 0
0 0 0 0 1 1 0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 0 1 1 1 1 1 1 1 0
0 1 1 0 0 0 0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 0 1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Netharax - The Black Horse of Abaddon
※ The act of posting and sharing problems & solutions tothe outside of the company online/offline is strictly prohibited.Problems of the SW Expert Academy are only open to Samsung Electronicsemployees.
[Restrictions]
Execution Time 4 sec (C/C++) / 5 sec (Java) for 10 test cases combined
Memory Limit Maximum 256 MB is available for heap and static memory combined (Note: Maximum 1MB can be used for stack)
[Problem Description]
Abaddon - the Death Knight - Lord of Avernus - had a black horse named Netherax, which gives him power. This horse can go anywhere, across the world, through any dangerous terrain. Netharax stayed by Abaddon from war to war, from battle field to battle field in "Defense of the Ancients".
One day, Abaddon lost his way in Under Lord Play Ground, where the rules of unknown forces covered all places and restrained their power. With the abilities and experiences trained through so many battles in the past, Abaddon eventually saw through the rules of this place.
The terrain was divided into squares like a chess board. All the map included long hallways with exit gates at the end. In each square, there was a pillar hidden with mysterious things, maybe a treasure or maybe a trap.
When he tried to move, he found out that Netherax could not move as his will... Some pillars showed faint light and seemed like he can only go there.
From the pillar where he stood at, there were total 4 pillars he can move to:
- The pillar is 2 steps away from the left in the next row
- The pillar is 2 steps away from the right in the next row
- The pillar next to the right side in 2 rows above
- The pillar next to the left side in 2 rows above
1 6 6 6 6 6 6 6 6
2 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0
1 2 3 4 5 6 7 8
In order to escape this evil place, Abaddon decided to ask for help from IO – supercomputer. Abaddon, thanks to his acquaintance with "Keeper of the Light", clarified the value of the item existing in every pillar in this corridor.
His data for IO is as follows:
15 8 4 (NxM: size of corridor, X: column position of Abaddon and Netherax at the start of the corridor)
The next N lines (Abaddon described the corridor by using numbers)
6 6 6 6 6 6 6 6
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0: Stone pillar contains the item 0
1: Stone pillar contains the item 1
2: Stone pillar contains the item 2
3: Stone pillar contains the item 3
4: Stone pillar contains the item 4
5: Stone pillar contains the item 5
6: Stone pillar contains teleport gate
Item 0: Iron Branch
Item 1: Boot of speed
Item 2: Hyper Stone
Item 3: Dagon
Item 4: Mask of Madness
Item 5: Roshan's Aegis
If Netharax moves to any position, that position’s effect will affect him.
If Netharax reaches pillar with item 4, he will go insane. Consequently, Abaddon will lose his mind and then lose the game.
But if there is Roshan's Aegis, Abaddon can stay alive by its resurrection effect (The whole map has only 1 Roshan's Aegis in maximum and can help Abaddon 1 time only)
Pick up the Boot of speed, Abaddon and Netharax will get 10 points
Pick up 3 Boots of speed, Abaddon and Netharax will combine into Phase Boot and get 50 points
Pick up 6 Boots of speed, Abaddon and Netharax will combine to be BoT (Boot of Travel) and get 150 points
Pick up Hyper Stone, Abaddon and Netharax will get 30 points
Pick up 2 Hyper Stones, Abaddon and Netharax will combine to become Moon Shard and get 100 points
Pick up Dagon, Abaddon and Netharax will get 20 points
Pick up 2 Dagons, Abaddon and Netharax will get 50 points
Pick up 3 Dagons, Abaddon and Netharax will get 100 points
Pick up 4 Dagons, Abaddon and Netharax will get 200 points
Pick up 5 Dagons, Abaddon and Netharax will get 500 points
(Picking more Dagon does not increase points)
Please help Abaddon go through the corridor to reach the destination in the position of portal No. 6 with MAX score(teleport back to the arena "Defense of the Ancients")
Sample Input:
10 // Number of testcase:
15 8 4 // N M X: Row / Col / Abaddon (5 <=N <= 20; 4<=M<=10; 1<=X<=M)
// Next N row, each row have M number (value from 0-6)
Output:
#1 71
#2 1106
#3 1751
Adversiment Schedule
A shop need to display the advertisement 3 times a day.
However, they only has 1 electric board to display the advertisement, hence they should select the time to display advertisements so that visitors can watch them as much as possible.
When visitors watch advertisement, they can get points which calculated as below :
1. Three Ads have length L1, L2, L3 and the points a person can get after watched them P1, P2, P3.
2. A visitor can get the point of a Ads only when he/she watch the Ads fully (from beginning to the end of that Ads )
3. When a visitor watch more than one Ads and also get the point for them, only the Ads with highest point will be given to that person.
4. Only one Ads can be displayed on electric board at a time (But the next Ads can be displayed right after the previous one ended)
Given the length of each Ads L1, L2, L3 and the point gained for them P1, P2, P3, the arrival time of each visitor into the shop and the time duration that he/she stay in the shop, write a program to select advertisement display time so that as many points as possible can be given to visitors. Print out the total sum of points that the visitors can get.
Ex: There are 7 visitors go to the shop with the arrival time and staying duration as below
Visitor 1 Visitor 2 Visitor 3 Visitor 4 Visitor 5 Visitor 6 Visitor 7
Arrival Time 2 6 3 7 1 2 1
Time Duration 2 4 3 2 1 1 10
Length Point(s)
Advertisement 1 1 1
Advertisement 2 2 2
Advertisement 3 3 3
Assuming that Ads1 is displayed at time 2, Ads2 at time 7 and Ad3 at time 3, the visitors will watched the ads as below schedule :
Visitor 1 Visitor 2 Visitor 3 Visitor 4 Visitor 5 Visitor 6 Visitor 7
Ads 1 Watch - - - - Watch Watch
Ads 2 - Watch - Watch - - Watch
Ads 3 - - Watch - - - Watch
(Note that visitor 1 didn't watch Ads3 fully, so the point of Ads3 is not given to him)
The points that each visitor can get from watching Ads is show as below :
Visitor 1 Visitor 2 Visitor 3 Visitor 4 Visitor 5 Visitor 6 Visitor 7
Ads 1 1 - - - - 1 1
Ads 2 - 2 - 2 - - 2
Ads 3 - - 3 - - - 3
Total 12 Points 1 2 3 2 0 1 3
(Visitor 7 watched all Ads fully, however he can only get the highest of one Ads - which is 3 points of Ads 3)
There are many way to arrange the display time, and the method above give us the maximum sum of points which visitors can get, so the answer in this case is 12.
[Constraints]
- The number of visitors N (1 ≤ N ≤ 50)
- The arrival time Ai, the time duration Di of each visitor and the length of each Ads L1, L2, L3 are given as integers (1 ≤ Ai, Di, L1, L2, L3 ≤ 50)
- Ai + Di ≤ 50
- L1 + L2 + L3 ≤ 50
- The starting time of an Ads : 1 ≤ starting time ≤ 50
- P1, P2, P4 are integers (1 ≤ P1, P2, P3 ≤ 1000)
[Input]
The 1st line given T - the total number of TC (T ≤ 50)
In each TC :
- The 1st line contains N, L1, L2, L3, P1, P2, P3 in this order
- The next N lines : each line gives the arrival time Ai and time duration Di of each visitor
5 // Number of test cases T=5
7 1 2 3 1 2 3 // Test case 1 N=7, L1=1, L2=2, L3=3, P1=1, P2=2, P3=3
2 2 // A1 = 2, D1 = 2
6 4 // ...
3 3
7 2
1 1
2 1
1 10
4 3 2 1 6 4 3
1 5
1 3
2 4
2 2
...
[Output]
Out put the maximum sum of points that visitors can get from watching advertisements.
Case #1
12
Case #2
18
Case #3
17
Case #4
16
Case #5
17998
//#include <stdio.h>
//
//typedef struct mx{
// int L; //length
// int P; //point
//} mx;
//
//int ad[60];
//int cus[52][52];
//mx adInput[3];
//
//void generate(int i){
//
// for(int k=0; k<50; ++k){
// a[k] =
//
// }
//
//}
//
//int main(){
//
// int T;
// int maxPoint;
// int N;
// int atN, longN;
// int in, ilongN;
//
// freopen("sample_input.txt", "r", stdin);
// scanf("%d", &T);
// for(int icase=1;icase<=T;++icase){
//
// /*input*/
// scanf("%d %d %d", &N,
// adInput[0].L,
// adInput[1].L,
// adInput[2].L,
// adInput[0].P,
// adInput[1].P,
// adInput[2].P
// );
//
// for(in=1;in<N;++in){
// scanf("%d %d", &atN, &longN);
// for(ilongN = atN; ilongN<N; ++ilongN){
// cus[in][ilongN] = 1; //has time
// }
// }
//
// /*reset*/
// generate(1);
//
// /*start*/
//
// /*final*/
// printf("#%d %d\n",icase ,maxPoint);
// }
//
// return 0;
//}
#include <stdio.h>
typedef struct mx{
int value; //length
int checked; //point
} mx;
typedef struct mx1{
int value;
int checked;
int L; //length
int P; //point
} mx1;
//mx a[60];
int ad[60];
int cus[50][50];
mx1 adInput[3];
int m[3];
int maxPoint;
int tempPoint;
int getSum(int N, int at, int L){
for(int in=0;in<N;in++){
if(cus[in][at] >= L){
maxPoint += L;
}
}
return maxPoint;
}
int generate(int i){
for(int k=0; k<3; ++k){
if(adInput[k].checked == 0){
adInput[k].checked = 1;
m[i] = k;
tempPoint = getSum(50,k,adInput[k].L);
if(maxPoint <= tempPoint){
maxPoint = tempPoint;
}
if(i==2){
return maxPoint;
}else{
generate(i);
}
adInput[k].checked = 0;
}
}
}
int main(){
int T;
//int maxPoint;
int N;
int atN, longN;
int in, ilongN;
freopen("sample_input.txt", "r", stdin);
scanf("%d", &T);
for(int icase=1;icase<=T;++icase){
/*input*/
scanf("%d %d %d", &N,
adInput[0].L,
adInput[1].L,
adInput[2].L,
adInput[0].P,
adInput[1].P,
adInput[2].P
);
for(in=1;in<N;++in){
scanf("%d %d", &atN, &longN);
for(ilongN = atN; ilongN<N; ++ilongN){
cus[in][ilongN] = longN; //has a LONG time
}
}
for(int k=0;k<3;++k){
adInput[k].checked = 0;
}
/*reset*/
tempPoint = 0;
maxPoint = 0;
int finalPoint = generate(1);
/*start*/
/*final*/
printf("#%d %d\n",icase ,finalPoint);
}
return 0;
}
Reflecting Mirrors
The Samsung S/W Company plans to develop a game using mirrors on a nxn 2-dimensional grid. Each mirror is a two-way mirror and has only two directions as follows.
In the game, when a laser beam starts at (0, 0) in right direction, they need to count the number of times the beam hits a mirror until it hits a wall (boundary) of the grid.
[Example] In the following configuration, the beam hits mirrors 7 times until it hits the upper wall.
For this company, write a program to count the number of times the beam hits a mirror until it hits a wall (boundary) of the grid.
[Constraints]
1. The size n of a 2-dimensional grid is not more than 100. (5 ≤ n ≤ 100)
2. No mirror in (0, 0)
[Input]
The test cases consist of the following format. In the first line, the number of test cases is given. From the next line, each test case is provided in n+ 1 line. In the first line of each test case, n is given. In the next n lines, a nxn 2-dimensional array is given row-by-row, one row per line. If an element of the array is ‘0’, it indicates an empty cell. When it is ‘1’, there is a mirror with [Direction 1] and if it is ‘2’, there is a mirror with [Direction 2] in the corresponding cell.
[Output]
Print out the number of times hits a mirror of the beam that starts at (0, 0), for each test case on a separate line, starting with ‘#x’, where x is the case number. Place a blank between two adjacent numbers for printing.
[Sample Input]
4 // Total number of test cases
10 // n = 10,Test Case #1
0 0 0 0 0 0 0 2 0 0 // 0 : empty cell, 1 : [Direction 1], 2 : [Direction 2]
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 2 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 1 0 0
1 0 0 0 2 0 0 2 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
5 // Test Case #2
0 2 0 0 0
0 0 0 0 0
0 2 0 1 0
2 0 0 1 0
0 2 0 0 0
10 // Test Case #3
0 0 0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0
0 0 2 1 0 0 0 2 0 0
0 0 0 0 0 1 0 1 0 0
0 0 0 0 2 0 0 0 1 0
0 2 0 0 0 0 1 0 0 1
0 0 0 0 0 0 2 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 2 0 0 0 0 0 0 1
10 // Test Case #4
0 0 0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 2 0 1
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 2 2 0 0 1
0 0 0 0 0 0 0 2 0 1
0 0 0 2 1 0 2 0 2 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 0
[Sample Output]
#1 7
#2 3
#3 3
#4 4
BlockDropping
There are blocks on an 10*10 grid. All blocks take up two adjacent cells either horizontally or vertically.
Diagram shows an example. It has a total of eleven blocks. Now, with the grid given, you wish to drop all the blocks vertically at once. During this process, if the block touches the floor or hits another block, the drop stops. Once the blocks in Diagram 1 are dropped, it will result in Diagram 2.
Given an 10*10 grid with blocks as above, write a program to drop the blocks by following the rules above.
For your convenience, answer by indicating the height of blocks in each column and continue in sequence.
For example in Diagram 2, the height of blocks in the 2nd column is 3 and the height of blocks in the 6th is 4. A column without a block is indicated with ‘0’.
To keep the level of difficulty of this test, you may assume that the blocks do not adjoin left, right or top, bottom.
Diagram 3 shows some of the typical examples of invalid block positions. Such distribution will not be included in the input, thus you may leave this out.
[Input]
A total of 10 test cases are given. In 10 lines of each case, 10*10 grid status is given. Those without blocks are indicated with '0' and those with blocks are marked with '1'.
Adjacent cells in the same line are separated with space.
[Output]
Print your answer for each of the 10 test cases. On the first line of each case, write ‘#x’ (‘x’ represents case number) and leave a space. Then, express the shape of the result.
For your convenience, when expressing the result, only indicate the height sequence of blocks in each column. In other words, it is expressed in 10 numbers of integer sequence.
For example, in Diagram 2, it is expressed as ‘3 3 4 4 4 4 1 3 3 0’. Columns without the blocks are indicated with ‘0’. Adjacent numbers are separated with space.
[Example of input and output]
Input
0 0 1 1 0 0 0 0 0 0 ← Start of case #1
0 0 0 0 1 1 0 0 0 0
1 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 1 0
1 0 0 1 1 0 0 0 0 0
1 0 0 0 0 0 1 1 0 0
0 0 0 1 1 0 0 0 1 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 ← Start of case #2
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0
0 0 0 0 1 1 0 0 1 0
0 1 1 0 0 0 0 0 0 1
0 0 0 1 0 1 1 0 0 1
1 1 0 1 0 0 0 0 1 0
0 0 1 0 1 1 0 0 1 0
0 0 1 0 0 0 0 0 0 1
1 1 0 0 0 1 1 0 0 1
...
Output (composed of ten lines in total)
#1 3 3 4 4 4 4 1 3 3 0
#2 2 3 3 2 4 4 3 0 4 6
...
Editor is loading...