Problem B: B Have a Nice Day
Time Limit: 1 Sec Memory Limit:
128 MB
Submit: 136 Solved: 40
[Submit][Status][Web Board]
Description
Problem
Rumour has it that the P versus N P question has been solved: the two classes are not equal. This
implies that many well-known problems, such as the Traveling Salesman Problem, will remain
difficult forever. It can be considered a waste of time to search for polynomial time solutions:
essentially only brute-force approaches can solve them. Nothing you can do about that.
In view of the international crisis, the new Dutch government has therefore announced that
on certain days it is not allowed to work on these hard problems anymore. Instead, one must
concentrate on easier issues. These days are called nice. Of course, the algorithm to decide
whether a given date is nice or not should itself be easy. So far politicians could not find such an
algorithm. Can you?
A date day month year is written down using the digits 0,. . . ,9. A date is called nice if the
digits occurring in it occur an equal number of times, and if it can be split. A date can be split
if its four number set can be divided into two disjoint subsets with equal sum; the four numbers
are the day, the month, the left part of the year (the number represented by its first and second
digit; for 1957 this is 19) and the right part of the year (the number represented by its third and
fourth digit; for 2000 this is 0). For example, 16 5 4928 is nice, because all digits occur exactly
once and 16 + 5 + 28 = 49.
Input
The first line of the input contains a single number: the number of test cases to follow. Each test
case has the following format:
• One line with three integers D, M and Y separated by single spaces, satisfying 1 ≤ D ≤ 31,
1 ≤ M ≤ 12 and 1000 ≤ Y ≤ 9999: the day, month and year of a valid date, respectively.
Output
For every test case in the input, the output should contain the string "yes" or "no": the fact
whether the date is nice or not.
Sample Input
4 16 5 4928 14 12 2747 11 11 1111 3 3 2014
Sample Output
yes no yes no
HINT
此题昨晚甚是纠结。。。。。。今天看了大神的代码,恍然大悟!!!!!!
只怪自己太弱。。。。
题意:给你三个数:day,month,year(左右各取两位,分成左右两个数)要求这四个数出现的次数相等,而且任意两个数相加等于另外两个数相加或者任意三个数相加等于另外一个数。
#include<stdio.h> #include<string.h> int digs[10]; void countdigs(int x) { while(x) { x%=10; digs[x]++; x/=10; } } bool solve(int a,int b,int c,int d) { return a == b + c + d || a + b == c + d || a + c == b + d || a + d == b + c || a + b + c == d || a + b + d == c || a + c + d == b; } int main() { int t,d,m,y; scanf("%d",&t); while(t--) { memset(digs,0,sizeof(digs)); scanf("%d%d%d",&d,&m,&y); countdigs(d); countdigs(m); countdigs(y); for(int i=0;i<10;i++) for(int j=0;j<10;j++) { if(digs[i]>0&&digs[j]>0&&digs[i]!=digs[j]) { printf("no\n"); return 0; } } if(solve(d,m,y/100,y%100)) printf("yes\n"); else printf("no\n"); } return 0; }