FilesExpand file tree

 main

/

Whatsinit.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

131 lines (98 loc) · 3.18 KB

 main

/

Whatsinit.java

Copy path

Top

File metadata and controls

• Code
• Blame

131 lines (98 loc) · 3.18 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

package idiopen;

import java.io.FileInputStream;

import java.io.FileNotFoundException;

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;

public class Whatsinit {

static Scanner sc;

public static void main(String[] args) throws FileNotFoundException {

System.setIn(new FileInputStream("inputs/whatsinit2.txt"));

sc = new Scanner(System.in);

new Whatsinit(sc.nextLine());

}

public Whatsinit(String input) {

int nrItems = Integer.parseInt(input);

List<Item> allItems = new ArrayList<>();

List<Item> unknownItems = new ArrayList<>();

int knownSum = 0;

for (int i = 0; i < nrItems; i++) {

String[] ins = sc.nextLine().split(" ");

Item item = new Item();

item.name = ins[0];

if (ins[1].equals("?")) {

item.unknown = true;

unknownItems.add(item);

} else {

int value = Integer.parseInt(ins[1]);

item.lower = value;

item.upper = value;

knownSum += value;

item.unknown = false;

}

allItems.add(item);

}

for (int i = 0; i < allItems.size(); i++) {

Item item = allItems.get(i);

if (!item.unknown) {

continue;

}

int upper = 100;

int parent = i - 1;

while (parent >= 0) {

Item p = allItems.get(parent--);

if (!p.unknown) {

upper = p.upper;

break;

}

}

item.upper = upper;

int lower = 0;

int desc = i + 1;

while (desc < allItems.size()) {

Item d = allItems.get(desc++);

if (!d.unknown) {

lower = d.upper;

break;

}

}

item.lower = lower;

}

int rest = 100 - knownSum;

while(iterate(unknownItems, rest)) {}

for (Item item : allItems) {

System.out.println(item.name + " " + item.lower + " " + item.upper);

}

}

private boolean iterate(List<Item> unknownItems, int rest) {

boolean hasChanged = false;

int lowerSum = 0;

for (Item unknownItem : unknownItems) {

lowerSum += unknownItem.lower;

}

for (Item unknownItem : unknownItems) {

int upper = rest - (lowerSum - unknownItem.lower);

if (upper < unknownItem.upper) {

hasChanged = true;

unknownItem.upper = upper;

}

}

int upperSum = 0;

for (Item unknownItem : unknownItems) {

upperSum += unknownItem.upper;

}

for (Item unknownItem : unknownItems) {

int lower = rest - (upperSum - unknownItem.upper);

if (lower > unknownItem.lower) {

hasChanged = true;

unknownItem.lower = lower;

}

}

return hasChanged;

}

static class Item {

String name;

boolean unknown;

int lower, upper;

}

}