时间限制:

10000ms

单点时限:

1000ms

内存限制:

256MB

描述

Given a set of constraints like 0<N<=M<=100 and values for all the variables, write a checker program to determine if the constraints are satisfied.

More precisely, the format of constraints is:

token op token op ... op token

where each token is either a constant integer or a variable represented by a capital letter and each op is either less-than ( < ) or less-than-or-equal-to ( <= ).

输入

The first line contains an integer N, the number of constraints. (1 ≤ N ≤ 20)

Each of the following N lines contains a constraint in the previous mentioned format.

Then follows an integer T, the number of assignments to check. (1 ≤ T ≤ 50)

Each assignment occupies K lines where K is the number of variables in the constraints.

Each line contains a capital letter and an integer, representing a variable and its value.

It is guaranteed that:

1. Every token in the constraints is either an integer from 0 to 1000000 or an variable represented by a capital letter from 'A' to 'Z'.

2. There is no space in the constraints.

3. In each assignment every variable appears exactly once and its value is from 0 to 1000000.

输出

For each assignment output Yes or No indicating if the constraints are satisfied.

样例输入

2A<=E3<=E<52A 1B 2E 3A 3B 5E 10 样例输出

YesNo

---

比较简单的字符串处理题。写这篇是要记录下C++的istream类的用法。

朴素实现：

#include 
     
      using namespace std;map
      
        mp;string c[20];bool used[26];bool ok(int a, string &op, int b){    if(op=="<") return a
       
        >n;    for(int i=0; i
        
         >c[i];        for(auto x:c[i])            if(isalpha(x)) used[x-'A']=true;    }    int nv=0;    for(int i=0; i<26; i++) nv+=used[i];    for(cin>>T; T--; ){        for(int i=0; i
         
          >x>>v;            mp[x]=v;        }        puts(check(n)?"Yes":"No");    }}
         
        
       
      
     

借助stringstream类的实现：

#include 
     
      using namespace std;map
      
        mp;string c[20];bool used[26];int get_val(stringstream &x){    int res;    char v;    x>>res;    if(x.fail()){    //check whether badbit or failbit is set        //When an istream object turns fail, it stops working until flags reset         x.clear();    //new        x.get(v), res=mp[v];    }    return res;}string get_op(stringstream &x){    char v;    string res;    if(x.str().empty()) return res;    for(;;){        x.get(v);        if(ispunct(v)) res+=v;        else{            x.putback(v);            return res;        }    }}bool ok(int a, string &op, int b){    if(op=="<") return a
       
        >n;    for(int i=0; i
        
         >c[i];        for(auto x:c[i])            if(isalpha(x)) used[x-'A']=true;    }    int nv=0;    for(int i=0; i<26; i++) nv+=used[i];    for(cin>>T; T--; ){        for(int i=0; i
         
          >x>>v;            mp[x]=v;        }        puts(check(n)?"Yes":"No");    }}
         
        
       
      
     

这里系统介绍一下C++的Stream I/O. （以下内容来自 The C++ Programming Language 4th Ed. by Bjarne Stroustrup, 38 I/O Streams）.

• The I/O stream library provides formatted and unformatted buffered I/O of text and numeric values. The definitions for I/O stream facilities are found in <istream>, <ostream>, etc.;
• An istream converts a stream of characters (bytes) to typed objects:

Byte sequences --> stream buffer --> istream --> typed values

An iostream is a stream that can act as both an istream and an ostream. You need stream buffers (streambufs) to define a mapping from an iostream to a new kind of device, file, or provide a new locale, you need a copy of the standard, a good systems manual, and examples of working code in addition to what is presented here.

 

The key components of the stream I/O system can be represented graphically like this:

　　　　ios_base:　　　　　　　　　　　|-------------------------------------->|---------------------------------->locale: format information 　　　　　　　　　　　　　　　　　　

locale independent format state　　　　　   |　　　　　　　　　　　　  |　

　　　　^　　　　　　　　　　　　　　　|------> basic_streambuf<>:　--------------------------------> real destination/source:

　　　　I　　　　　　　　　　　　　　　 |　　　　buffering　　　　　|　　　　　　　　　　　　　

　　　　I　　　　　　　　　　　　　　　 |　　　　　　　　　　　　    |　

　　basic_ios<>: ------------------------------------|　　　　　　　　　　　　　|--------------------------------> character buffer

locale dependent format state

　　stream state

　　　　^

　　　　|

　　　　|

　basic_iostream<>:

formatting (<<, >>, etc.)

　　setup/cleanup

 

The vertical arrows represent "derived from." The horizontal arrows represent "pointer to." The classes marked with <> are templates parameterized by a character type and containing a locale.  

38.3 Error Handling

  An iostream can be in one of four states, defined in basic_ios from <ios>:

---

 

Stream States

---

 

good()　　The previous iostream operations succeeded

eof() 　　  We hit end-of-input ("end-of-file")

fail()　　　Something unexpected hapened (e.g., we looked for a digit and found 'x')

bad()　　  Something unexpected and serious happened (e.g., disk read error)

---

 

Any operation attempted on a stream that is not in the good() state has no effect; it is a no-op. An iostream can be used as a condition. In that case, the condition is true (succeeds) if the state of the iostream is good().

38.4.4 Stream State

In <ios>, the standard library defines the base class ios_base defining most of the interface to a stream class.

The basic_ios class manages the state of a stream:

• The mapping between a stream and its buffers
• The formatting options
• The use of locales
• Error handling
• Connections to other streams and stdio

It might be the most complicated class in the standard library.

---

 

ios_base Stream State iostate Member Constants

---

 

badbit　　Something unexpected and serious happened (e.g., a disk read error)

failbit　　Something unexpected hppened (e.g., we looked for a digit and found 'x')

eofbit　　We hit end-of-input (e.g., end-of-file)

goodbit　All is well

---

 

Functions for reading these bits (good(), fail(), etc.) in a stream are provided by basic_ios.