Description

Input

Output

Sample Input  Download

Sample Output  Download

Partial Judge Code

12392.c

Partial Judge Header

12392.h

Tags

Discuss

Description

 

"Go Down Chicken is a vicious monster, it will hit you until you have cerebral concussion(腦震盪)." ~from an anonymous bestiary.

To avoid from being attacked by Go Down Chicken, you need to solve the following problem.

This question has multiple input in each testcase. The input end with EOF.

Each input contain n numbers a_i(1 <= i <= n) and q queries x_j(1 <= j <= q).

Each number a_i represents a game.

The game is that you need to fill a 3 * a_i tiles with the shape(The left one) described in the picture below.

The shape can't overlap and no empty space allow. For each a_i you need to calculate how many ways you can fill the tiles.

The number of ways may be very large, therefore you need to mod the answer with 1000000007.

For example:

The picture above present a 3*6 tiles, you will have 8 ways to fill the tiles with the shape.

 

Once you finish those n games, you need to answer q queries.

Each query will give you one integer x_j means the ways to fill the tiles.

You need to answer x_j is in which round of the games?

If there're multiple answers, answer the earliest round.

If you can't find the answer, print "Go Down Chicken 404"

 

Sample input explain:

You have n = 5, q = 3

Then you have 5 integer: 6, 9, 13, 4, 3

If the tiles is 3*6: you have 8 ways to fill it.

If the tiles is 3*9: you have 0 ways to fill it.

If the tiles is 3*13: you have 0 ways to fill it.

If the tiles is 3*4: you have 4 ways to fill it.

If the tiles is 3*3: you have 0 ways to fill it.

 

Then you have 3 queries: 0, 4, 1024

There are multiple rounds turn out have 0 ways, but you need to answer the earliest round. The earliest round is second round.

Therefore the answer is 2.

The round that turns out have 4 ways is the forth round.

Therefore the answer is 4.

The round that turns out have 1024 ways can't be found.

Therefore the answer is "Go Down Chicken 404".

 

Input

The input is end with EOF

Each input contains several lines.

First line contains two integer n(1 <= n <= 1000000), q( 1 <= q <= 1000000).

Second line contain n integer a_i( 1 <= a_i <= 1000000).

Each a_i is followed by a symbol "(/`A`)/ ~I__I" and separated by a blank from the next integer.

The following q lines each line contains one integer x_j .

Output

For each query print that x_j is the result of which round of the games(start from 1).

If there're multiple answers, answer the earliest round.

If you can't find the answer, print "Go Down Chicken 404"

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

"I have a dream that one day I can become a calculator."

~by anonymous Asian

But you are a programmer(you have no life). You can design a program to calculate for you(and become shame of Asian).

The input will contain multiple expression and end by EOF.

Each expression will only contain +, -, *, /, % and numbers(No parentheses).

You need to calculate the answer of the expression.

There may be several blanks or no blanks between operator and number.

You can use the code below and just finish the "Todo" part.

