Codeforces Round #270 A～D - c++编程基础

) high=i; if(now+all[i]<=k) { now+=all[i]; all[i]=0; } else /// now + all[i]>k { int res=k-now; all[i]-=res; now=k; } } if(now==k||i==1) { ans+=(high-1)*2; now=0;high=1; } } printf("%d\n",ans); return 0; }

C. Design Tutorial: Make It Nondeterministic time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

A way to make a new task is to make it nondeterministic or probabilistic. For example, the hard task of Topcoder SRM 595, Constellation, is the probabilistic version of a convex hull.

Let's try to make a new task. Firstly we will use the following task. There are n people, sort them by their name. It is just an ordinary sorting problem, but we can make it more interesting by adding nondeterministic element. There are n people, each person will use either his/her first name or last name as a handle. Can the lexicographical order of the handles be exactly equal to the given permutation p?

More formally, if we denote the handle of the i-th person as hi, then the following condition must hold: $\$ .<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KCgoKSW5wdXQKPHA+ClRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgPGVtPm48L2VtPiAoMT+h3D88ZW0+bjwvZW0+P6HcPzEwNSkgoaoKIHRoZSBudW1iZXIgb2YgcGVvcGxlLjwvcD4KPHA+ClRoZSBuZXh0IDxlbT5uPC9lbT4gbGluZXMgZWFjaCBjb250YWlucyB0d28gc3RyaW5ncy4gVGhlIDxlbT5pPC9lbT4tdGgKIGxpbmUgY29udGFpbnMgc3RyaW5ncyA8ZW0+ZjwvZW0+PGVtPmk8L2VtPiBhbmQgPGVtPnM8L2VtPjxlbT5pPC9lbT4gKDE/odw/"fi|,?|si|?≤?50) ― the first name and last name of the i-th person. Each string consists only of lowercase English letters. All of the given 2n strings will be distinct.

The next line contains n distinct integers: p1,?p2,?...,?pn (1?≤?pi?≤?n).

Output

If it is possible, output "YES", otherwise output "NO".

Sample test(s) input

3
gennady korotkevich
petr mitrichev
gaoyuan chen
1 2 3

output

NO

input

3
gennady korotkevich
petr mitrichev
gaoyuan chen
3 1 2

output

YES

input

2
galileo galilei
nicolaus copernicus
2 1

output

YES

input

10
rean schwarzer
fei claussell
alisa reinford
eliot craig
laura arseid
jusis albarea
machias regnitz
sara valestin
emma millstein
gaius worzel
1 2 3 4 5 6 7 8 9 10

output

NO

input

10
rean schwarzer
fei claussell
alisa reinford
eliot craig
laura arseid
jusis albarea
machias regnitz
sara valestin
emma millstein
gaius worzel
2 4 9 6 5 7 1 3 8 10

output

YES

Note

In example 1 and 2, we have 3 people: tourist, Petr and me (cgy4ever). You can see that whatever handle is chosen, I must be the first, then tourist and Petr must be the last.

In example 3, if Copernicus uses "copernicus" as his handle, everything will be alright.

#include 
    
     
#include 
     
       #include 
      
        #include 
       
         using namespace std; int n,p[100100]; struct NME { char str1[60],str2[60]; }name[100100]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s%s",name[i].str1,name[i].str2); //cout<
        
         
 
         
 
          D. Design Tutorial: Inverse the Problem time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 
          There is an easy way to obtain a new task from an old one called "Inverse the problem": we give an output of the original task, and ask to generate an input, such that solution to the original problem will produce the output we provided. The hard task of Topcoder Open 2014 Round 2C, InverseRMQ, is a good example. 
          Now let's create a task this way. We will use the task: you are given a tree, please calculate the distance between any pair of its nodes. Yes, it is very easy, but the inverse version is a bit harder: you are given an n?×?n distance matrix. Determine if it is the distance matrix of a weighted tree (all weights must be positive integers). Input 
          The first line contains an integer n (1?≤?n?≤?2000) ― the number of nodes in that graph. 
          Then next n lines each contains n integers di,?j (0?≤?di,?j?≤?109) ― the distance between node i and node j. Output 
          If there exists such a tree, output "YES", otherwise output "NO". Sample test(s) input 
         3
0 2 7
2 0 9
7 9 0
 output 
         YES
 input 
         3
1 2 7
2 0 9
7 9 0
 output 
         NO
 input 
         3
0 2 2
7 0 9
7 9 0
 output 
         NO
 inp

Codeforces Round #270 A～D(二)