10022 - Delta-wave

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

10022 - Delta-wave

Post by stcheung » Sun Nov 24, 2002 3:26 pm

Alright I keep getting WA for 10022, and I can't find the bug at all. I have tested on M,N from 1 to 25 extensively, and the program seems to be working perfectly. Can anyone test my program and tell me some test cases that can break my program? THANKS.


#include <iostream.h>
#include <stdlib.h>

void findlevel(unsigned, unsigned[]);

int main()
{
unsigned M, N, levelM, levelN, answer=0;
unsigned left, right, numInLevel, result[2];
unsigned leftMost, rightMost, level, temp1, temp2;
cin >> temp1 >> temp2;
M = (temp1 < temp2 ? temp1 : temp2);
N = (temp1 == M ? temp2 : temp1);
findlevel(M, result);
levelM = result[0];
numInLevel = result[1];
findlevel(N, result);
levelN = result[0];
answer+=(2 * (levelN - levelM));
level = levelM;
leftMost = M;
rightMost = M;

while(true)
{
if(level == levelN)
break;
leftMost+=numInLevel;
rightMost+=(2 + numInLevel);
level++;
numInLevel+=2;
}
//cout << "leftmost: " << leftMost << "\t" << "rightmost: " << rightMost;
//cout << "\n";
//cout << "answer at line 37: " << answer << "\n";
if(levelM == levelN)
answer = N - M;
else if(N >= leftMost && N <= rightMost)
{
answer = ((N - leftMost)%2 == 0 ? answer : answer+1);
}
else if(N > rightMost)
{
answer+=(N - rightMost);
}
else if(N < leftMost)
{
answer+=(leftMost - N);
}

// cout << "answer at line 53: " << answer << "\n";
if((levelM%2 == 0 && M%2 == 0) || (levelM%2 == 1 && M%2 == 1))
{
if(N>=leftMost && N<=rightMost &&
((levelN%2 == 0 && N%2==1) || (levelN%2 == 1 && N%2==0)))
answer-=2;
}

cout << answer << "\n";
return 0;
}

void findlevel(unsigned num, unsigned result[])
{
unsigned level=1, numInLevel=1, sofar=1;
while(true)
{
if(sofar >= num)
{
result[0] = level;
result[1] = numInLevel;
return;
}
level++;
numInLevel+=2;
sofar+=numInLevel;
}
}

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

NEVERMIND...It's Multiple Input thingy

Post by stcheung » Sun Nov 24, 2002 4:31 pm

Alright this multiple input thingy keeps screwing me up. Well kinda my bad, I didn't read carefully and thought green key is multiple input, when blue one is multiple input as well. haha...you fellows out there should watch out for those too.

pingus
New poster
Posts: 18
Joined: Sat May 03, 2003 10:33 pm

Post by pingus » Sat Jul 19, 2003 8:57 pm

hello

You can tell me some test cases for

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Tue Jul 22, 2003 7:53 am

Yes, your output is right.

another test case:
input:
2

1 1
2 1
100 3
40 5
299143 193914510
9 1023

56601 99
401 3001
9 1
1000 1000
1000 1001
3123 4412
30040103 10204392
48582994 99499

output:
0
2
17
7
26758
57

456
84
4
0
1
64
6947
13310

hope this helps. :lol:

pingus
New poster
Posts: 18
Joined: Sat May 03, 2003 10:33 pm

Post by pingus » Wed Jul 23, 2003 6:27 pm

Hello Red Scorpion

Thank you for the response

But, the problem was related with reading multiple input (icon key blue).

I get AC(PE)

Best regards

pingus

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10022 - Delta-wave

Post by DD » Sat Nov 15, 2008 1:35 pm

I just got A.C., and the Judge's input seems do not very tricky. Even my poor algorithm which simulates directly the whole process could solve this problem in a short time. :oops:
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Post Reply

Return to “Volume 100 (10000-10099)”