Coding Exercise – Timus Online Judge – 1877. Bicycle Codes – C++ solution


1877 Coding Exercise - Timus Online Judge - 1877. Bicycle Codes - C++ solution algorithms beginner brute force c / c++ code implementation math programming languages

The problem is from Timus Online Judge.

Den only has two locks. He never uses the same lock two days in a row. Therefore, if the thief wants to open the lock, he needs to guess the combination that happens to be used that night.

To solve this problem, we just have to emulate the situation iteratively. When the combination used by the thief is bigger than both, then it is impossible.

The following C++ code is straightforward to demonstrate the combination-guessing game.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;
 
int main()
{
    int code[2];
    cin >> code[0] >> code[1];
 
    int test = 0;
    int idx = 0;
    while (true)
    {
        if (test == code[idx])
        {
            cout << "yes" << endl;          
            break;      
        }       
        test ++; // combination used by theif       
        if ((test > code[0]) && (test > code[1]))
        {
            cout << "no" << endl;
            break;
        }
        idx = (idx + 1) % 2;
    }
 
    return (0);
}
#include <iostream>
using namespace std;

int main()
{
	int code[2];
	cin >> code[0] >> code[1];

	int test = 0;
	int idx = 0;
	while (true)
	{
		if (test == code[idx])
		{
			cout << "yes" << endl; 			
			break; 		
		} 		
		test ++; // combination used by theif 		
		if ((test > code[0]) && (test > code[1]))
		{
			cout << "no" << endl;
			break;
		}
		idx = (idx + 1) % 2;
	}

	return (0);
}

A Facebook friend suggests a quicker solution (and how come I didn’t think of this in the first place?)

If the first lock’s combination is an odd number and the second’s is an even number, then the thief won’t get the bicycle. It’s shorter and much faster than trying all 10,000 combinations.

Yes, pure math!

1
2
3
4
5
6
7
8
9
10
#include <iostream>
using namespace std;
 
int main()
{
    int code[2];
    cin >> code[0] >> code[1];
    cout << (((code[0] % 2) == 0) || ((code[1] % 2) != 0) ? "yes" : "no");
    return (0);
}
#include <iostream>
using namespace std;

int main()
{
    int code[2];
    cin >> code[0] >> code[1];
    cout << (((code[0] % 2) == 0) || ((code[1] % 2) != 0) ? "yes" : "no");
    return (0);
}

However, the test cases (only four digit combination, so the input range is small) are weak, both programs get AC in 0.031 s (roughly the same time).

Considering apply this to the same problem with larger input domain, the second one is obviously better, tex_3be74cac013d6997340f7ab8973bbd70 Coding Exercise - Timus Online Judge - 1877. Bicycle Codes - C++ solution algorithms beginner brute force c / c++ code implementation math programming languages rather than the first approach tex_caa5d58969fcc95bcd6477b6782501fa Coding Exercise - Timus Online Judge - 1877. Bicycle Codes - C++ solution algorithms beginner brute force c / c++ code implementation math programming languages .

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
457 words
Last Post: Coding Exercise - Timus 1785. Lost in Localization - C++ solution - Online Judge
Next Post: Coding Exercise - Timus Online Judge - 1293. Eniya, C/C++ solution

The Permanent URL is: Coding Exercise – Timus Online Judge – 1877. Bicycle Codes – C++ solution

Leave a Reply