You can write your own code too.

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
​
#define MAX_LENGTH 1000
​
// Token / AST kinds
enum {
    // Non-operators
    Value,
    // Operators
    /// Precedence 1
    Mul, Div, Rem,
    /// Precedence 2
    Add, Sub,
};
typedef struct _TOKEN {
    int kind;
    int param; // Value
    struct _TOKEN *prev, *next;
} Token;
typedef struct _AST {
    int type;
    int val; // Value
    struct _AST *lhs, *rhs;
} AST;
​
// Utility Interface
​
// Used to create a new Token.
Token *new_token(int kind, int param);
// Used to create a new AST node.
AST *new_AST(Token *mid);
// Convert Token linked list into array form.
int list_to_arr(Token **head);
// Use to check if the kind can be determined as a value section.
int isValueSection(int kind);
// Function called when an unexpected expression occurs.
void err();
​
// Used to find a appropriate operator that split the expression half.
int find_Tmid(Token *arr, int l, int r);
//get the Precedence of operator or value
int getOpLevel(int kind);
// calculate the answer 
void getanswer(AST *ast);
​
// Main Function
​
char input[MAX_LENGTH];
int regis[1000], now_reg = -1;
​
// Convert the inputted string into multiple tokens.
Token *lexer(char *in);
// Use tokens to build the binary expression tree.
AST *parser(Token *arr, int l, int r);
// calculate the answer
void calculate(AST *ast);
​
int main() {
    while(fgets(input, MAX_LENGTH, stdin) != NULL) {
        // build token list by lexer
        Token *content = lexer(input);
        // convert token list into array
        int length = list_to_arr(&content);
        
        // build abstract syntax tree by parser
        AST *ast_root = parser(content, 0, length-1);
        // calculate the answer
        calculate(ast_root);
        
        /*Todo*/
        // print the answer here.
        
        /*Todo*/
        // do some reset??
    }
    return 0;
}
AST *parser(Token *arr, int l, int r) {
    if(l > r) return NULL;
    // covered in parentheses
    int mid = find_Tmid(arr, l, r);
    AST *newN = new_AST(arr + mid);
    
    if(l == r || newN->type == Value)
        return newN;
​
    /*Todo*/
    //finish the parser
    return newN;
}
AST* new_AST(Token *mid) {
    AST *newN = (AST*)malloc(sizeof(AST));
    newN->lhs = newN->rhs = NULL;
    newN->type = mid->kind;
    newN->val = mid->param;
    return newN;
}
int find_Tmid(Token *arr, int l, int r) {
    /*Todo*/
    //find the node to be contructed
}
int getOpLevel(int kind) {
    /*Todo*/
    // you may use this finction in find_Tmid
}
void calculate(AST *ast) {
    /*Todo*/
    // traverse the tree by postorder
}
​
void getanswer(AST *ast){
    /*Todo*/
    // calculate the answer here.
    // you can calculate the answer by simulating the registers
}
​
Token *lexer(char *in) {
    Token *head = NULL;
    Token **now = &head, *prev = NULL;
    for(int i = 0; in[i]; i++) {
        if(in[i] == ' ' || in[i] == '\n')
            continue;
​
        else if(isdigit(in[i])) {
            int val = 0, oi = i;
            for(; isdigit(in[i]); i++)
                val = val * 10 + (in[i] - '0');
            i--;
            // Detect illegal number inputs such as "01"
            if(oi != i && in[oi] == '0')
                err();
            (*now) = new_token(Value, val);
        }
​
        else {
            switch(in[i]) {
                case '+': // '+'
                    (*now) = new_token(Add, 0);
                    break;
                case '-':
                    (*now) = new_token(Sub, 0);
                    break;
                case '*':
                    (*now) = new_token(Mul, 0);
                    break;
                case '/':
                    (*now) = new_token(Div, 0);
                    break;
                case '%':
                    (*now) = new_token(Rem, 0);
                    break;
                default:
                    err();
            }
        }
        (*now)->prev = prev;
        if(prev != NULL) prev->next = (*now);
        prev = (*now);
        now = &((*now)->next);
    }
    return head;
}
Token *new_token(int kind, int param) {
    Token *res = (Token*)malloc(sizeof(Token));
    res->kind = kind;
    res->param = param;
    res->prev = res->next = NULL;
    return res;
}
int list_to_arr(Token **head) {
    int res = 0;
    Token *now = (*head), *t_head = NULL, *del;
    while(now!=NULL) {
        res++;
        now = now->next;
    }
    now = (*head);
    t_head = (Token*)malloc(sizeof(Token)*res);
    for(int i = 0; i < res; i++) {
        t_head[i] = (*now);
        del = now;
        now = now->next;
        free(del);
    }
    (*head) = t_head;
    return res;
}
int isValueSection(int kind) {
    if(kind == Value) return 1;
    return 0;
}
void err(){
    exit(0);
}
​

 

 

 

 

Input

The input will contain multiple expression and end by EOF.

Each expression will only contain +, -, *, /, % and numbers(No parentheses).

Each expression will not exceed 10000 characters.

We guarantee that every expression is legal.

Output

For each expression print the answer you calculate.

remember to print \n at every end of answer.

Sample Input  Download

Sample Output  Download

Tags

Discuss