Problem 11245

[shahriar_manzoor]

It is a tricky situation.

No correct verdict can be made incorrect after contest.

Given the situation I just wonder whether a rejudgement will be fair bcause no way the problem can be corrected.

[A1]

This problem is actually an edited version of :
http://www.kalva.demon.co.uk/usa/usoln/usol951.html
A MathOlympiad problem!! So the people who did practice for math olympiad problems could get it common!!!
And i think, they just forgot to mention the Prime thing..

IMO: I belive that in a programming contest there could be maximum one problem which needs math or geometry concept and which could have 3-4 lines of derivation and 15-20 lines of code !! Not 15-20 lines derivation and 2-4 lines of code! otherwise it could ruin the basic concept of programming contest!!!

[sohel]

A wrong problem (badly written or false judge data) can really ruin the whole contest. Similar thing happend in another contest recently[wrong judge data].

My team spent a lot of time on this problem trying to find some sort of pattern. But the pattern can only be found for odd primes.
Looking at the ranklist, it was observed that a team already solved this problem, so we thought we were very close(!) to the solution for non-prime numbers as well. And this was in the middle of 13 times WA on D :|.
This also created some impediments to switch to other problems.

So following the ranklist isn't always a good idea.

Sadly, these kinds of things can't be accounted for during rejudgement.


Deja Vu. Coimbatore 2006!

[shahriar_manzoor]

This problem is actually an edited version of :
http://www.kalva.demon.co.uk/usa/usoln/usol951.html
A MathOlympiad problem!! So the people who did practice for math olympiad problems could get it common!!!
And i think, they just forgot to mention the Prime thing..

IMO: I belive that in a programming contest there could be maximum one problem which needs math or geometry concept and which could have 3-4 lines of derivation and 15-20 lines of code !! Not 15-20 lines derivation and 2-4 lines of code! otherwise it could ruin the basic concept of programming contest!!!

I think you are over saying. a programming contest with 2 geometric problems is common. And then a number theory problem is still common. May be this contest had two math problem more and no geometric problem. But that is a different story not somthing related to this thread. And always people will differ with their idea of combination of problemset. The best idea is two have different combination for each contest and don't become predictable. While selecting problems we don't have an unending supply of problems so just have to work with the problems in hand.

It remineds me something that happened in 2004 NCPC a long thread critisizing the problemset.

[Robert Gerbicz]

From problem statement:

Code: Select all

 This contest took place realtime in Bangladesh on 20th July, 2007. So don't be surprised to see pretty early submissions.

Is it general on programming contests?
How is it fair? So non Bangladesh users has got 4 hours to solve the problems, but if you live in Bangladesh then you've got 10 days. Not bad.

[shahriar_manzoor]

This contest is for practice. At UVa we hold a lot of old contest every year.

Holding a contest parallel is often difficult for us.

[sohel]

How is it fair? So non Bangladesh users has got 4 hours to solve the problems, but if you live in Bangladesh then you've got 10 days. Not bad.

Well, many of the Bangladeshi Contestants refrained themselves from doing the contest for this reason. I only did the ones that I couldn't solve during the onsite contest.

[Carlos]

shahriar, what shall I do for the 24 hours OJ? Shall I change the description and delete huge test cases?

[anonymousbd]

i THINK IT SHOULD BE

B
Anti Arithmetic Sequence

Input: Standard Input

Output: Standard Output





An anti-arithmetic sequence is one in which no subsequence of length p does form an arithmetic sequence. An arithmetic sequence is a sequence of numbers such that the difference of any two successive members of the sequence is a constant. For instance, the sequence 3, 5, 7, 9, 11, 13... is an arithmetic progression with common difference 2. Now for a given p an infinite anti-arithmetic sequence is built in the following way.
The sequence will contain only positive numbers and strictly increasing.
The first p-1 numbers of the sequence is 1, 2,…., p-1. After that each time the smallest number is added to the sequence so that no subsequence of length p forms an arithmetic sequence. For p = 3 the infinite sequence is 1, 2 , 4, 5, 10, 11, 13, 14, 28, 29 and so on.

Your task is to given p and n find the nth value of the anti-arithmetic sequence.


Input

First line of the input contains an integer T (1≤T≤1000) which denotes the number of test cases. Then each of the following T lines contains one test case. Each case contains 2 integers n (1≤n≤2*10^10) and p (3≤p≤30).


Output

For each test case output contains 1 number indicating the nth value of the anti arithmetic sequence of p. This value will always fit into 64-bit signed integer.


Sample Input Output for Sample Input
3

10 3

10 5

100 7


29

12

130




ProblemCOPIER: Abdullah al Mahmood

Special Thanks: Derek Kisman

because it was COPIED from
http://www.kalva.demon.co.uk/usa/usoln/usol951.html

and he unfortunately forget to mention p is prime.

[shahriar_manzoor]

To anonbd:

I think you yourself know that what you are trying to do is not fair and that is why your handle is anonymousbd rather than your own one.

Problem Setting is not paper writing, so copying idea is allowed. How many problems have you seen that uses Floyd's algorithm or tries to ask you to find phi function or convex hull, does that mean it is copying?. May be this problem gave the people with previous IMO experience a bit advantage but calling someone problemCopier is way too much. You are not giving the problem setters the honour of writing a good paper for a good problem, in that sense it is not always fair to expect brand new problems.

I first saw got link you gave (copied from) from the problem setter himself. So I don't think he had any intension to copy it and hide it from everyone. So by providing the link you are not doing some heroic thing...

I have already sent the updated the problem statement, and I see that it has been updated. And the statement you provide does not say that p is prime but states the range correctly, which will again probably confuse people, but I guess that is what people like you do...