출처: https://train.usaco.org/usacogate
문제 설명
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).
입력
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).
출력
Line 1: The number of distinct dial settings that will open the lock.
입력 예
50
1 2 3
5 6 7
출력 예
249
문제 풀이 내용
입력받은 수에서 각 자리수들이 가능한 영역을 결정하고, 가능한 모든 3자리 수를 만들어서 set에 입력한다. 중복되는 조합은 set 특성에 의해서 없어지므로, set에 입력된 조합의 개수를 출력한다.
프로그램 내용
#define MAX_DIAL 100
int RANGE[5];
/// dial_num -1 -> 47, 48, 49, 50, (1), adding code value=1,
/// dial_num -> 48, 49, 50, (1), (2),adding code value=1, 2
/// code : 1 -> (49), (50), 1, 2, 3, adding code value=dial_num, dial_num-1
/// code : 2 -> (50), 1, 2, 3, 4, adding code value = dial_num
void set_Range(int input, int dial_num);
int main() {
/// Read dial number
fin >> dial_num;
int f1, f2, f3;
fin>> f1 >> f2 >> f3;
int m1, m2, m3;
fin>> m1 >> m2 >> m3;
set <string> codes;
/// build passed codes range for all codes
vector <string> f1_code;
vector <string> f2_code;
vector <string> f3_code;
vector <string> m1_code;
vector <string> m2_code;
vector <string> m3_code;
/// if dial_num < 5
/// all codes are not available.
/// if dail_num = 1, 1^3
/// if dail_num = 2, 2^3
/// if dail_num = 3, 3^3
/// if dail_num = 4, 4^3
/// if dail_num = 5, 5^3
/// init f_codes
set_Range(f1, dial_num);
set_Range(f2, dial_num);
set_Range(f3, dial_num);
/// insert all codes from farmers code
for (int idx=0; idx < 5; ++idx)
{
...
}
/// init m_codes
set_Range(m1, dial_num);
set_Range(m2, dial_num);
set_Range(m3, dial_num);
/// insert codes from master code
for (int idx=0; idx < 5; ++idx)
{
...
}
if (dial_num < 6)
fout << dial_num * dial_num * dial_num << endl;
else
fout << codes.size() << endl;
return 0;
}
Chapter 1. Getting started
'USACO Training' 카테고리의 다른 글
| Problem 1.4.8 Ski Course Design (0) | 2019.09.12 |
|---|---|
| Problem 1.4.7 Wormholes (0) | 2019.09.12 |
| Problem 1.4.5 Prime Cryptarithm (0) | 2019.09.12 |
| Problem 1.4.3 Barn Repair (0) | 2019.09.12 |
| Problem 1.4.2 Mixing Milk (0) | 2019.09.12 |