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.

  1. I input the integer n.
  2. The game ends here if n = 1.
  3. You respond by outputting two positive integers which multiply to n.
    This step increases your score by 1.
  4. I choose one of the numbers you outputted. Let this number be n.
  5. Repeat from step 1.
The objective of the game is to maximize your 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)

so does the program chooses the factor arbitrarily or the lowest factor?

Re-read the question.

do i use an AVL tree for this?

Please read this

For Test Case #7, what am I getting wrong?
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.

64 786
8 8
2 4
1 2
1

You're not outputting that last line, are you? Because that would make it incorrect o_o.

Oh, no I'm not lol. So do you know the correct output?

Well, your output isn't correct.
64 786
8 8
2 4
1 2

Instead of picking 64, the program would actually pick 786.
I assume then that your program outputs
3 262
, which is where you got the 3.

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.

I'm pretty sure I also have a score of 4...
Score | Output
1 | 64 786
2 | 8 8
3 | 2 4
4 | 1 2

Instead of picking 64, the program would actually pick 786.
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

Oh, sorry didn't notice that, thnx.

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?

It's not a problem on the Judge's end. Try the case 1000000 --- your program crashes before it prints anything at all.


Okay, I can tell you it's 50304, if that helps...

He hard-coded 50304 into his solution...

Flushing is important! Otherwise you'll get TLE automatically.
For C/C++ users fflush(NULL) after cout/printf (as stated) is fine.
Pascal users should put flush(output) after writeln(...).

What does flushing do?
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).

can i see a example of flushing? please output '11' with flushing. in pascal. im a bit confused

writeln(11); 
flush(output);

What is 'Bad_output_format:_'? confused.gif

You outputted nothing when it was expecting something.
Just a regular TLE.