Among the large Wisconsin cattle ranchers, it is customary to brand cows with serial numbers to please the Accounting Department. The cow hands don't appreciate the advantage of this filing system, though, and wish to call the members of their herd by a pleasing name rather than saying, "C'mon, #4734, get along."
Help the poor cowhands out by writing a program that will translate the brand serial number of a cow into possible names uniquely associated with that serial number. Since the cow hands all have cellular saddle phones these days, use the standard Touch-Tone(R) telephone keypad mapping to get from numbers to letters (except for "Q" and "Z"):
2: A,B,C 5: J,K,L 8: T,U,V
3: D,E,F 6: M,N,O 9: W,X,Y
4: G,H,I 7: P,R,S
Acceptable names for cattle are provided to you in a file named "dict.txt", which contains a list of fewer than 5,000 acceptable cattle names (all letters capitalized). Take a cow's brand number and report which of all the possible words to which that number maps are in the given dictionary which is supplied as dict.txt in the grading environment (and is sorted into ascending order).
For instance, the brand number 4734 produces all the following names:
GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI GREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEI GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFI HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDI HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEI IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFI ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI
As it happens, the only one of these 81 names that is in the list of valid names is "GREG".
Write a program that is given the brand number of a cow and prints all the valid names that can be generated from that brand number or ``NONE'' if there are no valid names. Serial numbers can be as many as a dozen digits long.
PROGRAM NAME: namenum
INPUT FORMAT
A single line with a number from 1 through 12 digits in length.SAMPLE INPUT (file namenum.in)
4734
OUTPUT FORMAT
A list of valid names that can be generated from the input, one per line, in ascending alphabetical order.SAMPLE OUTPUT (file namenum.out)
GREG
思路：把字典存在set里面，然后按题目要求生产各种可能情况，看是否在set里即可
/*
ID: youqihe1
PROG: namenum
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include<string.h>
#include<set>
using namespace std;
set<string> name;
int main() {
FILE *fin1 = fopen ("namenum.in", "r");
FILE *fin2 = fopen ("dict.txt", "r");
FILE *fout = fopen ("namenum.out", "w");
int i,j,k;
char A[12];
fscanf(fin1,"%s",A);
int LEN=strlen(A);
int flag=0;
for(i=0;i<4617;i++)
{
char B[12];
fscanf(fin2,"%s",B);
int len=strlen(B);
if(LEN!=len)
continue;
int flag1=1;
for(j=0;j<len;j++)
{
char c=B[j];
if(c>='Q') c--;
int a=(c-'A')/3+2;
if(A[j]-'0'!=a)
{
flag1=0;
break;
}
}
if(flag1)
{
fprintf(fout,"%s\n",B);
flag=1;
}
}
if(flag==0)
fprintf(fout,"NONE\n");
return 0;
}
同样用到容器，我用set做了这题，把可能的组合放到set，自动去重
Farmer John's cows keep escaping from his farm and causing mischief. To try and prevent them from leaving, he purchases a fancy combination lock to keep his cows from opening the pasture gate.
Knowing that his cows are quite clever, Farmer John wants to make sure they cannot easily open the lock by simply trying many different combinations. The lock has three dials, each numbered 1..N (1 <= N <= 100), where 1 and N are adjacent since the dials are circular. There are two combinations that open the lock, one set by Farmer John, and also a "master" combination set by the lock maker.
The lock has a small tolerance for error, however, so it will open even if the numbers on the dials are each within at most 2 positions of a valid combination.
For example, if Farmer John's combination is (1,2,3) and the master combination is (4,5,6), the lock will open if its dials are set to (1,3,5) (since this is close enough to Farmer John's combination) or to (2,4,8) (since this is close enough to the master combination). Note that (1,5,6) would not open the lock, since it is not close enough to any one single combination.
Given Farmer John's combination and the master combination, please determine the number of distinct settings for the dials that will open the lock. Order matters, so the setting (1,2,3) is distinct from (3,2,1).
PROGRAM NAME: combo
INPUT FORMAT:
| Line 1: | The integer N. |
| Line 2: | Three space-separated integers, specifying Farmer John's combination. |
| Line 3: | Three space-separated integers, specifying the master combination (possibly the same as Farmer John's combination). |
SAMPLE INPUT (file combo.in):
50 1 2 3 5 6 7
INPUT DETAILS:
Each dial is numbered 1..50. Farmer John's combination is (1,2,3), and the master combination is (5,6,7).
OUTPUT FORMAT:
| Line 1: | The number of distinct dial settings that will open the lock. |
SAMPLE OUTPUT (file combo.out):
249
/*
ID: youqihe1
PROG: combo
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include <set>
using namespace std;
struct key
{
int a;
int b;
int c;
bool operator <(const key &AA) const
{
if(AA.a==a)
{
if(AA.b==b)
return AA.c<c;
return AA.b<b;
}
return AA.a<a;
}
};
int main() {
FILE *fin = fopen ("combo.in", "r");
FILE *fout = fopen ("combo.out", "w");
int N;
int i,j,k;
set<key>HEHE;
fscanf(fin,"%d",&N);
int B[3];
fscanf(fin,"%d %d %d",&B[0],&B[1],&B[2]);
int A[3][5];
for(i=0;i<3;i++)
{
for(j=-2,k=0;j<3;j++,k++)
{
int t=(B[i]+j);
if(t<=0)
t=N+B[i]+j;
else t=(B[i]+j)%N;
if(t==0)
t=N;
A[i][k]=t;
}
}
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
for(k=0;k<5;k++)
{
key hh;
hh.a=A[0][i];
hh.b=A[1][j];
hh.c=A[2][k];
HEHE.insert(hh);
}
}
}
fscanf(fin,"%d %d %d",&B[0],&B[1],&B[2]);
for(i=0;i<3;i++)
{
for(j=-2,k=0;j<3;j++,k++)
{
int t=(B[i]+j);
if(t<=0)
t=N+B[i]+j;
else t=(B[i]+j)%N;
if(t==0)
t=N;
A[i][k]=t;
}
}
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
for(k=0;k<5;k++)
{
key hh;
hh.a=A[0][i];
hh.b=A[1][j];
hh.c=A[2][k];
HEHE.insert(hh);
}
}
}
int sum=HEHE.size();
fprintf(fout,"%d\n",sum);
return 0;
}