545 - Heads

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

Moderator: Board moderators

Oog
New poster
Posts: 6
Joined: Sat Dec 20, 2003 5:29 am

545 is multiple input??

Post by Oog » Sun Sep 05, 2004 8:41 pm

i was having trouble with 545 so i started searching the forums and found out that it was multiple input but it says nothing about that in the problem and the input sample is not in the format of a multiple input.

where does it say this problem is multiple input?

http://acm.uva.es/p/v5/545.html[/list]

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Sep 05, 2004 11:07 pm

Blue tick means multi-input.

Oog
New poster
Posts: 6
Joined: Sat Dec 20, 2003 5:29 am

Post by Oog » Mon Sep 06, 2004 10:43 am

blue tick?

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Tue Sep 07, 2004 2:32 am

That a problem is a multiple input is never told in any problem description. But if you check

http://online-judge.uva.es/cgi-bin/OnlineJudge?Volume:5

Then you'll see a checkmark besides each question. And if you look at the very top you'll see a key for what they mean, and a link to what Multiple Input means.
I'm always willing to help, if you do the same.

Oog
New poster
Posts: 6
Joined: Sat Dec 20, 2003 5:29 am

Post by Oog » Tue Sep 07, 2004 7:16 am

i did not know that. every other problem i have read that is multi-input has said it in the problem description and has demonstrated it in the sample input.

Heartattack!
New poster
Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET
Contact:

474

Post by Heartattack! » Wed Nov 10, 2004 11:37 am

pc5971,
I'm trying the problem using a different algo. I have all the correct floats(x.xxx) and the ints (y). I'm having trouble with output precission. I got my code to get the same output as you for all ints from 1 to 1000000. I submitted both your code and mine. They both get WA. You said your code got AC, but it doesn't seem so.

I understand 474 is not multiple input but 545 is. Could anyone send critical output for 474?

What'll the output be for:

Code: Select all

12
24
48
2^-12=2.44140625E-04
pc's code produces 2.442E-4
2^-24=5.960464478E-08
Should this be 5.961E-4 or 5.960E-4?

Please help. This is quite frustrating as I get the same results by a calculator and my code. I just can't get the output to get AC :cry:
We will, We will BREAK LOOP!!!!

Heartattack!
New poster
Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET
Contact:

Post by Heartattack! » Sat Nov 13, 2004 8:16 am

Jackie, I got AC with 474, but keep getting WA with 545. I tried to hard code the cases of n=6 and n=7. But I still got WA. Could you send your AC code by PM? I'll only use it to compare output. Thanks in advance.
We will, We will BREAK LOOP!!!!

Heartattack!
New poster
Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET
Contact:

Post by Heartattack! » Sat Nov 13, 2004 8:39 am

Jackie,
I just added this to the main() func and got Accepted PE:

