Description

Nonogram is a puzzle solving game.

The rule of solving Nonogram is simple:
you are given an empty 2D matrix, and your goal is to color some grid to fit given conditions.

There is a list of numbers beside each row and column,
which tells you the length of each consecutive colored grid of that row/column.

If the list on each row and column is fit, then the Nonogram is solved.

Your sister just tells you that she finished her summer homework,
and her homework is to solve Nonogram!

She asks you to verify wherther the Nonogram she colored is correct or not.

As an engineer, we should make everything automatically. So just build a Nonogram Validator!

ouo.

---

For the first Nonogram in the sample input, the input is as follows:
notice that the order of the input is blue arrows from up to down, then green arrows from left to right.
For the first row, there are exactly 2 consecutive colored grids both of length 1,
for the second row, there are exactly 3 consecutive colored grids all of length 1,
...
for the first column, there is 1 consecutive colored grid of length 2,
for the second column, there are exactly 2 consecutive colored grids both of length 1,
...

So the answer is "Yes".

---

For the second Nonogram in the sample input, the input is as follows:

the grid at the third row and the third column should be a 'o' so that the Nonogram can be correct,
so the output should be a "No".

---

 

Input

The first line contains an integer T,
representing that your sister has just finished T Nonograms.

Then for each Nonogram, the first line contains 2 integers N, M, representing the numbers of rows and columns of the Nonogram, respectively.

Then for each of the following N lines,
there is an integer Row_L_i representing the length of the list beside the i_th row,
followed by Row_L_i integers, separated by spaces, representing the numbers of the list beside the i_th row,
where the numbers in the list are given from left to right.

Then for each of the following M lines,
there is an integer Col_L_i representing the length of the list beside the i_th column,
followed by Col_L_i integers, separeted by spaces, representing the numbers of the list beside the i_th column,
where the numbers in the list are given from up to down.

Lastly, each of the following N lines has M characters,
representing the Nonogram your sister has finished, where
the character 'o' represents that the grid is colored, while
the character 'x' represents that the grid is not colored and empty.

It is guaranteed that:

1 <= T <= 10,
1 <= N, M <= 45

and the given lists of numbers are always valid.

Output

Output should contain T lines:

for each Nonogram,

output "Yes" (without quotes) if the Nonogram is solved correctly;

otherwise, output "No" (without quotes).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

During the New Year sale, Panda wants to purchase items from his wish list.

The wish list has N items.
Each item has name, original price, discount, quality (Si, Pi, Di, Qi).
The selling price for an item is its original price subtract discount (Pi − Di)

Panda’s budget is only X dollars which is too less to pruchase all items in wish list.
He designs 3 kinds of purchase strategies for items:

Strategy 1: less selling price first, the item with less selling price will be selected first.
Strategy 2: more discount first, the item with more discount will be selected first.
Strategy 3: higher quality first, the item with higher quality will be selected first.

Panda will sort the wish list by applying these strategies in a special order O.
Then purchase the items from top to down until his budget can’t buy anything.

This problem is a partial judge problem.
You have to complete functions under given interface.
Please refer to function.h, main.c for implementation details.

function.h

#ifndef __FUNCTION_H__
#define __FUNCTION_H__


typedef struct _Item {
    char* name;
    int price;
    int discount;
    int quality;
} Item;

Item* CreateList(int N);
void AddItem( Item* L, int idx, char* name, int price, int discount, int quality );
void DeleteList(Item* L, int N);

int price_cmp( const void* lhs, const void* rhs );
int discount_cmp( const void* lhs, const void* rhs );
int quality_cmp( const void* lhs, const void* rhs );

#endif

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "function.h"

#define MAX_NAME 100

typedef int (*func_ptr)(const void*, const void*);

int N, X;
int O[3];
func_ptr cmp[3] = { price_cmp, discount_cmp, quality_cmp };

int qsort_cmp( const void* lhs, const void* rhs){
    for(int i=0; i<3; i++){
        int res = cmp[ O[i]-1 ](lhs, rhs);
        if( res != 0 ) // If not same
            return res;
    }
    // This case will not appear in Test cases;
    int str_res = strcmp( ((Item*)lhs)->name, ((Item*)rhs)->name);
    if( str_res < 0 ) return -1;
    if( str_res > 0 ) return 1;
    return 0;
}


int main(){
    int T;
    scanf("%d", &T);
    for(int cnt=1; cnt<=T; cnt++){
        scanf("%d %d %1d%1d%1d", &N, &X, &O[0], &O[1], &O[2]);

        Item* L = CreateList(N);
        char name[MAX_NAME+1];
        int P, D, Q;
        for(int i=0; i<N; i++){
            scanf("%s %d %d %d", name, &P, &D, &Q);

            AddItem(L, i, name, P, D, Q);
        }
        
        qsort( L, N, sizeof( Item ), qsort_cmp);

        printf("case %d:\n", cnt);
        for(int i=0; i<N; i++){
            int sp = L[i].price - L[i].discount;
            if( sp < X ){
                printf("%s\n", L[i].name);
                X -= sp;
            }
        }
        DeleteList(L, N);
    }
    return 0;
}

Input

This problem contains multiple inputs.
There’s an integer T on the first line, denoting the number of input.

For each input, there’re N, X, O on the first line.
There’re Si, Pi, Di, Qi on the following N lines.

It’s guaranteed that:

• 1 ≤ T ≤500
• 1 ≤ N ≤ 1000
• 1 ≤ X ≤10⁶
• |Si| ≤ 100
• (Pi, Di, Qi) ≠ (Pj, Dj, Qj) for all i ≠ j.
•  O ∈{123, 132, 213, 231, 312, 321 }

Output

Output the item names Panda decides to purchase ( in sorted wish list order ).

Explaintation for Sample I/O:

The budget is 200, and the wish list:

A 120 50 1 // selling price = 70
B 100 40 2 // selling price = 60
C 100 30 2 // selling price = 70
D 100 40 3 // selling price = 60
E 100 30 4 // selling price = 70

• O = 123:
  • First, sort by selling price (increasing order)
  • Second, sort by discount (decreasing order) for those have the same selling price.
  • Third, sort by quality (decreasing order) for those have the same selling price and discount.
  • The sorted list:

    D 100 40 3
    B 100 40 2
    A 120 50 1
    E 100 30 4
    C 100 30 2
    

  • Pandas will using 190 dollars to purchase “D”, “B”, “A”
• O = 312:
  • First, sort by quality
  • Second, sort by selling price for those have the same quality.
  • Third, sort by discount for those have the same selling quality and selling price.
  • The sorted list:

    E 100 30 4
    D 100 40 3
    B 100 40 2
    C 100 30 2
    A 120 50 1
    

  • Pandas will using 190 dollars to purchase “E”, “D”, “B”

Sample Input  Download

Sample Output  Download

Partial Judge Code

13099.c

Partial Judge Header

13099.h

Tags

Discuss