Page 2 of 3
Posted: Tue Jun 14, 2005 10:12 am
by Gaolious
temper_3243 wrote:Well the code you posted and ryan posted differs in output. My code produces the output exactly that ryan gave.
Btw galious, how is input for 3 a length of 1 . For n=3 my output is 0 3. For n=1 my output is 0 1. Your output is 1 1.
In problem it is stated that after the elimination round.For n=2 it is 1 1.
My mistake when convert to PHP language
sorry^^;;
Posted: Tue Jun 14, 2005 3:37 pm
by temper_3243
Please tell me what is wrong with this code. Please do post me the output/zip for 1 to 31000 to
temper_3243@yahoo.com
It gives the exact output for the test cases given by you.
Code: Select all
#include<iostream>
#include<map>
#include<cstdio>
using namespace std;
map < int, int >m;
map < int, int >h;
inline int
myg (int r)
{
if (m.count (r) == 0){
int ans, tmp = 1;
while (r >= tmp)
{
tmp = tmp * 2;
}
tmp = tmp / 2;
ans = r - tmp;
ans = (2 * ans) + 1;
m[r] = ans;
return m[r];
}
else
return m[r];
}
inline int
compute (int n)
{
if (m.count (n) == 1 && m[n] == n)
return n;
else
{
m[n] = myg (n);
return m[n];
}
}
int
main ()
{
int a,i, z,n,no;
for(i=1;i<=35000;i++)
z=compute(i);
scanf("%d",&no);
for(i=1;i<=no;i++)
{
scanf (" %d", &a);
n=a;
int len=0;
while(m[n]!=n)
{
len++;
n=m[n];
}
printf ("Case %d: %d %d\n",i, len, n);
}
return 0;
}
Posted: Wed Jun 15, 2005 9:32 am
by Ryan Pai
I ran the code you posted against all possible inputs and it agreed with mine (I modified it so that it was in it's own function and then compared the output of that function with the output of mine). So I would assume that the error would be in your input/output. I typically use cin/cout so I can't be sure, but should there be a space in your scanf string?
Posted: Wed Jun 15, 2005 1:38 pm
by temper_3243
That space is not required. Can you run it without the space in scanf.
Also i don't understand what you said by running it inside a function . What does that mean ? Please post some example.
Well thanks ryan and others for the help.
Best Regards
Posted: Wed Jun 15, 2005 3:29 pm
by Ryan Pai
I basically did this
Code: Select all
pair<int,int> yours(int n){
// I put the main part of your code here, but took out the scanf
return make_pair(len,n); //and did this instead of printf
}
pair<int,int> mine(int n){
// my code here
}
int main(){
for(int i=1;i<N;i++)
if(yours(i)!=mine(i)){
cout<<"Oh pants, we don't agree on "<<i<<'\n';
return 1;
}
cout<<"Everything checks out\n";
}
And it gave the all good message.
Posted: Wed Jun 15, 2005 5:14 pm
by temper_3243
I tried running it after removing the space. It is giving me the wrong answer.
Just run this program and save the output in a file.
Run my code and your program for the same input. Diff it tell me where it fails .
Btw is your code accepted
Code: Select all
#include<stdio.h>
int main()
{
int i;
for(i=0;i<31000;i++)
printf("%d\n",i);
return 0;
}
Strange code
Posted: Wed Jun 15, 2005 5:16 pm
by temper_3243
Hi,
I am getting same output as others who have the accepted solution. This code is behaving strangely. Where is it going wrong ?
Code: Select all
#include<iostream>
#include<map>
#include<cstdio>
using namespace std;
map < int, int >m;
map < int, int >h;
inline int
myg (int r)
{
if (m.count (r) == 0){
int ans, tmp = 1;
while (r >= tmp)
{
tmp = tmp * 2;
}
tmp = tmp / 2;
ans = r - tmp;
ans = (2 * ans) + 1;
m[r] = ans;
return m[r];
}
else
return m[r];
}
inline int
compute (int n)
{
if (m.count (n) == 1 && m[n] == n)
return n;
else
{
m[n] = myg (n);
return m[n];
}
}
int
main ()
{
int a,i, z,n,no;
for(i=1;i<=35000;i++)
z=compute(i);
scanf("%d",&no);
for(i=1;i<=no;i++)
{
scanf (" %d", &a);
n=a;
int len=0;
while(m[n]!=n)
{
len++;
n=m[n];
}
printf ("Case %d: %d %d\n",i, len, n);
}
return 0;
}
Posted: Wed Jun 15, 2005 8:59 pm
by N|N0
I can't tell you what's wrong, because you didn't say whait is it supposed to do
Posted: Thu Jun 16, 2005 2:20 am
by Ryan Pai
Well, I ran your code and mine on every input the diff said they were exactly the same (and my code got AC).
This is a really odd situation.
See this thread
Posted: Thu Jun 16, 2005 7:12 am
by temper_3243
Posted: Thu Jun 16, 2005 7:34 am
by chunyi81
Did u use online submission or e-mail? Sometimes submitting via e-mail can cause problems.
Posted: Thu Jun 16, 2005 5:10 pm
by temper_3243
I used online submission. Why don't the admins comment anything about this problem ?
Posted: Thu Jun 16, 2005 5:12 pm
by temper_3243
Whats happening with this i don't know? Is there a problem with submit.php ?
is there any other way. I tried copying my code into the text box and even sending it by browse.
Well ryan if you don't mind please send me your code to
temper_3243@yahoo.com
Posted: Fri Jun 17, 2005 6:54 am
by chunyi81
Hi temper_3243. I checked the outputs from your code inputs 1 to 30000 against my AC code, which I got AC a few minutes ago.
Your code fails for the following test case:
Input:
1
1
Correct Output:
Case 1: 0 1
Your Program Output:
Case 1: 1 0
I have also removed the space in the scanf when I compiled your code.
In fact, your code gives the following output for input 1 to 30000
Case 1: 1 0
Case 2: 1 0
Cases 3 to 30000 also give 1 0.
The environment I ran your code with is g++ 2.95 in Unix, which is similar to UVA online judge environment.
I have tried to debug your code and found one line that could be a problem.
What I can tell you is that I inserted printfs in the compute method and myg method in your code and I got something very interesting.
At the beginning of the myg method
Code: Select all
printf("myg %d %d\n",r,m.count(r));
and at the beginning of the compute method
Code: Select all
printf("compute %d %d\n",n,m.count(n));
For each n, m.count(n) = 0 is correct. But for each r, m.count(r) = 1. This should not be so.
This is a problem with the judge's compiler.
When I compiled your code with g++ 3.3.1 under Dev C++ 4.9.9.1 in Windows wthout the printfs I added and ran it with the same set of inputs and I got your program's output to be the same as from my AC program's output.
Posted: Fri Jun 17, 2005 9:21 am
by chunyi81
There is nothing wrong with your code. It is the judge's compiler. See my post in Volume CVII.