[cpp]
void main()
{
int n;
char c=1;//I added this
scanf("%d",&n);
while(!)
{
if(scanf("%d",&n)==EOF)break;
if(start)start=0;//I added this
else printf("\n");//and this
if(n==6)...../*Code
}
}
[/cpp]

I don't understand. I only added a new line at the end of every case and got AC:PE from WA. Why can that be?
We will, We will BREAK LOOP!!!!

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

545

Post by Emilio » Sun Jan 16, 2005 12:42 am

Hi,
I have tried this problem about thousands, and thousands of ways, but I always obtain WA. In this code I search the precision, but I don't get AC. Please, Can anyone say me what is the cases that is wrong in my code, please, or send me the 9000 posible cases with its output, please. I can't understand that is wrong :cry: .

Code: Select all

cut
Thanks very much!
Last edited by Emilio on Fri May 27, 2005 8:29 pm, edited 2 times in total.

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

Re: P545: Heads, Help please, I'm mad

Post by nnahas » Fri Jan 21, 2005 3:56 pm

I haven't attempted to solve the problem but there are several errors I see in your program.
1) You shouldn't get the number of cases from the input stream . The first line isn't the number of cases. it is the first number fot which you have to produce an output.
2)The remaining part of your input code is also wrong. As far as I understand you should only use getc in this program,not gets and scanf, because you don't know the number of cases in advance.
3)I don't think you have a precision problem , because you used repeated squaring but just in case you do, I suggest you multiply the decimal logarithm of 0.5 by the number given , take its fractional part and exponentiate it to get the number before the E.
Try this and tell me if it works.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sat Jan 22, 2005 12:46 pm

Hi nnahas,
1) You shouldn't get the number of cases from the input stream . The first line isn't the number of cases. it is the first number fot which you have to produce an output.
2)The remaining part of your input code is also wrong. As far as I understand you should only use getc in this program,not gets and scanf, because you don't know the number of cases in advance.
This is a multiple input problem.
http://acm.uva.es/problemset/minput.html
3)I don't think you have a precision problem , because you used repeated squaring but just in case you do, I suggest you multiply the decimal logarithm of 0.5 by the number given , take its fractional part and exponentiate it to get the number before the E.
I'll try this later, and I'll tell you the result, now I have a lot of exams.
Thanks! :)

Evan Tsang
New poster
Posts: 11
Joined: Sun Jan 02, 2005 9:14 am

Post by Evan Tsang » Sun Jan 23, 2005 5:59 am

Try n = 137,138,6461,

your program output
2^-137 = 5.73:E-42
2^-138 = 2.86:E-42
2^-6461 = 1.10:E-1945

Evan Tsang
New poster
Posts: 11
Joined: Sun Jan 02, 2005 9:14 am

Post by Evan Tsang » Sun Jan 23, 2005 6:07 am

Beside this bug,

You may have a precision problem too
Your program output
2^-14 = 6.103E-5

[evan@enigma 545] $ bc -l
bc 1.06
Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
2^-14
.00006103515625000000

Should the answer be 6.104E-5 ?

-evan

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

Post by nnahas » Sun Jan 23, 2005 5:42 pm

I got AC after several WA.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:53290

You're right this is a multiple input problem, also the precision is difficult to get right.
Personally, I implemented *exact* computation (which is possible because when you divide by 2 you always get a finite number of digits) to know where I got my errors. Of course I didn't submit that code because it would get time limit exceeded, but it helped me find my errors.

Here are 150 comma separated cases:

2^-8001 = 2.877E-2409, 2^-8002 = 1.439E-2409, 2^-8003 = 7.194E-2410, 2^-8004 = 3.597E-2410, 2^-8005 = 1.798E-2410, 2^-8006 = 8.992E-2411, 2^-8007 = 4.496E-2411, 2^-8008 = 2.248E-2411, 2^-8009 = 1.124E-2411, 2^-8010 = 5.620E-2412,
2^-8011 = 2.810E-2412, 2^-8012 = 1.405E-2412, 2^-8013 = 7.025E-2413, 2^-8014 = 3.512E-2413, 2^-8015 = 1.756E-2413, 2^-8016 = 8.781E-2414, 2^-8017 = 4.391E-2414, 2^-8018 = 2.195E-2414, 2^-8019 = 1.098E-2414, 2^-8020 = 5.488E-2415,
2^-8021 = 2.744E-2415, 2^-8022 = 1.372E-2415, 2^-8023 = 6.860E-2416, 2^-8024 = 3.430E-2416, 2^-8025 = 1.715E-2416, 2^-8026 = 8.575E-2417, 2^-8027 = 4.288E-2417, 2^-8028 = 2.144E-2417, 2^-8029 = 1.072E-2417, 2^-8030 = 5.360E-2418,
2^-8031 = 2.680E-2418, 2^-8032 = 1.340E-2418, 2^-8033 = 6.700E-2419, 2^-8034 = 3.350E-2419, 2^-8035 = 1.675E-2419, 2^-8036 = 8.374E-2420, 2^-8037 = 4.187E-2420, 2^-8038 = 2.094E-2420, 2^-8039 = 1.047E-2420, 2^-8040 = 5.234E-2421,
2^-8041 = 2.617E-2421, 2^-8042 = 1.309E-2421, 2^-8043 = 6.543E-2422, 2^-8044 = 3.271E-2422, 2^-8045 = 1.636E-2422, 2^-8046 = 8.178E-2423, 2^-8047 = 4.089E-2423, 2^-8048 = 2.045E-2423, 2^-8049 = 1.022E-2423, 2^-8050 = 5.111E-2424,
2^-8051 = 2.556E-2424, 2^-8052 = 1.278E-2424, 2^-8053 = 6.389E-2425, 2^-8054 = 3.195E-2425, 2^-8055 = 1.597E-2425, 2^-8056 = 7.986E-2426, 2^-8057 = 3.993E-2426, 2^-8058 = 1.997E-2426, 2^-8059 = 9.983E-2427, 2^-8060 = 4.992E-2427,
2^-8061 = 2.496E-2427, 2^-8062 = 1.248E-2427, 2^-8063 = 6.239E-2428, 2^-8064 = 3.120E-2428, 2^-8065 = 1.560E-2428, 2^-8066 = 7.799E-2429, 2^-8067 = 3.900E-2429, 2^-8068 = 1.950E-2429, 2^-8069 = 9.749E-2430, 2^-8070 = 4.875E-2430,
2^-8071 = 2.437E-2430, 2^-8072 = 1.219E-2430, 2^-8073 = 6.093E-2431, 2^-8074 = 3.047E-2431, 2^-8075 = 1.523E-2431, 2^-8076 = 7.616E-2432, 2^-8077 = 3.808E-2432, 2^-8078 = 1.904E-2432, 2^-8079 = 9.521E-2433, 2^-8080 = 4.760E-2433,
2^-8081 = 2.380E-2433, 2^-8082 = 1.190E-2433, 2^-8083 = 5.950E-2434, 2^-8084 = 2.975E-2434, 2^-8085 = 1.488E-2434, 2^-8086 = 7.438E-2435, 2^-8087 = 3.719E-2435, 2^-8088 = 1.859E-2435, 2^-8089 = 9.297E-2436, 2^-8090 = 4.649E-2436,
2^-8091 = 2.324E-2436, 2^-8092 = 1.162E-2436, 2^-8093 = 5.811E-2437, 2^-8094 = 2.905E-2437, 2^-8095 = 1.453E-2437, 2^-8096 = 7.264E-2438, 2^-8097 = 3.632E-2438, 2^-8098 = 1.816E-2438, 2^-8099 = 9.080E-2439, 2^-8100 = 4.540E-2439,
2^-8101 = 2.270E-2439, 2^-8102 = 1.135E-2439, 2^-8103 = 5.675E-2440, 2^-8104 = 2.837E-2440, 2^-8105 = 1.419E-2440, 2^-8106 = 7.093E-2441, 2^-8107 = 3.547E-2441, 2^-8108 = 1.773E-2441, 2^-8109 = 8.867E-2442, 2^-8110 = 4.433E-2442,
2^-8111 = 2.217E-2442, 2^-8112 = 1.108E-2442, 2^-8113 = 5.542E-2443, 2^-8114 = 2.771E-2443, 2^-8115 = 1.385E-2443, 2^-8116 = 6.927E-2444, 2^-8117 = 3.464E-2444, 2^-8118 = 1.732E-2444, 2^-8119 = 8.659E-2445, 2^-8120 = 4.329E-2445,
2^-8121 = 2.165E-2445, 2^-8122 = 1.082E-2445, 2^-8123 = 5.412E-2446, 2^-8124 = 2.706E-2446, 2^-8125 = 1.353E-2446, 2^-8126 = 6.765E-2447, 2^-8127 = 3.382E-2447, 2^-8128 = 1.691E-2447, 2^-8129 = 8.456E-2448, 2^-8130 = 4.228E-2448,
2^-8131 = 2.114E-2448, 2^-8132 = 1.057E-2448, 2^-8133 = 5.285E-2449, 2^-8134 = 2.643E-2449, 2^-8135 = 1.321E-2449, 2^-8136 = 6.606E-2450, 2^-8137 = 3.303E-2450, 2^-8138 = 1.652E-2450, 2^-8139 = 8.258E-2451, 2^-8140 = 4.129E-2451,
2^-8141 = 2.064E-2451, 2^-8142 = 1.032E-2451, 2^-8143 = 5.161E-2452, 2^-8144 = 2.581E-2452, 2^-8145 = 1.290E-2452, 2^-8146 = 6.451E-2453, 2^-8147 = 3.226E-2453, 2^-8148 = 1.613E-2453, 2^-8149 = 8.064E-2454, 2^-8150 = 4.032E-2454,

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Mon Jan 24, 2005 4:41 am

ARRRRRRRRRRGGGGGGGGGHHHHHH!!!!! :x

I GOT ACCEPTED!!!

Thanks very very much Evan Tsang and nnahas!!!!

I had a bug with '9' + 1 = ':'.
I had another bug (maybe never I would have discovered), if you have 1.11550 the correct answer is 1.116, and for my previous program was 1.155, I thought that 1.155 was the correct answer but no.

AAARRRRRRRRRRRRRGGGGGGGGHHHHHHHH!!!! :x :x :x

Thanks very very very much another time!!!!!!! :) :lol: :D

Post Reply

Return to “Volume 5 (500-599)”