Lăn xúc xắc - Đề thi Tin học trẻ Quốc gia

#1

Em mới lụm được bài này trong đề tin học trẻ quốc gia. Do giới hạn giá trị khá lớn nên em chưa bao hàm được hết tất cả trưởng hợp. Mong mọi người giúp em ạ

LĂN XÚC XẮC

Cho một bảng vuông được chia thành lưới gồm n x n ô vuông đơn vị. Các hàng của bảng được đánh số từ 1 tới n theo thứ tự từ trên xuống và các cột của bảng được đánh số từ 1 tới n theo thứ tự từ trái qua phải. Gọi ô (i,j) là ô nằm trên giao của hàng i và cột j. Có một quân xúc xắc hình khối lập phương đơn vị được đặt lên bảng sao cho mặt đáy của xúc xắc phủ kín ô (1,1). Mỗi mặt của xúc xắc có thể có từ 1 tói 6 chấm: Mặt trên của xúc xắc có 1 chấm, mặt hướng mép trái của bảng có 2 chấm, mặt hướng mép trên của bảng có 3 chấm, tổng số chấm trên hai mặt đối diện bất kỳ luôn bằng 7.

Khi lăn quân xúc xắc trên bảng từ một ô sang một ô khác kề cạnh với ô đang đứng, mặt trên của xúc xắc sẽ trở thành mặt bên tương ứng với hướng di chuyển và mặt bên theo hướng di chuyển sẽ trở thành mặt đáy. Sau mỗi phép lăn, các chấm ở mặt đáy của quân xúc xắc sẽ in lên ô mà quân xúc xắc vừa mới lăn sang. Ban đầu xúc xắc in 6 chấm lên ô (1,1).

Bước 1: Lăn sang phải đến khi tất cả các ô cùng hàng với xúc xắc đều được in chấm thì dừng lại.
Bước 2: Lân xuống dưới đến khi tất cả các ô cùng cột với xúc xắc đều được in chấm thì dừng lại.
Bước 3: Lăn sang trái đến khi tất cả các ô cùng hàng với xúc xắc đều được in chấm thì dừng lại.
Bước 4: Lăn lên trên đến khi tất cả các ô cùng cột với xúc xắc đều in chấm thì dừng lại.

Quá trình lăn xúc xắc lặp lại từ bước 1 và kết thúc ngay khi tất cả các ô của bảng đã được in chấm.

Yêu cầu: Nhập vào từ bàn phím số tự nhiên N (1<=N<=10^19) là số ô có trên một cạnh của bảng vuông. Xuất ra màn hình tổng số chấm được xúc xắc in lên bảng.

3 Likes
In ma trận mxn thành hình xoắn ốc
#2

đề gì mà như game :smile: có cái để nghịch rồi :smiley:

1 Like
#3

Hi vọng đúng :smile:

#include <stdio.h>
int dice[6]={6,5,1,2,3,4};
int diceT[6];
int n;
int status;
void change()
{
    diceTemp[0]=dice[(status+0)%4];
    diceTemp[1]=dice[5];
    diceTemp[2]=dice[(status+2)%4];
    diceTemp[3]=dice[4];
    diceTemp[4]=dice[(status+1)%4];
    diceTemp[5]=dice[(status+3)%4];
    //
    int i;
    for (i=0;i<6;i++)
        dice[i]=diceTemp[i];
}
int main()
{
    int i,j;
    printf("N=");
    scanf("%i",&n);

    status=n%5;
    if (n<5) status--;

    int s=0;
    s+=((n/4)*14)*4;
    for (i=0;i<=3;i++)
    {
        for (j=0;j<status;j++)
        {
            //printf("\n%i",dice[j]);
            s+=dice[j];
        }
        change();
    }
    printf("S=%i",s);
    getch();
    return 0;
}
1 Like
#6

bạn giải thích thuật toán cho mình được ko ?

#7

This post was flagged by the community and is temporarily hidden.

#8

Lúc đầu nhìn đề có vẻ phức tạp và cũng hơi … hack não nhưng khi đọc xong code anh @Rok_Hoang thì thấy chỉ dùng C nên mình sẽ quất luôn :laughing:

#9

:)) code thời năm nhất
Nói chung là code có mùi sai rồi, nhưng ý tưởng là change() là để chuyển trạng thái của xúc sắc, sau đó cộng dồn lên thôi.

2 Likes
#10

Submit lại xem sao

#include <stdio.h>
int dice[6]={6,5,1,2,3,4};
int diceTemp[6];
int n;
int status;
void change()
{
    diceTemp[0]=dice[(status+0)%4];
    diceTemp[1]=dice[5];
    diceTemp[2]=dice[(status+2)%4];
    diceTemp[3]=dice[4];
    diceTemp[4]=dice[(status+1)%4];
    diceTemp[5]=dice[(status+3)%4];
    //
    int i;
    for (i=0;i<6;i++)
        dice[i]=diceTemp[i];
    status = 0;
}
void roll()
{
    diceTemp[0]=dice[1];
    diceTemp[1]=dice[2];
    diceTemp[2]=dice[3];
    diceTemp[3]=dice[0];
    diceTemp[4]=dice[4];
    diceTemp[5]=dice[5];
    //
    int i;
    for (i=0;i<6;i++)
        dice[i]=diceTemp[i];
}
int main()
{
    int i,j;
    printf("N=");
    scanf("%i",&n);
    //n=3;

    status = 0;
    int s=0;
    while (n>=1)
    {
        s+=dice[0];
        //printf("\n%i",dice[0]);
        for (i=0;i<3;i++)
        {
            for (j=1;j<n;j++)
            {
                //printf("\n%i",dice[j%4]);
                s+=dice[j%4];
            }
            status = (n-1)%4;
            change();
        }
        for (j=1;j<(n-1);j++)
        {
            //printf("\n%i",dice[j%4]);
            s+=dice[j%4];
        }
        status = (n-2)%4;
        change();
        roll();
        n-=2;
    }
    printf("\nS=%i",s);

    return 0;
}
1 Like
#11

Cái ý này mình không hiểu lắm. Anh @Rok_Hoang hay chủ thớt giải thích hộ em được không?

Nếu hiểu theo ý em thì, khi lăn xúc xắc từ ô này qua ổ bên cạnh (bên phải) thì lăn 2 lần: mặt U (up) sẽ thành mặt D (down) đúng không nhỉ?
Hay chỉ lăn 1 lần: Mặt U (up) thành mặt R (right)?

Nếu lăn 2 lần (mặt U thành mặt D) thì rất dễ:
int ketqua= 1*(canh*canh)/2 + 6*((canh*canh)/2+1)
Bởi vì đề cho là khi con xúc xắc đang nằm ở ô (1,1) thì mặt D là 6 rồi, mặt U là 1. Nếu cứ lăn 2 lần (mặt U thành mặt D) thì chỉ làm việc với 2 con số là 1 và 6 thôi, còn các mặt khác thì không liên quan?
Nói chung là cái đề hack não quá!

#12

chỉ lăn 1 lần thôi, từ U thành R. Con xúc sắc sẽ lăn theo hình xoắn ốc.
Notice: Đề nó còn một chỗ là 2 mặt đối diện nhau đều có tổng là 7 :slight_smile: dùng cái này tính nhanh hơn nhiều.

1 Like
#15

À em quên ghi là test lớn nhất là N = 987654321123456789 ạ

#16

Huhu :sob:
Bữa giờ không biết mua cục xúc xắc ở đâu nên không hình dung được để làm bài này ! Dự định là mình sẽ giải theo phương pháp Mảng 2 chiều

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