Hướng dẫn giải của [Beginner Free Contest 08] INSPIRE
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Mỗi thủy thủ chạy quanh vòng 28 thẻ theo đường ngắn nhất, lấy lần lượt các thẻ ứng với các ký tự của câu. Thời gian gồm quãng đường chia cho 15 m/s và 1 giây cho mỗi thẻ lấy được.
Mô phỏng trực tiếp — ~O(|câu|)~
Đánh số thẻ: A..Z là 0..25, dấu cách là 26, dấu nháy đơn là 27. Giữa hai thẻ liên tiếp, số bước là ~\min(d, 28-d)~ với ~d~ là hiệu chỉ số. Mỗi bước dài ~60\pi/28~ mét. Tổng thời gian là ~số bước \cdot 60\pi/(28\cdot 15) + |câu|~ giây.
Nếu chỉ nộp sub này: đúng 2/2 test. Đề không chia subtask nên chỉ viết 1 sub.
Chương trình hoàn chỉnh
Đây là lời giải đầy đủ, chỉ có một sub vì đề không chia subtask.
#include <bits/stdc++.h>
using namespace std;
// 28 the tren vong tron, theo thu tu: A..Z (vi tri 0..25), dau cach (26), dau nhay don (27).
// Moi thuy thu chay quanh ben ngoai vong tron theo duong ngan nhat, lay lan luot cac the
// theo thu tu trong cau cam hung. Moi buoc giua 2 vi tri ke nhau = 60*pi/28 met, toc do 15 m/s.
// Moi the lay mat 1 giay.
// Chi co mot cach tinh, khong co subtask nen viet 1 sub.
int posOf(char ch) {
if (isalpha((unsigned char)ch)) return toupper((unsigned char)ch) - 'A';
if (ch == ' ') return 26;
return 27; // dau nhay don
}
void sub1(const string &s) {
int steps = 0;
int prev = posOf(s[0]);
for (size_t i = 1; i < s.size(); i++) {
int cur = posOf(s[i]);
int d = abs(cur - prev);
steps += min(d, 28 - d);
prev = cur;
}
const double PI = acos(-1.0);
double arc = 60.0 * PI / 28.0;
double t = steps * arc / 15.0 + (double)s.size(); // di chuyen + thoi gian lay the
printf("%.4f\n", t);
}
int main() {
int n;
cin >> n;
string line;
getline(cin, line); // bo phan con lai cua dong so n
for (int i = 0; i < n; i++) {
getline(cin, line);
string s;
for (char c : line)
if (isalpha((unsigned char)c) || c == ' ' || c == '\'') s += c;
if (s.empty()) { printf("0.0000\n"); continue; }
sub1(s);
}
return 0;
}
Bình luận