Sane's Monthly Algorithms Challenge: November 2008
The Factor Game (Senior Level)
For this challenge, things are a little different. You are playing a game against Sane himself!
The game goes like so, starting with a positive integer n, and a score = 0.
- I input the integer
n. - The game ends here if
n= 1. - You respond by outputting two positive integers which multiply to
n.
This step increases yourscoreby 1. - I choose one of the numbers you outputted. Let this number be
n. - Repeat from step 1.
score.You may assume that I am trying my hardest to minimize your
score with Step 4.
Input
Every line will be a legal integer n (1 ≤ n ≤ 2,000,000,000), according to the rules of the game. I will stop inputting numbers as soon as I enter 1.
Output
Every line will be two integers, separated by a space.
Remember to end each line with a newline character.
You should flush the output buffer after each line (fflush(NULL) in C/C++, flush(output) in PAS).
Optimal Sample Interaction (Correct)
Input in italics.
32
4 8
4
2 2
2
2 1
1
This obtains a score of 3 (which is the maximum).
Suboptimal Sample Interaction (Incorrect)
Input in italics.
32
2 16
2
2 1
1
This obtains a score of 2 (this is not the maximum).
Grading
For each interaction where you obtain the maximum possible score, you will have passed that piece of test data. If you ever make an illegal move, or get a lower score than the best possible, you will have failed that piece of test data.
Hints
Make sure you can prove to yourself that your strategy is, in fact, optimal.Remember that I know how to make the best choice (especially in the long run) at
Step 4.
All Submissions
Best Solutions
Point Value: 15
Time Limit: 1.00s
Memory Limit: 16M
Added: Jan 17, 2009
Author: DrSane
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
I tried 50304 on my computer, and nowhere did it output 3, but it said it did when I submitted my code.
Here's my output:
64 786
8 8
2 4
1 2
1
Can somebody tell me what's wrong with this output and the correct output? Thanks.
8 8
2 4
1 2
1
You're not outputting that last line, are you? Because that would make it incorrect o_o.
8 8
2 4
1 2
Instead of picking 64, the program would actually pick 786.
I assume then that your program outputs
A correct simulation might be, for example:
50304
24 2096
2096
4 524
4
2 2
2
2 1
1
That yields a score of 4, superior to your score of 3.
Score | Output
1 | 64 786
2 | 8 8
3 | 2 4
4 | 1 2
I assume then that your program outputs
(Quote: 3 262)
, which is where you got the 3.
Score | Input | Resulting Output
1 | 50304 | 64 786
2 | 786 | 3 262
3 | 3 | 1 3
Anyone know why I'm getting this message for 5/13? Runtime Error (11: SIGSEGV) [IOError: [Errno 32] Bs, .write('please quit!')] [Program_crash_] I'm getting AC on all other test cases, plus the ones I made, and it doesn't seem to be in any danger of TLEing. Any ideas?Runtime Error (11: SIGSEGV) [IOError: [Errno 32] Bs, .write('please quit!')]
[Program_crash_]
I'm getting AC on all other test cases, plus the ones I made, and it doesn't seem to be in any danger of TLEing.
Any ideas?
For C/C++ users fflush(NULL) after cout/printf (as stated) is fine.
Pascal users should put flush(output) after writeln(...).
Short Answer: It forces the buffer to be printed.
Long Answer: The OS doesn't always print something when you want it to. Sometimes, it accumulates your output in a buffer until the time comes when it feels that it should be printed. The obvious reason why is because it can be faster to buffer a series of characters and call a low-level routine once, than to call that routine multiple times. But, the trade-off is things don't always get printed out as soon as they are needed. If you are communicating with a program via command line, it will always know that you want to read the text and it will flush the buffer immediately. But the OS doesn't know that my program (your opponent) wants to read the text, and so it will think it's smart to save the buffer for later. Consequently, my program is waiting for your input while you have already moved on and are now waiting for my input. Both programs hang, and nobody is happy. You can prevent this by asserting that you don't save the buffer after each output statement with an fflush(NULL).
Just a regular TLE.