10034 - Freckles

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

bitaron
New poster
Posts: 12
Joined: Mon Jan 06, 2014 9:40 pm

Re: 10034 - Freckles

Post by bitaron » Sat Mar 01, 2014 8:08 pm

still wa .

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10034 - Freckles

Post by brianfry713 » Sun Mar 02, 2014 5:20 am

Post your updated code.
Check input and AC output for thousands of problems on uDebug!

bitaron
New poster
Posts: 12
Joined: Mon Jan 06, 2014 9:40 pm

Re: 10034 - Freckles

Post by bitaron » Mon Mar 03, 2014 5:53 am

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include <fstream>
#include <iomanip>
using namespace std;

struct point
{
   double x,y;
};
struct edge
{
   int s,d;
   double w;
    bool operator < ( const edge& p ) const { //overloading operator
       return w > p.w; }
};
vector<point>nodes;
priority_queue<edge>dis;
vector<double>resulted;
int main()
{
   int c,n,i,j,flag[10000];
//   vector<int>disflag[100];
   double a,b;
//   vector<double>dis[100];
   vector<int>rnode;
   cin>>c;
   for(i=0;i<c;i++)
   {
      double result=0;
   
      cin>>n;
      nodes.clear();
      rnode.clear();
      while(!dis.empty())
      {
         dis.pop();
      }
      for(j=0;j<n;j++)
      {
         cin>>a>>b;
         point temp;
         temp.x=a;
         temp.y=b;
         nodes.push_back(temp);
         flag[j]=0;
      }
      
      int h,k,on=1;
      
       h=0;
      rnode.push_back(h);
      flag[0]=1;
      while(rnode.size()!=n)
      {
         if(on==1){
         for(k=0;k<n;k++)
         {
            if(flag[k]==0 )
            {
               double t=nodes[h].x-nodes[k].x;
                  t=t*t;
               double w=nodes[h].y-nodes[k].y;
                  w=w*w;
               double p=t+w;
                  p=sqrt(p);
                  edge temp;
                  temp.s=h;
                  temp.d=k;
                  temp.w=p;
            //   cout<<"\nrr"<<p<<"  "<<h<<k<<"\n";
                  dis.push(temp);
               
                  
            }
            
         }
         }
         on=0;
         edge temp2;
         temp2=dis.top();
         dis.pop();
         if(flag[temp2.d]==0)
         {
            rnode.push_back(temp2.d);
            flag[temp2.d]=1;
            result=result+temp2.w;
         //   resulted.push_back(result);
            h=temp2.d;
            on=1;
         }
         
         
      //   cout<<"\nrr"<<result<<"\n";
      }
         //   cout<<"\nrr"<<result<<"\n";
      resulted.push_back(result);
      //cout<<"\n"<<resulted[0]<<"\n";
      
      
   }
   
   
for(i=0;i<c;i++)
{
   std::cout << std::fixed;
      std::cout << std::setprecision(2);
      cout<<resulted[i];
      cout<<"\n";
    cout<<"\n";
      
}
   return 0;

}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10034 - Freckles

Post by brianfry713 » Mon Mar 03, 2014 11:54 pm

The outputs of two consecutive cases will be separated by a blank line. Don't print an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10034 - Freckles

Post by brianfry713 » Wed Mar 26, 2014 12:38 am

Input:

Code: Select all

20

17
-2.28 7.23
-2.32 -7.84
-7.21 7.11
-9.76 -8.79
-0.70 7.84
2.42 7.73
-6.86 7.28
-5.75 1.60
8.05 5.41
6.76 4.76
6.11 -9.99
-2.47 -3.22
-8.75 -3.88
0.40 -7.16
-8.34 1.03
-1.75 8.39
6.12 -5.04

20
4.48 7.64
7.88 -1.71
7.59 2.32
-5.27 5.60
4.31 4.87
4.69 1.91
-0.05 -0.29
-3.53 -0.56
-4.45 -4.47
3.06 -1.18
-4.36 -2.76
7.64 1.48
3.14 6.67
-9.52 1.59
-2.29 3.67
1.30 1.99
-9.73 -7.82
0.07 -0.82
-9.66 7.87
-1.70 4.81

9
-7.02 -7.72
2.23 9.94
-3.60 2.42
3.54 7.77
-3.61 0.79
6.43 -9.23
8.41 7.87
-3.42 -1.34
-0.85 0.00

20
6.71 3.28
1.03 1.55
6.30 6.99
0.42 -8.90
1.48 2.21
-3.14 8.72
-8.31 -0.67
-8.45 -7.63
-1.23 4.11
-2.35 4.89
6.86 5.14
-2.87 -6.01
-7.60 4.72
6.87 1.37
-9.49 -2.03
6.82 7.12
-5.77 2.79
-4.66 -6.59
-9.92 6.10
-1.70 5.76

