Tương truyền rằng, ngày xưa có một mưu sĩ thấy dân chúng quá nghèo khổ nên ông ta đã
đến thách đố đánh cờ cùng nhà vua nhằm lấy thóc trong kho đem phân phát cho dân nghèo. Nhà vua ra điều kiện nếu đánh thua nhà vua thì mưu sĩ sẽ bị chém đầu, ngược lại mưu sĩ sẽ được trọng thưởng bằng vật chất. Nếu đánh thắng cờ với nhà vua, mưu sĩ chỉ xin một điều đó là trong mỗi ô cờ gồm 8x8 ô thì lần lượt bỏ vào ô thứ 1: 1 hạt thóc, ô thứ 2: 1x2 hạt thóc, ô thứ 3: 1x2x3 hạt thóc,… cho đến ô cuối cùng. Nhà vua nghe qua rất khoái chí và đồng ý ngay. Sau lần đấu cờ đó nhà vua đã mất rất nhiều kho lương thực cho dân nghèo. Do bản tính hiếu thắng của nhà vua, ông vẫn tiếp tục thách đấu với những tay cao thủ cờ khác trong thiên hạ nhưng bây giờ rút kinh nghiệm ông chỉ xuất trong kho ra bây giờ không phải là thóc nữa mà là vàng. Nguyên tắc để nhận được vàng sau khi đánh thắng nhà vua như sau:
1. Mỗi ô trong bàn cờ có một số. Con số này được gán vào như sau:
- Ô số 1: 1
- Ô số 2: 1x2 = 2
- Ô số 3: 1x2x3 = 6
… …
- Ô số 10 1x2x3x….x10 = 3 628 800
… …
- Ô số 21 1x2x3x….x21 = 51 090 942 171 709 440 000
… …
2. Số vàng nhận được chính là con số khác không đầu tiên kể từ hàng đơn vị lên phía
trước của ô mà đối thủ sẽ chọn. Ví dụ, chọn ô số 10 thì sẽ được 8 lạng vàng, ô số 21 sẽ
được 4 lạng vàng, …
3. Đối thủ chỉ được chọn mỗi lần một ô để nhận vàng. Không được phép chọn các ô bé
hơn 5.
4. Bàn cờ dùng thi đấu là bàn cờ 8x8, nhưng bàn cờ để chọn vàng là NxN, các ô được
đánh số liên tục từ 1đến N.
Yêu cầu: Tìm số vàng mà đấu thủ nọ nhận được khi chọn một ô.
Dữ liệu: Gồm 1 số nguyên N là số thứ tự của ô mà đấu thủ chọn (1 ≤ N ≤10 000)
Kết quả: Ghi ra 1 số duy nhất là số vàng đấu thủ nhận được