Bài toán bánh xe giải thưởng

#1

Nay là một ngày may mắn của Đăng, vì hôm nay anh ấy đã nhận được 1 lượt quay số lấy giải. Trên vòng quay có n số từ 1 đến n đại diện cho giá trị của giải thưởng. Các số đó được điền từ trái sang phải như hình sau. Đăng có thể quay vòng quay đó theo chiều kim đồng hồ hoặc ngược lại.

Ngoài ra Đăng có 1 khả năng đặc biệt là kiểm soát lực mình quay. Đăng sẽ quay vòng quay với 1 lực trong khoảng từ L đến R (Cụ thể là được xài các lực L, L+1, L+2,… ,R−1, R). Khi đó vòng quay mất 1 lực khi qua thêm 1 số. Và sẽ dừng khi lực bằng 0. Ví dụ: Vòng quay xuất phát từ 1. Đăng quay cùng chiều với lực là 2. Thì khi đó bánh xe ở vị trí 1 có lực là 2. Nó dịch chuyển sang vị trí 2 và lực còn 1. Nó dừng tại 3 với lực bằng 0. Và khi đó bánh xe dừng tại 3

139b57192238b3936a9a9a36c37ac3b7302d6da0.png
139b57192238b3936a9a9a36c37ac3b7302d6da0.png627×594 70.9 KB

.

Hãy cho biết giá trị lớn nhất mà Đăng có thể quay được là bao nhiêu?

Ví dụ: Nếu bạn vòng quay có n = 5. Đăng có thể quay lực trong khoảng từ L = 2 đến R = 3. Thì Đăng có thể quay lực là 3 theo chiều kim đồng hồ để để đạt được giá trị là 4.

Input
Dòng đầu tiên có chứa 3 số nguyên dương n,L,R (Với 1≤n,L,R≤10^8) lần lượt là số giá trị trên vòng quay, lực nhỏ nhất và lực lớn nhất Đăng có thể quay.

Output
Một dòng duy nhất chứa 1
số là giá trị lớn nhất mà Đăng có thể quay được.

Example
-Input
5 2 3
-Output
4

Bài này em có hỏi ở một phần reply ở bài trước đó hôm qua em đăng. Nhưng khi tự giải bài này thì em có nhiều khúc mắc, do toán em không giỏi nên hơi khó có cách giải tối ưu. Em có nghĩ ra được 1 cách :

  • lực tay trái thì gán giá trị đầu là (n+1), sau đó khi muốn trừ đi giá trị (Đăng xoay bánh xe theo ngược chiều kim đồng hồ) thì em tạo vòng lặp while để trừ tuần tự
    if (lucL < soGiaTriN) {
    while (lucL > 0) {
    ketQuaL--;
    lucL--;
    }
    }
  • lực tay phải thì gán giá trị đầu là 1, sau đó muốn cộng thêm giá trị (xoay lực tay phải) thì em cũng dùng vòng while
    if (lucR < soGiaTriN) {
    while (lucR > 0) {
    ketQuaR++;
    lucR--;
    }
    }

hoặc ketQuaR = lucR + 1 nó đều ra kết quả
và khi em đem lên submit thì nó không đúng tất cả test, chắc khoảng 20 -> 30 test ( tổng cộng 200 test case).
Nay em đăng lên đây coi như là luyện tập cho ae group, đồng thời hỏi bài luôn ạ. Em đang hóng cao nhân nào nghĩ ra được cách giải tốt hơn. Em cảm ơn ạ.

#2

Bị sai là do số lọt ra ngoài 1…N đó.

Quy ước chiều + là chiều kim đồng hồ vậy ngược chiều kim đồng hồ ta quy về cùng chiều luôn :slight_smile: bài này vài ba phép tính.

5 Likes
#3

quy thế nào hả bác, nếu lực L = 2 xoay xong nó ra giá trị 4, mà quy về xong L vẫn bằng 2, xoay nó ra 3. E vẫn chưa hiểu ý của bác lắm.

em có sửa khúc này
tay phải

else if (lucR > soGiaTriN) {`
		tempR = lucR - soGiaTriN;
		while (tempR > soGiaTriN) tempR -= soGiaTriN;			
		if (tempR == soGiaTriN) ketQuaR = soGiaTriN;
		if (tempR == 0) ketQuaR = soGiaTriN;
		if (tempR < 0 && tempR < soGiaTriN) 
			while (tempR > 0) {
				ketQuaR++;
				tempR--;
			}
	}

tay trái

else if (lucL > soGiaTriN) { 
      tempL = lucL - soGiaTriN;
		while (tempL > soGiaTriN) 
			tempL -= soGiaTriN;

		if (tempL == soGiaTriN) 
			ketQuaL = soGiaTriN;
		if (tempL > 0 && tempL < soGiaTriN) {
			ketQuaL = soGiaTriN + 1;
			while (tempL > 0 && tempL < soGiaTriN) {
				ketQuaL--;
				tempL--;
			}
		}	
    }

nó tăng lên thêm 20 test case nữa bác ạ, rồi còn lại sai hết

#4

tự facepalm :sweat:

Đăng có thể quay tít 100 vòng :smiley: nên ta quy về trường hợp quay 1 vòng.

  1. Nếu | L-R | >= N thì ô lớn nhất chính là N.
  2. Lấy modulo N cho L và R, nếu L > R thì ô lớn nhất vẫn là N :slight_smile:
  3. Với L<=R thì kq là 1 + max(L, R, N-L, N-R) hay 1 + max(R, N-L)
5 Likes
#5

Cái này em hơi ngu ấy, là N % L hay L % N

#6

E mới test lại, thì thuật toán của bác chỉ đc 310/500 điểm. Vẫn chưa tối ưu bác ạ. Chắc vẫn còn những trường hợp đặc biệt.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?