15
0.74 4.47
1.73 6.46
8.02 3.11
7.45 -8.59
-5.37 -1.53
-4.68 2.58
9.72 -1.38
-3.41 5.62
-1.95 1.08
-2.84 4.56
-3.06 -4.84
-5.04 5.52
-9.14 -4.07
-3.99 -8.95
-0.64 6.62

19
-9.91 -3.34
3.96 -4.83
8.76 3.20
-3.79 5.37
10.00 -2.77
-1.88 8.80
4.08 -5.81
0.78 9.31
-2.64 -9.28
-6.55 -4.66
-2.15 -1.91
3.06 8.97
9.83 3.78
9.80 -0.32
4.61 2.02
4.25 -1.49
3.68 0.27
9.04 -1.80
-6.43 2.44

14
9.14 5.24
-6.65 -5.96
8.12 -6.68
4.11 8.24
-4.41 4.41
7.86 5.02
8.44 3.68
-7.70 6.82
2.22 2.22
-2.42 1.99
-3.41 -5.77
8.48 1.66
-4.67 6.87
5.90 -7.76

10
-8.86 -8.62
-9.48 -1.43
-2.50 -9.25
4.44 9.42
-0.91 -4.27
-3.11 -1.16
-3.31 9.68
8.12 -9.44
8.45 9.09
1.30 -4.10

20
1.10 3.48
-9.30 2.59
-4.98 -0.43
1.81 -8.40
4.95 6.50
3.21 -1.23
-5.14 9.09
-7.85 3.97
-6.03 -5.73
-1.06 -2.12
4.77 -1.61
0.65 -1.39
-7.71 0.91
-0.65 -0.27
6.60 -1.81
7.24 5.35
-2.07 -2.31
2.83 7.94
9.55 -1.47
-4.98 -9.79

4
8.23 -1.02
3.84 -5.29
-3.13 -2.24
-2.69 3.68

15
5.70 -7.39
1.23 -4.91
1.57 -3.66
1.65 -0.91
7.29 -9.09
1.83 -1.76
5.94 4.52
-1.97 5.33
-6.15 -1.24
-5.46 -6.86
3.20 -1.13
-7.33 3.52
-2.65 3.48
-9.66 -4.00
3.31 -8.97

17
-5.43 9.22
-3.99 1.33
-7.11 0.92
8.14 5.11
2.39 9.38
1.20 -3.63
7.88 -7.53
-3.93 -3.48
0.38 -7.79
-3.25 -0.79
7.98 4.82
3.06 -9.73
-6.81 1.46
-2.63 4.64
-6.49 9.80
9.02 8.04
-0.64 -1.91

7
2.25 4.58
2.71 5.70
-1.92 -2.81
8.39 9.08
6.96 -3.87
2.20 -5.09
0.86 4.74

7
-8.76 -8.52
7.33 0.53
7.56 -0.12
-5.49 -9.48
5.89 -5.07
-7.04 -1.98
6.11 0.47

15
-3.75 1.07
-3.24 -9.86
-2.66 8.96
3.61 0.42
6.55 -8.71
-8.23 0.56
-9.14 -5.69
6.87 -1.80
-0.55 -7.66
9.68 -7.03
-9.48 9.33
9.41 5.77
1.65 -4.55
-6.01 -2.58
9.11 7.70

7
-9.08 -1.24
5.52 -2.40
4.94 9.89
3.49 -4.07
8.05 1.81
3.58 9.62
-9.53 7.94

5
8.39 4.80
7.77 -3.20
-8.31 8.06
-0.61 3.87
9.32 -8.91

9
-6.70 -5.92
8.76 4.31
-6.94 0.76
8.37 9.69
5.14 4.15
-9.92 -1.13
-9.33 -1.38
-6.20 3.70
1.63 -0.17

9
-8.00 1.61
3.98 8.23
1.86 5.34
-0.80 5.67
2.33 -8.76
7.86 -5.91
-7.04 6.41
0.74 2.16
0.79 3.73

20
-5.06 -2.34
6.53 -8.88
-4.69 -4.98
4.29 2.78
-7.40 -0.89
-5.48 -8.51
-6.51 -0.22
-6.25 -7.26
4.60 4.40
9.18 4.99
-2.69 5.85
-0.73 -6.74
-8.21 9.29
0.02 -8.57
2.22 1.09
8.75 6.01
2.70 7.16
7.75 5.28
-6.38 8.01
-7.32 -2.39
AC output:

Code: Select all

59.85

56.74

42.05

52.79

52.65

60.46

51.17

55.30

60.58

19.67

48.87

53.88

26.89

29.51

70.48

39.66

31.75

