Find the Largest Cube formed by deleting minimum number of digits from a number

[pth573 (Phạm Thanh Hằng)]

Bài này em có làm mà WA mà không biết sai ở đâu mong mọi người chỉ giúp em lỗi sai với ạ. Em cám ơn ạ

[noname00 (HK boy)]

Bạn vui lòng đăng code lên đây dưới dạng chữ, không chụp hình. Xem hướng dẫn ở đây:

Cách post Code dùng Markdown trong Category Programming

Làm sao để có thể hiển thị syntax highlighting bằng markdown? Các bạn phải đánh dấu ``` như ví dụ dưới đây Chú ý, dấu ``` được tạo ra bởi nút nằm bên trái số 1 trên bàn phím, nút này sẽ là ~ khi bấm giữ Shift Ví dụ cho C Nội dung: ``` void main() { } ``` Và đừng quên ``` ở cuối Kết quả void main() { } Ví dụ cho Pascal Nội dung: ``` Program HelloWorld; Begin WriteLn('Hello world!') {no ";" is required after the last statement of a block - adding one adds a "null statement" to t…

[pth573 (Phạm Thanh Hằng)]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll ans;

void eraseFunction(string s)
{
	unordered_set<string> visited;
	queue<string> q;
	q.push(s);
	visited.insert(s);
	while(!q.empty())
	{
		string x = q.front(); 
		q.pop();
		if(x.empty()) continue;
		ll tmp = cbrt(stoll(x));
		if(tmp * tmp * tmp == stoll(x))
		{
			ans = max(ans, stoll(x));
		}
		string str;
		for(int i = 0; i < x.size(); i++)
		{
			str = x.substr(0, i) + x.substr(i + 1);
			if(visited.find(str) == visited.end() && str.size() > 0)
			{
				q.push(str);
				visited.insert(str);
			}
		}
	}
}

int main()
{
	int t; cin >> t;
	while(t--)
	{
		string s; cin >> s;
		ans = LLONG_MIN;
		eraseFunction(s);
		if(ans == LLONG_MIN) cout << "-1" << endl;
		else cout << ans << endl;
	}
}

Dạ vâng em cám ơn ạ. Em có up lại ở dưới rồi ạ

[tntxtnt]

@pth573

cbrt(stoll(x));

lỗi là ở đây nè, cbrt(long long) đồng nghĩa với cbrt(double), thì kiểu long long được cast ngầm định thành kiểu double, mà kiểu double chỉ chính xác tới 54 bit, trong khi kiểu long long có tới 63 bit, nên sẽ mất 9 bit đi, ko còn chính xác nữa.

có thể xài std::cbrtl(long double), cast stoll(x) thành long double xem nó có chính xác hơn ko, nếu vẫn ko chính xác thì phải tìm cách khác kiểm tra xem 1 số có phải số lập phương. Hình như cbrt ko bảo đảm chính xác tuyệt đối thì phải, long double cũng ko bảo đảm có độ chính xác nhiều hơn 54 bit, tìm cách khác ktra long long lập phương thôi

edit: ngạc nhiên là long long d = std::cbrtl(static_cast<long double>(n)); lại đúng hết

[pth573 (Phạm Thanh Hằng)]

Em vẫn không hiểu lắm. Ví dụ độ chính xác chênh lệnh, nhưng mà em lấy int của cbrt chứ không phải double để nhân r check. Vì căn bậc 3 của 1 số lập phương là 1 số nguyên. Nếu không thì em nghĩ ví dụ 1 số mà có số thập phân mà nhân lên thì nó đã bị lệch so với số lập phương em cần xét. Ví dụ cbrt(9) = 2. Mà khi 2* 2 * 2 = 8 chứ nó không thể = 9 được nên em vẫn không biết em sai cụ thể test nào. Anh vẫn có thể chỉ ra giúp em 1 số mà hàm đó sai dc ko ạ

[pth573 (Phạm Thanh Hằng)]

à em hiểu r ạ. Em cám ơn a ạ

[tntxtnt]

em chạy thử long long i = 1 tới 1000000, lấy long long n = i * i * i rồi lấy cbrt(n) đem so với i là thấy mà, nhiều lắm

nhưng mà j = cbrt(n) với i chênh lệch có 1 đơn vị à, thế thì kiểm tra j*j*j hoặc (j+1)(j+1)(j+1) với n là được, nếu cái long double kia vẫn ko chính xác

edit: ngạc nhiên là mingw gcc cbrt(double) ra kết quả đúng hết, còn gcc trên linux thì có thể cho kết quả sai số 1 đơn vị

[pth573 (Phạm Thanh Hằng)]

Dạ em hiểu r ạ em cám ơn a nhiều. Em sửa long double như ở trên là AC rùi ạ