Task: | Robotti |
Sender: | TNT |
Submission time: | 2024-10-31 20:34:58 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 30 |
#2 | ACCEPTED | 70 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2 | details |
#2 | ACCEPTED | 0.00 s | 1, 2 | details |
#3 | ACCEPTED | 0.00 s | 1, 2 | details |
#4 | ACCEPTED | 0.00 s | 1, 2 | details |
#5 | ACCEPTED | 0.00 s | 1, 2 | details |
#6 | ACCEPTED | 0.00 s | 1, 2 | details |
#7 | ACCEPTED | 0.00 s | 1, 2 | details |
#8 | ACCEPTED | 0.00 s | 1, 2 | details |
#9 | ACCEPTED | 0.00 s | 1, 2 | details |
#10 | ACCEPTED | 0.00 s | 1, 2 | details |
#11 | ACCEPTED | 0.00 s | 1, 2 | details |
#12 | ACCEPTED | 0.00 s | 2 | details |
#13 | ACCEPTED | 0.00 s | 2 | details |
#14 | ACCEPTED | 0.00 s | 2 | details |
#15 | ACCEPTED | 0.00 s | 2 | details |
#16 | ACCEPTED | 0.00 s | 2 | details |
#17 | ACCEPTED | 0.01 s | 2 | details |
#18 | ACCEPTED | 0.01 s | 2 | details |
#19 | ACCEPTED | 0.01 s | 2 | details |
#20 | ACCEPTED | 0.01 s | 2 | details |
#21 | ACCEPTED | 0.01 s | 2 | details |
#22 | ACCEPTED | 0.01 s | 2 | details |
#23 | ACCEPTED | 0.01 s | 2 | details |
#24 | ACCEPTED | 0.01 s | 2 | details |
Compiler report
input/code.cpp: In function 'std::vector<int> CollectCoins(int, std::string, std::vector<int>, std::size_t)': input/code.cpp:20:83: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare] 20 | while ((((int)RobotPos-PrevSearch>=0) || ((int)RobotPos+PrevSearch<Layout.length())) && (DistanceLeft == -1 && DistanceRight == -1)) { | ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~ input/code.cpp:20:119: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare] 20 | while ((((int)RobotPos-PrevSearch>=0) || ((int)RobotPos+PrevSearch<Layout.length())) && (DistanceLeft == -1 && DistanceRight == -1)) { | ~~~~~...
Code
#include <iostream>#include <ostream>#include <string>#include <vector>std::vector<int> CollectCoins(int Rooms, std::string Layout, std::vector<int> Output, std::size_t RobotPos = 0) {while (true) {if (RobotPos == 0) RobotPos = Layout.find('R');//std::cout << RobotPos << "\n";// Failsafe initializationsstd::size_t CoinLeft = -1;std::size_t DistanceLeft = -1;std::size_t CoinRight = -1;std::size_t DistanceRight = -1;// Iteratively search for coinsint SearchDepth = 5;int PrevSearch = 0;while ((((int)RobotPos-PrevSearch>=0) || ((int)RobotPos+PrevSearch<Layout.length())) && (DistanceLeft == -1 && DistanceRight == -1)) {if (RobotPos != (size_t)0) {int SearchStart = (int)RobotPos-PrevSearch;if (SearchStart <= 0) SearchStart = 0;for (int i = SearchStart; (i>=SearchStart-SearchDepth) && (i>=0); i--) {//std::cout << "left: " << i << "\n";if (Layout[i]=='*') {CoinLeft = i;break;}}//std::cout << CoinLeft << "\n";if (CoinLeft!=-1) DistanceLeft = RobotPos - CoinLeft;}if (RobotPos != (size_t)(Rooms-1)) {int SearchStart = (int)RobotPos+PrevSearch;if (SearchStart >= Layout.length()) SearchStart = Layout.length()-1;for (int i = SearchStart; (i<=SearchStart+SearchDepth) && (i<Layout.length()); i++) {//std::cout << "right: "<< i << "\n";if (Layout[i]=='*') {CoinRight = i;break;}}//std::cout << CoinRight << "\n";if (CoinRight!=-1) DistanceRight = CoinRight - RobotPos;}PrevSearch += SearchDepth;//SearchDepth *= 2;}/*if (DistanceLeft < DistanceRight) {std::cout << "robot: "<< (int)RobotPos-PrevSearch << " " << RobotPos << " " << (int)RobotPos+PrevSearch << "\n";;std::cout << "left: "<< DistanceLeft << " " << CoinLeft << "\n"<< "right: "<< DistanceRight << " " << CoinRight << "\n" << std::endl;throw;}*/if (DistanceLeft==DistanceRight || ((CoinLeft == (size_t)-1) && (CoinRight == (size_t)-1))) {/*std::cout << "Returning with: " << "\n"<< "layout:\n" << Layout << "\n"<< "left: "<< DistanceLeft << " " << CoinLeft << "\n"<< "right: "<< DistanceRight << " " << CoinRight << "\n" << std::endl;*/return Output;}Layout[RobotPos] = '.';Output[1]++;//std::cout << "Robot at: " << RobotPos << "\n";if (DistanceLeft<DistanceRight) {RobotPos = CoinLeft;Output[0] += DistanceLeft;Layout[CoinLeft] = 'R';} else {RobotPos = CoinRight;Output[0] += DistanceRight;Layout[CoinRight] = 'R';}//std::cout << Layout << "\n";//std::cout << "Robot at: " << RobotPos << "\n";/*std::cout << "SearchDepth: " << SearchDepth/2 << "\n";std::cout << "CoinLeft: " << CoinLeft << "\n";std::cout << "CoinRight: " << CoinRight << "\n";std::cout << "Distances: " << DistanceLeft << " " << DistanceRight << "\n\n";*/}}int main () {// Input:// n rooms// Building layout// e.g.// 20// **.*......*.R*...*..// * = coin; . = empty; R = robotint Rooms;std::string Layout;std::cin >> Rooms;std::cin >> Layout;// GOAL: Find the max number of coins the robot can collect by always going to// the closest coinstd::vector<int> Output = {0,0};Output = CollectCoins(Rooms, Layout, Output);int Steps = Output[0];int Coins = Output[1];std::cout << Steps << " " << Coins << "\n";}
Test details
Test 1
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1 R |
correct output |
---|
0 0 |
user output |
---|
0 0 |
Test 2
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 ...R...... |
correct output |
---|
0 0 |
user output |
---|
0 0 |
Test 3
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 **.R...*** |
correct output |
---|
12 5 |
user output |
---|
12 5 |
Test 4
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 ***R****** |
correct output |
---|
0 0 |
user output |
---|
0 0 |
Test 5
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 R................................ |
correct output |
---|
947 9 |
user output |
---|
947 9 |
Test 6
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 ................................. |
correct output |
---|
886 9 |
user output |
---|
886 9 |
Test 7
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 .....*..*....**..**..*......*.... |
correct output |
---|
1287 400 |
user output |
---|
1287 400 |
Test 8
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 ************.*****************... |
correct output |
---|
0 0 |
user output |
---|
0 0 |
Test 9
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 ******************************... |
correct output |
---|
0 0 |
user output |
---|
0 0 |
Test 10
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 R*****************************... |
correct output |
---|
999 999 |
user output |
---|
999 999 |
Test 11
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 ******************************... |
correct output |
---|
999 999 |
user output |
---|
999 999 |
Test 12
Group: 2
Verdict: ACCEPTED
input |
---|
10000 .......**........*...........*... |
correct output |
---|
10971 999 |
user output |
---|
10971 999 |
Test 13
Group: 2
Verdict: ACCEPTED
input |
---|
10000 *..*....*......*.....*..*........ |
correct output |
---|
9999 999 |
user output |
---|
9999 999 |
Test 14
Group: 2
Verdict: ACCEPTED
input |
---|
10000 *.*.*...**.*...*....**.**.**..... |
correct output |
---|
18766 5000 |
user output |
---|
18766 5000 |
Test 15
Group: 2
Verdict: ACCEPTED
input |
---|
10000 R*****************************... |
correct output |
---|
9999 9999 |
user output |
---|
9999 9999 |
Test 16
Group: 2
Verdict: ACCEPTED
input |
---|
10000 ******************************... |
correct output |
---|
9999 9999 |
user output |
---|
9999 9999 |
Test 17
Group: 2
Verdict: ACCEPTED
input |
---|
200000 ................................. |
correct output |
---|
0 0 |
user output |
---|
0 0 |
Test 18
Group: 2
Verdict: ACCEPTED
input |
---|
200000 ................................. |
correct output |
---|
299934 10000 |
user output |
---|
299934 10000 |
Test 19
Group: 2
Verdict: ACCEPTED
input |
---|
200000 **.***....**..**.....***.*..*.... |
correct output |
---|
299998 100000 |
user output |
---|
299998 100000 |
Test 20
Group: 2
Verdict: ACCEPTED
input |
---|
200000 ******************************... |
correct output |
---|
0 0 |
user output |
---|
0 0 |
Test 21
Group: 2
Verdict: ACCEPTED
input |
---|
200000 R................................ |
correct output |
---|
133765 3 |
user output |
---|
133765 3 |
Test 22
Group: 2
Verdict: ACCEPTED
input |
---|
200000 R................................ |
correct output |
---|
199982 5000 |
user output |
---|
199982 5000 |
Test 23
Group: 2
Verdict: ACCEPTED
input |
---|
200000 R*****************************... |
correct output |
---|
199999 199999 |
user output |
---|
199999 199999 |
Test 24
Group: 2
Verdict: ACCEPTED
input |
---|
200000 ******************************... |
correct output |
---|
199999 199999 |
user output |
---|
199999 199999 |