35.33

37.76

57.12
Check input and AC output for thousands of problems on uDebug!

dypbrg
New poster
Posts: 3
Joined: Sun Aug 17, 2014 1:05 pm

Re: 10034 - Freckles

Post by dypbrg » Sun Aug 17, 2014 1:08 pm

I have tried all the given input in this thread and my code outputs the correct answers. But when I submit it to the judge, I always get WA. I also already took note of the extra lines needed and that there shouldn't be any blank line after the last test case but i still get WA. What seems to be the problem?

Code: Select all

import java.util.ArrayList;
import java.util.Scanner;


public class Main {
	static int numDots;
	static Node[] adjacencyList;

	static class Node{
		double key;
		boolean visited;
		int data;
		double x;
		double y;
		ArrayList<Node> children;
		Node parent;
		public Node(double x, double y, int data){
			this.data = data;
			this.x = x;
			this.y = y;
			visited = false;
			key = Double.MAX_VALUE;
			children = new ArrayList<Node>();
			parent = null;
		}
		
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int numCases = sc.nextInt();
		sc.nextLine();
		for(int g = 0; g<numCases; g++){
			sc.nextLine();
			numDots = sc.nextInt();
			adjacencyList = new Node[numDots];
			for(int a = 0; a<numDots; a++){
				Node n = new Node(sc.nextDouble(), sc.nextDouble(), a);
				adjacencyList[a] = n;
			}
			
			//add children to each node
			for(int b = 0; b<numDots; b++){
				for(int c = 0; c<numDots; c++){
					if(b!=c)
						adjacencyList[b].children.add(adjacencyList[c]);
				}
			}
			
			adjacencyList[0].key = 0;
			
			for(int a = 0; a<numDots; a++){
				int u = getMinKey();
				adjacencyList[u].visited = true;
				for(int b = 0; b<numDots; b++){
					double newKey = 0;
					if(adjacencyList[b].visited == false && (newKey = Math.sqrt(Math.pow(Math.abs(adjacencyList[u].x-adjacencyList[b].x), 2.0) +
							Math.pow(Math.abs(adjacencyList[u].y - adjacencyList[b].y), 2.0)))  < adjacencyList[b].key){
						adjacencyList[b].key = newKey;
						adjacencyList[b].parent = adjacencyList[u];
						
					}
				}
			}
			
			double sum = 0;
			for(int z = 0; z<numDots; z++){
				sum+=adjacencyList[z].key;
			}
			System.out.printf("%.2f",sum);
			if(g<numCases-2)
			System.out.println("\n");
			
		}
	}
	public static int getMinKey(){
		int minIndex = 0;
		
		double minKey = Double.MAX_VALUE;
		for(int a = 0; a<numDots; a++){
			if(adjacencyList[a].visited == false && adjacencyList[a].key < minKey){
				minKey = adjacencyList[a].key;
				minIndex = a;
			}
		}
		
		return minIndex;
	}
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10034 - Freckles

Post by brianfry713 » Tue Aug 19, 2014 2:23 am

The outputs of two consecutive cases will be separated by a blank line.
Check input and AC output for thousands of problems on uDebug!

dypbrg
New poster
Posts: 3
Joined: Sun Aug 17, 2014 1:05 pm

Re: 10034 - Freckles

Post by dypbrg » Thu Aug 21, 2014 5:20 am

I already have this part of the code that does it.

Code: Select all

 
System.out.printf("%.2f",sum);
if(g<numCases-2)
    System.out.println("\n");

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10034 - Freckles

Post by brianfry713 » Thu Aug 21, 2014 7:34 pm

Check input and AC output for thousands of problems on uDebug!

dypbrg
New poster
Posts: 3
Joined: Sun Aug 17, 2014 1:05 pm

Re: 10034 - Freckles

Post by dypbrg » Sun Aug 24, 2014 2:35 am

ohh I see
if I change my code to this one:

Code: Select all

System.out.printf("%.2f",sum);
if(g<numCases-1)
    System.out.println("\n");
it still outputs wrong answer. see output here http://ideone.com/pT0plI

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10034 - Freckles

Post by brianfry713 » Tue Aug 26, 2014 11:44 pm

Print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

hengbinluo
New poster
Posts: 2
Joined: Sun Aug 09, 2015 8:25 am

Re:

Post by hengbinluo » Sun Aug 09, 2015 8:28 am

ovidiu wrote:You use too small data structures. Just think how many edges can be.

Reading your code I found that after last output there need only one endl and got ACC my code. Thank you!

In my beginner opinion, judging as WA if there are 0 or 2 endl it is a "little" ... unpleasant ...
Agreed. It happened to me too when there was an extra endl for the last case.

Post Reply

Return to “Volume 100 (10000-10099)”