The problem is from Timus Online Judge: [see this page].
The problem asks you to print the square root in reverse order. Pay attention to the input size, which is no more than 256KB. To check if input has finished, use the EOF value. Also, the numbers are separated by space and line breaks.
The input is at most 10^18, which should be held by unsigned 64-bit integer (e.g. unsigned long long). Suppose each integer is two characters (one digit and one separator), you can create a buffer that is size of [256KB / 2]. Get the square root as each input and print them in reverse order.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #include <stdio.h> #include <math.h> double buf[128 * 1024]; int main() { int i = 0; unsigned long long n; // 64-bit unsigned integer while (scanf("%llu", &n) != EOF) { buf[i ++] = (double)sqrt(n * 1.0); // store in buffer } for (; --i >= 0; ) { printf("%.4lf\n", buf[i]); // reverse order } return 0; } |
#include <stdio.h>
#include <math.h>
double buf[128 * 1024];
int main()
{
int i = 0;
unsigned long long n; // 64-bit unsigned integer
while (scanf("%llu", &n) != EOF) {
buf[i ++] = (double)sqrt(n * 1.0); // store in buffer
}
for (; --i >= 0; ) {
printf("%.4lf\n", buf[i]); // reverse order
}
return 0;
}Using static array (pre-allocated) is always faster than dynamic array and linked list. The above approach gets AC in 0.187 s but the following (just an idea, using linked list) is way slower (AC in 0.734s)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include <iostream> #include <math.h> #include <stdio.h> using namespace std; typedef __int64 BIG; #define round(x) (__int64)((x)+0.5) struct node { double value; struct node *prev; }; int main(int argc, char** argv) { char* buffer=new char[255]; struct node* lnk; struct node *p=NULL; double n; while (cin >> n) { lnk=new struct node; lnk->value=round(sqrt(n)*10000)/10000.0; lnk->prev=p; p=lnk; } while (p) { sprintf(buffer,"%.4lf",p->value); cout<<buffer<<endl; p=p->prev; } return 0; } |
#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;
typedef __int64 BIG;
#define round(x) (__int64)((x)+0.5)
struct node
{
double value;
struct node *prev;
};
int main(int argc, char** argv)
{
char* buffer=new char[255];
struct node* lnk;
struct node *p=NULL;
double n;
while (cin >> n)
{
lnk=new struct node;
lnk->value=round(sqrt(n)*10000)/10000.0;
lnk->prev=p;
p=lnk;
}
while (p)
{
sprintf(buffer,"%.4lf",p->value);
cout<<buffer<<endl;
p=p->prev;
}
return 0;
}–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Assoc and Ftype on Windows Command Shell
Next Post: Coding Exercise - Timus Online Judge - 1000 - A+B Problem - C/C++ solutions with Assembly
How can a user exit from the while loop in first code?
when the input character is EOF with is Ctrl+D on linux or Ctrl+Z on Windows
If I type a character instead of a number in 1st program, the program crashes. But if I type a character in your second program, the program terminates successfully (showing the sqrts as well) Why is that?
sure.. because it doesn’t check for characters. It assumes numbers only.